Course contentsShow
← Computer Science
Lesson 434 of 2,87210. Hash TablesFree lesson

Worst-Case Time Complexity Scenarios

Understanding when hash tables degrade to O(n) performance due to collisions and poor hash functions.

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?

  1. 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.

  2. Pathological input: An attacker or unlucky data set might exploit your hash function's weaknesses, causing massive clustering.

  3. 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.