字符串的哈希函数

Question

字符串的哈希函数

calgorithmhashdictionaryhashtable

173

我正在使用C语言实现哈希表，并测试字符串的哈希函数。

首先，我尝试了将ASCII码相加并使用模运算（% 100），但是在第一组包含130个单词的数据测试中，结果很差：40个冲突。

最终输入的数据将包含8000个单词（这是一个存储在文件中的字典）。哈希表声明为int table[10000]，其中包含单词在.txt文件中的位置。

什么是最适合哈希字符串的算法？
如何确定哈希表的大小？

- lilawood

11

如果你的哈希表有1万个条目，为什么要使用模100？在如此小的模数下得到130个单词中的40次冲突并不奇怪。 - Carey Gregory

15

请参考以下资源了解各种哈希函数（从通用到字符串到加密）：http://burtleburtle.net/bob/hash/evahash.html 和 http://www.partow.net/programming/hashfunctions/。 - user166390

5

为了澄清@CareyGregory先生的问题：您是否意识到，作为基本的数学定理，在100个桶中放置130个物品（即mod 100），必然会产生30次碰撞（其中碰撞是指将第二、第三等物品放入同一个桶的每次情况），对吗？因此，您只比这还多一点点。 - derobert

4

@lilawood：好的，我明白了，但为了更好地测试，您应该使用80个单词和100个条目的哈希表。这将给您与实时数据相同的比例，并且不会强制发生冲突。 - Carey Gregory

5

可能是字符串好的哈希函数的重复问题。 - M.J. Rayburn

显示剩余7条评论

11个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Peyman · Answer 1

我想为像我一样的C语言新手总结一下。根据Andriy Makukha的精确努力，MurmurHash3是最好的选择：

unsigned long hash(const char* str){
    unsigned int h = 0x12345678;
    for (; *str; ++str) {
        h ^= *str;
        h *= 0x5bd1e995;
        h ^= h >> 15;
    }
    return h;
}