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.