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

問題本文

自然数をキーとするデータを，ハッシュ表を用いて管理する。キー x のハッシュ関数 h(x) を h(x) ＝ x mod n とすると，任意のキー a と b が衝突する条件はどれか。ここで，n はハッシュ表の大きさであり，x mod n は x を n で割った余りを表す。

選択肢

• ア.a＋b が n の倍数
• イ.a－b が n の倍数
• ウ.n が a＋b の倍数
• エ.n が a－b の倍数

正解

イ. a－b が n の倍数

解説

ハッシュ法では 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で割り切れることである。