什么是适用于英语单词的好哈希函数？

Question

我有一长串英文单词需要进行哈希处理。你能给出一个好的哈希函数吗？目前我的哈希函数是将字母的ASCII值相加，再取模表格大小。我正在寻找一些高效简洁的方案。

- Mike G

---

请在此处查看：http://www.cse.yorku.ca/~oz/hash.html - c-smile

可能是以下问题的重复：字符串的好哈希函数和Java中用于文本字符串的好的64位哈希函数是什么？。 - M.J. Rayburn

这个问题的好答案可以在其他的stackexchange网站上找到：https://softwareengineering.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed - Yann Droneaud

Answer 1

简单地对字母求和并不是一个好策略，因为不同排列的结果相同。

这个（djb2）非常流行，并且对ASCII字符串效果很好。

unsigned long hashstring(unsigned char *str)
{
    unsigned long hash = 5381;
    int c;

    while (c = *str++)
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

    return hash;
}

更多信息请点击此处。

如果需要更多选择和一些性能指标，请在此处阅读。

添加：这些是通用的哈希函数，输入域事先未知（除非有一些非常一般的假设：例如上述对ascii输入略微更有效），这是最常见的情况。 如果您具有已知的受限域（固定输入集），则可以做得更好，请参见Fionn的答案。

- leonbloy

---

不，这只是一个“种子”，相当随意的。 - leonbloy

@MikeG：那是“种子”或起始值。这个通常被称为“Times 33”哈希。 - user7116

@sixlettervariables 我在哪里指定表的长度？如果返回的数字大于我的表怎么办？ - Mike G

理论上，它可以返回任何有效的“unsigned long”值。由您来操纵哈希以适应您的限制。 - Jonathan Grynspan

@MikeG：一般来说，在哈希算法中你不需要指定表的大小（如果你不知道，可以使用已有的表……）。好的实现会根据项目数量增加或减小表的大小，因此你只需计算哈希值，并将其模除当前大小，就可以知道要把它放在哪个桶中。 - Matthieu M.

Answer 2

也许像这样的东西可以帮助你：http://www.gnu.org/s/gperf/ 它会为输入域生成一个优化的哈希函数。

- Fionn

Answer 3

如果您不需要加密安全性，我建议使用Murmur哈希。它非常快速且扩散性高。易于使用。

http://en.wikipedia.org/wiki/MurmurHash

http://code.google.com/p/smhasher/wiki/MurmurHash3

如果您确实需要一个加密安全哈希，我建议使用OpenSSL中的SHA1。

http://www.openssl.org/docs/crypto/sha.html

- selbie

---

+1 对于 MurmurHash，你知道 CityHash 和 MurmurHash 之间的比较吗？我听说过两者都很好，但从未见过全面的比较，只是一些轶事事实。 - Matthieu M.

Answer 4

虽然有点晚，但以下是一种哈希函数，其64位版本具有极低的冲突率，而32位版本则几乎一样好：

uint64_t slash_hash(const char *s)
//uint32_t slash_hash(const char *s)
{
    union { uint64_t h; uint8_t u[8]; } uu;
    int i=0; uu.h=strlen(s);
    while (*s) { uu.u[i%8] += *s + i + (*s >> ((uu.h/(i+1)) % 5)); s++; i++; }
    return uu.h; //64-bit
    //return (uu.h+(uu.h>>32)); //32-bit
}

哈希数字也非常均匀地分布在可能的范围内，我无法检测到任何成团现象 - 这是使用随机字符串进行检查的。
[编辑]
还测试了从本地文本文件中提取的单词与LibreOffice字典/同义词（英语和法语 - 超过97000个单词和构造）的组合，64位没有冲突，32位有1个冲突 :)

(还将其与相同数据集上的FNV1A_Hash_Yorikke、djb2和MurmurHash2进行比较：Yorikke和djb2表现不佳；斜杠哈希在所有测试中略优于MurmurHash2)

- slashmais

---

这是一个合理的哈希函数。我建议避免使用未命名联合体 -->> union { uint64_t h; uint8_t u[8]; } uu; 以及代码中类似的更改 -->> uu.h=strlen(s); ... uu.u[i%8] += ... 等。 - joop