Two hash values and the keys they copy

Choices that are not independent measured a construction that makes many hash choices out of two hash values. Compute $h_1(x)$ and $h_2(x)$, take the choices to be $h_1$, $h_1 + h_2$, $h_1 + 2h_2$ and so on, and a table where each key goes to the emptiest of its choices balances exactly as well as one with independent hashes. On a million keys with four choices the two tails agreed to within a tenth of a per cent. The one dependence that mattered was choices that coincide, and forcing the step to be odd removed it.

That essay closed by pointing at the place the construction is used most, which is not a balanced table but a Bloom filter. A filter that sets seven bits per key normally evaluates seven hash functions per insertion and per lookup, and making the seven positions from two values saves five of them. The analysis says the false-positive rate converges to the independent rate as the filter grows. The essay predicted where the finite-size cost would come from — generated positions colliding with each other slightly more often than independent ones — and that the step’s parity problem would return in a sharper form.

This page measures the rate under four constructions across filter sizes and hash counts. The second half of that prediction holds. The first half names the wrong collisions.

Four ways to choose k bits #

A filter of $m$ bits sets $k$ positions for every key and answers yes to a query when all $k$ of the query’s positions are set. The four constructions differ only in how the positions are made.

• Independent. $k$ separately seeded hash functions, each reduced to $[0, m)$.
• Two values. Positions $h_1 + i \cdot h_2 \bmod m$ for $i = 0, 1, \dots, k-1$, with both values in $[0, m)$.
• Two values, odd step. The same, with the step $h_2$ forced odd. Every filter here has a power-of-two length, so an odd step makes the $k$ positions distinct and never lets the step be zero.
• Two values and a cubic term. Positions $h_1 + i \cdot h_2 + (i^3 - i)/6 \bmod m$. The added term is zero for the first two positions and grows after, bending the progression. It is a published variant proposed for exactly this construction, and it costs nothing to compute.

The hash functions are the site’s standard ones — multiplication and addition keeping the high bits of the product — seeded once per construction, and each filter is filled with fresh random keys, so a rate is an average over many filters built by the same functions.

One small filter #

A 64-bit filter holding six keys at six positions each is small enough that every effect is large. Independent hashes answer yes to 0.69% of absent keys, close to the textbook 0.63%. Two values answer yes to 2.2%, over three times as often. Forcing the step odd brings that to 1.6%, and adding the cubic term brings it to 0.83%.

The middle panel is the test of the predicted mechanism, and it fails the prediction. A key whose six positions include the same bit twice sets fewer bits, which makes the filter emptier, not fuller. Independent hashes repeat a bit in 22.5% of keys, two values in 6.7%, and the odd step in none at all, since an odd step on a power-of-two filter cannot revisit a position in fewer than $m$ steps. So the construction with no repeats is the one with more than twice the independent rate. Whatever is costing the two-value filter, it is not positions colliding within a key.

The bottom panel shows what it is. Of the independent filter’s false positives essentially none are covered by the six positions of a single stored key; each is assembled from bits that several different keys happened to set. Of the odd-step filter’s false positives, 37.3% are covered entirely by one stored key. The query did not find six set bits by chance. It found a stored key whose six bits are its own six bits.

A query that copies a stored key #

The mechanism has a count, and the count is short.

With two values, a key’s positions are fixed by one pair of numbers, its start $h_1$ and its step $h_2$. A query’s positions are the same set as a stored key’s in exactly two ways: when its pair is the stored key’s pair, and when its pair is the stored key’s progression read backwards — starting at the last position and stepping by $-h_2$. With the step odd, there are $m$ starts and $m/2$ steps, so a random query copies a particular stored key with probability $2/(m \cdot m/2) = 4/m^2$, and one of $n$ stored keys with probability about

$$\frac{4n}{m^2}.$$

For the 64-bit filter that is $4 \times 6 / 4{,}096 = 0.59\%$ of all queries. The plate measures 1.6% answered yes, of which 37.3% — 0.59% of all queries — are covered by one stored key. Every one of those queries is answered yes, because every bit a stored key sets is set.

