Bloom filters

Approximate set membership in a few bits per item. False positives, but NEVER false negatives.

Bit array + k hashes

• Add: hash k ways, set those k bits to 1 (bits only turn ON)
• Query: all k bits set → "probably present"; any 0 → "definitely absent"
• A 0 bit PROVES absence → no false negatives, ever
• Stores no items, only their bit shadow → size independent of item size

Watch add & query

Add cat/dog/fox → bits light up. Query cat → all set → yes. 'hycr' never added, but its 3 bits are all set → FALSE POSITIVE.

A hundredfold less memory

1M keys at 1% FPR: Bloom 1.2 MB, set 122 MB → 100× smaller (9.6 bits/item, k=7).

The design formula

• FPR ≈ (1 − e^(−kn/m))^k
• Optimal k = (m/n)·ln2 → the array ends up ~half full
• Bits per item ≈ 1.44·log₂(1/p) — depends ONLY on error rate, not item size
• Can't delete, can't enumerate, can't overfill

Takeaway

Exactness is a resource you can spend — trade a little error for lots of space. The founding idea of probabilistic structures (HyperLogLog, count-min sketch). Next: skip lists — balanced-tree performance from coin flips.