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

正解

イ. a−b が n の倍数

正答率 61.2%（1,223人中 748人が正解）

問題の解説

衝突(シノニム)とは、異なるキー a と b の格納位置 h(a)＝h(b) が一致することを指す。h(x)＝x mod n なので衝突条件は a mod n＝b mod n、すなわち a と b を n で割った余りが等しいことである。余りが等しいのは差 a−b がちょうど n で割り切れるとき、つまり a−b が n の倍数のときなので、正解は イ である。

選択肢ごとの解説

• アa＋b が n の倍数でも余りが等しいとは限らない(例 n＝5, a＝1, b＝4 では a＋b＝5 だが余りは 1 と 4 で異なる)ので誤り。
• イa−b が n の倍数のとき a と b の余りは等しくなり、h(a)＝h(b) で衝突する。これが正しい衝突条件である。
• ウ「n が a＋b の倍数」は割る数 n と割られる側の大小関係が逆で、余りが等しい条件にはならず誤り。
• エ「n が a−b の倍数」は a−b と n の役割が逆で、衝突条件「a−b が n の倍数」を取り違えているので誤り。