The other two constructions fit the same account. With the step unforced there are $m$ steps instead of $m/2$, which halves the copies, but the steps now include zero and $m/2$: one query in 64 has a zero step and sets a single position, and is answered yes whenever that one bit is set, which in this filter is nearly half the time. That is why two values are worse than the odd step and why their share of single-key coverage is higher. The arithmetic closes: whole copies of a stored key, now $2n/m^2$, are 0.29% of queries; a zero step, one query in 64, is answered yes about 43% of the time on a filter this full, another 0.67%; together about 1.0%, where the plate measures 1.03% covered by one key. With the cubic term, reading the progression backwards no longer produces the same set, so only the exact pair copies a key, and the count is $n/m^2$: 0.15% on this filter, against a measured 0.146%.

The count holds across sizes. With seven positions per key and the filter holding its optimal load of $m \ln 2 / 7$ keys, the odd step’s single-key coverage measures 0.59%, 0.33%, 0.16%, 0.074% and 0.040% at 64, 128, 256, 512 and 1,024 bits, against $4n/m^2$ of 0.59%, 0.32%, 0.15%, 0.078% and 0.039%. The cubic term tracks $n/m^2$ at every size. At 4,096 bits the counts are small enough that sampling shows, and both are still within three tenths of the formula.

At the optimal load $n$ is proportional to $m$, so the copies fall as $1/m$ while the independent rate stays where the load put it. That is the finite-size effect the analysis promises will vanish, measured as a mechanism rather than inferred from a limit.

The penalty against size #

A whole copy is not the only copy. A query whose start is a stored key’s second position and whose step is the same shares all but one of that key’s positions, and is answered yes if its one remaining bit happens to be set, which at the optimal load is about half the time. Shifted by two steps, it shares all but two, and needs two more set bits. With the odd step, each shift can happen in four ways — forwards or backwards along the progression, read in either direction — so a stored key adds about $4/m^2$ for its whole copy and $8/m^2 \times (\tfrac12 + \tfrac14 + \cdots)$ for its shifted copies. That is about $12/m^2$ per stored key, and the excess over the independent rate should be about $12n/m^2$. With the cubic term, a shift changes every later position, and only the whole copy survives: about $n/m^2$.

Those are the dashed lines. The odd step measures 1.23 times the independent rate at 512 bits against an account of 1.29, 1.10 at 1,024 against 1.15, and 1.05 at 4,096 against 1.04. At 128 and 256 bits the account overstates the excess by about a fifth — it predicts 2.0 and 1.6 where the filter measures 1.74 and 1.34 — because on a filter that small the extra positions of a shifted copy are not independent of each other the way the account assumes. From 512 bits up the count of copies is the penalty.

So the penalty is a small-filter effect, as the analysis says. At seven positions per key it is a fifth at 512 bits, a tenth at 1,024, and within the noise at 4,096. The cubic term removes nearly all of it at every size.

More positions make it worse #

The account says something the size plate cannot show. The excess is $12n/m^2$, and at the optimal load $n = m \ln 2 / k$, so the excess is about $8.3/(k\,m)$ — falling only slowly as the number of positions grows. The independent rate at the optimal load is $2^{-k}$, halving with every position added. Their ratio is therefore about $8.3 \cdot 2^k / (k\,m)$, and it doubles, less a little, with every extra position.

On 1,024 bits the odd step costs 1.01 times the independent rate at five positions, 1.13 at seven, 1.41 at nine, 2.20 at eleven and 5.35 at thirteen, where the account predicts 5.5. Two values unforced cost 9.69 times. On 4,096 bits the plate above shows the same curve four times later: 1.02 at seven positions, 1.34 at eleven, 2.36 at thirteen.

Thirteen positions is what a filter sized for about one false positive in ten thousand uses. So the construction’s cost is worst exactly where a designer has asked for the lowest rate, and a filter that was safe with two hash values at one per cent is not safe at 0.01% on the same number of bits. The account gives the size at which the excess falls to a tenth: $m \approx 83 \cdot 2^k / k$ bits, about 1,500 bits at seven positions and 52,000 at thirteen. The cubic term, on the same plates, never costs more than 1.20 times at 1,024 bits or 1.16 at 4,096.

Where filters are small #

