The second choice

Throw $n$ balls into $n$ bins uniformly at random. The average bin holds one. The busiest holds about $\log n / \log\log n$ — three at a thousand bins, four at a million, and growing without bound however slowly.

Now change one thing. For each ball, pick two bins at random and put it in whichever currently holds fewer. The average is unchanged; it cannot change, since the same number of balls go into the same number of bins. The busiest bin now holds about $\log\log n$, which is five at a million and six at a billion.

That is not a smaller constant on the same function. It is a different function, and the gap between them grows.

The result is worth stating carefully because it is easy to hear as something weaker. It is not that two hashes spread keys better than one — they do not; each hash on its own is exactly as good as the other, and either one used alone gives the first column of the table below. It is not that the keys are moved afterwards to even things up; nothing is ever moved. Two independently good hashes, plus one comparison at the moment of insertion, produce a distribution whose tail is a different function of $n$.

What the two curves are #

The measurement is over a range because two numbers at one size are a constant and cannot distinguish two growth rates.

The first column rises. The second is nearly flat across a 256-fold range, moving once. The third is flatter still and — this is the part that surprises people — barely different from the second.

The published statements match that shape. With one choice the maximum is $\Theta(\log n / \log\log n)$; with $d \ge 2$ choices it is $\log\log n / \log d + \Theta(1)$. So going from one choice to two changes the function, and going from two to three divides an already-small logarithm of a logarithm by $\log 3 / \log 2$. Almost all of the benefit is in the second choice and there is nearly none in the third, which is why the result is called the power of two choices rather than the power of many.

The measured maxima are about twice the asymptotic prediction — six where $\log n / \log\log n$ is three at a thousand — and that gap is a constant this collection is used to. A ratio test across the range is what grants a class here, and the ratio for the one-choice column is flat while the two-choice column’s is not, which is the honest way to say the two are different shapes.

There is a second reason a range is necessary and it is about what the plate would otherwise be measuring. The maximum over $n$ buckets is itself a random variable, and a single build at a single size gives one draw from it. What makes the flat column trustworthy is not that four is a small number; it is that the same seeded construction at four different sizes produces three, three, three and four, and the one-hash column produces six, six, seven and eight over the same sizes. Two sequences moving differently is evidence; two numbers are not. Expected is not average makes the same argument about a single run of a randomised algorithm, and it binds here because the quantity being reported is itself a tail statistic.

Why it works, in one sentence #

The mechanism is worth stating because it is not obvious that the improvement should be so large.

Under one hash a bin’s load is a sum of independent indicators, and its distribution has a tail that decays like a Poisson’s — so the maximum over $n$ bins is wherever the tail crosses $1/n$, which is high because a Poisson tail is not very thin.

Under two, a bin reaches load $k+1$ only if both of a ball’s choices already held $k$ or more. So if a fraction $f_k$ of bins have load at least $k$, the fraction reaching $k+1$ is about $f_k^2$. Squaring a fraction below one repeatedly drives it to zero at a doubly exponential rate, and that is exactly the $\log\log$: the number of squarings needed to take $1/2$ below $1/n$ is $\log_2\log_2 n$.

The improvement comes from a fraction being squared rather than multiplied, which is why a third choice cubes rather than squares and buys correspondingly little.

The argument also says where the improvement stops. Squaring drives a fraction to zero fast, and it only starts once the fraction is below one — so the mechanism operates on the upper tail and does nothing at all to the bulk. That is visible in the numbers: the mean is one in both schemes, the number of empty buckets is nearly the same, and the whole of the difference is in the handful of buckets at the top. A technique that improves only a tail is exactly as valuable as the tail is, and no more, which is the reason the next section is about who is limited by a maximum.

What a maximum is, as a statistic #

The plate reports a maximum and this collection almost always reports a total or a mean, so it is worth a paragraph on what changes.

A total is additive and a maximum is not. Two tables’ comparison counts add; two tables’ worst buckets do not. That means a maximum cannot be amortised, cannot be traded across operations, and does not shrink when a system is made larger — it grows, because a maximum over more samples is larger. Every intuition built on totals runs the wrong way here.

