时间戳

首页 > 解决方案 > 我将如何确定我的哈希表中的某个索引是否还没有值？

c - 我将如何确定我的哈希表中的某个索引是否还没有值？

问题描述

我正在尝试创建一个程序，该程序读取一个充满字典中单词的文件，然后将每个单词存储在哈希表中，我已经有一个哈希函数，例如哈希函数返回一个索引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..

标签： chashtablehash-function

解决方案

我将如何确定该索引是否还没有价值

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

我应该把这个词作为列表的新标题还是应该将它添加到列表的末尾？

应该没关系。节点上的单个列表应该很短。哈希表的想法是将所有单词的线性搜索转变为平均W对单词进行更快的线性搜索。W/N如果您看到您的表只有几个长列表，那么您的哈希函数并不好。

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

我是否应该首先将整个数组初始化为“NULL”之类的东西，因为如果一个变量没有被初始化，它包含垃圾值，那么这对结构中的数组是否同样有效。

是的，请将您的头节点指针数组初始化为NULL，以便哈希表处于定义状态。（如果您的数组在文件范围内，或者static，表应该已经初始化为空指针，但明确初始化并没有什么坏处。）

推荐阅读