Choices that are not independent

Every argument for the power of choices in this ladder has leaned on one word. The second choice explained why two choices flatten the busiest bucket with a recurrence — the fraction of buckets at load $i+1$ is about the square of the fraction at load $i$ — and that square is the probability that two independent choices both land on busy buckets. The tie that breaks left sharpened the recurrence by staggering the rounds, and still multiplied probabilities of independent events.

Independence is not free. Each choice is a separate evaluation of a separate hash function, and a scheme with four choices evaluates four hash functions on every insertion and every lookup, for the life of the table. Hash evaluation is often the dominant cost of a lookup in a table whose buckets are already in cache.

There is a standard way to cheapen it, borrowed from open addressing: double hashing. Compute two hash values, $h_1(x)$ and $h_2(x)$, and generate the $d$ choices as

$$g_i(x) = h_1(x) + i \cdot h_2(x) \pmod{n}, \qquad i = 0, 1, \dots, d-1.$$

That is two hash evaluations for any number of choices. And the choices it produces are not independent in any sense: once the first two are known, every later one is fixed, since they form an arithmetic progression. This page measures whether the load distribution notices.

Why independence was assumed, and what the proof multiplies #

It is worth stating exactly where the analysis uses independence, because that says what a weaker scheme would have to preserve.

The recurrence behind the power of choices is a statement about one arriving key. If a fraction $f_i$ of buckets currently hold at least $i$ keys, the key raises some bucket to $i+1$ only if every one of its $d$ choices already holds at least $i$. With independent, uniform choices that probability is $f_i^d$, and the whole of the doubly logarithmic maximum follows from iterating it.

So the proof needs one thing of the $d$ choices: that the probability they all land among the busy buckets is about $f_i^d$. Full independence gives that, but it gives far more — it says the choices are unrelated in every respect, including respects the recurrence never consults. An arithmetic progression with a random start and a random odd step does not make the choices unrelated. It does make each choice individually uniform, and it spreads them over the table in a pattern that has nothing to do with which buckets happen to be busy. Since the busy buckets are themselves determined by where earlier keys’ progressions went, the question is whether progressions correlate with the set of busy buckets in a way that raises the chance of all $d$ landing in it. There is no mechanism by which they would, and the measurements below find none.

That kind of argument — a proof stated under a strong assumption, and a result that holds under a much weaker one because the proof only ever used part of the assumption — is the ordinary situation for randomised analysis, and it is why independence has a degree rather than being a yes-or-no property.

The comparison #

Both schemes put the same keys into the same number of buckets, one key per bucket on average, each key going to the least loaded of its choices. The independent scheme draws its $d$ choices from $d$ independently seeded hash functions. The double-hashing scheme draws $h_1$ and $h_2$ from two independently seeded functions and generates the rest. The step $h_2$ is forced to be odd, for a reason that turns out to be the whole story and is taken up below.

The statistic is the tail of the load distribution — how many buckets hold two or more keys, three or more, and so on — because the tie that breaks left found the tail count to be a far more sensitive measure than the maximum. Bars are drawn with logarithmic length, since the rows run from hundreds of thousands to single digits.

For two choices the comparison is already not quite empty. $g_0 = h_1$ and $g_1 = h_1 + h_2$ are computed from two independent hashes, but with the step forced odd, $g_1$ always has the opposite parity to $g_0$ — so the second choice is uniform only over the half of the table the first choice is not in, and the two are dependent in that one respect. It is a dependence that can only help, since it guarantees the two choices are different buckets. The small difference between 60,418 and 59,994 is two different pairs of hash functions producing two different tables, and it is the size of difference any two independent runs show.

For three choices the generated scheme is genuinely different: $g_2 = h_1 + 2h_2$ is determined by $g_0$ and $g_1$. The tails still agree — 46,456 against 46,243 at load two, the same maximum of three.

A million keys, and four choices #

At a million keys, with four choices where three of the four are determined by the first two, the tails agree to within a tenth of a per cent at load two and within a few per cent in the rows above. The four-choice tables have 21 and 23 buckets at load three respectively — two tables built from different hash functions, differing by what two tables built from different hash functions differ by.

