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