试着用C写一个哈希表，我在这里做正确的事情吗?

Question

我已经有了一个哈希函数

我有一个对象结构:

OBJKT 
{
   OBJKT *o_hash_next;
   OBJKT *o_hash_prev;
   ... bunch of other stuff
}

我还在头文件中声明了哈希数组:OBJKT *hash_tbl[hsize];

应该将给定OBJKT添加到哈希的方法接受哈希键和我们正在添加的OBJKT。

所以这是我不确定我做的正确:

void insert_in_hash(int hashindex, OBJKT *thisObject)
{
   *thisObject->o_hash_next = *hash_tbl[hashindex];
   *hash_tbl[hashindex]->o_hash_prev=*thisObject;
   *hash_tbl[hashindex] = *thisObject;
}

这看起来正确吗?我试图设置前一个/下一个指针，然后将thisObject添加到哈希中。

Answer 1

看起来不错。对于哈希表，你不一定需要一个双链表。

不要忘记在开始时将hash_tbl归零。

您可能会发现在OBJKT条目中直接使用哈希值非常有用，可以加快搜索速度。

更新

基于未开发的评论(那些该死的"*"字符)，它可能看起来像这样:

void insert_in_hash(int hashindex, OBJKT *thisObject)
{
   thisObject->o_hash_next = hash_tbl[hashindex];
   thisObject->o_hash_prev = NULL;
   hash_tbl[hashindex]->o_hash_prev=thisObject;
   hash_tbl[hashindex] = thisObject;
}

Answer 2

很晚了，我有点累了，但我看到的是额外的取消引用。

第一:OBJKT *hash_tbl[]已经是一个指向链表的指针数组。
所以当你需要列表的头时，你只需要使用hash_tbl[index]，它会给你一个指针，这个指针必须分配给你thisObject->o_hash_next，它也是一个指针。不要废弃。您所拥有的*thisObject->o_hash_next = *hash_tbl[hashindex]正在将值从一个地址复制到另一个地址，这不是我假设的您想要的。同样的事情也适用于前一个指针。

您的解决方案可能如下所示:

void insert_in_hash(int hashindex, OBJKT *thisObject)
{
    thisObject->o_hash_next          = hash_tbl[hashindex];
    hash_tbl[hashindex]->o_hash_prev = thisObject;
    thisObject->o_hash_prev          = NULL; // Don't forget to NULL if not in use
}

最后一行被删除，因为这不是你通常跟踪列表开头的方式。

不管怎样，就像我说的，很晚了，我没有时间测试我的代码，但这里有一个有用的链接到一个链表教程:C/c++链表教程

编辑
您应该像在代码中所做的那样保留列表的头部:hash_tbl[hashindex] = thisObject。请看下面的评论