Bloom Filter Cheat Sheet: Formulas & Tuning
A one-page Bloom filter reference: the m, k, and false-positive-rate formulas, when to use one (LSM reads, dedup, cache admission), and when to avoid it.
Never lies about absence; only exaggerates presence.
“Not present” is certain; “present” is probable. That asymmetry is why it guards expensive lookups.
What it is
- An
m-bit array +kindependent hash functions. Stores no keys. add(x): set the k bits x hashes to.contains(x): “no” if any bit is 0, else “probably”.- No delete in the standard form — bits are shared. Use a counting Bloom filter to delete.
The math
| Quantity | Formula |
|---|---|
| False-positive rate | (1 − e^(−kn/m))^k |
| Optimal hash count | k = (m/n)·ln 2 |
| FP rate at optimal k | (0.5)^k |
| Bits/item (m/n) | Optimal k | ≈ FP rate |
|---|---|---|
| 8 | 6 | ~2% |
| 10 | 7 | ~1% |
| 16 | 11 | ~0.05% |
Where it lives / when not to
- Use: skip disk reads in LSM-tree stores (RocksDB, Cassandra), dedup, cache/CDN admission.
- Avoid: when you need deletes, exact answers, or to enumerate the set — it can’t do any of those.
- Watch saturation: FP rate climbs as it fills past its design n. Rebuild or partition.
Variants (one line each)
- Counting: counters not bits → supports delete (more space).
- Scalable: chain of filters that grows to hold a target FP rate as n rises.
- Cuckoo filter: alternative supporting delete with better locality at low FP rates.