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

正解

ウ. 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つのキーが衝突する条件を満たさないため誤り。