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

Question

我正在阅读K&R的"The C Programming Language"一书.在"结构"一章中,在"表查找"(页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 != '\0'; 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

我不明白这个功能究竟是做什么的？

它基本上散列char *s指针指向的字符串,直到它遇到字符串的末尾,该字符串由空字符标记'\0'.换句话说,它将给定输入字符串计算(或映射)为整数值.

您还可以看到它通过遍历字符串中的每个字符(即s++)来实现这一点,使得此函数的时间复杂度线性地依赖于字符串长度O(N)- 或 - 并且它避免生成超出边界的值具有最终模数运算的数组.

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

它接受输入值(即字符串被散列)并使用它来找出应该放置字符串的数组中的索引.因此,技术上不会生成地址,因为该函数不会返回指针.字偏移在这里会更准确.

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

真正.这称为碰撞.编写善于避免冲突的散列函数并不容易.在大多数讨论中,您将看到冲突解决方法,以便处理这些情况.

例如,一种方法可以是将每个数组元素转换为指向链表的指针,其中附加了已经冲突的元素(即,散列相同的索引值).还有其他方法,但这是一个不同的讨论.

理想情况下,将使用完美的散列函数,因为它们保证永远不会为两个不同的输入生成相同的散列值,从而无需进行冲突解决.

有关于这些主题的书籍章节,主要是在搜索方面,所以你可能想给那些阅读.

为什么HASHSIZE是101并且hashval乘以31(为什么不是100或32)？

因为101和31是素数,因此不太可能通过将自己与先前的,不同的字符串相乘/分成同一个桶而最终产生冲突.

Answer 2

散列函数通常可能为不同的字符串生成相同的散列值.这就是为什么需要解决冲突的原因.

关于HASHSIZE和hashval的值:我不是哈希函数的专家,但在我读过的少数几个中,使用的数字是凭经验获得的.您可以阅读其他主题的答案,这可能会对您有所帮助.