Expert · Module 22 · Lesson 4 of 4
Expected cost of hashing
Hash tables are O(1) only in expectation, and only if the hash function spreads keys well. Choosing the function at random from a universal family makes that expectation hold for every set of keys, which is also the defense against hash-flooding attacks.
By the end you can
- Compute the expected chain length under universal hashing, and explain why it bounds lookups at O(1 + α)
- Explain why any fixed hash function has bad inputs, and how a random seed removes them
- Relate load factor, resizing and probing to the expected cost, and recognize stronger guarantees such as cuckoo hashing
Builds on Randomized algorithms, Resizing and load factor.
01 · A question first
In 2011, researchers showed that a single web request of a few hundred kilobytes could keep a server's CPU busy for minutes. The request carried form fields whose names all hashed to the same bucket, turning every hash table insert into a scan. The fix in most languages was one line: pick the hash function at random when the process starts. Why does that work?
Make a guess before you read on.
02 · The idea
Members only
Unlock the full lesson
This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.
What's inside
- O(1) is a statement about probability
- Every fixed function has bad inputs
- Universal hashing
- The expected cost
- Probing needs more
- Stronger guarantees
- In practice
- Pseudocode & Multi-Language Implementations (C++, Java, Python)
03 · Practice
Asked in interviews
Something wrong with this lesson? Report a problem