自然数を除数とした剰余を返すハッシュ関数がある。値がそれぞれ571，1168，1566である三つのレコードのキー値を入力値としてこのハッシュ関数を施したところ，全てのハッシュ値が衝突した。このとき使用した除数は幾つか。
- 193
- 197
- 199
- 211
解答
ウ
解説
剰余が同じであるということは、値の差が除数の倍数であることを示します。
571 = 除数 × ？ + 剰余
1168 = 除数 × ？ + 剰余
1566 = 除数 × ？ + 剰余
3つの値の差は
1168 − 571 = 597
1566 − 1168 = 398
1566 − 571 = 995
であり、これらの公約数は199であるため、除数は199とわかります。
参考情報
分野・分類
| 分野 | テクノロジ系 |
| 大分類 | 技術要素 |
| 中分類 | データベース |
| 小分類 | データベース設計 |
出題歴
- AP 平成30年度秋期 問27
