応用情報技術者試験 応用情報技術者試験 令和6年度秋期 午前 問6: 自然数をキーとするデータを，ハッシュ表を用いて管理する。キー x のハッシュ関数 h（x）を h（x）= x mod n とすると，任意のキー a と b が衝

正解

イ. a－b が n の倍数

正答率 65.0%（779人中 506人が正解）

問題の解説

ハッシュ法で異なるキーが同じ格納位置になることを衝突（シノニム）といい、ここでは 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 で割り切れる）であるため誤りである。