Throw n keys into m slots uniformly at random. The expected number of colliding pairs is n(n − 1)/2m and the expected number of empty slots is m(1 − 1/m)ⁿ, both by linearity of expectation over events that are not independent. The point where a collision becomes more likely than not is found by multiplying the exact product out. The maximum load is a different question and this library answers it nowhere.
Core ideas
The hard idea is that linearity needs no independence, and here the events are visibly dependent. The other two are the exact product behind the birthday bound and the honest status of the maximum.
For each of the C(n, 2) pairs of keys, let Xᵢⱼ be 1 if they land in the same slot. Two keys land together with probability 1/m, so E[Xᵢⱼ] = 1/m, and E[Σ Xᵢⱼ] = C(n, 2)/m = n(n − 1)/2m by linearity. The indicators are not independent — if 1 and 2 collide and 2 and 3 collide then 1 and 3 certainly do — and linearity does not care. That is the step most readers believe they need independence for.
For each slot, let Yⱼ be 1 if it is empty. A given key misses a given slot with probability 1 − 1/m, and the n keys are thrown independently, so E[Yⱼ] = (1 − 1/m)ⁿ and E[Σ Yⱼ] = m(1 − 1/m)ⁿ. At 23 keys in 365 slots that is 342.68, and the seeded throw left 343 empty. The same technique, a different index set, and again no independence between the Yⱼ is needed or available.
With as many keys as slots the expected load per slot is 1, and the maximum load is about log n / log log n. That result is quoted on the panel and labelled STATED, NOT PROVED, in those words, because its proof needs Chernoff bounds and this course excludes them. Beside it the panel puts the maximum it counted — 4 at 365 keys in 365 slots on this seed, against a stated figure of 3.32. One of those two numbers was computed here.
The material
The collision arithmetic behind every hash table on this path, with each quantity's standing stated next to it.
n keys are thrown into m slots, each key landing in a uniformly random slot, independently of the others. This is the idealisation a hash function is assumed to realise; Universal Hashing is where the assumption is replaced by something provable. A collision is a pair of keys in the same slot, and the load of a slot is how many keys it holds.
The expected number of unordered pairs of keys that land in the same slot is n(n − 1)/2m, exactly, for every n and m.
Index the C(n, 2) = n(n − 1)/2 unordered pairs. For a pair {i, j} let Xᵢⱼ = 1 if keys i and j land in the same slot and 0 otherwise. The number of colliding pairs is X = Σ Xᵢⱼ.
Condition on where key i lands. Key j lands there with probability 1/m whatever that slot was, so P(Xᵢⱼ = 1) = 1/m and E[Xᵢⱼ] = 1/m.
Linearity of expectation gives E[X] = Σ E[Xᵢⱼ] = C(n, 2)·(1/m), which is n(n − 1)/2m. The indicators are dependent — collision is transitive — and linearity holds for dependent summands, so nothing here needs repair.
□
At 23 keys in 365 slots that is 253/365 ≈ 0.693, a number below one. The seeded throw on the panel produced exactly one colliding pair. Change the seed and the count moves between 0 and 3; the expectation does not move at all, and it is printed as the fraction 253/365 rather than as a decimal for the same reason every other exact quantity on this course is.
The expected number of slots holding no key is m(1 − 1/m)ⁿ, exactly.
For slot j let Yⱼ = 1 if slot j is empty. A single key misses slot j with probability 1 − 1/m, and the n keys are independent of each other, so all n miss it with probability (1 − 1/m)ⁿ.
So E[Yⱼ] = (1 − 1/m)ⁿ, and the expected number of empty slots is Σⱼ E[Yⱼ] = m(1 − 1/m)ⁿ by linearity. The Yⱼ are dependent — if m − 1 slots are empty the last one is not — and again that costs nothing.
□
Note which independence was used and which was not. Inside a single Yⱼ the n keys are independent, and that is a genuine hypothesis of the model. Between the Yⱼ nothing is assumed, and nothing is true. Keeping those two apart is the whole skill: the first is about the throws, the second would be about the slots, and only the first is available.
The probability that all n keys land in distinct slots is the product (m/m)·((m − 1)/m)·…·((m − n + 1)/m), and the lab evaluates it as an exact fraction over BigInt. At m = 365 it first drops below a half at n = 23, where it is 0.492703…; so 23 keys make a collision more likely than not, and 22 do not. The familiar √(2m ln 2) ≈ 22.5 is a rule of thumb, and the panel does not use it — it searches upward through the exact product and reports the first n that crosses.
m = 64 slots: even odds at n = 10. m = 128: at n = 14. m = 365: at n = 23. m = 1000: at n = 38. Each of those is close to √m and nowhere near m. A table with a thousand slots is not comfortable until far fewer than a thousand keys have arrived — it sees its first collision at around forty, which is four per cent full.
This is why hash tables are engineered around load factors and chains rather than around avoiding collisions. Collisions are not an anomaly to be designed out; they are the expected state of a table that is a few per cent full, and Hashing with Chaining spends its whole page on what to do about them.
Throw n keys into n slots. The mean load is exactly 1. The maximum load is Θ(log n / log log n) with high probability, and if each key picks two slots and takes the emptier the maximum drops to about ln ln n. Both of those are quoted on the panel and both are labelled STATED, NOT PROVED. Their proofs need Chernoff bounds, which no Subject in this library teaches, and stating a result is not proving it.
So the panel does the one honest thing available: it prints the stated figure and the counted maximum in adjacent rows. At m = 365 with 365 keys the stated one-choice figure reads 3.32 and the seeded throw's tallest slot held 4. Those do not contradict each other — an asymptotic growth rate with suppressed constants is not a prediction of a small instance — and the gap is a reminder of what a growth rate is and is not.
Partitioning and Load Balancing, on the System Design path, is where the maximum load matters rather than the mean, because a shard's capacity is set by its busiest moment. That course measures the same two quantities on real placements and quotes the same two asymptotics under the same caveat. Between the two pages the expectations are derived once, here, and the maximum is measured twice and derived nowhere.
Interactive
Both expectations exact, the even-odds point found by multiplying it out
Method
Choose the index set first. Everything else is one probability and a sum.
Pairs of keys for collisions, slots for emptiness, keys for something else. The choice fixes the size of the sum and is where almost all the difficulty is; the two results on this page differ only in that choice.
E[Xᵢⱼ] = P(the pair collides) = 1/m. E[Yⱼ] = P(slot j is empty) = (1 − 1/m)ⁿ. This is one probability about one object, and it is where the model's independence assumption is used if it is used at all.
Linearity holds for dependent summands. If you find yourself arguing that the indicators are approximately independent, you have added a false premise to a proof that did not need one, and it will be false in the next example.
An expectation over pairs is not a probability of a collision, and neither is a statement about the maximum. On this page all three are printed, they differ, and only the first two are computed here.
The classic instance, with every quantity the panel prints and the standing of each. n = 23, m = 365, throw seed 4.
The expected number of colliding pairs is below one and yet a collision is more likely than not: 0.693 against 0.507. There is no contradiction — the first is an expected count and the second is a probability of a count being at least one — but the pair of numbers is a good test of whether the distinction has landed. Markov's inequality, from the previous lesson, even relates them: P(X ≥ 1) ≤ E[X]/1 = 0.693, and the truth is 0.507.
The empty-slot figure is the one that surprises people in the other direction. 343 of 365 slots empty after 23 throws is obvious once said and rarely predicted, and it is the same arithmetic that makes a hash table's memory cost real: most of the table is doing nothing at low load.
For a faded rehearsal, set the slots to 128 and predict the even-odds point before moving the keys slider. The supplied first move is this: it is near √m, and √128 ≈ 11.3. Say whether the true answer is above or below that, then find it — and then say why n(n − 1)/2m = 1 gives yet another nearby number, and which of the three questions each one answers.
You should be able to derive both results on this page from indicators, say exactly where independence was and was not used, distinguish an expected count from the probability of at least one, and state the standing of every row the panel prints.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.