問19応用情報技術者 令和5年度 春期

解説

正解は4。ハッシュ表では、キーからハッシュ関数で格納位置を計算し、その位置を直接参照する。問題文の条件どおり衝突（同じハッシュ値）が起きなければ、データが何件あっても1回の計算と参照で見つかるので、1個当たりの探索時間は件数によらず一定になる。件数を横軸にしたグラフでは水平な直線になるエが当たる。

• 1は、件数が増えると探索時間が急に伸びる形で、一定にはならない。
• 2は、件数に比例して伸びる直線で、線形探索（O(n)）の特性に当たる。
• 3は、件数とともに伸びて次第に緩やかになる形で、2分探索（O(log n)）に近い。

根拠：探索アルゴリズムの標準的な理解（ハッシュ法の探索時間は衝突がなければO(1)）