C 中字符串的哈希函数

Question

我目前正在尝试用 C 语言为我的程序实现哈希函数。我找到了许多可能的解决方案，但我不理解它们。下面是哈希函数：

int hash(const char *word) {
    int hash = 0;
    int n;
    for (int i = 0; word[i] != '\0'; i++) {
        // alphabet case
        if (isalpha(word[i]))
            n = word[i] - 'a' + 1;
        else  // comma case
            n = 27;

        hash = ((hash << 3) + n) % SIZE;
    }
    return hash;
}

我们为什么要从'a'+1中减去word[i]？另外，我们为什么要做以下事情：hash = ((hash << 3) + n) % SIZE？

Answer 1

为什么我们要在字符串中添加“a”+1？

We are not ...-表示减法，而不是加法，并且 word[i] 是字符串的字符，而不是字符串。因此，我们将字符串的每个字符减去 'a' 并加 1。

如果 word[i] 是小写字母，则word[i] - 'a' + 1计算该字母的数量： 'a' -> 1, ... 'z' -> 26。如果它不是小写字母怎么办？好吧，非字母字符（不仅仅是逗号，与注释相反）被映射到 27，但大写字母（如果存在）会导致未定义的行为。

“散列 = ((散列 << 3) + n) % 大小”？

这会将先前的哈希值乘以 8，然后为当前字符加上值 1 ... 27，并保证结果不会超过 SIZE，这大概是哈希桶的数量。如果字符串包含的字符多于字长/3，则初始字符将被移出。如果 SIZE 是 2 的幂并且字符串的字符数超过 SIZE/3，则所有这些附加字符都将被移出。

这就是它的工作原理，但它不是一个很好的哈希函数。除了代码有错误的注释并且不处理大写字母之外，它也不能很好地处理长字符串，因为如上所述，初始字符将被移出。此外，移位和添加操作以非随机方式组合相邻字符，因此会产生比最佳值更多的哈希桶冲突。这个哈希函数很快，但是还有更好的快速哈希函数。请参阅https://en.wikipedia.org/wiki/Hash_function了解更多信息。