問題プレビューID: 8d88f5b3応用情報技術者試験 2015年(平成27年度)春期 午前

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

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

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

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

解説

正解は「イ」です。

キー aa と bb が衝突するのは,ハッシュ値が等しい,すなわち a mod n=b mod na \bmod n = b \bmod n となるときです。これは aa と bb を nn で割った余りが等しいことを意味するので,a−ba-b が nn の倍数である場合に衝突します。

  • ア: a+ba+b が nn の倍数であることは衝突の条件ではありません。
  • ウ・エ: 「nn が ⋯\cdots の倍数」とするのは主客が逆であり,正しい条件ではありません。

関連問題

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