剰余を用いたハッシュ関数におけるキー衝突の条件

正解は イ です。 a と b が衝突するのは、 n で割った余りが等しい ときです。a=pn+r、b=qn+r(余りが同じ r)と表すと、$a-b=(p-q)n$ となり、差が n の倍数になります。 例(n=7) a mod 7 b mod 7 衝突 a−b a+b a=17, b=3 3 3 する 14(7の倍数) 20 a=10, b=4 3 4 しない 6 14(7の倍数) 2行目のように a+b が n の倍数でも衝突しないことがあるので、アは誤りです。

自然数をキーとするデータを,ハッシュ表を用いて管理する。キー xx のハッシュ関数 h(x)h(x) を

h(x)=x mod nh(x) = x \bmod n

とすると,任意のキー aa と bb が衝突する条件はどれか。ここで,nn はハッシュ表の大きさであり,x mod nx \bmod n は xx を nn で割った余りを表す。

出典令和4年度 秋期 応用情報技術者試験 午前 問5
ア
a+ba+b が nn の倍数
イ
a−ba-b が nn の倍数
ウ
nn が a+ba+b の倍数
エ
nn が a−ba-b の倍数