令和4年度秋期 情報処理安全確保支援士 午前Ⅰ 問3

午前I 問03：ハッシュの衝突は「同じ余り」になるときだよ

ハッシュ関数 `h(x)=x mod n` は、ざっくり言うと「x を n で割った余り」を番号札として使う仕組みだよ。だから `a` と `b` が衝突するのは、2人が同じ番号札をもらうとき、つまり `a mod n = b mod n` になるときなんだ。これは言い換えると、`a-b` が `n` で割り切れる、つまり `n` の倍数になるということだよ。選択肢では和や積に目が行きがちだけど、見るべきポイントは「同じ余りになるか」だよ。

この問題で問われていること

`mod` は「割った余り」だと押さえて、衝突条件を `a mod n = b mod n` と立てられるかがポイントだよ。

Collision Condition for a Modulo Hash Function

for h(x)=x mod n、 collisions occur when two keys leave the same remainder modulo n、 which means their difference is a multiple of n

collision = same remainder\na mod n = b mod n\na-b is a multiple of n\nignore sum or product distractors

確認ポイント

• 余りが同じ条件に戻す。
• 和や積に引っ張られない。
• mod の定義で考える。

正解

イ

出典

問題文と解答は IPA 公開の過去問題冊子・解答例を基にしています。

選択肢ア

不正解だよ。これは「a+bの方がnで割り切れる」という話だけど、衝突は合計では決まらないんだ。ロッカー番号を決めるときに、2人の番号を足しても意味がなくて、それぞれをnで割った余りが同じかを見る必要があるよ。

選択肢イ（正解）

不正解だよ。abがnの倍数でも、aとbをnで割った余りが同じとは限らないんだ。合鍵の番号を決めるとき、2つの番号を掛けても同じ窓口に行くかは分からない、という感じだね。衝突を見るなら、aとbの差がnで割り切れるかを確認しよう。

選択肢ウ

不正解だよ。ハッシュ表では、キーをnで割った「余り」が同じなら同じ箱に入って衝突するんだ。見るべきなのはa+bではなく、aとbの差だよ。例えばn=6でa=2、b=4ならa+b=6でnの倍数だけど、余りは2と4で別の箱だから衝突しないよ。

選択肢エ

不正解だよ。ab、つまりaとbを掛けた数を見ても、同じ箱に入るかは分からないよ。例えばn=6、a=2、b=3ならab=6でnの倍数だけど、余りは2と3で違う箱になるよ。衝突の条件は掛け算ではなく、a-bがnの倍数になることだよ。