什么是英语单词的好散列函数？

我有一长串英文单词，我想散列它们。什么是一个好的散列函数？到目前为止，我的哈希函数将这些字母的ASCII值相加，然后对表格大小进行取模。我正在寻找一些高效和简单的东西。什么是英语单词的好散列函数？

2011-10-08 Mike G

入住这里的http：//www.cse。 yorku.ca/~oz/hash.html –

可能的重复[良好的字符串哈希函数]（https://stackoverflow.com/questions/2624192/good-hash-function-for-strings）和[什么是好东西Java中的64位散列函数用于文本字符串？]（https://stackoverflow.com/questions/1660501/what-is-a-good-64bit-hash-function-in-java-for-textual-strings） –

简单地总结这些字母并不是一个好的策略，因为排列给出了相同的结果。

这一个（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; 
}

如果您需要更多替代方案和一些性能指标，请阅读here。

补充：这是一般散列函数，其中输入域事先不知道（也许除了一些很一般的假设：如上述作品稍好ASCII码输入），这是最常用的场景。如果你有一个已知的限制域（固定输入集），你可以做得更好，见Fionn的答案。

来源

2011-10-08 23:28:15 leonbloy

5381是表大小？ –

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

@MikeG：即“种子”或起始值。这通常被称为“Times 33”散列。 – user7116

也许这样的事情会帮助你：http://www.gnu.org/s/gperf/

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

来源

2011-10-08 23:25:21 Fionn

如果你不需要它是密码安全的，我会建议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

来源

2011-10-08 23:29:54 selbie

MurmurHash +1，do你知道CityHash和MurmurHash之间的比较吗？我已经听到了有关两者的好消息，但从来没有看到过全面的比较，只是有一些奇怪的事实。 –

晚了一点，但这里是一个非常低的碰撞率低于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）

来源

2012-12-23 11:16:46 slashmais

这是一个合理的散列函数。我建议避免未命名的联盟。 - >>'union {uint64_t h; uint8_t u [8]; } uu;'和代码中的类似变化 - >> uu.h = strlen（s）;'...'uu.u [i％8] + = ...'etc – joop

什么是英语单词的好散列函数？

回答

相关问题