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