平成23年度 秋期 応用情報技術者試験 午前 問5
テクノロジ／アルゴリズム自然数をキーとするデータを，ハッシュ表を用いて管理する。キー x のハッシュ関数 h(x) を h(x) ＝ x mod n とすると，キー a と b が衝突する条件はどれか。ここで，n はハッシュ表の大きさであり，x mod n は x を n で割った余りを表す。
出典：平成23年度 秋期 応用情報技術者試験 午前 問5
- アa＋b が n の倍数
- イa－b が n の倍数
- ウn が a＋b の倍数
- エn が a－b の倍数
正解：イ
解説
ハッシュ関数 h(x)＝x mod n では，aとbをnで割った余りが等しいとき衝突します。余りが等しいことは a－b が n で割り切れること，すなわち a－b が n の倍数であることと同値です。
選択肢ごとの解説
- ア誤り。a＋bがnの倍数であっても，aとbのnで割った余りが一致するとは限りません。
- イ正しい。h(a)＝h(b) は a－b が n の倍数であることと同値です。
- ウ誤り。nとa＋bの倍数関係が逆で，衝突条件の説明になっていません。
- エ誤り。nとa－bの倍数関係が逆で，条件として成立しません。