HOME»プロジェクトマネージャ平成21年春期»午前Ⅰ 問3
プロジェクトマネージャ平成21年春期 午前Ⅰ 問3
問3
自然数をキーとするデータを，ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)を
h(x)＝x mod n
とすると，キーaとbが衝突する条件はどれか。ここで，n はハッシュ表の大きさであり，x mod n は x を n で割った余りを表す。
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の倍数
- [出典]
- 応用情報技術者
平成21年春期 問6と同題
分類
テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム
正解
イ
解説
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＝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の倍数ではありません(×)。