The tie that breaks left

The second choice measured one of the most useful results in randomised algorithms. Put $n$ keys into $n$ buckets, each key going to a random bucket, and the busiest bucket holds about $\log n / \log\log n$. Give each key two random buckets and send it to the emptier, and the busiest bucket holds about $\log\log n$ — a different function, not a smaller constant — while the mean stays exactly one.

That essay left one detail unexamined because it looked like no detail at all. When a key’s two buckets are equally full, something has to decide, and the natural choice is a fair coin. It is fair, it is symmetric, and nothing about the analysis seems to depend on it.

It turns out to be the one place in the scheme where changing a rule improves the result without costing anything, and the change is to make the decision deliberately unfair.

Two schemes that differ only in the tie #

The comparison needs the two schemes to differ in as little as possible, so both are stated exactly.

Symmetric. Each key hashes to $d$ buckets anywhere in the table. It goes to the least loaded of them; if several are tied for least loaded, one of those is chosen uniformly at random.

Asymmetric. The table is split into $d$ groups of equal size, arranged left to right. Each key hashes to one bucket in each group. It goes to the least loaded of its $d$; if several are tied, it goes to the leftmost of them.

Both schemes hash each key $d$ times, both examine $d$ buckets on insertion and on lookup, both hold the same keys in the same number of buckets, and both have a mean load of exactly one. A lookup in either examines the same number of places. The asymmetric scheme also removes the coin.

The measurement puts the same keys into both tables with $d = 2$ and reports the tail of the load distribution: how many buckets hold two or more keys, three or more, and so on. Because a tail spans several orders of magnitude on one plate, the bars are drawn with logarithmic length and the counts printed beside them.

Sixty-five thousand keys #

The effect is not subtle. The number of buckets at load three or more falls by more than half, and the maximum drops by one. That is on a scheme whose maximum is already doubly logarithmic, where the previous essay found that adding a whole third choice moved the maximum by less than a bucket.

The rows below three are nearly identical in both schemes, because the bulk of the distribution — the buckets with zero, one or two keys — is set by the mean and by the second choice itself. The tie rule changes only the top of the tail, which is where the maximum lives.

With the one-choice tail beside them the scale of the two improvements is clear. The second choice removed four or five rows of the tail. The tie rule removes one more, and it is the row that determines the maximum.

Why unfairness helps #

The mechanism is worth stating carefully, because the result looks like it should be impossible — a deterministic, biased rule beating a fair random one at a task about spreading things evenly.

Recall why two choices work at all. If a fraction $f_i$ of buckets have load at least $i$, a new key lands at load $i+1$ only if both its buckets already have load $i$ or more, which happens with probability about $f_i^2$. So the fractions obey $f_{i+1} \approx f_i^2$, and a fraction squared repeatedly vanishes doubly exponentially fast.

Now split the table into a left half and a right half, with ties going left. The left half receives every tie, so it fills slightly faster; the right half receives a key only when its bucket is strictly emptier than the left one, so it fills slightly slower and acts as overflow. The consequence is that the two halves reach each load level at different times, and a key reaching load $i+1$ in the right half needs its left bucket to be at load $i+1$ already — a level the left half reached by an earlier step of the recurrence.

The recurrence therefore stops being “square the previous fraction” and becomes “multiply the fractions from two different recent steps”. Squaring doubles the exponent at each step; multiplying the last two exponents makes the exponents grow like the Fibonacci numbers, whose growth rate is the golden ratio. The published analysis turns this into a maximum load of about $\ln\ln n / (d \ln \phi_d)$ for the asymmetric scheme, against $\ln\ln n / \ln d$ for the symmetric one, where $\phi_2$ is the golden ratio. For two choices that is a leading term smaller by a factor of about 1.39; for four choices, by about 1.9.

The unfairness is not incidental. It is what makes the two halves fill out of step, and filling out of step is what turns a square into a product of two different terms.

