応用情報技術者 2018年 秋期 午前2 問27
問題文
自然数を除数とした剰余を返すハッシュ関数がある。値がそれぞれ 571, 1168,1566である三つのレコードのキー値を入力値としてこのハッシュ関数を施したところ、全てのハッシュ値が衝突した。このとき使用した除数は幾つか。
選択肢
ア：193
イ：197
ウ：199（正解）
エ：211
自然数を除数とした剰余を返すハッシュ関数の衝突問題【午前2 解説】
要点まとめ
- 結論：3つのキー値の剰余が同じになる除数は199である。
- 根拠：剰余が同じなら、キー値の差は除数の倍数であるため、差の最大公約数を求める。
- 差がつくポイント：複数の差の最大公約数を計算し、選択肢と照合することで正解を導く。
正解の理由
3つのキー値571、1168、1566の剰余が同じなら、それらの差は除数の倍数です。
差を計算すると、1168−571=597、1566−1168=398、1566−571=995です。
これらの最大公約数を求めると199となり、選択肢の中で該当するのはウ: 199です。
したがって、除数は199であり、全てのハッシュ値が衝突した理由が説明できます。
差を計算すると、1168−571=597、1566−1168=398、1566−571=995です。
これらの最大公約数を求めると199となり、選択肢の中で該当するのはウ: 199です。
したがって、除数は199であり、全てのハッシュ値が衝突した理由が説明できます。
よくある誤解
剰余が同じ＝キー値が同じと誤解しがちですが、実際は差が除数の倍数であることが重要です。
また、単に差の一つだけを見るのではなく、全ての差の最大公約数を求める必要があります。
また、単に差の一つだけを見るのではなく、全ての差の最大公約数を求める必要があります。
解法ステップ
- キー値の差を全て計算する（1168−571、1566−1168、1566−571）。
- 計算した差の最大公約数（GCD）を求める。
- 選択肢の中からGCDと一致する除数を選ぶ。
- その除数で剰余を計算し、衝突が起きることを確認する。
選択肢別の誤答解説
- ア: 193 → 597や398、995は193で割り切れないため不正解。
- イ: 197 → 同様に差が197の倍数ではなく不正解。
- ウ: 199 → 差の最大公約数と一致し、剰余が衝突するため正解。
- エ: 211 → 差が211の倍数ではないため不正解。
補足コラム
ハッシュ関数で剰余を使う場合、除数はできるだけ素数を選ぶことで衝突を減らす効果があります。
また、複数のキー値で剰余が衝突する場合は、キー値の差の最大公約数が除数の候補となります。
この考え方はハッシュ関数の設計や衝突解析に役立ちます。
また、複数のキー値で剰余が衝突する場合は、キー値の差の最大公約数が除数の候補となります。
この考え方はハッシュ関数の設計や衝突解析に役立ちます。
FAQ
Q: なぜ差の最大公約数を求めるのですか？
A: 剰余が同じなら差は除数の倍数であり、複数の差の最大公約数が除数の候補になるためです。
A: 剰余が同じなら差は除数の倍数であり、複数の差の最大公約数が除数の候補になるためです。
Q: 除数は必ず素数でなければなりませんか？
A: 素数を使うことで衝突を減らせますが、必須ではありません。問題の条件に合う除数を選べばよいです。
A: 素数を使うことで衝突を減らせますが、必須ではありません。問題の条件に合う除数を選べばよいです。
関連キーワード: ハッシュ関数、剰余演算、最大公約数、衝突、素数
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！