問題プレビューID: 8f47f6ae基本情報技術者試験 午前免除試験 2021年6月13日

問 8
基本情報技術者試験 午前免除試験 2021年6月13日

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

a mod n=b mod n  ⟺  (a−b) mod n=0  ⟺  a−b が n の倍数a \bmod n = b \bmod n \iff (a - b) \bmod n = 0 \iff a - b \text{ が } n \text{ の倍数}

  • ア・ウ: a+ba + b に関する条件は,余りが等しくなる条件とは関係ありません。
  • エ: nn が a−ba - b の倍数であるという条件は,a−ba - b が nn の倍数であることの逆であり,一般には成り立ちません。

関連問題

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