情報処理安全確保支援士試験 情報処理安全確保支援士試験 令和4年度秋期 午前Ⅰ 問3: 自然数をキーとするデータを，ハッシュ表を用いて管理する。キー x のハッシュ関数 h(x) を h(x) = x mod 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の倍数では余りの一致を意味せず、条件が逆向きで誤り。