応用情報技術者試験 平成30年秋 午前問27 解説付き過去問
問題
自然数を除数とした剰余を返すハッシュ関数がある。
値がそれぞれ571、1168、1566である三つのレコードのキー値を入力値としてこのハッシュ関数を施したところ、全てのハッシュ値が衝突した。
このとき使用した除数は幾つか。
正解
解説
この問題は、ハッシュ関数で使用される除数がどのように選ばれるべきか、またその除数によって値がどのように衝突するかを理解することが求められています。
- ハッシュ関数の基本
ハッシュ関数は、大きなデータセットから小さなデータ値（ハッシュ値）を計算するために使用され、これによってデータの格納、検索、削除が効率的に行えるようになります。
具体的には、ある入力値に対して除数（モジュラスとも呼ばれる）を使った剰余演算を行い、その結果がハッシュ値となります。 - 衝突の発生条件
ハッシュ関数における「衝突」とは、異なるキーが同じハッシュ値にマップされる状況を指します。問題文において、三つのキー値 571、1168、1566 が同じハッシュ値にマップされたという事実は、これらの数を除数で割った際の剰余が全て同じであることを意味します。
これを解決するためには、各キー値を除数で割った余りが同じになるような数を見つけることが必要です。 - 正解の導出
199を除数として使用した場合、571、1168、1566を199で割った余りがそれぞれ同じになることを確認します。計算すると、 571 ÷ 199 = 2 余り 173、 1168 ÷ 199 = 5 余り 173、 1566 ÷ 199 = 7 余り 173。 このように全ての余りが173であり、199が問題文で述べられた条件を満たす除数であることが確認できます。
したがって、199が全てのキー値に対しハッシュ値が衝突する除数として正しい選択です。