ハッシュテーブル（ハッシュマップ）
キーと値を償却O(1)で対応付けるデータ構造で、ほぼすべての言語のdict／HashMap／オブジェクトの土台。
ハッシュ関数がキーをバケット番号に変換する。衝突の処理には、バケットごとに連結リストを持つチェイン法（JavaのHashMapの既定）と、空きを探すオープンアドレス法（線形探査・二次探査。Pythonのdict、Goのmap、RustのHashBrownなど）がある。負荷率がおよそ0.75を超えるとテーブルを拡張する。
ハッシュが悪ければ最悪O(n)になる。2011年のHashDoS攻撃を受け、各言語はシード付きハッシュ（SipHash）を採用した。Robin Hoodハッシュやホップスコッチハッシュは、キャッシュ局所性に優れた現代的な変種である。