ハッシュについて教えて下さい

質問

現在出来るだけ高速に大量の英単語の登録(検索)を行いたいと考えています。
現在は受け付ける文字の種類を進数にして桁上げして、クローズドで(最初にがっぽり配列を用意してその中のどこかに入れる形式で)計算しています。

例えば0～9の文字のみ受け付ける仕様だとすると、文字の種類は10種類なので、「192」という文字列なら、
1*10^2 + 9*10^1 + 2*10^0 = 192番地に登録
といった感じです。今回大小アルファベットを含むので10→62で計算しています。

しかしこの方法では、62進数が膨大な数になるため、配列に上限があることから、完全なユニークな数値が生成出来ません。
ある程度ハッシュ値がぶつかってしまいます。
完全にユニークな数値は無理でしょうが、出来るだけ衝突は避けたいと考えています。

そこで、もっと効率よいハッシュ値を求めるMurMurHash 2.0というアルゴリズムを聞いたのですが、HPを見ても何が何だかよくわかりません；
HPにてMurmurHash2.cppが公開されているので、もしご存知の方がいらっしゃればそのアルゴリズムを教えていただけないでしょうか。
http://www.google.co.jp/search?hl=ja&rlz=1C1GGLS_jaJP302JP303&q=MurMurHash+2.0&btnG

また、高速な文字列登録(検索)を行う為の方法があれば教えて下さい。
よろしくお願いいたします。

回答No.3

prophetok

＃２
unsigned int k = *(unsigned int *)data;
と
switch文内にbreak文がないことを見落としていました。

以下は嘘です。ちゃんと全バイトを評価しています。
すいません。

評価するデータは並び順に４バイト中１バイト
ただし、４バイト中１バイトしか評価していないので、英単語では同じハッシュ値を返すケースが多くなることが予想されます。

回答No.2

prophetok

勉強のため実用性（実装の効率も含む）を度外視して、自分で作ってみるという理解でいいですか？
もし、実用を考えているのであれば、既存のライブラリを利用することをおすすめします。
さて、ハッシュ値なのですが
MurmurHash2.cppの
unsigned int MurmurHash2 ( const void * key, int len, unsigned int seed )
の中身をみれば一目瞭然、評価するデータは並び順に４バイト中１バイト
・桁あふれを起こさせる
・評価するデータを下位ビットに反映させる
を繰り返してハッシュ値を求めていますね。
ハッシュ値はある意味疑似乱数なので、こうすることで万遍なく値が散らばるんでしょうね。
演算に使っているm,rは
// 'm' and 'r' are mixing constants generated offline.
// They're not really 'magic', they just happen to work well.
の通り、試行錯誤で選んだものと思います。
ただし、４バイト中１バイトしか評価していないので、英単語では同じハッシュ値を返すケースが多くなることが予想されます。
素直に全バイトを評価する以下のようなハッシュ関数を使った方が無難かと思います。
unsigned int hash(char *s) {
unsigned int h = 0;
for (;*s != '\0'; s++) {
h = h * 137 + *s;
}
return h % 1987;
}

自分でハッシュ法を実装するとなると、コリジョン時の処理とか結構大変ですよ。少なくとも中級以上の知識と経験がないとかなり苦労すると思います。がんばってください。

回答No.1

prophetok

既存のライブラリ（STLやMFCのMAP)を使わない理由はあるのですか？
自前のコードでハッシュマップを作成する必然性がありますか？

お礼

ご回答ありがとうございます。
今回はピュアCのみで機能は一から作りたかったので、このように考えました。
また、ハッシュ値はどのように計算するのが一番効率的なのか？ということも同時に考えたかったのです・・。