Why a hash table finds things in constant time

A hash table finds a key among a million others about as fast as among ten. It does not search. It computes where the key must be, and looks there.

Address instead of search

Each item has a key — a word, a number, a file name — and you later ask "is this key here?" Keep the items in an array of m slots, called buckets. A hash function turns any key into a bucket number from 0 to m−1. Storing computes the bucket and puts the item there; finding computes the same bucket and looks. The arithmetic costs the same for ten items or ten million.

Why it matters

This is the dictionary built into most programming languages; the MIT lecture notes list where else it sits: compilers mapping names to variables, routers mapping addresses to wires, virtual memory mapping virtual to physical addresses. The notes' comparison point, a balanced search tree, costs time logarithmic in the item count. Hashing removes that dependence — on average. The rest of this page is what that hides.

Collisions are inevitable

Far more keys are possible than buckets, so two must sometimes share one: a collision, and it comes sooner than intuition expects. Drop random keys into 64 buckets and the first collision arrives, on average, with the 11th key (10.7, computed exactly). With 365 buckets — the birthday problem — about the 25th (24.6). With 1,024, about the 41st. Collision-free is not realistic.

The notes' fix is chaining: each bucket holds a linked list of whatever hashed to it; a lookup walks that one list. Cost: one hash plus the chain length.

The load factor

How long is a chain? The lecture assumes — openly calling it cheating — simple uniform hashing: each key equally likely to land in any bucket, independently of the others. Then n keys in m buckets give n/m expected per bucket. The notes name this ratio the load factor α and give the expected search cost as Θ(1 + α): 1 for hashing, α for walking the list. Constant whenever α is — whenever m keeps pace with n.

Lecture 9 works out the rule the notes settle on (growing one bucket at a time is rejected first): when n reaches m, allocate 2m buckets and reinsert every key, since the hash function itself changes with m. That rebuild costs time proportional to n, but happens only at insertion 1, 2, 4, 8, … so the total over n insertions is still proportional to n. The notes call the cost per insertion Θ(1) amortized — averaged over the whole sequence, not promised per operation.

When it goes wrong

All of this rests on the keys spreading out. The notes state the worst case plainly: if all n keys hash to one slot, every operation costs Θ(n) — the table is one long list. A hash function reading only part of the key does this by itself; try the first-letter hash in the interactive. The notes' answer is universal hashing: pick the hash function at random from a family when building the table. Any two distinct keys collide under the chosen function with chance 1/m, so the expected number of other keys in your bucket is again α, assuming nothing about the keys. The worst case does not disappear; the random choice makes it unlikely, not impossible.

In short

Compute the bucket, look inside. Collisions arrive early, so each bucket keeps a chain of expected length n/m, the load factor. Doubling keeps that ratio bounded; a random hash function keeps chains short on any input not built to defeat it.