Worst-Case Time Complexity Scenarios
You'll learn: When hash tables lose their speed advantage and degrade from O(1) to O(n) operations.
The Problem
Hash tables shine with average O(1) lookups, insertions, and deletions—but this assumes keys are distributed evenly across buckets. In the worst case, everything falls apart.
When does worst-case O(n) happen?
-
Poor hash function: If your hash function maps all keys to the same bucket (or a few buckets), you've essentially created a linked list. Every operation must traverse that chain.
-
Pathological input: An attacker or unlucky data set might exploit your hash function's weaknesses, causing massive clustering.
-
High load factor: As the table fills up (especially with open addressing), collisions multiply. While rehashing helps on average, you can still hit worst-case scenarios before rehashing triggers.
The Analogy
Imagine a library with 100 shelves but a terrible cataloging system that files all books on Shelf #1. Finding your book now requires scanning through every single title—no better than a plain list!
Real Impact
In separate chaining, if all n keys hash to one bucket, searching requires traversing the entire chain: O(n). With open addressing, if clustering is severe, you probe through most of the table: also O(n).
This is why hash function quality matters. A good hash function plus proper load factor management keeps worst-case scenarios rare in practice, but they're theoretically always possible.
Key Takeaway: Hash tables degrade to O(n) performance when poor hash functions or pathological inputs cause all keys to collide into the same bucket or cluster, forcing linear search through the entire structure.