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

正解

ウ. 199

正答率 70.7%（771人中 545人が正解）

問題の解説

「除数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で正解はウ。