我不明白这个哈希函数代码

Question

谁能解释一下这个哈希函数是如何工作的？我花了很多时间想弄明白，但仍然不知道它是如何工作的。

完整代码来自https://gist.github.com/choaimeloo/ffb96f7e43d67e81f0d44c08837f5944#file-dictionary-c-L30

// Hashes the word (hash function posted on reddit by delipity)
// The word you want to hash is contained within new node, arrow, word.
// Hashing that will give you the index. Then you insert word into linked list.

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

我不明白他为什么使用 (<< 和 ^)？

还有他为什么要用strlen(hash_this)?

Answer 1

哈希函数的目的是检索给定序列（字节、字符等）的唯一值。

因此需要序列的长度，这里用'strlen'。

如果没有位移运算符 (<<)，序列 'abc' 和 'cba'.

会得到相同的结果

xor 运算符 (^) 'scrambles' / 'hashes' 进一步计算当前值，因此它变得更不可能，相似的序列会产生等效值（想象具有特定模式的序列，例如'abcabc...').

Answer 2

他使用 strlen 因为他正在遍历字符串并处理每个字符。他还可以测试 hash_this[i] 不为零：

for ( int i = 0; hash_this[i] != 0; i++ )
  ...

哪个会做同样的事情。

按位运算符可防止哈希函数为相同字母的不同组合计算相同的索引。您希望 hash_index( "bat" ) 到 return 与 hash_index( "tab" ).

不同的值

为不同的字符串返回相同的索引被称为冲突，这是你想要避免的事情，所以大多数好的散列函数都会对每个字符串进行某种算术或按位运算字符，以尽量减少这种可能性。

我不明白这个哈希函数代码

I don't understand this hash-function code

c

hash-function

linked-list

hashcode

data-structures