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

問 5
応用情報技術者試験 2022年(令和4年度)秋期 午前

自然数をキーとするデータを,ハッシュ表を用いて管理する。キー 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−b) mod n=0(a - b) \bmod n = 0,つまり a−ba - b が nn で割り切れる(a−ba - b が nn の倍数である)ことと同値です。

  • ア: a+ba + b が nn の倍数となるのは,たとえば二つの余りが互いに補い合う場合であり,衝突の条件ではありません。
  • ウ・エ: 「nn が a+ba+b(又は a−ba-b)の倍数」という関係は,余りが等しくなる条件とは異なります。

関連問題

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