情報処理安全確保支援士試験 情報処理安全確保支援士試験 令和6年度秋期 午前Ⅰ 問3: 自然数をキーとするデータを，ハッシュ表を用いて管理する。キー x のハッシュ関数 h(x) を h(x) ＝ x mod n とすると，任意のキー a と b

正解

イ. a－b が n の倍数

正答率 25.0%（4人中 1人が正解）

問題の解説

ハッシュ法では h(x)=x mod n が同じ値になるキー同士が同じ格納位置を争い、これを衝突という。h(a)=h(b) すなわち a mod n = b mod n が成り立つのは、a と b を n で割った余りが等しい、つまり差 a-b が n で割り切れる(n の倍数)ときである。イが正しい。衝突条件の理解はハッシュ表サイズ n の選定やチェイン法・オープンアドレス法の設計判断に直結する。

選択肢ごとの解説

• ア和a+bがnの倍数でも余りが等しいとは限らず、衝突の条件にはならない。
• イa-bがnの倍数なら両者の余りが一致し、同じハッシュ値となって衝突する正しい条件。
• ウnがa+bの倍数という関係は剰余の一致を意味せず、衝突条件として誤り。
• エ向きが逆で、衝突に必要なのはnがa-bを割るのではなくa-bがnで割り切れることである。