The honest way to put the result is that on these tables, at these sizes, no row of the tail distinguishes generated choices from independent ones. The differences between the two schemes are of the same size and sign-randomness as the differences between two runs of the same scheme with different seeds, which is what a measurement looks like when the thing measured is not there.

The published analysis says the same thing asymptotically. For balanced allocation, the fraction of buckets at each load under double hashing converges to the same values as under independent choices as the table grows, and the same pattern holds for Bloom filters, where generating $k$ bit positions from two hash values gives the same false-positive rate in the limit as $k$ independent functions. The measurement here is that the limit is already reached, row for row, at a quarter of a million keys.

A smaller table #

On a small table the counts are small enough for sampling noise to show, and it shows in the way noise should: the generated scheme has fewer buckets at load two than the independent one for two choices, and more for three. A systematic effect of dependence would push both in the same direction. Differences that change sign between conditions are the signature of chance, and they are about the size — a few per cent of a few thousand — that the square root of the counts predicts.

When the maximum disagrees #

With a different set of keys the maxima for two choices differ — three for the independent scheme, four for the generated one — and a reader looking only at the maximum would conclude the generated choices were worse. The tail counts at load two differ by less than one per cent, in the same direction as on the first seed; a single bucket reaching four in one table and not the other is a fact about one bucket.

This is the practical content of expected is not average for this ladder. The maximum is the statistic the power of choices is usually stated in, and it is the worst statistic to test it with: an integer taking one of two adjacent values, determined by the single most unlucky bucket. The first seed and the second seed together are a small demonstration that the maximum can flip between schemes while every other number on the plate agrees.

The same thing happens with four choices on a smaller table, and there the flip goes the other way.

With four independent choices on sixty-five thousand keys, no bucket reached three — the smallest maximum a table with a mean of one can have short of a perfect assignment — and with four generated choices one bucket did. Read alone, that says the generated scheme is worse. Read with the tail beside it, the two tables have 9,212 and 9,264 buckets at two or more, a difference of 52 in counts whose sampling spread is about a hundred, and a single bucket reaching three is an event whose probability at this size is small for both schemes and not zero for either. The first seed had the maxima equal; the second had the generated scheme one bucket higher for two choices and level for three; the small and the million-key tables had them level; and this plate has the generated scheme one higher for four. Maxima that agree on some tables and differ by one on others, over tables whose tails agree to within their noise every time, are what a statistic measuring one bucket does.

The same observation says how a test of double hashing should be written if anyone were to rely on it. A test that compared maxima would fail on the second seed and pass on the first, and would therefore be testing the seed. A test that compared the tail counts at load two, with a tolerance of a few standard deviations of a count that size, passes on both — and would fail on a scheme with a real defect, such as an unconstrained step, where the tail at load two grows because a fraction of keys have fewer distinct choices than they appear to. The site’s check is written the second way, with the tolerance scaled to the square root of the count, which is what makes it a test of the scheme rather than of one table.

The dependence that does matter #

If generated choices behave like independent ones, it is fair to ask what the independence assumption was protecting against. The answer is visible in the one detail of the construction that was not justified above: the step is forced to be odd.

The table has a power-of-two number of buckets. If $h_2(x)$ happens to be even, the progression $h_1 + i \cdot h_2$ visits only buckets of one parity; if it is a multiple of four, only a quarter of the table; and if it is zero, every choice is the same bucket. A key whose “four choices” are one bucket four times has no choice at all, and a key whose choices are confined to a small subgroup of the table is choosing from a much smaller table than the analysis assumed. With the step unconstrained, one key in $n$ has a zero step and one in two has an even one.

Forcing the step to be odd makes every $g_i$ distinct and makes the progression visit the whole table before repeating, since an odd number is invertible modulo a power of two. That single constraint is what makes the generated choices behave independently for the purpose of balancing, while remaining completely dependent in the formal sense.

So the dependence the analysis must rule out is not correlation between choices in general — it is choices that coincide, or that collapse onto a small part of the table. A scheme can have enormous formal dependence between its choices and none of that kind, and then the balancing argument goes through: what the recurrence actually needs is that a key’s choices are distinct buckets spread over the table with no bias towards the busy ones, and an arithmetic progression with an odd step from a uniform start supplies that.

