我一直未能理解哈希函数的设计。我正在举一个例子。正如您在函数注释中所看到的，为什么要选择 31 作为要相乘的数字。你怎么决定？这是随机的还是意味着什么？
unsigned int hash(hash_table_t *hashtable, char *str)
{
unsigned int hashval;
/* we start our hash out at 0 */
hashval = 0;
/* for each character, we multiply the old hash by 31 and add the current
* character. Remember that shifting a number left is equivalent to
* multiplying it by 2 raised to the number of places shifted. So we
* are in effect multiplying hashval by 32 and then subtracting hashval.
* Why do we do this? Because shifting and subtraction are much more
* efficient operations than multiplication.
*/
for(; *str != '\0'; str++) hashval = *str + (hashval << 5) - hashval;
/* we then return the hash value mod the hashtable size so that it will
* fit into the necessary range
*/
return hashval % hashtable->size;
}
最佳答案
有问题的哈希被称为 Bernstein 哈希、Torek 哈希，或简称为“times 33”哈希。它非常受欢迎，因为它简单、速度快，并且可以很好地分发英文字符串数据。
你的评论指出它实际上乘以 31，这对你来说似乎是任意的，实际上 有点任意。 Apache Portable Runtime has a comment in their hash algorithm source其中指出许多可能的常量都可以很好地工作(33 是最常见的)。它们都是奇数并且接近 2 的幂，这意味着它们可以很好地转化为移位和加减法。
帮助理解散列的其他一些资源:
关于c - 好的散列函数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8949220/