When the algorithm flips a coin
A structure made of coin flips
What a skip list is, why its shape is decided before a single key is compared, and what changes when the structure of a data structure stops being a function of the data.
The height is a distribution, and the coin is a parameter
Why a skip list's height is a random variable rather than a bound, what changes when the promotion probability moves from a half to a quarter, and the three-way trade between comparisons, pointers and random bits that the choice of coin decides.
One pass, k slots, and two randomness budgets
How a uniform sample is drawn from a stream nobody has counted, what an off-by-one does to it that no correctness test would catch, and why two algorithms with identical output can differ by a factor of 145 in a resource nothing else measures.
A filter that is allowed to be wrong
What a Bloom filter is, why its false-positive rate is a measurable quantity with a closed form, and what changes when a data structure is permitted to be wrong in one direction only.
A hash is a family, not a function
Why a hash function chosen once at compile time has an input that destroys it, what universality actually guarantees, and how a family turns a claim about the data into a claim about the algorithm.
The second choice
The power of two choices, measured — how the maximum load stops growing while the mean does not move, and what the second probe costs on every lookup thereafter.
An insertion that can fail
Cuckoo hashing measured — the displacement chain, the load at which it stops terminating, and how the threshold sharpens as the table grows.
A match decided by a number
The rolling hash, why its cost has a closed form, why the closed form is an expectation rather than a guarantee, and the arithmetic that decides whether an adversary can build a collision at all.
The evidence a filter cannot remove
What deletion costs three approximate-membership structures, measured — the false negatives a cleared Bloom filter produces, the space the repairs cost, and the precondition one of them adds.
The estimate that is a median of means
Why averaging buys accuracy and only a median buys confidence, what the two purchases cost separately, and how a failure rate is measured rather than quoted.
The independence an estimator spends
k-wise independence as a measured resource — enumerated exactly over GF(13), sampled where it cannot be, and the estimator whose error stops falling when the family is too weak.
The intersection two filters cannot report
The bitwise AND of two Bloom filters against a filter built directly on the intersection. The AND keeps every shared key, but its false positives for keys in one set only are set by the other filter's load rather than the intersection's size, and a size read off its bits overstates the intersection badly while inclusion–exclusion over the union does not.
More hashes or wider buckets
The cuckoo construction's failure rate against load for several shapes — two, three and four hash functions, and buckets of one, two and four slots. Each shape has a threshold rather than a slope, the measured thresholds sit on the published ones, and the shapes differ in what a lookup reads rather than in how many keys they hold.
The tie that breaks left
The power of two choices with random tie-breaking against the asymmetric version — the table split into groups, one choice in each, ties sent to the leftmost group. Deterministic, unfair tie-breaking thins the tail by half and lowers the maximum, and the effect grows with the number of choices.
A filter past its design size
One Bloom filter filled past the number of keys it was sized for, and a scalable stack of tightening filters that is not. The single filter degrades smoothly and without limit, exactly as its formula says; the stack keeps a stated bound on its rate however far it grows, and pays for the guarantee in bits.
Choices that are not independent
Balanced allocation with d choices generated by double hashing from two hash values, against d independent hashes, on the same keys. The tails agree to within what two independent runs disagree by, for two, three and four choices — the dependence that matters is choices coinciding, and an odd step removes it.
A filter that grows by moving a bit
A quotient-style fingerprint table that doubles in place, with 0 to 5 bits of its fingerprints reserved for growth, against a single Bloom filter and a stack of tightening Bloom filters, given the same keys up to 32 times a forecast. Reserving log₂ of the growth holds the target rate and costs at the end exactly what a correctly sized table costs; the stack holds its bound at any growth and pays for it in bits that grow faster than the keys.
Two hash values and the keys they copy
Bloom filters of 64 to 4,096 bits with k from 3 to 13, their positions made by independent hashes, by h₁ + i·h₂, with the step forced odd, and with a cubic term added. The excess false positives come from queries that copy a stored key's progression, whole or shifted, and a count of those copies predicts them; a cubic term removes most of the copies and nearly all of the penalty.
The bits given to the wrong keys
Lengthening fingerprints as a resizable filter grows, measured against reserving bits in advance and against a stack of tightening Bloom filters, in rate, in bits and in how far each design can be grown before it cannot store a key at all.
Positions confined to one line
Blocked Bloom filters measured against whole-filter ones — the rate a block costs on its own at each block size and each density, the cache lines a lookup reads either way, and whether the two-hash-value construction and its cubic repair behave inside a block as they do across a filter.
Two blocks and the chances they add
A blocked Bloom filter whose keys choose the emptier of two blocks, measured against one block, one block twice as wide and the whole filter at 8 to 24 bits a key: the spread of keys a block, the false-positive rate, the cache lines an absent and a stored key's lookup reads, and every design at 20 bits a key set against the lines it costs.
A block the lookup can work out
A blocked Bloom filter whose first block carries a threshold on an ordering hash, so a lookup reads one threshold and one block rather than two blocks: the false-positive rate against one-choice and two-choice designs from 8 to 24 bits a key, the load spread each achieves, how wide the threshold has to be, and where the capacity that fills it should sit.
The day a filter cannot grow
A fingerprint table forecast for 2,000 keys at 1% and grown to 2,000,000, measured four ways: rebuilt from the store on its own rate, rebuilt only when it can no longer double, a single table with ten bits reserved for the whole growth, and a stack of tightening Bloom filters. The rate each holds, the bits each spends as the growth proceeds, the keys the rebuilds read back, what the reserve's extra bits are worth per key read if the growth stops early, and the ledger at two million keys.
A penalty set by the block
Blocked Bloom filters at sixteen bits a key — one block, the emptier of two, and one chosen by a threshold — measured over a 64-fold range of filter sizes and a 16-fold range of block widths, with the one-block rate computed exactly as Bloom's formula averaged over a Poisson load: why the size does not matter, how the busiest block grows without moving the rate, what the width does, and the line count at which a threshold and a wider block give the same rate.
The bits a second threshold costs
Blocked Bloom filters of 8,192 keys at sixteen bits a key, at block widths from 256 to 2,048 bits: one block a key, a threshold on the first block, thresholds on both of a key's blocks with a third block for keys both refuse, and one block four times as wide — false-positive rates on two million absent keys a point, the spread of block loads, the rate split into what the tables cost in load and what the spread costs, the rate against the bits a threshold is stored in, and the loads themselves.
A threshold knows only its own block
Blocked Bloom filters of 8,192 keys at 16 bits a key with one four-bit threshold shared by each group of 1 to 16 adjacent blocks, the table paid for in blocks, at 256- and 512-bit widths: the false-positive rate against group size beside one block and one block twice as wide, the rate split into its no-spread floor and the spread, where each block's own threshold closes, the share of keys placed in their first block, and two ways to close a shared threshold.
Two hashes that shared their low bits
The one-threshold blocked Bloom filter at 16 bits a key built twice from the same keys, seeds and queries — its block and ordering hashes reduced by a modulo, as the published filters were, and by their top bits: which combinations of ordering value and block the keys reach, the rate over eight seeds at four block widths, the rate against the block count, the threshold's width re-measured over four seeds, and the emptier-of-two filter, which the same dependence leaves untouched.
A code that has to fit its worst line
The one-threshold blocked Bloom filter at 16 bits a key, hashes read from their top bits, about two thousand blocks at widths of 64 to 512 bits, with its threshold table stored four bits each, three bits each, as a Huffman code from the filter's own closing distribution packed end to end with an index, and packed a fixed count to a cache line with and without in-line offsets, every table paid for in blocks: where thresholds close and each value's code word, the bits a block each layout takes, what a lookup reads and decodes, the false-positive rate over four seeds, and the table's share of the filter.
A bit for whether it closed
The one-threshold blocked Bloom filter at 16 bits a key, hashes read from their top bits, about two thousand blocks at widths of 64 to 512 bits, with its threshold table stored as a bit vector of which blocks closed plus a value for each closed block, found by rank — packed a line at a time and end to end — beside plain four- and three-bit tables and a line-packed Huffman code, four seeds a point: bits a block, the line-packed split against its mean, lines read and work done a lookup, false-positive rates by seed, and the saving against block width.