| 第１種情報処理技術者試験 |
2000年度 ＝ 平成12年度 |
午前 |
問11 |
自然数をキーとするデータを、ハッシュ表を用いて管理したい。ハッシュ関数h (x )を
h (x)＝ x mod n
で定める。ここで、n はハッシュ表の大きさで、x mod n はx をn で割った余りとする。キーがa であるデータと、キーがb であるデータに対して、衝突が起きる条件はどれか。
ア a ＋ b が n の倍数
イ a － b が n の倍数
ウ n が a ＋ b の倍数
エ n が a － b の倍数
イ
キーがa であるデータと、キーがb であるデータに対して、衝突が起きるということは、a mod n とb mod n が等しいということです。
a mod n ＝ b mod n
(a - b ) mod n ＝ 0
したがって、選択肢イの〔a － b が n の倍数〕が正解です。
