高度情報処理技術者試験・情報処理安全確保支援士試験 令和6年度 秋期 午前I 問3

【正解】イ

ハッシュ表で衝突が発生するのは、異なるキーから同じハッシュ値が得られるときです。したがって条件は、a mod n＝b mod nです。aとbをnで割った余りが等しい場合、その差a－bはnで割り切れます。つまりa－b＝knとなる整数kが存在し、a－bがnの倍数であることが衝突の条件です。例えばn＝10、a＝23、b＝13なら、どちらの余りも3であり、差10はnの倍数です。よってイが正解です。

アの「a＋bがnの倍数」は誤りです。例えばn＝10、a＝3、b＝7では和は10ですが、ハッシュ値は3と7で衝突しません。和ではなく差に注目します。

ウの「nがa＋bの倍数」は誤りです。例えばn＝10、a＝2、b＝3では、nはa＋b＝5の倍数ですが、ハッシュ値は2と3です。これはハッシュ値が等しくなる条件ではありません。

エの「nがa－bの倍数」は誤りです。倍数の関係が逆です。例えばn＝10、a＝6、b＝1では、nは差5の倍数ですが、ハッシュ値は6と1で衝突しません。必要なのは、差がnの倍数になることです。

【ポイント】 「同じ余りになる」という関係を合同といい、a≡b mod nと表します。 合同であるための条件は、a－bがnで割り切れることです。 ハッシュ値が一致してもキー自体は同じとは限らないため、衝突への対処が必要です。