キー値が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
(ウ)になる。
【キーワード】
・ハッシュ表
- ハッシュ表
データの格納方法で、データからハッシュ関数で用いたハッシュ値をキーとして格納位置を決めます。
異なったデータから同じハッシュ値になることを衝突(コリジョン)といい、衝突が発生した場合の格納位置の求め方も考慮しておく必要があります。
もっと、「ハッシュ表」について調べてみよう。
戻る
一覧へ
次へ