Every sketch trades a little accuracy for a lot of memory, and every lesson pins the trade with exact values: the precise bits an Add sets, the k double-hash indices for a known input, the optimal m and k for a target false-positive rate, a deliberately constructed false positive, an add-then-delete that restores the counters, the minimum across Count-Min rows beating a colliding single row, and a HyperLogLog register holding the maximum leading-zero count. The hash functions are specified exactly - FNV-1a plus a splitmix64 mix - so every index, counter, and register is deterministic and checkable in any language.
Over 28 lessons you build a small library of probabilistic data structures: the space-efficient sketches that trade exact answers for tiny, fixed memory. You start with the two primitives everything rests on - a deterministic pair of hash functions (a specified FNV-1a and a splitmix64 mix) and a bit array - then build four sketches on top of them, each answering a different question about a stream of items.
The Bloom filter answers "have I possibly seen this?" with no false negatives and a tunable false-positive rate; you derive its sizing math and construct an actual false positive. A counting Bloom filter adds delete by replacing bits with small saturating counters. A Count-Min sketch estimates how often each item appeared, using the minimum across independent rows to stay an over-estimate that never reads low. A HyperLogLog estimates how many distinct items a stream held from a handful of registers, using leading-zero counts and a harmonic mean. The project ends by running one deterministic stream through all three at once and asserting the exact bit, counter, and register states.
Because the hash functions are pinned exactly rather than borrowed from the language runtime, every index, counter, and register in every lesson is reproducible in any language. This is a teaching-grade library built around the classic papers (Bloom 1970, Cormode and Muthukrishnan, Flajolet and colleagues): it uses a single deterministic hash pair rather than a full independent hash family, small register and counter widths chosen for hand-checkable examples, and no serialization, merging, or concurrency - which is exactly the honest core that production libraries like RedisBloom and the sketches in data-warehouse engines extend.
A Bloom filter is, underneath, a big array of single bits with hashing bolted on top. Today you build that array - create it with a fixed number of bits, set an individual bit, and read whether a bit is set.
Create a bit array of a fixed number of bits, set one bit, and read whether a given bit is set.
Every sketch in this project rests on the same humble structure: a fixed array of bits, each one either set or clear. A Bloom filter is exactly this array plus a rule for which bits an item touches. Storing one bit per slot instead of a whole key is where all the space savings come from, so getting the array right - create it at a chosen size, flip one bit, read one bit - is the whole foundation.
The only wrinkle is packing: most languages have no single-bit type, so we store the bits inside machine words and address bit i as position i % 64 inside word i / 64. That detail stays hidden behind Set and Get; the rest of the project only ever asks “is bit i set?” Keep this deliberately small today - the array does nothing clever yet.
// pack the bits into words; bit i lives in word i/64 at position i%64type Bits struct{ words []uint64 }func NewBits(m int) *Bits { return &Bits{words: make([]uint64, (m+63)/64)} }func (b *Bits) Set(i int) { b.words[i/64] |= 1 << (uint(i) % 64) }func (b *Bits) Get(i int) bool { return b.words[i/64]>>(uint(i)%64)&1 == 1 }
A genuinely working library of four probabilistic sketches - a Bloom filter with tunable false positives and no false negatives, a counting Bloom filter with delete and saturating counters, a Count-Min sketch for frequency, and a HyperLogLog for distinct counting, each with its sizing helpers, a runnable demo, and graceful handling of degenerate parameters - but it uses a single deterministic double-hashed hash pair rather than a fully independent hash family, small fixed counter and register widths chosen for hand-checkable examples, and has no serialization, merging, or concurrency safety.
The original 1970 paper that introduced the Bloom filter - a bit array plus several hash functions, trading a small false-positive rate for a large space saving. Short, readable, and the source of the sizing math this project derives.
Shows that the k hash functions a Bloom filter needs can be generated from just two base hashes by double hashing, with no loss of accuracy - the exact trick used here to turn one FNV-1a and one splitmix64 mix into k indices.
A wide survey of Bloom filter variants and uses, including the counting Bloom filter that adds delete. Good context for where these structures show up in real systems.
The Count-Min sketch paper: a two-dimensional counter grid with one hash per row, answering frequency queries by taking the minimum across rows. The width-and-depth sizing and the error bound in the Count-Min chapter come straight from here.
The HyperLogLog paper - estimating the number of distinct items from the maximum leading-zero count per register, combined with a harmonic mean and a bias correction. The alpha constants and the small-range correction used here are defined in this paper.
A single accessible overview of the whole family - membership, frequency, and cardinality sketches - with worked math and clear diagrams. The best one-book companion to this project.