305. Why is hash table lookup O(1) on average but O(n) in the worst case? What are expected collisions for n keys in m slots?
MediumSymbol tables & hashing
Show model answer
A good hash function spreads keys roughly uniformly, so each bucket holds about α = n/m keys. If the table resizes to keep α bounded by a constant, the expected work per operation is constant. This is an average over hash behaviour, not a guarantee: if many keys share a bucket, a lookup scans all of them, which is O(n) in the extreme. Randomized or keyed hash functions (universal hashing, SipHash) prevent attackers from forcing that case.
With uniform hashing, each of the n(n − 1)/2 pairs collides with probability 1/m, so the expected number of colliding pairs is n(n − 1)/(2m). This is the birthday paradox: with 365 slots, 23 keys already give better than even odds of at least one collision, and collisions become expected once n is around √m.