Hash Table Complexity — O(1) Average, O(n) Worst Case
Deep dive into hash table time complexity: why lookups are O(1) on average, when they degrade to O(n), and how load factor, resizing, and collision resolution affect performance.
Detailed Explanation
Hash Table Time Complexity
Hash tables (hash maps, dictionaries) are one of the most important data structures in computer science because they provide O(1) average-case lookups, insertions, and deletions.
Operation Complexity
| Operation | Average | Worst Case |
|---|---|---|
| Lookup | O(1) | O(n) |
| Insert | O(1)* | O(n) |
| Delete | O(1) | O(n) |
| Resize | O(n) | O(n) |
*Amortized O(1) when accounting for resizing.
Why O(1) on Average?
A good hash function distributes keys uniformly across buckets. With a load factor α = n/m (where n is the number of keys and m is the number of buckets):
- Chaining: Expected chain length is α. If α is kept constant (by resizing), lookup is O(1 + α) = O(1).
- Open addressing: Expected probes = 1/(1 - α). With α < 0.75, this is O(1).
When It Degrades to O(n)
The worst case occurs when many keys hash to the same bucket, creating a long chain or cluster. This can happen with:
- A poor hash function
- Adversarial inputs (hash collision attacks)
- Not resizing when the load factor gets too high
Collision Resolution Strategies
| Strategy | Avg Lookup | Worst Lookup | Cache Friendly? |
|---|---|---|---|
| Chaining (linked lists) | O(1) | O(n) | No |
| Open addressing (linear probing) | O(1) | O(n) | Yes |
| Robin Hood hashing | O(1) | O(log n) expected | Yes |
| Cuckoo hashing | O(1) worst case | O(1) | Moderate |
Load Factor and Resizing
Most implementations resize when α exceeds 0.7-0.75. Resizing doubles the table size and rehashes all entries — O(n) work, but amortized O(1) per insert over a sequence of operations.
Language Implementations
- Python
dict: Open addressing with perturbation - Java
HashMap: Chaining; converts to red-black tree when a bucket exceeds 8 entries - C++
unordered_map: Chaining with buckets - Go
map: Hash map with overflow buckets
Use Case
Hash tables are essential for caches, databases (index structures), symbol tables in compilers, frequency counting, deduplication, and any scenario requiring fast key-value access.
Try It — Big-O Reference
Related Topics
Constant Time O(1) — Operations That Never Slow Down
Complexity Classes
Amortized Analysis — Average Cost Over a Sequence of Operations
Analysis Concepts
Best, Worst, and Average Case — Understanding Algorithm Bounds
Analysis Concepts
Tree Traversal Complexity — DFS, BFS, and Balanced Trees
Data Structures
Linear Time O(n) — Processing Every Element Once
Complexity Classes