Every expectation about a hash table assumes something about the keys, and an adversary who can see your hash function can break the assumption. A universal family removes it: choose the function at random, and any fixed pair of distinct keys collides with probability at most 1/m, whichever pair it is. The lab counts every function in the family for a pair you choose, and the fraction is an exact count rather than a sample.
Core ideas
The hard idea is where the randomness lives. The other two are the definition it makes possible and the guarantee that definition is worth.
“Balls in Bins and the Birthday Bound” assumed the keys were thrown uniformly at random. That is an assumption about the input, and an input can refuse to satisfy it — keys that are all multiples of m under h(k) = k mod m, for instance. A universal family makes no assumption about the keys at all: the keys are whatever they are, possibly chosen by someone who has read your code, and the function is what is drawn at random.
A family H of functions from keys to 0..m−1 is universal if for every pair of distinct keys x and y, a uniformly random h from H has P(h(x) = h(y)) ≤ 1/m. It says nothing about three keys, nothing about the shape of the whole table, and nothing about any particular h — some member of the family maps everything to one slot, and that is allowed. It is a statement about pairs, averaged over the family.
That is why pairs are the right thing to bound. The expected length of the chain holding key x is 1 + Σ over the other n − 1 keys of P(h(y) = h(x)), which is at most 1 + (n − 1)/m by universality and linearity. No independence between pairs is needed, which is fortunate, because a universal family need not provide any.
The material
The definition, one family that meets it, the exact count over every member, and what a fixed function loses.
Start with what goes wrong. Take h(k) = k mod 8, a perfectly reasonable hash function, and hand it to someone who wants the table to perform badly. They insert 8, 16, 24, 32, …. Every key lands in slot 0, every lookup walks the whole chain, and the table's average-case analysis was about a distribution of keys that this input is not from. Hashing with Chaining shows that instance running; this lesson is what to do about it.
Let U be the set of possible keys and m the number of slots. A finite family H of functions U → {0, …, m − 1} is universal if for every pair of distinct keys x ≠ y in U, P(h(x) = h(y)) ≤ 1/m when h is drawn uniformly at random from H. The probability is over the choice of h only; x and y are fixed first, and may be chosen by an adversary who knows H.
The order of quantifiers is the content of the definition. For every pair, the average over functions is small. Not: for every function, most pairs are fine — that would be a much weaker statement and it is what a fixed hash function offers. The adversary is allowed to pick the pair after seeing the family, and is not allowed to see the coin that picks h.
Fix a prime p larger than every key. For a in 1..p − 1 and b in 0..p − 1, let hₐ,ᵦ(k) = ((a·k + b) mod p) mod m. The family is all p(p − 1) of these functions, and drawing h uniformly means drawing a and b uniformly.
For distinct keys x and y below p, a uniformly chosen hₐ,ᵦ has P(hₐ,ᵦ(x) = hₐ,ᵦ(y)) ≤ 1/m.
Work modulo p, which is a field because p is prime. Write r = (ax + b) mod p and s = (ay + b) mod p. As (a, b) ranges over the p(p − 1) allowed pairs, (r, s) ranges over all p(p − 1) pairs with r ≠ s, each exactly once: given r ≠ s, solving r − s = a(x − y) for a is possible and unique because x − y is invertible modulo p, and b is then determined.
So the question becomes: for how many pairs r ≠ s is r mod m = s mod m? For each of the p choices of r, the values s congruent to it modulo m and different from it number at most ⌈p/m⌉ − 1 ≤ (p − 1)/m.
That gives at most p(p − 1)/m colliding pairs out of p(p − 1), so the probability is at most 1/m.
□
The lab does not take that proof on trust: it enumerates. At p = 11 and m = 4 the family has 10 × 11 = 110 functions, and for the pair 3 and 7 exactly 20 of them collide. That is 2/11 ≈ 0.1818, comfortably under the bound 1/4. Change the pair and the count changes; over every pair of distinct keys below 11, the worst is still 2/11, so this family does better than universality requires on this instance.
p = 11, m = 4, pair 3 and 7: 20 collisions in 110 functions, 2/11 = 0.1818, bound 1/4. p = 7, m = 3, pair 1 and 4: 10 in 42, 5/21 = 0.2381, bound 1/3. p = 13, m = 5, pair 2 and 9: 22 in 156, 11/78 = 0.1410, bound 1/5. Every one of those is a complete enumeration of the family, not a sample of it.
The guarantee is about a pair fixed before the coin is flipped, and it holds for every such pair. So a table built on a universal family has an expected chain length of at most 1 + (n − 1)/m for every input, including inputs constructed to be bad. The expectation is over the choice of h, and it is the same guarantee that “Randomised Quicksort” gets from a random pivot: the input is arbitrary, the coins are the algorithm's, and the average is over the coins.
What is not bought is any promise about the particular h you drew. Some member of the family is terrible for your keys, and you may have drawn it. The guarantee says that is unlikely, in the precise sense that the average over the family is small; if the table turns out slow you re-draw h and rebuild, and that is a real operation with a real cost. A guarantee in expectation is not a guarantee per instance, which is the same distinction “The Cost Is a Distribution” drew for a comparison count.
Set the comparison the other way. Fix h(k) = k mod 4 and let the adversary choose. They pick 1 and 5, which are congruent modulo 4, and those two keys collide with probability 1 — certainty, not 1/4. The panel prints that row beside the counted rate, and the contrast is the entire argument for the family: 2/11 against 1, on keys the adversary chose in both cases.
There is a cost, and it is worth naming. Every lookup now computes a multiplication, an addition and two remainders instead of one remainder, and the table must store a, b and p. Whether that is worth paying depends on whether anyone can choose your keys, which is a question about the system rather than about the algorithm — and it is the reason a compiler's symbol table and a public web service make different choices here.
Interactive
The randomness is in the function, and the keys may be chosen against you
Method
Check what is fixed, what is random, and in what order.
Here it is over the choice of h, with x and y fixed first. Every sentence about universal hashing is wrong if that is reversed, and the reversal is the natural reading of the phrase “the probability that two keys collide”.
Move the two key sliders to whatever looks worst. The counted rate stays under 1/m because the definition quantifies over pairs. Then fix a single function and try the same thing: the panel shows the pair that collides with certainty.
Universality bounds pair collisions and nothing else. An expected chain length follows by linearity over pairs; a claim about the maximum chain, or about three keys landing together, does not follow and needs a stronger property.
Two modular reductions per lookup and three stored constants, in exchange for a guarantee that survives chosen keys. Decide whether anything in the system can choose the keys; if nothing can, the guarantee is buying insurance against an event that cannot occur.
p = 11, m = 4, keys x = 3 and y = 7. The family has 10 choices of a and 11 of b, so 110 functions, and the question is how many of them put 3 and 7 in the same slot.
Look at the a = 1 block alone: seven collisions out of eleven, a rate far above 1/4. Universality is not a promise about any one value of a; it is a promise about the average, and six of the ten values of a collide on this pair not once in eleven, which is what brings the total to 20. Reading a guarantee about an average as a guarantee about every member is the mistake this table is laid out to make visible.
Notice also that the rate came out 2/11 rather than 1/4. The bound is an inequality and this family clears it with room to spare on this instance; ⌈p/m⌉ − 1 in the proof is 2 here while (p − 1)/m is 2.5, so the counting step gave away a little. A bound that is met with slack is the normal case, and the lab prints both numbers so the slack is visible rather than assumed away.
For a faded rehearsal, switch to p = 7, m = 3 and predict the collision count before reading it. The supplied first move is this: the family has 6 × 7 = 42 members and the bound is 1/3, so at most 14 of them may collide. Say how many actually do, then check — and then say why the answer does not depend on which pair of distinct keys you picked, on this particular p and m.
You should be able to define a universal family, verify the multiply-shift family meets it, derive the expected chain length from pairwise collisions and linearity, and say precisely what the guarantee does not cover about the function you happened to draw.
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.