平成27年度 春期 応用情報技術者試験 午前 問5

キー a と b が衝突するのは，ハッシュ値が等しい，つまり a mod n ＝ b mod n のときです。これは a と b を n で割った余りが等しいことであり，a－b が n の倍数であることと同じです。

• ア: a＋b が n の倍数
  誤り。例えば n ＝ 5，a ＝ 1，b ＝ 4 のとき a＋b ＝ 5 は5の倍数ですが，余りは1と4で異なり衝突しません。

• イ: a－b が n の倍数
  正しい。a mod n ＝ b mod n ＝ r とすると，a ＝ pn＋r，b ＝ qn＋r と表せるので，a－b ＝ (p－q)n となり n の倍数です。逆に a－b が n の倍数なら余りは等しくなります。

• ウ: n が a＋b の倍数
  誤り。a＋b と n の関係が逆であり，余りが等しくなる条件ではありません。

• エ: n が a－b の倍数
  誤り。倍数の関係が逆です。例えば n ＝ 6，a ＝ 5，b ＝ 2 のとき n は a－b ＝ 3 の倍数ですが，余りは5と2で異なり衝突しません。

答え

イ: a－b が n の倍数