这个哈希函数是如何工作的？这些数字是随机的吗？

Question

我目前正在阅读 K&R 的 "The C Programming Language" 书。在 "Structures" 章节中，在 "Table Lookup" 的子主题下（第 144 页）我找到了这个哈希生成函数

#define HASHSIZE 101

struct nlist {
    struct nlist *next;
    char *name;
    char *defn;
}

static struct nlist *hashtab[HASHSIZE];

unsigned hash(char *s)
{
    unsigned hashval;

    for (hashval = 0; *s != '[=10=]'; s++)
        hashval = *s + 31 * hashval;
    return hashval % HASHSIZE;
}

我不明白这个函数到底做了什么。

我认为它会为给定的字符串 (char *s) 生成一个唯一地址（作为 hashtab 上的索引）。

但我认为两个不同的字符串可以被赋予相同的索引，因为 (hashval % HASHSIZE) 是给定的地址 (203 % 101 = 405 % 101 = 1)。

为什么HASHSIZE 101 和hashval 乘以31？为什么不是 100 或 32？

Answer 1

What I don't understand is what this function actually do?

它基本上对char *s指针指向的字符串进行哈希处理，直到遇到字符串的结尾，即空字符'[=11=]'所标记的字符串。换句话说，它将给定的输入字符串计算（或映射）为整数值。

您还可以看到它通过遍历字符串中的每个字符（即 s++）来执行此操作，使此函数的时间复杂度线性相关关于字符串长度 -- 或 O(N)-- 并且它避免生成一个超出数组边界的值与最终模运算。

I think it generates an unique address (as an index on hashtab) for the given string(char *s).

它获取输入值（即被散列的字符串）并使用它来找出数组中应放置字符串的 index。因此，从技术上讲，它不会生成地址，因为该函数不会 return 一个指针。 offset 这个词在这里会更准确。

But I think two different strings can be given the same index since (hashval % HASHSIZE) is the given address (203 % 101 = 405 % 101 = 1).

没错。这称为碰撞。编写擅长避免冲突的哈希函数并不容易。在大多数讨论中，您会看到用于处理这些情况的冲突解决方法。

例如，一种方法可能是将每个数组元素变成一个指向链表的指针，在链表中附加了发生冲突的元素（即散列相同的索引值）。还有其他方法，但那是另外的讨论。

理想情况下，perfect hash functions 将被使用，因为它们保证 永远不会 为两个 不同的 生成相同的哈希值输入，使冲突解决变得不必要。

有关于这些主题的书籍章节，主要涉及搜索，所以您可能想读一读。

And Why HASHSIZE is 101 and hashval is multiplied by 31 (why not 100 or 32)?

因为 101 和 31 是质数，因此 不太可能 最终通过 multiplying/dividing 自身产生碰撞与前一个不同的字符串相同的桶。

Answer 2

散列函数通常可能会为不同的字符串生成相同的散列值。这就是为什么需要 collision resolution。

关于HASHSIZE和hashval的值：我不是散列函数的专家，但在我读到的少数几个中，使用的数字是根据经验得出的。您可以阅读其他主题的 answer，这可能对您有所帮助。

这个哈希函数是如何工作的？这些数字是随机的吗？

How does this hash function work? Are these numbers random?

c

hash

struct

hashtable