応用情報技術者 2011年 秋期 午前2 問05

ハッシュ関数の衝突条件【午前2 解説】

要点まとめ

• 結論：キー$a$と$b$が衝突するのは、$a-b$がハッシュ表の大きさ$n$の倍数のときです。
• 根拠：ハッシュ関数$h(x)=x\mathrm{mod}n$は、$x$を$n$で割った余りを返すため、余りが同じなら衝突します。
• 差がつくポイント：余りの定義と「差が$n$の倍数であること」が衝突の本質である点を理解できるかが重要です。

正解の理由

よくある誤解

解法ステップ

1. ハッシュ関数の定義を確認する：$h(x)=x\mathrm{mod}n$
2. 衝突の意味を理解する：$h(a)=h(b)$
3. 余りの等しさを式で表す：$a\mathrm{mod}n=b\mathrm{mod}n$
4. これを差の形に変形：$(a-b)\mathrm{mod}n=0$
5. 結論として、$a-b$が$n$の倍数であることを導く

選択肢別の誤答解説

• ア: 「$a+b$が$n$の倍数」→和の倍数は余りの等しさとは無関係です。
• イ: 「$a-b$が$n$の倍数」→正解。余りが等しい条件そのものです。
• ウ: 「$n$が$a+b$の倍数」→ハッシュ表の大きさがキーの和の倍数であることは衝突条件ではありません。
• エ: 「$n$が$a-b$の倍数」→逆の関係であり、$a-b$が$n$の倍数である必要があります。

補足コラム

FAQ