Hash Table

キーをハッシュ関数で整数に変換し、配列の添字として使うデータ構造。平均 $O(1)$ でキーの探索・挿入・削除を行える。衝突（異なるキーが同じハッシュ値を持つ場合）はチェイン法やオープンアドレス法で解決する。最悪 $O(n)$ は全要素が同一バケットに衝突したとき。Python の dict と set はハッシュ表で実装されている。