1

我一直无法理解哈希函数的设计。我正在经历一个例子。在函数注释中可以看到，为什么要选择 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;
}
4

2 回答 2

3

有问题的散列被称为 Bernstein 散列、Torek 散列或简称为“33 倍”散列。由于其简单、速度和与英文字符串数据的良好分布，它非常受欢迎。

您的评论指出它实际上是乘以 31，这对您来说似乎是任意的，实际上有点任意。Apache Portable Runtime 在其散列算法源中有一个注释，其中指出许多可能的常量都可以正常工作（33 是最常见的）。它们都是奇数且接近 2 的幂，这意味着它们可以很好地转化为移位和加法或减法。

其他一些有助于理解散列的资源：

于 2012-01-21T00:22:26.487 回答
1

这是关于具有 65k 视图的哈希函数的讲座。在 youtube 上：http ://www.youtube.com/watch?v=KW0UvOW0XIo

这并不完全是您所要求的，但是您的问题表明您在散列方面的知识是有限的。最好阅读教程或查看演示文稿。

于 2012-01-20T23:40:08.060 回答