応用情報技術者試験 応用情報技術者試験 令和5年度春期 午前 問19: ハッシュ表の理論的な探索時間を示すグラフはどれか。ここで，複数のデータが同じハッシュ値になることはないものとする。

正解

エ. 横軸を表の中のデータの個数，縦軸をデータ1個当たりの探索時間としたとき，データの個数にかかわらず探索時間が一定であるグラフ

正答率 46.2%（773人中 357人が正解）

問題の解説

ハッシュ表は、キーからハッシュ関数で格納位置を直接求めるので、データの個数が増えても、1 個を探す手間は変わらない（計算量は O(1)）。衝突が起きないという前提なので、探索時間は個数に関係なく一定で、グラフは横軸に平行な直線になる。

選択肢ごとの解説

• ア探索時間が加速度的に増える曲線は、個数が増えるほど手間が急増する場合のものである。ハッシュ表の探索時間は個数に影響されない。
• イ個数に比例して直線的に増えるのは、先頭から順に比べる線形探索の特徴である。ハッシュ表は個数が増えても探索時間が変わらない。
• ウ増加がしだいに緩やかになる曲線は、2 分探索のように個数の対数に比例して時間が増える方法に近い。ハッシュ表では、そもそも増加しない。
• エ正しい。ハッシュ値から格納位置が直接決まるので、データの個数にかかわらず探索時間は一定になり、グラフは水平な直線になる。