Why is the worst-case lookup O(n)? How do modern implementations avoid this? (Tree buckets)
Worst-Case Lookup and Tree Buckets
Worst-case Hash Table lookup is O(n) because a malicious or pathological key distribution can place many entries in the same bucket. A lookup may then need to inspect every entry in that bucket. Some modern separate-chaining implementations convert sufficiently large buckets from linked structures into balanced search trees, reducing bucket lookup from linear to logarithmic time.
- 1
Good hash distribution normally keeps bucket sizes small.
- 2
Treeification protects against pathological collision chains in some implementations.
- 3
Tree-based buckets can provide O(log k) lookup within a bucket.
- 4
Treeification has additional memory and comparison overhead.
- 5
The exact thresholds and implementation strategy are library-specific.
- 6
This optimization does not mean all Hash Table operations are unconditionally O(log n); expected behavior remains approximately O(1).
Follow-up Questions
- How does Java HashMap treeification work?
- Why not use trees for every bucket?
- What are the memory trade-offs?