A small worked example makes the out-of-step filling concrete. Early in the fill, nearly every key sees two empty buckets and the tie rule sends it left, so the left half reaches a load of one faster than the right. Once most left buckets hold one key, a new key whose left bucket holds one and whose right bucket holds none goes right — so the right half now fills its empty buckets, while the left half’s buckets sit at one. When a key finds both its buckets at one, it goes left again, and the left half begins to reach load two. At every level the left half leads and the right half follows, and the right half’s buckets only reach a level once the left half’s are already there. A key that reaches load three in the right half needed the left half to have reached three first, and the left half needed an earlier round of the same argument. The fractions at each level therefore come from staggered rounds rather than from the same round twice.

A million keys #

At a million keys the pattern holds with the same proportions: the buckets at load three or more fall from 9,316 to 4,694, almost exactly half, and the maximum is three against four. The one-choice maximum has grown from eight to nine over the sixteen-fold increase in size; neither two-choice maximum has moved, which is what a doubly logarithmic function looks like over a range this narrow.

That last point limits what the plate can claim, and it should be said plainly. The theory’s improvement is in a $\log\log n$ term, and over sizes from sixty-five thousand to a million, $\log_2 \log_2 n$ goes from 4 to 4.3. No measurement at these sizes can distinguish a factor of 1.39 in that term from a constant. What the measurement can establish is the count of buckets in the tail, which is a much more sensitive statistic than the maximum and which halves consistently — and that is the statistic a system limited by its busiest buckets actually experiences, since a tail of nine thousand overfull buckets is nine thousand places where something waits.

A table with fixed-size buckets makes that concrete in a way that does not depend on anything waiting. Suppose each bucket is laid out with room for two entries, which is what a hardware table or a cache-friendly software table does, since a bucket that fits in one read is the whole reason for choosing the scheme. Every bucket holding three or more keys then overflows into some secondary structure that must be searched on every lookup that reaches it. On a million keys the symmetric scheme has 9,316 such buckets and the asymmetric one has 4,694. The tie rule has halved the overflow structure, and it is the overflow that sets the worst-case lookup.

A small table, where the rule has less room #

On a small table the maxima coincide, because both schemes’ maximum is three and there is no room for either to be lower without being two, which the mean load of one makes very unlikely for four thousand keys. The tail count separates them anyway: 37 against 10, a larger ratio than on the bigger tables, although with counts this small it is also much noisier. Counts of this size behave roughly like Poisson counts, whose standard deviation is the square root of the mean: about six for a count of 37 and about three for a count of 10. The gap between them is several standard deviations, so the separation is real on this table, but the ratio of nearly four is not to be trusted — the million-key table’s ratio of two is the better estimate of the effect, because its counts are large enough for their ratio to be stable.

This is a second reason to report the tail rather than the maximum. Expected is not average argues that a single run’s summary statistic can hide the distribution it was drawn from, and a maximum is the most fragile summary there is — it is one bucket, and on a small table it is an integer with two plausible values. Distributions, not averages is the theme; the tail count is the distribution’s top rows, read directly.

Four choices, where the rule matters most #

With four choices the asymmetric scheme removes the load-three row entirely. Its busiest bucket holds two keys — the smallest maximum possible for a table with a mean of one that is not a perfect assignment — while the symmetric scheme with the same four choices still leaves six buckets at three.

The theory said the advantage grows with the number of choices, and the plate agrees in the only way a plate at this size can: the symmetric scheme’s tail stops one row later. Four symmetric choices bought a maximum of three, the same as two asymmetric ones on a table a quarter the size. That is the practical form of the result: the tie rule is worth about as much as doubling the number of choices, and it costs nothing, where doubling the choices costs a doubling of every lookup. The comparison is across different table sizes and should be read as an order of magnitude rather than an exchange rate. What it does establish is the direction the theory predicts: the asymmetric scheme’s advantage grows with $d$, because the staggered recurrence spreads over $d$ groups rather than two, and each additional group adds another step of stagger to every level of the tail.

The randomness it saves #

This field’s own accounting has one more thing to say, and it runs in the tie rule’s favour too.

