平成18年春期試験問題 午前問13

キー値が1~1,000,000の範囲で一様にランダムであるレコード3件を,大きさ10のハッシュ表に登録する場合,衝突が起こらない確率は幾らか。ここで,ハッシュ値にはキー値をハッシュ表の大きさ10で割った余りを用いる。

  • 0.28
  • 0.7
  • 0.72
  • 0.8
正解 問題へ
分野:テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:アルゴリズム
解説
ハッシュ値は"、キー値をハッシュ表の大きさ10"で割った余りなので、キー値の1の位がそのままハッシュ値ということになります。

まず1件目のレコードがハッシュ表の任意の場所に格納されます。2件目のレコードのハッシュ値が1件目のものと衝突しないためにはキー値の1の位が異なっていればいいので、衝突しない確率は9/10になります。

最後の3件目のレコードが格納されるときには、2つのレコードがすでに格納されていて、衝突が起こらないためには1,2件目両方のキー値の1の位が異なる必要があるため、衝突しない確率は8/10になります。

3件のレコードすべてが衝突しない確率は、「1,2件目が衝突しない確率」と「1,2件目と3件目が衝突しない確率」を掛け合わせたものなので、

 9/10×8/10=0.72

したがって「0.72」が適切です。

Pagetop