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