ハッシュ関数

質問

ハッシュ関数について悩んでいます．
ハッシュ関数の例として以下Wikiの引用です
http://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E9%96%A2%E6%95%B0

unsigned int hash(char *s) {
unsigned int h = 0;
for (;*s != '\0'; s++) {
h = h * 137 + *s;
}
return h % 1987;
}

このハッシュ関数において，

「hの更新計算で用いる137という数は、2(7乗)+2(3乗)+2(0乗)
というものであり、乗法した後にも2進数表現の下位の桁にも
情報が残るようになっている。そのため前の方の文字の情報が
桁あふれによって失われることはない。」

と記述されているのですが，私が考えてしまうのは以下の通りです．

「最終的にハッシュ値は合計を1987で割った余りになるのだから，
下位の桁（1～1987）に情報を残さなければならない．
それぞれのsの上位から下位までの情報を合計の数値の下位に
残すのであれば，137は掛けるのではなく割るべき．」

もちろん私の考え方が間違っているのはわかりますが，
なぜ137を掛けるのかを理解できません．
どなたかわかりやすくご教授いただけたら幸いです．

回答No.2

mtaka2 · ベストアンサー

> 「最終的にハッシュ値は合計を1987で割った余りになるのだから，
> 下位の桁（1～1987）に情報を残さなければならない．

ここ、間違いです。
余りを取る元の数において、「1と2の区別」ができるのと同じように、
「1988と1989の区別」ができます。
「1987で割った余り」を取る元の数は1987を超えてても問題ありません。

問題は、元の数が「unsigned int」の範囲に収まるかどうです。
つまり、
> 乗法した後にも2進数表現の下位の桁にも情報が残るように
の「下位の桁」とは、「unsigned int の表現能力である32bit」を指すのです。
たとえば、計算式が「h=h*256+*s」だったとします。
これでもし、元の文字列が"ABCDEFGH"だったとしたら、
ループ処理後最終的なhの値は、その桁数に制限が無かったとしたら
「h=0x4142434445464748」になるはずです。(Aのアスキーコード=0x41～Hのアスキーコード=0x48)
ところが、hは32bit変数ですから、この64bitな数の上位32bitは切り捨てられて、
「h=0x45464748」になります。ここから求まるハッシュ値は1338(0x45464748を1987で割った余り)になりますが、
このハッシュ値は、元になるhに文字列の最後の4文字の情報しか反映されてません。
つまり、このようなハッシュ関数では、最後の4文字だけがハッシュ値に反映され、それより前の部分の文字が異なっていても、同じハッシュ値になってしまうわけです。
これが「前の方の文字の情報が桁あふれによって失われ」た状態です。

そうならないようにするためには、かける数を2進数で見て最下位が1だったら大丈夫です。

そういう数は137以外にもいろいろありますから、
その中で「137」を選んだことには論理的理由はそれほどありません。
強いて言えば「統計的・経験的にみてハッシュ値の散らばり具合が良い」数だったから、ですね。

お礼

間違いを明確に指摘していただいたのでとてもわかりやすかったです．

1987の範囲に情報の重みを置かないといけないと考えていたのですが，
「余り」という概念の使い方を誤っていたようです．
ありがとうございます．

回答No.1

shred

137で割っていくと情報が全然残りません。
文字列の最後の２つが同じ文字であった場合ハッシュ値が同じになります。ハッシュ関数としては使い物になりません。
今回12bitのハッシュ値を返すハッシュ関数を作りたい。
対象とする文字列は大きすぎるので文字単位で計算を行う。
文字は8bitである。
12bit以上になるように拡張処理を行う。
137 == 2<<7 + 2<<3 + 2<<0　です。
シフト操作でイメージしてください。
そうすればわかるはずです。

お礼

前提条件を明示していただいて，頭が整理されました．
確かに割ると使いものにならなくなりますね．
そして掛けると，intの範囲に情報が反映されます．
大変参考になりました．ありがとうございます．