Archivehashing
Bloom Filters and the Cost of False Positives
A bloom filter never lies about absence, but its false-positive rate is a tunable bill you pay in bits and hashes.
- Published
- Reading time
- 1 min read
A bloom filter answers "definitely not present" or "maybe present". With m bits and k hash functions for n items, the false-positive rate is approximately:
p ≈ (1 - e^(-kn/m))^k
The optimal number of hash functions is k = (m/n) ln 2, which for 10 bits per item is about 7 hashes and gives roughly a 1% false-positive rate.
Where it fits
- Avoid a disk or network lookup for keys that certainly do not exist (SSTable reads in LSM engines).
- Reduce cache misses for hot negative lookups.
- Pre-filter in anti-entropy and blocklist sync.
Where it does not
- You cannot delete items without a counting variant, and counting filters cost several bits per counter.
- You cannot enumerate members.
- A false positive near 0 requires a lot of bits: going from 1% to 0.1% roughly doubles memory.
Takeaway: bloom filters buy negative lookups with memory and a bounded lie rate. If you need deletes or iteration, pick a different structure (cuckoo or quotient filter) instead of rebuilding the filter every hour.