哈希函数精度问题

Question

我正在编写一个拼写检查单词的程序，但我的哈希函数没有为相同的单词返回相同的数字。

我的问题是我的散列函数为什么不为相同的输入返回相同的散列。

这是我的问题的一个最小的、可重现的例子：

// Implements a dictionary's functionality

#define HASHTABLE_SIZE 65536

// Represents a node in a hash table
typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;

// Number of buckets in hash table
const unsigned int N = HASHTABLE_SIZE;

// Hash table
node *table[N];
unsigned int totalWords = 0;

// Hashes word to a number
unsigned int hash(const char *word)
{
    unsigned int hash_value;

    for (int i=0, n=strlen(word); i<n; i++)
        hash_value = (hash_value << 2) ^ word[i];

    return hash_value % HASHTABLE_SIZE;
}

Answer 1

哈希函数中的

hash_value 未初始化，它会造成内存破坏，从而导致不可预测的结果。来自引用post:

unsigned int hash = 0;

Answer 2

您的 fscanf 写入了 word 指向的内存块外部。

    char *word = malloc(LENGTH);  // this is too small to hold a word + '[=10=]'
    ...
    while (fscanf(dicfile, "%s", word) != EOF)
    {

将大小增加到 LENGTH+1。

哈希函数精度问题

Hash function precision issue

c

hash-function

hashtable

cs50