応用情報技術者試験 応用情報技術者試験 令和元年度秋期 午前 問7: 自然数をキーとするデータを，ハッシュ表を用いて管理する。キー 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 の倍数

解説

衝突(シノニム)とは、異なるキー 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 の倍数」を取り違えているので誤り。