情報処理安全確保支援士試験 情報セキュリティスペシャリスト試験 平成27年度春期 午前Ⅰ 問3: 自然数をキーとするデータを，ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)を h(x) ＝ x mod n とすると，キーaとbが衝突する条件はどれか

正解

イ. a−bがnの倍数

問題の解説

ハッシュ関数h(x)=x mod nでキーaとbが衝突するのは、h(a)=h(b)すなわちa mod n＝b mod nのとき。これはaとbをnで割った余りが等しいことを意味し、差a−bがnで割り切れる（nの倍数になる）条件と同値。イが正しい。衝突はハッシュ表性能を左右するため、表サイズnの選び方や衝突解決法（チェイン法・オープンアドレス法）の理解が実装上重要となる。

選択肢ごとの解説

• アa+bがnの倍数でも余りが等しいとは限らず、衝突条件と無関係で誤り。
• イa−bがnの倍数⇔a mod n＝b mod nで、両者のハッシュ値が一致し衝突するため正しい。
• ウnがa+bの倍数という関係は剰余の一致を導かず、衝突条件として誤り。
• エ倍数の向きが逆で、通常a−b≧nなので「nがa−bの倍数」とはならず誤り。