アルゴリズム (全82問中68問目)

No.68

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

分類

テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム

正解

解説

ハッシュ値は"、キー値をハッシュ表の大きさ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」が適切です。
© 2010-2018 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop