An unfair tie-break cuts overloaded bins 120-fold
Throw n balls into n bins, each into a random bin, and the fullest bin ends up with about ln n / ln ln n balls. Look at two random bins and use the emptier one instead, and the maximum drops to about ln ln n / ln 2. That's the "power of two choices" (Azar, Broder, Karlin and Upfal, 1994). Berthold VΓΆcking found a strange improvement in 1999: split the bins into a left half and a right half, take one choice from each, and when the two are tied, always pick the left one. The maximum drops again, to about ln ln n / (2 ln Ο), where Ο is the golden ratio. That's 1.04 instead of 1.44 in front of the ln ln n.
Both of those results hide a "+ O(1)", and ln ln n barely moves (it's 3.0 at a billion), so I wanted to see what the rule does at sizes you could actually build.
The run
A short JavaScript loop with one byte per bin and four rules: one random bin; two random bins with ties broken by a coin; one bin from each half with ties broken by a coin; and one bin from each half with ties going left. Sizes ran from 212 to 230 bins (a billion), with 400 seeds per rule at the small sizes and 6 at the largest. That's 9,448 runs, about 25 minutes on eight cores.
To check the simulation I also solved the fluid limit, the differential equations that the fraction of bins at each load follows as n grows. For two choices it's dsi/dt = siβ1Β² β siΒ², where si is the share of bins holding at least i balls. Go-left needs one such pair of equations per half. At every size, the simulated shares match the equations to three or four digits.
| share of bins holding | two choices, coin tie | two halves, coin tie | two halves, go left |
|---|---|---|---|
| β₯ 2 balls | 22.95% | 22.95% | 22.39% |
| β₯ 3 balls | 0.890% | 0.890% | 0.448% |
| β₯ 4 balls | 6.0 Γ 10β6 | 6.0 Γ 10β6 | 5.2 Γ 10β8 |
| β₯ 5 balls | 1.3 Γ 10β12 | 1.3 Γ 10β12 | 1.2 Γ 10β21 |
(The β₯ 5 row comes from the equations. No run got a bin to 5 under any of the two-choice rules.)
Splitting the bins into halves changes nothing on its own. The gain comes entirely from the tie-break: bins at 3 balls are halved, bins at 4 are 120 times rarer, and the next level falls 109-fold.
The maximum moves in steps
The fullest bin can only be a whole number, so the better tail only shows up as a lower maximum at some sizes:
| bins | runs with max load 4, coin tie | runs with max load 4, go left |
|---|---|---|
| 216 (65K) | 35% | 0.5% |
| 220 (1M) | 99.8% | 4% |
| 224 (16M) | 100% | 58% |
| 226 (67M) | 100% | 95% |
| 228 and 230 | 100% | 100% |
Every other run topped out at 3. Between about a hundred thousand and ten million bins, going left buys you one ball off the maximum. At a billion bins both rules sit at 4, and the equations say they stay tied until about 1012 bins, where the coin-tie rule starts to reach 5. Go-left doesn't reach 5 until around 1021. The asymptotic win is real, but at a billion bins it shows up in how many bins are near the top, not in the top itself.
Where the balls go
"Always left" sounds like it should pile everything onto the left half, and it does tilt: the left half ends up holding 61% of the balls (an average of 1.22 per bin against 0.78). Almost all the bins with 3 or more are on the left. But the left half's crowded tail is no worse than an ordinary two-choice table's, and the right half is nearly flat. A bin on the right only gets a ball when its partner on the left is strictly fuller, so the right half fills in where the left has already peaked. That coordination is what a fair coin throws away.
For a hash table or a load balancer, the rule costs nothing: same two lookups, one fewer random bit. If you do two-choice hashing, take the two choices from separate halves and break ties the same way every time.