A filter of a few thousand bits sounds like a toy, and many real filters are exactly that size. The filter each run carries measured a store in which every sorted run has its own Bloom filter, and designs that keep a filter per block of a run make each filter as small as the block’s keys. A filter per block of a hundred keys at ten bits a key is a thousand bits with seven positions — the size at which this page measures a tenth of excess with the odd step, and more with an unforced one.

Whether saving five hash evaluations is worth that depends on what else a lookup costs. Counting the coin flips is the site’s account of randomness as its own resource, and here the saving is plain: two evaluations instead of $k$. Two probes are two misses is the reminder that on a filter too large for the cache the lookup’s cost is its memory reads, one per position, which no choice of hashing reduces. The two-value construction buys most in exactly the filters small enough to be cached, and those are the filters where its penalty is largest.

Why the balanced table did not notice #

The same construction, with the same odd step, balanced a table as well as independent hashes did, and the count of copies says why the two structures disagree about it.

In a balanced table, a key that copies another key’s set of choices is not answered anything. It is placed in the emptier of its choices, which are the other key’s choices, and at worst the two keys end up in the same bucket. Among a quarter of a million keys in as many buckets, with each pair of keys copying each other with probability about $4/n^2$, the expected number of pairs that copy each other is about $\binom{n}{2} \cdot 4/n^2$, which is two. Two pairs of keys with identical choices can raise two buckets by one key each, in a tail that counts sixty thousand buckets at a load of two. The effect exists and is invisible.

In a filter, a copy is an answer. Every absent key that reproduces any one of the $n$ stored progressions is reported present, whatever else the filter holds, so the relevant probability is not the chance that two stored keys copy each other but the chance that each query copies any stored key — $4n/m^2$, with $n$ in the numerator — and it is paid on every lookup for the life of the filter. A balanced table counts copies among its keys, once. A filter counts copies between its keys and everything it is asked about.

That difference is the whole reason the construction’s analysis is stated separately for the two structures, and why the balanced table’s clean result could not simply be carried across.

What independence was protecting against #

Choices that are not independent found that the dependence a balanced table cares about is a key’s own choices coinciding, and that an odd step removed it. A Bloom filter cares about something a balanced table does not: whether two different keys’ choices coincide as a set. A balanced table places each key once and forgets its choices; a filter keeps the union of every stored key’s positions and asks whether a query’s positions are all inside it. A query that reproduces a stored key’s set is inside it for certain.

Independent hashes make that event about as likely as matching $k$ random positions, which is negligible. Two values make it as likely as matching two numbers, which is $1/m^2$ for each of a handful of ways. That is the whole difference, and it is why the degree of independence that matters is a property of what the structure asks. The independence an estimator spends measured a sketch that needs only four-wise independence because its proof multiplies four hashes; this filter needs something no small degree of independence names, which is that two keys’ $k$ positions should not be determined by the same two numbers in the same way.

What the measurement leaves out #

Hash quality. Every construction here starts from good hash values. A hash is a family, not a function measured what a poor hash does to structured keys, and a construction that derives every position from two values concentrates any weakness in those two.

An adversary. A caller who knows the two functions can choose keys whose progressions copy each other, and the count of copies becomes whatever the caller wants. The adversary who knows the seed is the measurement that applies.

Lengths that are not powers of two. On other lengths an odd step is not enough to make the positions distinct; the step must share no factor with the length, and the counts of copies change accordingly.

Time. No plate charges a hash evaluation or a memory read, so the saving the construction exists for is described and not measured.

Still open: positions confined to a block #

The penalty on this page belongs to small filters, and there is a common design that makes every filter small from a key’s point of view. A blocked Bloom filter uses its first hash to choose one block of, say, 512 bits — one cache line’s worth, in the spirit of the bucket that fits a line — and sets all $k$ positions inside that block, so a lookup reads one line. If the positions within the block are made from two values, every key’s copies are counted against a 512-bit block rather than the whole filter, and the penalty this page measured at 512 bits applies to a filter of any size.

The measurement that follows builds blocked filters with independent and two-value positions inside each block, at the same bits per key as the plates here, and asks how much of the rate the block costs on its own, how much the two values add on top, and whether the cubic term recovers the difference inside a block as it does across a whole filter.