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

【解説】

ハッシュ関数 h(x) = x mod n において、キー a と b が衝突するとは：

h(a) = h(b) すなわち a mod n = b mod n となることを意味します。

この等式を変形すると：

(a – b) mod n = 0

つまり、a – b が n の倍数であるとき、a と b は衝突します。

各選択肢の検討：

• ア: a＋bがnの倍数 → 誤り。衝突条件とは無関係です。
• イ: a－bがnの倍数 → 正しい。上記の説明通り、ハッシュ値が等しくなります。
• ウ: nがa＋bの倍数 → 誤り。条件に合いません。
• エ: nがa－bの倍数 → 誤り。a – b が n の倍数であることが条件であり、その逆ではありません。