| 基本情報技術者試験 |
2010年度 ＝ 平成22年度・春期 |
午前 |
問6 |
ハッシュ表探索において、同一のハッシュ値となる確率が最も低くなるのは、ハッシュ値がどの分布で近似されるときか。
| ア ２項分布
| イ 一様分布
| ウ 正規分布
| エ ポアソン分布
|
イ
ハッシュ法は、キー値に対して何らかの変換関数を適用することによって、そのデータを格納する位置（レコード番号や配列の添字など）を求める手法です。なお、変換関数のことをハッシュ関数と呼びます。
異なるキー値に対してハッシュ関数を適用して得られたハッシュ値が同一値となることは、衝突と呼ばれます。衝突が発生した場合、データを格納する位置を何らかの方法で求め直す必要があります（チェイン法やオープンアドレス法などの手法があります）。各値が一様の確率で現われる分布である一様分布となるようなハッシュ関数であれば、衝突が発生しにくくなります。
