ハッシュテーブル（適切なハッシュ関数と負荷率を保つ場合）の平均的・期待される探索（検索）時間のオーダーはどれか？

ハッシュテーブルは衝突解決（チェイニングや開番地法）を適切に行い、負荷率を一定に保てば、キーの探索（挿入・削除・検索）の期待時間は定数時間、すなわち O(1) になります。これは平均的・確率的な議論に基づくもので、最悪ケース（悪いハッシュ関数や全衝突など）では O(n) になることがありますが、実用的には期待 O(1) が利点です。