平成27年度 春期 応用情報技術者試験 午前 問5
テクノロジ／アルゴリズム自然数をキーとするデータを，ハッシュ表を用いて管理する。キー x のハッシュ関数 h(x) を h(x) = x mod n とすると，キー a と b が衝突する条件はどれか。ここで，n はハッシュ表の大きさであり，x mod n は x を n で割った余りを表す。
出典：平成27年度 春期 応用情報技術者試験 午前 問5
- アa＋bがnの倍数
- イa−bがnの倍数
- ウnがa＋bの倍数
- エnがa−bの倍数
正解：イ
解説
ハッシュ関数h(x)＝x mod nでは，xをnで割った余りが同じ値になるキー同士が衝突します。キーaとbが衝突する条件はa mod n＝b mod 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の倍数であることは，衝突条件のa−bがnの倍数とは異なる条件です。
- エ誤り。nがa−bの倍数（a−bがnの約数）であることは，正しい条件（a−bがnの倍数）とは逆の関係です。