SW:H16春期午前問13

質問

解き方として、ハッシュ関数を x mod 11と仮定し、衝突が起きる組み合わせを1、12、23と考えているという箇所がテキストにあったのですが、ハッシュ関数を x mod 11に仮定した理由とそこから1、12、23をどのように導いたのか分かりません。ご理解のある方はご教授お願い致します。

回答No.1

jjon-com · ベストアンサー

11を仮定した理由は，(1)ハッシュ関数では素数による剰余計算がよく用いられるから，かつ，(2)「11で割った余り」は暗算でも計算しやすい適度な大きさ・適度な小ささだから，だと思います。
http://ja.wikipedia.org/wiki/ハッシュ関数

衝突が起きる ＝ ｎで割った余りが同じ，ですから，余り１の場合と適当に想定して，11で割った余りが同じ１になる数を適当に２つ（ａ＝12，ｂ＝１）当てはめてみたのでしょう。

×　ア　12＋１ が 11の倍数
○　イ　12－１ が 11の倍数
×　ウ　11が 12＋１の倍数
○　エ　11が 12－１の倍数

イ・エのどちらかに絞られました。余りが１になる別の２つの数（ａ＝23，ｂ＝１）を当てはめてみます。

○　イ　23－１ が 11の倍数
×　エ　11が 23－１の倍数

最後まで残った正解は イ となりました。

ちなみにｎ＝11でなくても問題は解けます。素数でなくても大丈夫です。ｎ＝100としてみましょうか（余りが０～99と分かりやすいので）

ともに余りが23となる数の組を当てはめます（ａ＝123，ｂ＝23）

×　ア　123＋23 が 10の倍数
○　イ　123－23 が 10の倍数
×　ウ　10が 123＋23の倍数
×　エ　10が 123－23の倍数

正解は イ となりました。

参考URL：

http://zigen.cosmoconsulting.co.jp/index.htm#SW

お礼

これ以上ないほど分かりやすい説明有難うございました。