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