Randomness — the series
-
A structure made of coin flips
Insert the same 512 keys into a skip list twice, once sorted and once shuffled, from the same seed, and the two structures are identical — the same 11 levels, the same height for every key, the same silhouette. Nothing about the data reached the layout. The 1,064 coin flips did all of it.
-
The height is a distribution, and the coin is a parameter
A skip list over 2,048 keys is described as being about log₂ n levels tall. Across two hundred builds of exactly those keys its height ranged from 9 to 19. The number in the description is the mean of something, and choosing the coin is choosing which something.
-
One pass, k slots, and two randomness budgets
Reservoir sampling takes a uniform sample of k items from a stream of unknown length in one pass and k slots. The textbook version and a second version draw from exactly the same distribution, and at 65,536 items one of them spends 1,356,399 random bits and the other spends 9,380.
-
A filter that is allowed to be wrong
A Bloom filter holding four thousand keys in five thousand bytes answers membership in four memory probes and gets 1.14% of its negative answers wrong. It never gets a positive one wrong. That asymmetry is the whole design, and the rate it makes errors at is a third quantity beside the operation count and the space.
-
A hash is a family, not a function
Two thousand and forty-eight keys into two hundred and fifty-six buckets. Under a hash that takes the low bits of the key, all 2,048 land in bucket zero and 255 buckets are empty. Under a multiplier drawn at random, the worst bucket holds 11. The keys are the same keys, and they are the multiples of the table size.
-
The formula everybody sizes filters with
Fill a Bloom filter with four thousand random keys and its measured false-positive rate is within 4% of the textbook formula. Fill the same filter with the integers 1 to 4,000 and the rate is 30% worse than the formula says — not because the hash is bad, but because it is too good on that input.
-
The second choice
Two hundred and sixty thousand keys into as many buckets. Under one hash the busiest bucket holds eight; under two, with each key going to whichever of its two is emptier, it holds four. The mean is exactly one in both. Nothing is rearranged afterwards, no key is ever moved, and the whole of the improvement is in a decision taken once, at the moment the key arrives.
-
An insertion that can fail
Every randomised structure in this field buys an expected cost and accepts a tail. Cuckoo hashing buys a worst case — a lookup examines exactly two slots, for any keys, always — and pays for it in the construction, which can fail outright. On a table of four thousand slots the construction never fails below 0.45 keys per slot and fails nineteen times in twenty above 0.55.
-
The evidence a filter cannot remove
A Bloom filter never says no about a key it holds, and that is its whole guarantee. Clear the bits of a thousand deleted keys and it starts saying no about 638 of the thousand it still holds. A counter in every cell repairs it at four times the space; a fingerprint repairs it at twice, and acquires a condition on the caller that neither of the others has.
-
More hashes or wider buckets
A cuckoo table with two hash functions and one slot per bucket cannot be built past about half full. Give it a third hash function and it builds to 0.92. Keep two hashes and give each bucket two slots and it builds to 0.89; four slots, past 0.95. Every shape keeps the worst-case lookup the plain table was built for, and every shape pays for its threshold in a different place.
-
The tie that breaks left
Two choices per key, the emptier bucket wins, and when the two are equally full a coin decides. Replace the coin with a rule — split the table into halves and always send a tie to the left one — and on a million keys the buckets holding three or more fall from 9,316 to 4,694, and the busiest bucket drops from four to three. The hashing, the probes and the keys are unchanged, and the rule spends no randomness at all.
-
The intersection two filters cannot report
Two Bloom filters over sets that share five hundred keys, ANDed bit by bit. The result never denies a shared key, and it looks like a filter of the intersection. It is not one — a key in only one of the sets passes it 1.8% of the time where a real filter of the intersection passes none, and reading the intersection's size off its bits gives 900.
-
Choices that are not independent
The power of two choices is analysed for choices drawn independently, and computing four independent hashes per key costs four hash evaluations. Compute two and take the choices to be h₁, h₁ + h₂, h₁ + 2h₂ and h₁ + 3h₂, and the choices are about as far from independent as they could be. On a million keys the buckets holding two or more come to 147,536 against 147,367 for four independent hashes, and the busiest bucket holds three either way.
-
A filter past its design size
A Bloom filter sized for two thousand keys at one per cent answers yes to 15.6% of absent keys at four thousand and 68.1% at eight thousand. Nothing fails and nothing warns. A stack of filters that adds a tighter layer whenever the top one fills holds 2.0% at eight thousand, under a bound it can state in advance — in 2.9 times the bits of one filter sized for eight thousand from the start.
-
Two hash values and the keys they copy
A Bloom filter that makes its k bit positions from two hash values, as h₁ + i·h₂, answers yes to 1.6% of absent keys on a 64-bit filter where k independent hashes answer 0.69%. The penalty is not the one expected. With the step forced odd no key ever repeats a bit, while a quarter of independent keys do. What costs the filter is a query whose start and step reproduce a stored key's whole progression, which happens with probability 4n/m², measured to within a few per cent from 64 bits to 4,096. The penalty fades as the filter grows and returns as the hash count rises — 1.13 times at seven positions on 1,024 bits, 5.35 times at thirteen.
-
A filter that grows by moving a bit
A table of fingerprints can double in place, moving one stored bit of every fingerprint into its slot number, and so grow as one structure with one lookup where a stack of Bloom filters adds layers. Its false-positive rate is fixed by the fingerprint's length and not by the table, so with nothing reserved it doubles as the keys double — 0.69% at a forecast of 2,000, 5.7% at eight times that. Reserve three bits at the start and it holds 0.66% at eight times, in 294,912 bits, exactly what a table built for sixteen thousand keys would hold and fewer than the stack's 428,938. The reserve is a forecast of growth, and past it the rate climbs again.
-
Positions confined to one line
A Bloom filter lookup reads 5.55 cache lines because its six positions are scattered across the whole filter. Confining them to a 512-bit block makes it exactly one, and costs 7% more false positives at eight bits a key. At sixteen bits a key the same block costs 91%, and the two-value trick that is free across a whole filter costs another 135% inside one — because a block is a small filter, and small filters are where the penalty lives.
-
The bits given to the wrong keys
A fingerprint table that gives later arrivals longer fingerprints holds 3.6% where a table that reserves nothing holds 21.1%, and it never runs out of reserve because it has none. It also dies at exactly the same size as the table that reserved nothing — 32 times its forecast, on the same key — because every generation shares one quotient, and the generation with the shortest fingerprint is the one that arrived first.
-
Two blocks and the chances they add
Send each key to the emptier of two 512-bit blocks and the busiest block of a filter at sixteen bits a key holds 38 keys instead of 55. The false-positive rate does not move: 0.100% against 0.095%. At eight bits a key it doubles. A lookup cannot tell which block a key went to, so it has to ask both, and asking twice is two chances to be wrong. The repair that tames a hash table's worst bucket buys a filter nothing that a block twice as wide does not.