応用情報技術者 2013年 秋期 午前2 問07

自然数キーのハッシュ関数における衝突条件【午前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$を式変形し、$(a-b)\mathrm{mod}n=0$と導く。
4. これが$a-b$が$n$の倍数であることを意味することを確認する。
5. 選択肢の中から該当するものを選ぶ。

選択肢別の誤答解説

• ア: $a+b$が$n$の倍数
  → 和が$n$の倍数であっても余りが同じとは限らず、衝突条件とは無関係です。
• イ: $a-b$が$n$の倍数
  → 正解。余りが同じなら差は$n$の倍数になるため衝突します。
• ウ: $n$が$a+b$の倍数
  → $n$がキーの和の倍数であることはハッシュ関数の衝突条件とは関係ありません。
• エ: $n$が$a-b$の倍数
  → $n$が差の倍数という表現は意味が逆で、衝突条件は差が$n$の倍数であることです。

補足コラム

FAQ