平成21年春期試験問題 午前Ⅰ 問3

自然数をキーとするデータを,ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)を
 h(x)=x mod n
とすると,キーaとbが衝突する条件はどれか。ここで,n はハッシュ表の大きさであり,x mod n は x を n で割った余りを表す。

  • a+bがnの倍数
  • a-bがnの倍数
  • nがa+bの倍数
  • nがa-bの倍数
正解 問題へ
分野:テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:アルゴリズム
解説
aをnで割ったときの商をk、bをnで割ったときの商をl、余りがどちらもxとなる場合を式で表すと、

 a=kn+x
 b=ln+x

となります。これをxについて解くと、

 x=a-kn
 x=b-ln

と変換できます。余りであるxが等しくなるとき a-kn と b-ln は等しいので、方程式で関係を導きます。

 a-kn=b-ln
 a-b=kn-ln
 a-b=n(k-l)

ここで、aとb及びnが自然数であることから商であるkとlも自然数となります。よって n(k-l) はnの倍数です。

 ∴余りxが同じとき、a-bはnの倍数
 
以上より、キーの衝突には「a-bがnの倍数」という条件があるとわかります。したがって「イ」が正解です。

ここまでが論理的に解を導く方法ですが、計算結果が同じになるa・b・nを用意して選択肢の記述の正誤を判断することもできます。例えば、a=51、b=27、n=12(どちらも余りが3)で試してみると、
  • a+b=78なので、12の倍数ではありません(×)。
  • a-b=24なので、12の倍数になっています(〇)。
  • a+b=78なので、12は78の倍数ではありません(×)。
  • a-b=24なので、12は24の倍数ではありません(×)。

Pagetop