自然数をキーとするデータを，ハッシュ表を用いて管理する。キー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、bのハッシュ値はそれぞれ
h(a) = a mod n （aをnで割った余り）
h(b) = b mod n（bをnで割った余り）
となります。
ここで、任意の自然数α、βを用いて、a、bは次のように表せます。
a = n × α + (a mod n)
b = n × β + (b mod n)
任意のキーaとbが衝突する場合、a mod n = b mod n であるので
a - b = n × α - n × β = n(α - β)
つまり、a−bがnの倍数となります。
参考情報
分野・分類
| 分野 | テクノロジ系 |
| 大分類 | 基礎理論 |
| 中分類 | アルゴリズムとプログラミング |
| 小分類 | アルゴリズム |
出題歴
- AP 令和4年度秋期 問5
- AP 令和元年度秋期 問7
- AP 平成27年度春期 問5
- AP 平成25年度秋期 問7
- AP 平成23年度秋期 問5
- AP 平成21年度春期 問6
