平成26年春期試験問題 午前問19

ハッシュ表の理論的な探索時間を示すグラフはどれか。ここで,複数のデータが同じハッシュ値になることはないものとする。

  • 19a.gif
  • 19i.gif
  • 19u.gif
  • 19e.gif
正解 問題へ
分野:テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:アルゴリズム
解説
ハッシュ表は、キー(key)とそれに対応する値(value)の組を格納するデータ構造です。

ハッシュ表では、キーと値の組を格納する際、キーにハッシュ関数を使用して、格納する場所(インデックス)を一意に決め、そこに格納します。あるキーに対する値を取り出すときも、キーにハッシュ関数を使用することで格納場所を特定し、一発で目的のデータを参照することが可能です。ハッシュ関数からハッシュ値を計算する速度はほぼ一定なので、ハッシュ表に格納されているデータの数にかかわらず、探索時間はほぼ一定(定数時間)となります。

ハッシュ表探索では、表中のデータの数が増えても探索時間は変わらないので、適切な関係を表すグラフは「エ」です。

この問題の出題歴


Pagetop