英語の単語にはどのような良いハッシュ関数がありますか？

Question

私は長い単語のリストを持っており、それらをハッシュしたいと思います。良いハッシュ関数は何でしょうか？これまでの私のハッシング関数は、文字の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; 
} 

さらに多くの代替手段と性能指標が必要な場合は、hereをお読みください。

を追加しました：これらの入力領域が事前に知られていない一般ハッシュ関数、です（おそらくいくつかの非常に一般的な仮定を除いては：例えば、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

少し遅れ

が、ここでは32ビット版のために良いとして、以下の64ビット版のための非常に低い衝突率を持つハッシュ関数である、と〜ほとんど〜：

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 
} 

ハッシュ番号もまた、可能な範囲に非常に均等に分散しています。検出できないほどの塊はありません。これはランダムな文字列のみを使用してチェックされています。

64ビットの衝突が0で、32ビットの衝突が1つのLibreOffice辞書/シソーラス語（英語とフランス語 - 97000を超える単語と構造体）と組み合わせたローカルテキストファイルから抽出された単語に対してもテストされています。 ）

（また同じセットのFNV1A_Hash_Yorikke、djb2とMurmurHash2と比較：Yorikke & djb2はうまくやっていなかった。slash_hashは、すべてのテストにMurmurHash2よりもわずかに良いやった）