It also means a maximum is a statement about one sample. The busiest bucket at a quarter of a million keys is one bucket out of 262,144, and the fact that it holds eight rather than four is a fact about a single location that the mean is entirely blind to. Distributions, not averages is the theme this collection has for the distinction, and this page is its cleanest instance: two schemes with identical means, identical variance in the bulk, and different tails.

The practical consequence is that the two schemes are indistinguishable by any measurement that summarises. A benchmark reporting mean lookup time sees nothing; a benchmark reporting the ninety-ninth percentile sees the whole effect. Which of those a benchmark reports decides whether the technique appears to do anything at all.

What it is not #

Two things this result is regularly confused with, and both are structures this collection has already measured.

It is not Robin Hood hashing. The probe nobody waits for measures a scheme that makes an inserting key steal a slot from a key that has probed less far, and finds the mean number of probes afterwards is 4.817 — identical to what it was before, and necessarily so, because the total displacement is fixed by the hash. Robin Hood moves keys after they have been placed and redistributes an unchanged total. Two choices places each key once and changes the total.

It is not a better hash function. A hash is a family, not a function shows what a bad hash does — all 2,048 keys in bucket zero — and what a good one does. Both hashes here are good ones drawn from the same family. The improvement is not in where either of them sends a key; it is in having two answers and being allowed to pick.

The distinction matters because the three techniques compose. A table can use two good hashes, take the emptier bucket, and rearrange afterwards, and each of the three does something the others do not.

Where the result came from, and what it is used for #

The measurement above is a laboratory version of a result whose value is entirely in the settings it is deployed in, and naming those makes the plate’s regime look less arbitrary.

A load balancer. Requests arrive and must be sent to one of $m$ servers. Sending each to a random server is the one-hash column; sending each to the less loaded of two randomly chosen servers is the two-hash column. The quantity a user experiences is the queue at the server they landed on, and the quantity that determines the worst experience is the maximum queue. Halving it is the difference between a system whose tail latency is acceptable and one whose is not.

A distributed cache. Each key lives on the machine its hash names, and a machine holding many keys is a hot spot. Two hashes with the emptier chosen spread the hot spots, and the cost — reading both machines on a lookup — is a second request rather than a second round trip if they are issued together.

A sharded queue. Work items are placed into one of many queues and drained by workers. The slowest queue sets the completion time of the whole batch, which is a maximum again.

What all three share is that the resource being balanced is a thing somebody waits for rather than a thing that is summed. That is the condition under which a maximum is the right statistic, and it is why this result is ubiquitous in systems work and nearly absent from the analysis of in-memory data structures — where an algorithm looks is the kind of question that matters there, and it is a question about totals.

What the second probe costs #

Nothing on this site is free and the accounting here is unusually clean.

On insertion: two hash evaluations and two bucket reads instead of one. That is a factor of two on the cheapest part of the operation.

On lookup: both buckets must be examined, because the key could be in either and nothing records which. That is the real price, it is paid on every lookup for the life of the table, and it is a factor of two on the operation the table exists for.

So the trade is: the worst bucket halves, and every read doubles. Whether that is worth it depends entirely on which of the two quantities the system is limited by, and there is a clean answer.

A table whose buckets are chains in memory cares about the average, because a lookup follows one chain and the average chain is short either way — and a bucket that becomes a tree is what a library does about the tail instead. Two choices makes it worse.

A system where a bucket is a machine cares about the maximum, because the maximum is the slowest server and the slowest server is the response time. Here two choices is transformative, and this is where the result is actually used — load balancers, distributed caches, sharded queues. The extra probe is a second request in flight, which costs bandwidth rather than latency.

That difference is the same one expected is not average is about: a mean describes a cost that is paid many times and amortised, and a maximum describes a cost that is paid once and felt.

The randomness it spends, which is the resource this field counts #

This field’s own instrument charges for random bits, and it is worth pointing it at this technique because the answer is unusual.

Counting the coin flips found that a skip list spends 2.03 random bits per key and a treap spends exactly thirty-two, that reservoir sampling spends 1,356,399 bits on a stream of 65,536 and a better version spends 9,380, and that none of those numbers appears in any complexity class the structures are described by.

