応用情報技術者試験 令和5年春 午前問19 解説付き過去問

この問題は、ハッシュ表における探索時間の理論的特性について問うものです。特に、ハッシュ衝突が発生しない理想的な状況において、データ件数と探索時間の関係を理解しているかが重要です。

1. ハッシュ表の仕組み
   ハッシュ表は、キーと値のペアを効率よく格納・検索するためのデータ構造です。
   キーに対してハッシュ関数を適用し、算出されたハッシュ値を使って格納位置（インデックス）を決定します。
   データの検索時も同じハッシュ関数を使うことで、データが存在する位置を即座に特定できます。
   
   
2. 探索時間の特徴
   ハッシュ関数の処理は高速であり、さらに衝突（複数のキーが同じハッシュ値になる現象）が発生しない前提であれば、検索にかかる時間は常に一定です。
   このため、データ件数が増加しても、探索時間はほとんど影響を受けません。
   これは計算量としてO(1)（定数時間）と表され、データ件数に依存しないことを意味します。
   
   
3. グラフの形状
   探索時間がデータ件数に比例して増加する場合は右上がりのグラフになりますが、
   ハッシュ衝突がない前提のハッシュ表では探索時間は一定であるため、横に真っ直ぐな直線のグラフになります。
   
   

したがって、データ件数が増加しても探索時間が一定であるという特性を表している、横ばいのグラフが正解です。