応用情報技術者試験 令和4年度 秋期 午前 問5

【正解】イ

ハッシュ表で衝突するとは、異なるキーをハッシュ関数に与えたとき、同じ格納位置が得られることです。このハッシュ関数では、aとbをnで割った余りが等しいときに衝突します。余りが等しいなら、ある整数p、qを用いてa＝pn＋r、b＝qn＋rと書けます。両式の差を取ると、 a－b＝（p－q）n となります。したがって、a－bがnの倍数であることが衝突の条件であり、イが正解です。例えばn＝7、a＝12、b＝5なら、どちらの余りも5であり、差の7はnの倍数です。

アの「a＋bがnの倍数」は誤りです。余りの和がnになることはあっても、二つの余りが等しいとは限りません。例えばn＝7、a＝2、b＝5では和は7ですが、余りは2と5です。

ウの「nがa＋bの倍数」は誤りです。衝突条件とは無関係な上に、割り切る側と割り切られる側も逆です。

エの「nがa－bの倍数」は誤りです。必要なのは、差がnで割り切れること、すなわちa－bがnの倍数になることです。

【ポイント】 x mod nが等しいことは、合同式ではa≡b（mod n）と表します。 これはnがa－bを割り切ることと同値です。 衝突そのものは避けられない場合があるため、チェイン法やオープンアドレス法で処理します。