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

我有很多英文单词，我想哈希。 什么是良好的散列函数？ 到目前为止，我的散列函数将字母的ASCII值相加，然后以表格大小为模。 我正在寻找一些高效而简单的东西。

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的答案。

Answer 2

也许这样的事情可以帮到你： http ： //www.gnu.org/s/gperf/

它为输入域生成优化的散列函数。

Answer 3

如果你不需要加密安全，我会建议Murmur Hash。 它非常快并且具有高扩散性。 使用方便。

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

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

如果你确实需要加密安全散列，那么我建议通过OpenSSL使用SHA1。

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

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]; }; int i=0; h=strlen(s); while (*s) { u[i%8] += *s + i + (*s >> ((h/(i+1)) % 5)); s++; i++; } return h; //64-bit //return (h+(h>>32)); //32-bit } 

散列数也非常均匀地分布在可能的范围内，没有我能检测到的聚集 – 这只是使用随机字符串进行检查。
[编辑]
还针对从本地文本文件中提取的单词和LibreOffice词典/词库单词（英语和法语 – 超过97000个单词和结构）进行了测试，在64位中有0次冲突，在32位中有1次冲突:)

（还与相同集合上的FNV1A_Hash_Yorikke，djb2和MurmurHash2进行比较：Yorikke和djb2表现不佳;在所有测试中，slash_hash的表现略好于MurmurHash2）