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