問題プレビューID: 52ed7555応用情報技術者試験 2009年(平成21年度)春期 午前

問 6
応用情報技術者試験 2009年(平成21年度)春期 午前

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

h(x) = x mod n

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

解説

正解は「イ」です。

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

  • ア: a+b が n の倍数である必要はありません。
  • ウ: n が a+b の倍数という条件は衝突と関係がありません。
  • エ: n が a−b の倍数という関係は,a−b が n の倍数とは逆の関係です。

したがって,「イ」が正解です。

関連問題

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