情報処理安全確保支援士試験 情報処理安全確保支援士試験 令和4年度秋期 午前Ⅰ 問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は、xをnで割った余りを格納位置にする。キーaとbが衝突するのはa mod n＝b mod n、すなわち両者をnで割った余りが等しいとき。これはa−bがnで割り切れる、つまりa−bがnの倍数であることと同値で、イが正解。実装上は衝突を完全に避けられないため、チェイン法やオープンアドレス法など衝突解決法とnの選び方(素数など)が性能を左右する。

選択肢ごとの解説

• ア.a＋bがnの倍数でも余りが一致するとは限らず、衝突の条件にならないため誤り。
• イ.a−bがnの倍数なら余りが等しく、両キーが同じ位置に写って衝突するので正しい。
• ウ.nがa＋bの倍数という関係は剰余の一致と無関係で、衝突条件にならず誤り。
• エ.nがa−bの倍数では余りの一致を意味せず、条件が逆向きで誤り。