戻る
一覧へ
次へ
キー値が1〜1,000,000の安易で一様にランダムであるレコード3件を、大きさ10のハッシュ表に登録する場合、衝突が起こらない確率は幾らか。
ここで、ハッシュ値にはキー値をハッシュ表の大きさ10で割った余りを用いる。
| ア | 0.28 |
| イ | 0.7 |
| ウ | 0.72 |
| エ | 0.8 |
答え ウ
【解説】
問題から、衝突が発生するのは10で割った余り(剰余)が一致した場合です。10で割った余りから考えるとデータは10通りに分類できます。
2つのデータx1とx2を10で割った時の余りが一致しないのは、x1の余りが0〜9の何れか(10通り)で、x2の余りがx1の余りと一致しないどれか9通りのときなので、確率は0.9になる。
同様に3つのデータx1、x2、x3で考えると、x1は10通り、x2は9通り、x3は8通りの数が考えられるので、確率は
1×0.9×0.8=0.72
(ウ)になる。
【キーワード】
・ハッシュ表