問題プレビューID: d7f08855応用情報技術者試験 2019年(令和元年度)秋期 午前

問 7
応用情報技術者試験 2019年(令和元年度)秋期 午前

自然数をキーとするデータを,ハッシュ表を用いて管理する。キー 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(x)=x mod nh(x) = x \bmod n で,キー aa と bb が衝突するのは h(a)=h(b)h(a) = h(b),すなわち aa と bb を nn で割った余りが等しいときです。これは (a−b)(a - b) が nn で割り切れること,つまり a−ba - b が nn の倍数であることと同値です。

  • ア: a+ba + b が nn の倍数となるのは aa と bb の和が nn で割り切れる場合であり,衝突条件ではありません。
  • ウ・エ: 「nn が … の倍数」は関係が逆であり,誤りです。

よって,正解は「イ」です。

関連問題

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