平成23年度 秋期 応用情報技術者試験 午前 問5
自然数をキーとするデータを，ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)を
h(x) ＝ x mod n
とすると，キーaとbが衝突する条件はどれか。ここで，nはハッシュ表の大きさであり，x mod nはxをnで割った余りを表す。
キーボード：1〜4 で解答 → 次の問題 ← 前の問題
正解と解説を見る
解答する前に解説を開いたので、この問題は「見て解いた」として記録します（正解数には入りません）。
正解：イ
衝突とは，異なるキーa，bのハッシュ値が等しくなること，つまり a mod n ＝ b mod n となることです。
nで割った余りが等しい2数の差 a－b は，nで割り切れます。したがって，衝突する条件は「a－bがnの倍数」です。
-
ア: a＋bがnの倍数
誤り。例えばn＝5，a＝1，b＝4のとき a＋b＝5 ですが，余りは1と4で異なります。 -
イ: a－bがnの倍数
正しい。a mod n ＝ b mod n と a－b がnの倍数であることは同値です。 -
ウ: nがa＋bの倍数
誤り。余りが等しくなる条件とは関係ありません。 -
エ: nがa－bの倍数
誤り。倍数の関係が逆です。例えばn＝6，a＝3，b＝1のとき6は2の倍数ですが，余りは3と1で異なります。
答え
イ: a－bがnの倍数
出典：平成23年度 秋期 応用情報技術者試験 午前 問5
