ハッシュ関数について悩んでいます.
ハッシュ関数の例として以下Wikiの引用です
http://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%83% …
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ベストアンサー
- 回答日時:
> 「最終的にハッシュ値は合計を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
- 回答日時:
137で割っていくと情報が全然残りません。
文字列の最後の2つが同じ文字であった場合ハッシュ値が同じになります。ハッシュ関数としては使い物になりません。
今回12bitのハッシュ値を返すハッシュ関数を作りたい。
対象とする文字列は大きすぎるので文字単位で計算を行う。
文字は8bitである。
12bit以上になるように拡張処理を行う。
137 == 2<<7 + 2<<3 + 2<<0 です。
シフト操作でイメージしてください。
そうすればわかるはずです。
前提条件を明示していただいて,頭が整理されました.
確かに割ると使いものにならなくなりますね.
そして掛けると,intの範囲に情報が反映されます.
大変参考になりました.ありがとうございます.
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 防犯カメラ・監視カメラ・小型カメラ 屋外用のIPカメラ(ライブカメラ)の位置情報について 1 2022/06/23 18:32
- その他(生活家電) 電熱ヒーターパッド(17×24cm)の電源がすぐに切れるので困っています。 2 2022/12/20 13:31
- メルカリ ブラックケアシャンプー 600ml 最安はどこ? 2 2022/04/04 05:16
- その他(ニュース・時事問題) 岸田首相が顕忠院を訪問……こんな所、訪問してもエエんかぁ? 2 2023/05/08 18:34
- 英語 Sidewalks がなぜ複数形なのでしょうか? 2 2022/12/23 05:57
- デスクトップパソコン 小型PCのオススメを教えてください 3 2022/09/18 19:39
- 物理学 ギブス自由エネルギー変化における体積変化の影響 1 2023/06/25 04:56
- docomo(ドコモ) SIMフリー機種への乗り換えについて 7 2022/09/01 14:05
- Windows 10 プロファイルエラーについて 2 2022/12/16 09:31
- Y!mobile(ワイモバイル) Ymobileデータ増量OP550円2GBコスパ悪い。プランSとプランMを月ごと交互に契約可能ですか 5 2023/05/23 17:43
関連するカテゴリからQ&Aを探す
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
16進数 加算 減算 C言語
-
O(n log n)について2
-
浮動小数演算での誤差の蓄積が...
-
c languageで 簡単な質問があ...
-
Log関数に関する質問
-
大きすぎる数値になるとE+にな...
-
エクセル計算 答えは同じなの...
-
2038年問題 日付算出
-
2進数の足し算(C言語)
-
三菱シーケンサ(Aシリーズ)で...
-
100桁の計算ができなくて困って...
-
ExcelのINT関数の計算結果がお...
-
有効数字について 以前質問をし...
-
”/”を使わずに割り算したいんで...
-
2進数データのビット演算
-
除算を使わずに10で割りたい。
-
丸め誤差と桁落ちの違いとは
-
桁落ちのプログラムで真の値と...
-
Excel 計算結果誤差
-
【C言語】RGBと輝度の計算に関して
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
O(n log n)について2
-
16進数 加算 減算 C言語
-
c languageで 簡単な質問があ...
-
ExcelでPC(パソコン)によって...
-
”/”を使わずに割り算したいんで...
-
有効数字について 以前質問をし...
-
三角比の俯角の計算
-
ExcelのINT関数の計算結果がお...
-
VB.net Double と...
-
floatの有効桁数
-
パソコンで階乗を計算
-
三菱シーケンサ(Aシリーズ)で...
-
除算を使わずに10で割りたい。
-
VB6.0での小数点の扱いについて
-
EXCELの関数"STDEV(標準偏差)"...
-
時刻の比較
-
VBAでの割り算の余りの求め方
-
計算の丸め誤差の解消について
-
C言語プログラミングにて、arct...
-
VBAでミリ秒まで出力する方法
おすすめ情報