Independence has a degree is the theme this belongs to, and the independence an estimator spends is its most careful measurement on this site: a sketch whose guarantee is stated for fully independent hashing turns out to need only four-wise independence, and the degree it needs is a property of what the proof multiplies together. The power of choices, measured here, needs less than its proof assumes in the same way — and the thing it does need is not a degree of independence at all, but distinctness.

What the saving is worth #

The saving is two hash evaluations instead of $d$. For two choices it is nothing, for four it halves the hashing, and for the Bloom filters that use the same trick with seven or ten positions it removes most of the hashing entirely.

Whether that saving matters depends on what else a lookup costs, and on a real machine that is mostly memory. A table whose buckets are in cache spends most of a lookup hashing, and halving the hashing is close to halving the lookup. A table whose buckets are not in cache spends most of a lookup waiting for $d$ cache misses, one per choice, and computing those choices from two hashes instead of four changes nothing about the misses. Two probes are two misses measures that second regime for cuckoo tables, where every probe of an unrelated bucket is a separate miss — and it is the regime in which the number of choices, not the cost of computing them, is the price.

Counting the coin flips measured randomness as a resource separate from time, and this is the case where the two resources come apart cleanly. The independent scheme draws $d$ seeds for $d$ hash functions; the generated scheme draws two, whatever $d$ is. Both then spend no randomness per key. The measurement says the generated scheme’s distribution is indistinguishable from the independent one’s, so the extra seeds were buying nothing that shows in the load. What derandomising costs usually finds a price for removing randomness; here the randomness removed was surplus.

The same trade appears in the one place this ladder has already met many hash positions per key. A filter that is allowed to be wrong sets seven bits per key in a Bloom filter sized for one per cent, and seven independent hash evaluations per insertion and per lookup is the dominant cost of using the filter at all. The two-value construction was introduced for exactly that case, and it is the reason most practical filters compute two hashes regardless of how many positions they set. More hashes or wider buckets found cuckoo tables with three or four hash functions holding far more keys than with two, which is the other structure where generated choices are commonly used — and there the construction’s success depends on the choices forming a random hypergraph, a stronger requirement than balancing, which is not what this page measured.

What the measurement leaves out #

Random keys. The keys have no structure, which is the case every analysis assumes and the case where hash quality matters least. A hash is a family, not a function measured what a poor hash does to keys that are multiples of the table size: every key in one bucket. Double hashing inherits whatever $h_1$ and $h_2$ do on structured keys, and generating more choices from two bad hashes produces more bad choices, not better ones.

That makes double hashing’s requirement on its two functions stronger in one respect than independent hashing’s. With $d$ independent functions, a key set that is unlucky for one function is usually not unlucky for the others. With two functions generating $d$ choices, a key set unlucky for $h_1$ or $h_2$ is unlucky for every choice at once, since all of them are computed from those two values. The saving in evaluations is bought by concentrating the dependence on the quality of two functions.

An adversary. A caller who knows $h_1$ and $h_2$ can find keys whose progressions overlap heavily, and the structure of an arithmetic progression makes that search easier than it would be against independent functions. The adversary who knows the seed is the measurement that applies, and the result here is about keys nobody chose.

The symmetric scheme only. The generated choices were compared with independent ones under ties broken at random over the whole table. Combining double hashing with the split tables of the asymmetric scheme needs one choice per sub-table, which a single progression over the whole table does not give, and the combination is a different construction.

Where this ladder goes next: two hash values inside a filter #

The same construction is used far more often inside Bloom filters than inside balanced tables, and there it is known to be exact in the limit and has a known finite-size cost.

A Bloom filter with $k$ hash functions sets $k$ bits per key, and generating those $k$ positions as $h_1 + i\,h_2$ reduces its hashing from $k$ evaluations to two. The analysis shows the false-positive rate converges to the independent rate as the filter grows; at finite size the generated positions collide with each other slightly more often than independent ones, which raises the rate a little, and the step’s parity problem reappears in a sharper form, since a filter’s length is often a power of two. The next rung measures a filter’s false-positive rate under both constructions across sizes and numbers of hash functions — with the step forced odd and without — and finds where on that range the two-value filter is measurably worse, and by how much.