ハッシュ表の探索時間
出典: 令和5年度 春期 応用情報技術者試験 午前 問19 (IPA)
ハッシュ表の理論的な探索時間を示すグラフはどれか。ここで，複数のデータが同じハッシュ値になることはないものとする。
- ア
- イ
- ウ
- エ
正解と解説を見る
正解: エ
- ア: 急に増えていくグラフは、データ数の増加に対して探索時間が大きく増えるアルゴリズムです。
- イ: 比例して増えるグラフは、線形探索 (O(n)) の探索時間です。
- ウ: 増え方がゆるやかになるグラフは、2 分探索 (O(log n)) のような探索時間です。
- エ: 衝突が無ければデータの個数によらず探索時間は一定です。正しい答えです。
ポイント
- ハッシュ表は、キーから ハッシュ関数で格納位置を直接計算 して探します。
- 同じハッシュ値になること (衝突) が無ければ、データの個数に関係なく 1 回の計算で見つかります (計算量 O(1))。
- よって探索時間は、データの個数によらず 一定 (水平な直線) になります。