アルゴリズム (全97問中83問目)
No.83
キー値が1～1,000,000の範囲で一様にランダムであるレコード3件を，大きさ10のハッシュ表に登録する場合，衝突が起こらない確率は幾らか。ここで，ハッシュ値にはキー値をハッシュ表の大きさ10で割った余りを用いる。
出典：平成18年春期 問13
- 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」が適切です。
まず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」が適切です。