平成30年度秋期応用情報技術者問27

テクノロジ系

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

正解と解説

正解ウ

3つのキー値の差がすべて除数の倍数になれば、剰余は同じになります。差597、398、995はどれも199の倍数です。

2つの値を同じ数で割った剰余が等しいのは、その差が除数で割り切れるときです。差を求めると、1168−571=597、1566−1168=398、1566−571=995です。それぞれ597=199×3、398=199×2、995=199×5となり、すべて199で割り切れます。実際に剰余を求めると、571−199×2=173、1168−199×5=173、1566−199×7=173で、3つとも173になり衝突します。

ア：193で割ると、571の剰余は185、1168の剰余は10です。値が異なるので衝突しません。

イ：197で割ると、571の剰余は177、1168の剰余は183です。値が異なるので衝突しません。

エ：211で割ると、571の剰余は149、1168の剰余は113です。値が異なるので衝突しません。

出典：平成30年度秋期応用情報技術者試験問27

全年度から出題。10問で実力を判定します。登録不要。

出典：平成30年度秋期応用情報技術者試験問27（独立行政法人情報処理推進機構）

解説と用語ページは生成 AI が書き、別の生成 AI が確かめています。作り方