ハッシュ法におけるオープンアドレス法と衝突解決

正解は イ です。 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 で割った余りを表す。

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