我如何确定我的散列 table 中的某个索引是否还没有值？

Question

我正在尝试创建一个程序来读取字典中充满单词的文件，然后将每个单词存储在散列中 table，我已经有一个散列函数，例如散列function returns an index 123 我如何才能确定那个索引是否还没有值，否则如果某个索引有值，我应该把这个词作为列表的新头还是我应该将它添加到列表的末尾吗？我是否应该首先将整个数组初始化为 "NULL" 之类的东西，因为如果一个变量没有被初始化，它包含垃圾值，那么它是否与结构中的数组一样工作..

typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;

// Number of buckets in hash table
//                  N = 2 ^ 13
const unsigned int N = 8192;


// Hash table
node *table[N];

这是我的代码的一部分 LENGTH 上面定义的值为 45..

Answer 1

how will I be able to determine if that index right there has no value yet

你的table中的"slots"是链表。 table 存储指向这些链表头节点的指针。如果该指针为 NULL，则列表为空，但您无需将其设为特殊情况：查找单词时，只需在指向下一个节点的指针不为空时遍历列表即可。如果指向头节点的指针为空，那么你的步行就会提前停止，仅此而已。

should I just make the word the new head of the list or should I add it to the end of the list?

应该没什么大不了的。节点上的各个列表应该很短。散列 table 的想法是将对所有 W 个词的线性搜索转变为对平均 W/N 个词的更快线性搜索。如果您发现 table 只有几个长列表，则说明您的散列函数不好。

您必须遍历列表一次以确保无论如何都不会插入重复项，因此您可以在最后插入。或者您可以尝试让每个链表按字母顺序排序。选择一种方法并坚持下去。

Should I initialize the whole array first to something like "NULL" because if a variable wasn't initialized it contains garbage value, does that work the same with arrays from a struct.

是的，请将您的头节点指针数组初始化为 NULL，以便散列 table 处于已定义状态。（如果您的数组在文件范围内或 static，table 应该已经初始化为空指针，但显式初始化也无妨。）

我如何确定我的散列 table 中的某个索引是否还没有值？

How will I determine if a certain index in my hash table has no value yet?

c

hash-function

hashtable