平成30年度 秋期 応用情報技術者試験 午前 問27
テクノロジ／アルゴリズム自然数を除数とした剰余を返すハッシュ関数がある。値がそれぞれ571，1168，1566である三つのレコードのキー値を入力値としてこのハッシュ関数を施したところ，全てのハッシュ値が衝突した。このとき使用した除数は幾つか。
出典：平成30年度 秋期 応用情報技術者試験 午前 問27
- ア193
- イ197
- ウ199
- エ211
正解：ウ
解説
3つのキー値のハッシュ値が全て衝突する除数は，任意の2値の差を割り切る数です。1168−571＝597＝3×199，1566−1168＝398＝2×199，1566−571＝995＝5×199となり，これらの最大公約数は199です。したがって使用された除数は199と考えられます。
選択肢ごとの解説
- ア誤り。193は3値の差（597，398，995）のいずれも割り切れず，衝突を説明できません。
- イ誤り。197も同様に597，398，995を割り切れないため，条件を満たしません。
- ウ正しい。597，398，995はいずれも199で割り切れるため，除数199を使うと3つのキー値のハッシュ値が一致します。
- エ誤り。211も597，398，995を割り切れないため，全てのハッシュ値が衝突する除数にはなりません。