Hash Tables
← Back to Hash-Based Structures
Maps keys to values using a hash function. The workhorse of fast lookups — nearly every language provides a built-in implementation (dict, HashMap, Map, object).
Key Properties
Complexity
- Average — Insert O(1), Lookup O(1), Delete O(1).
- Worst case (all collisions) — O(n).
Related
- Hash Sets
- Arrays (underlying storage)
- Bloom Filters (probabilistic variant)