We should be more ambitious with the software we build
Data structure of the day · data structures
Bloom Filters
A few kilobytes that tell you, with no false negatives, what is definitely absent.
The mechanism. A bit array of size m and k independent hash functions. To insert, hash the element k times and set those bits. To query, hash and check: if any bit is 0 the element is definitely absent; if all are 1 it is probably present. No false negatives, tunable false positives, no deletions, and no way to enumerate what is in it.
The numbers worth memorising. About 10 bits per element gives a 1% false positive rate; 14 bits gives 0.1%. That is independent of element size — a million 200-byte URLs fit in roughly 1.2MB at 1%, versus ~200MB for a hash set. The optimal k is (m/n) * ln2, around 7 for the 1% case.
Where it earns its place. Every SSTable in an LSM tree carries one, so a point lookup skips files that cannot contain the key — that is what makes LSM reads tolerable. CDNs use them to decide whether an object is worth caching on first request. Chrome shipped one for malicious URLs. Bitcoin used them for light-client filtering.
Know the variants. Counting Bloom filters support deletion at 3–4x the space. Cuckoo filters support deletion and beat Bloom on space below ~3% error. Quotient filters are more cache-friendly. If you need counts rather than membership, you want Count-Min Sketch; if you need cardinality, HyperLogLog.
Takeaway. When a "probably" is cheap and a "definitely not" is valuable, this is the structure. Always ask what a false positive costs you before you reach for it.
Practice
Size a Bloom filter for 5 million cache keys at a 1% false positive rate, then say what a false positive costs in a read-through cache and in a password-breach checker.
Hint
About 10 bits per element, k = (m/n) * ln2. The cost asymmetry is the whole design question: one wastes a lookup, the other rejects a valid password.