好的散列函数

我一直不理解散列函数的设计。我正在通过一个例子。正如你在函数注释中看到的，为什么你应该选择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; 
}

来源

2012-01-20 Anusha Pachunuri

这就是被称为伯恩斯坦散，散托雷克，或简称为 “次33哈希”。我建议阅读[Apache Portable Runtime]中的注释（http://svn.apache.org/repos/asf/apr/apr/trunk/tables/apr_hash.c）。 – user7116

有问题的哈希被称为Bernstein哈希，Torek哈希，或者简称为“times 33”哈希。由于其简单，快速和体面的分布，它非常流行，其中英文字符串数据。

你的评论注意它实际上乘以31，这对你来说显得任意，实际上是有点任意。 Apache Portable Runtime has a comment in their hash algorithm source其中指出，许多可能的常数运作良好（33是最常见的）。它们都很奇怪，接近2的幂，这意味着它们很好地转换为转换和加法或减法。

其他一些资源，帮助了解哈希：

来源

2012-01-21 00:22:26 user7116

我基本上在思考“什么是设计散列函数的好方法”。现在至少有一个事实是，它们中的大多数都是试验和错误可以解除我的困扰。我了解times33哈希。谢谢 –

这是65k次散列函数的讲座。在YouTube上：http://www.youtube.com/watch?v=KW0UvOW0XIo

这不完全是你要求的，但是你的问题表明你在哈希方面的知识是有限的。最好阅读教程或检查演示文稿。

来源

2012-01-20 23:40:08 cateof

好的散列函数

回答

相关问题