什麼是英語單詞的好散列函數？

我有一長串英文單詞，我想散列它們。什麼是一個好的散列函數？到目前爲止，我的哈希函數將這些字母的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

什麼是英語單詞的好散列函數？

回答

相關問題