什么是英语单词的好哈希函数?
我有很多英文单词,我想哈希。 什么是良好的散列函数? 到目前为止,我的散列函数将字母的ASCII值相加,然后以表格大小为模。 我正在寻找一些高效而简单的东西。
简单地对字母求和不是一个好的策略,因为排列给出了相同的结果。
这个( 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的答案。
也许这样的事情可以帮到你: http : //www.gnu.org/s/gperf/
它为输入域生成优化的散列函数。
如果你不需要加密安全,我会建议Murmur Hash。 它非常快并且具有高扩散性。 使用方便。
http://en.wikipedia.org/wiki/MurmurHash
http://code.google.com/p/smhasher/wiki/MurmurHash3
如果你确实需要加密安全散列,那么我建议通过OpenSSL使用SHA1。
有点晚了,但这里有一个散列函数,对于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)