Two choices spends nothing extra. Both hashes are drawn once, at table construction, from a seeded family — a handful of words, independent of $n$ — and every key thereafter is placed deterministically given those two functions. There is no per-key randomness at all. So the technique improves a tail without consuming the resource that other randomised structures buy their guarantees with, and its cost is entirely in probes rather than in entropy.

That is worth having explicitly because it separates two things that usually travel together. A randomised structure is normally paying for its behaviour with randomness, and the amount is measurable and sometimes enormous. Here the randomness is a fixed cost paid once, and what is being paid per key is a comparison. The resource being spent is the one nobody thought to count, and the resource this field learned to count is not being spent at all.

What the measurement can and cannot support #

It cannot separate $\log\log n$ from a constant. Over the sizes drawn, $\log_2\log_2 n$ runs from 3.3 to 4.2 — a range of 0.9 — and the measured maximum moves from 3 to 4. Those are consistent with the published bound and they are also consistent with a constant, and no sweep this site can run distinguishes them. What the measurement does establish is that the two-choice maximum is not growing like the one-choice maximum, which is the claim the plate is making.

The load factor is one throughout. Every plate here puts $n$ keys into $n$ buckets. At a load factor well above one the picture changes: the maximum becomes the mean plus a fluctuation, both schemes’ maxima are dominated by the mean, and the difference between them shrinks to a lower-order term. The result is about the sparse regime, which is the regime a load balancer is in and not the regime a hash table is in.

Nothing here is measured under attack. The adversary who knows the seed shows what a key set chosen against a hash does to it, and two choices does not defend against that: an adversary who knows both functions can find keys that collide under both. The technique improves a distribution and does not create a guarantee, which is a distinction a guarantee is not a result is the theme for.

And the hashes are drawn from a family with a stated independence. Multiply–shift is universal, which is enough for a collision bound and is weaker than the full independence the published analysis assumes. That gap is the subject of a different rung in this field and it matters here in the usual direction: a weaker family can only make the measured maximum worse than the theory, and the measurement is consistent with the theory, so nothing is hiding in it.

What a third choice would have to buy #

The table’s third column is nearly the same as its second, and it is worth saying why that is the expected outcome rather than a disappointment.

Under $d$ choices the maximum is about $\log\log n / \log d$. Going from one choice to two replaces $\log n / \log\log n$ with $\log\log n$, which is a change of function. Going from two to three divides $\log\log n$ by $\log_2 3 = 1.58$, which at these sizes is the difference between 4.2 and 2.7 — a fraction of a bucket, invisible in an integer count.

Meanwhile the cost of the third choice is exactly as large as the cost of the second: one more hash on insertion, one more probe on every lookup. The benefit is dividing a doubly logarithmic quantity and the cost is a whole extra probe, so the marginal return collapses immediately and the measurement says so — three, three, three and four for two choices against two, three, three and three for three.

That is a cleaner instance of diminishing returns than most, because both sides of it are computable. It is also the reason a technique with a memorable name has the number two in it rather than a parameter: there is no interesting sweep to be had, and the first step is the whole result.

Where this ladder goes next: an insertion that can fail #

Every structure in this field so far buys an expected cost and accepts a tail. A skip list’s search is expected $\log n$ and occasionally more; a hash table’s probe is expected constant and occasionally long; two choices, on this page, improves a tail without removing it.

There is a structure that removes it, and the way it pays is worth a rung of its own. Cuckoo hashing gives each key two slots and guarantees that a lookup examines exactly two — not on average, and not for these keys: for any keys, always, a worst case rather than an expectation. What it gives up is that the build can fail: an inserting key displaces whatever is in its slot, which displaces the next, and the chain may not terminate.

So the randomness moves out of the query and into the construction, where it stops being a distribution of costs and becomes a probability of failing outright. And that probability has a threshold rather than a slope — below about half a slot per key it essentially never happens and above it essentially always does — which is a different kind of statement from anything this field has measured, and one whose location is exactly computable and exactly checkable.