有人可以向我解释这个哈希函数是如何工作的（如果他们有其他更好的选择）吗？

Question

我正在研究 CS50 的 pset 5，拼写器。我需要一个哈希表的哈希函数来有效地存储字典中的所有单词（~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;
}

Answer 3

在这里我了解代码是如何工作的，但我想知道这个问题的解决者如何看待这个解决方案或者他是如何得到这个解决方案的？