Counting the coin flips established that randomised structures spend random bits and that the amount is measurable and rarely reported. The symmetric scheme spends a random bit on every tie, and ties are common — early in the fill, most buckets are empty, so most keys see two empty buckets and need the coin. The asymmetric scheme spends none: its only randomness is the hash functions, drawn once.

So the asymmetric scheme is the rare case where removing randomness improves the result rather than costing something. What derandomising costs measures the usual case, where replacing random choices with deterministic ones gives up a guarantee or pays for a weaker one in time. Here the random coin was never doing useful work: a fair tie-break distributes ties evenly, and evenly distributed ties are exactly what keeps the two halves filling in step, which is what the asymmetric scheme gains by avoiding.

There is a second consequence of having no coin, and it concerns an adversary rather than a budget. The adversary who knows the seed measured what a caller who knows a structure’s random choices can do to it. A symmetric scheme’s tie-breaking coin is one more source of randomness that could be kept secret; the asymmetric scheme has none to keep, so its behaviour on a given set of keys is entirely determined by the hash functions. That neither helps nor hurts against an adversary who knows the hash functions — such an adversary can pile keys into one bucket under either scheme — but it means the asymmetric scheme is fully reproducible, which counting the coin flips noted is worth having for its own sake: a run can be replayed from the hash seeds alone.

Where the asymmetric scheme is used #

The result would be a curiosity if the split tables were awkward to build. They are not, and the scheme has a name where it is used: $d$-left hashing, a table of $d$ sub-tables with ties going to the leftmost.

The setting it suits is the one more hashes or wider buckets found cuckoo hashing suited — memory laid out in fixed-size buckets, where the number of places a lookup visits and the worst case of any bucket both need to be small and known in advance. A $d$-left table with buckets of a few slots has a maximum load that is small, grows almost not at all with the table, and can be provisioned for; a lookup reads $d$ buckets in known places; and nothing is ever moved after insertion, so an entry’s address is stable, which a table that points into other structures needs. It has been proposed for exactly that combination in hardware lookup tables and in counting filters whose counters live in buckets.

It also sits naturally beside the alternative that does move entries. The probe nobody waits for measured Robin Hood hashing, which rearranges keys after insertion to even out their probe lengths without changing the average. The asymmetric scheme changes the distribution without moving anything, and the two answer different constraints: one wants addresses that never change, the other wants the shortest probe sequence and accepts moving keys to get it.

What the measurement cannot separate #

The split and the bias are changed together. The asymmetric scheme differs from the symmetric one in two ways — the table is divided into groups with one choice in each, and ties go left — and the plates cannot say how much of the improvement belongs to each. The published analysis finds that the split alone, with random ties, gives essentially the symmetric result, and that the bias is what matters; a measurement of the split with random ties would check that, and it has not been drawn here.

The hash functions are independent. Each key’s two buckets are chosen by independent hashes. A hash is a family, not a function is the reminder that the guarantee is about a family with enough independence, and a table that generates its choices more cheaply is a different measurement.

Insertions only. Keys arrive and never leave. A table with deletions has a different load distribution, since a deletion can leave the left half emptier than the right, and the asymmetry’s advantage under a mixed workload is an open question for this ladder.

Where this ladder goes next: choices that are not independent #

Every scheme on this page — and on the essay it follows — computes $d$ independent hash values per key, and the analysis of the power of choices assumes the $d$ buckets are independent and uniform. Independent hashes are not free. Each is a full evaluation of a hash function, and for $d = 4$ that is four evaluations per insertion and per lookup.

There is a standard way to cheapen that: compute two hash values $h_1$ and $h_2$, and take the $d$ choices to be $h_1 + i \cdot h_2$ for $i$ from zero to $d-1$. That is two evaluations for any $d$, and the choices it produces are nowhere near independent — the third is completely determined by the first two. Whether the load distribution notices is not obvious, since the recurrence above leans on independence at every step. The next rung puts the same keys through both constructions and compares their tails bucket for bucket, at sizes up to a million keys and for two, three and four choices.