問題プレビューID: 55451e3e応用情報技術者試験 2011年(平成23年度)秋期 午前

問 5
応用情報技術者試験 2011年(平成23年度)秋期 午前

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

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

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

解説

正解は「イ」です。

ハッシュ値が衝突するとは,h(a)=h(b)h(a) = h(b),すなわち a mod n=b mod na \bmod n = b \bmod n となることです。aa を nn で割った余りと bb を nn で割った余りが等しいということは,aa と bb の差 a−ba - b が nn で割り切れること,つまり a−ba - b が nn の倍数であることを意味します。

よって,正解は「イ」です。ア・ウは加算に関する条件であり,エは倍数の向きが逆で,いずれも衝突の条件ではありません。

関連問題

本文が同じ・似ている問題を表示しています