応用情報技術者試験 応用情報技術者試験 令和6年度秋期 午前 問6: 自然数をキーとするデータを，ハッシュ表を用いて管理する。キー 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(a)＝h(b)、すなわち a mod n ＝ b mod n となる条件を求める問題である。2 数を n で割った余りが等しいということは、その差 a−b が n でちょうど割り切れること、つまり a−b が n の倍数であることと同値である。よって正解はイである。具体例として n＝5 のとき a＝13、b＝3 は差 10 が 5 の倍数で、ともに余り 3 で衝突することからも確認できる。

選択肢ごとの解説

• ア.a＋b が n の倍数でも余りが等しいとは限らない（例 n＝5,a＝1,b＝4 は和 5 が倍数だが余りは 1 と 4 で異なる）ため誤りである。
• イ.a−b が n の倍数のとき a と b を n で割った余りは必ず一致し h(a)＝h(b) となって衝突するため、これが正しい条件である。
• ウ.「n が a＋b の倍数」は割り切る向きが逆で、余りが等しいことを意味せず誤りである。
• エ.「n が a−b の倍数」も向きが逆で、衝突条件は a−b が n の倍数（n が a−b を割るのではなく a−b が n で割り切れる）であるため誤りである。