有人可以向我解释一下这个 HASH FUNCTION 是如何工作的吗（如果他们有其他更好的选择）？

Question

我正在研究 CS50 的 pset 5，speller。我需要一个散列 table 的散列函数，它将有效地存储字典中的所有单词 (~140,000)。我在网上找到了这个，但我不明白它是如何工作的。我不知道 << 或 ^ 是什么意思。这是哈希函数，谢谢！（如果你能帮助我，我将不胜感激:)）

int hash_it(char* needs_hashing)
{
    unsigned int hash = 0;
    for (int i=0, n=strlen(needs_hashing); i<n; i++)
        hash = (hash << 2) ^ needs_hashing[i];
    return hash % HASHTABLE_SIZE;
}

Answer 1

这两个是位运算符。这些简单易学，是程序员必学的。

<< - 是二进制左移运算符。

假设变量“hash”二进制是“0011”。

hash << 2 变为“1100”。

而^是异或运算符。（如果只在一个操作数中设置...而不是在两个操作数中设置）

假设在你的代码中

hash << 2 给出“1100”

needs_hashing[1] 给出“1111”

然后

(hash << 2) ^ needs_hashing[i] 给出“0011”

快速了解位运算符，快走这里 https://www.tutorialspoint.com/cprogramming/c_bitwise_operators.htm

Answer 2

在原题中，演示了非常低效的散列函数。计算后哈希的最低两位等于输入行中最后一个字符的最低两位 needs_hashing。结果，例如，如果所有字符串都包含最后一个字符的偶数 ascii 码，那么如果 HASHTABLE_SIZE 是偶数（2^n 左右），则所有哈希值也将是偶数。

更高效的散列，基于循环移位：

uint32_t hash_it(const char *p) {
  uint32_t h = 0xDeadBeef;
  while(char c = *p++)
    h = ((h << 5) | (h >> (32 - 5))) + c;
  h ^= h >> 16;
  return h % HASHTABLE_SIZE;
}

有人可以向我解释一下这个 HASH FUNCTION 是如何工作的吗（如果他们有其他更好的选择）？

Can someone explain to me how this HASH FUNCTION works (also if they have another better option)?

c

hash-function

hashtable

operators

cs50