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

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

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

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

とすると,任意のキー a と b が衝突する条件はどれか。ここで,n はハッシュ表の大きさであり,x mod n は x を n で割った余りを表す。

解説

正解は「イ」です。

キー a と b が衝突するとは,ハッシュ値が等しいこと,すなわち a mod n=b mod na \bmod n = b \bmod n となることです。これは「a を n で割った余りと b を n で割った余りが等しい」ことを意味し,a と b の差 a−ba-b が n で割り切れる,つまり a-b が n の倍数であることと同じです。

  • ア: a+b が n の倍数であることは衝突の条件ではありません(例:a=1,b=2,n=3 のとき a+b=3 ですが,1 mod 3=1,2 mod 3=2 で衝突しません)。
  • ウ・エ: 「n が a+b や a-b の倍数」という関係は逆であり,衝突の条件を表していません。

関連問題

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