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

ハッシュ表においてデータの探索時間は理論的には O(1)（定数時間）です。ハッシュ関数によってデータの位置が直接計算されるため、表の中のデータの個数が増えても探索時間は一定になります。

• ア: 指数的な増加は誤りです。ハッシュ表ではこのような動作はしません。
• イ: データの個数に比例する直線的な増加は、線形探索や連結リストの場合です。ハッシュ表ではこれに該当しません。
• ウ: 徐々に飽和するのはバケットの負荷が高くなった場合や、データ構造が不完全な場合です。理論上のハッシュ表では該当しません。
• エ: 正しい。データの個数に関係なく、探索時間が一定であるのがハッシュ表の特徴です。

答え

エ: データの個数に関係なく，探索時間が一定である水平線のグラフ。