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

正解

ウ. 199

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

問題の解説

除数 で割った余りが 3 個のキーで等しいとき、キー同士の差は の倍数になる。差は 、 なので、共通の約数（1 を除く）は 199 である。実際に 571、1168、1566 を 199 で割った余りは、いずれも 173 になる。

選択肢ごとの解説

• ア193 で割った余りは順に 185、10、22 で、全て異なるため衝突しない。
• イ197 で割った余りは順に 177、183、187 で、全て異なるため衝突しない。
• ウ正しい。199 で割った余りは三つとも 173 で、全て同じハッシュ値になり衝突する。
• エ211 で割った余りは順に 149、113、89 で、全て異なるため衝突しない。