情報処理安全確保支援士試験 情報処理安全確保支援士試験 平成30年度秋期 午前Ⅰ 問9: 自然数を除数とした剰余を返すハッシュ関数がある。値がそれぞれ571，1168，1566である三つのレコードのキー値を入力値としてこのハッシュ関数を施したところ，

問題本文

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

選択肢

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

正解

ウ. 199

解説

剰余ハッシュ(キー mod 除数)で複数キーが衝突する=同じ剰余をもつとは、キー同士の差がその除数で割り切れること。1168−571=597、1566−1168=398、1566−571=995の最大公約数を取ると、597=3×199、398=2×199、995=5×199で共通因数は199。よってウが正解。除数に素数を選ぶと衝突が偏りにくいという、ハッシュ表設計の基礎とも関係する。

選択肢ごとの解説

• ア.193では597や398を割り切れず、3キーが同一剰余にならないため誤り。
• イ.197では差597・398・995のいずれも割り切れず、全キーの衝突を説明できないため誤り。
• ウ.差597・398・995がいずれも199の倍数で、3キーが同じ剰余となり正しい。
• エ.211では差を割り切れず、3つのキーが衝突する条件を満たさないため誤り。