応用情報技術者試験 応用情報技術者試験 平成30年度秋期 午前 問27: 自然数を除数とした剰余を返すハッシュ関数がある。値がそれぞれ 571，1168，1566 である三つのレコードのキー値を入力値としてこのハッシュ関数を施したとこ

問題本文

自然数を除数とした剰余を返すハッシュ関数がある。値がそれぞれ 571，1168，1566 である三つのレコードのキー値を入力値としてこのハッシュ関数を施したところ，全てのハッシュ値が衝突した。このとき使用した除数は幾つか。

選択肢

• ア.193
• イ.197
• ウ.199
• エ.211

正解

ウ. 199

解説

「除数dで割った余り（mod d）が等しい＝衝突する」とき、2つのキーの差はdの倍数になる。3つの値の差をとると 1168−571＝597、1566−1168＝398。衝突するにはdがこれらの差を割り切る必要がある。597＝199×3、398＝199×2なので、共通の約数として199が当てはまる。実際に各値を199で割った余りは571÷199＝余り173、1168÷199＝余り173、1566÷199＝余り173で全て一致するため、除数は199で正解はウ。