Start here: the problem it solves#
TL;DRthe 30-second version
- A Bloom filter is a bit array plus k hash functions. To add a key, set the k bits it hashes to. To query a key, check those k bits: any 0 means definitely absent, all 1s means probably present.
- It can be wrong in one direction only. A false positive (says 'probably present' for a key never added) is possible. A false negative (says 'absent' for a key that was added) is impossible, because bits are only ever set, never cleared.
- About 10 bits per key buys a ~1% false-positive rate. A hash set needs hundreds of bits per key. In return, the filter can't list its contents, count, or delete.
- The sizing rule: optimal k = (m/n) × ln 2, which sets about half the bits. Each extra bit per key multiplies the false-positive rate by ~0.6.
Imagine a web crawler that has visited 100 million URLs. Every time it finds a new link, it asks: have I already crawled this? A hash set of all 100 million URLs would take roughly 8 to 10 GB of RAM. And the crawler does this check billions of times.
This is the general shape. A cheap membership test guards an expensive operation: a disk seek, a round trip to a database, a re-download. Most of the time the answer is 'no, not present'. If you could answer the 'no' cases in memory, you'd skip the expensive lookup almost every time.
The key observation is that the crawler doesn't need a perfect answer. It can tolerate revisiting a page it already crawled. That's a false positive: the filter wrongly said 'maybe seen'. It cannot tolerate missing a new page because the filter wrongly said 'already seen'. That's a false negative. One direction of error is fine; the other is not. A Bloom filter gives you exactly that asymmetry.
How it works: set k bits, check k bits#
A Bloom filter is a large array of bits, all starting at 0. Alongside it you have k hash functions. A hash function takes any input, like a URL, and always returns the same position in the array. Each of the k functions uses different math, so one input maps to k different positions. The hashes only need to be fast and spread inputs evenly; they don't need to be cryptographic. k is small, typically 3 to 10.
To add a key, run it through all k hash functions and set those k bits to 1. We'll use a 12-bit array so every step is visible.
highlighted = the 3 bits alice set
- ADD 'alice.com' with k=3: the hash functions return positions [2, 5, 9]
- Set bit 2, bit 5, and bit 9 to 1 (the highlighted bits above)
- ADD 'bob.com': the hash functions return positions [7, 2, 10]
- Set bit 7 to 1 (new). Bit 2 is already 1, so no change. Set bit 10 to 1 (new)
Bit 2 was already set by alice.com, and bob.com maps to it too. Two keys sharing a bit is a collision. Collisions are harmless during adds. They matter during queries, where they are the source of false positives.
To query a key, run it through the same k hash functions and look at those positions.
- If any of the k bits is 0, the key was definitely never added. Adding it would have set all k bits. This answer is always correct.
- If all k bits are 1, the key was possibly added. Those bits might have been set by other keys. This is a 'maybe'. It could be a genuine match or a false positive.
| QUERY | Bits checked | Verdict |
|---|---|---|
| carol | 2 = 1 ✓, 4 = 0 ✗ | Definitely not present. One 0 ends it; skip the disk read |
| mallory | 2 = 1 ✓, 5 = 1 ✓, 9 = 1 ✓ | Probably present, but it could be a false positive |
The no-false-negatives guarantee follows from one rule: bits are set, never cleared. If you added a key, its k bits are 1 and stay 1, so a later query for it always sees all 1s. The filter can only be wrong the other way: saying 'possibly present' for a key that was never added.
PredictA query can stop the moment it finds a 0 bit. So for a key that is genuinely absent, roughly how many of the k bits does it inspect on average?
Hint: About half the bits in a well-tuned filter are 1. What's the chance the first probed bit is already 0?
Usually one or two. At the optimal operating point about half the bits are 0, so there's roughly a 50% chance the very first probe lands on a 0 and the query returns 'absent' at once. On average a true-negative lookup inspects under two bits. That's why a Bloom check is essentially free compared to the disk read it prevents. Only a false positive, and every true positive, has to inspect all k bits.
One practical detail. You don't compute k separate hashes per key. Implementations compute two hashes, h1 and h2, and derive the i-th position as h1 + i × h2 (mod m). Kirsch and Mitzenmacher showed this costs no meaningful accuracy. That's why RocksDB and Cassandra can use one fast hash like MurmurHash for the whole thing.
Sizing it: bits per key and the false-positive rate#
As you add keys, more bits flip to 1. Eventually a key that was never added hashes to k positions that are all already 1, and the filter says 'possibly present'. That's a false positive. The fuller the array, the more often it happens.
- At 10% fill (1 in 10 bits set): false positives are rare. Most queries find a 0 and correctly return 'absent'.
- At 50% fill: the optimal operating point. A good balance of memory and accuracy.
- At 90% fill: almost every query returns 'possibly present' whether or not the key was added. The filter is nearly useless.
Two numbers control everything. m/n is the bits per key: total bits m divided by expected keys n. k is the number of hash functions. The optimal k is (m/n) × ln 2, about 0.69 × bits per key. At that k, half the bits are set on average, and the false-positive rate is as low as it can be for the memory you have.
| Bits/key (m/n) | Optimal k | False-positive rate |
|---|---|---|
| 6 | 4 | ~5% |
| 8 | 6 | ~2% |
| 10 | 7 | ~1% (the common default) |
| 14 | 10 | ~0.1% |
| 20 | 14 | ~0.007% |
Time is the easy part. Add and query are both O(k): a fixed handful of hashes and bit accesses, no matter how many keys the filter holds. Space is O(n) bits, with the constant set by your target false-positive rate.
Trade-offs: what you give up for the space
- Space vs accuracy is the central dial. Fewer bits per key saves memory but raises the false-positive rate, and the ~0.6 multiplier per bit is fixed. You pick a point on that curve; you can't beat it.
- 'Present' is never certain. If a wrong 'yes' is catastrophic rather than a wasted lookup, a Bloom filter alone is the wrong tool.
- No deletes in standard form. Bits are shared between keys, so clearing one key's bits would create false negatives for others. A counting Bloom filter replaces each bit with a small counter (typically 4 bits, so ~4x the memory) and decrements to delete. The common production alternative is to rebuild the filter from the source of truth.
- Can't enumerate or count. It answers 'is x a member?' and nothing else. For approximate distinct counts, use a HyperLogLog.
- Sized up front. You must estimate n to pick m. Overshoot and you waste memory; undershoot and the false-positive rate silently degrades. A scalable Bloom filter chains filters of growing size when you can't know n in advance, at the cost of slower queries.
Bloom filter vs hash set vs cuckoo filter
| Bloom filter | Hash set | Cuckoo filter | |
|---|---|---|---|
| Memory per key | ~10 bits (configurable) | ~100–400 bits (stores full keys) | ~7–12 bits at low FPP |
| 'Absent' answer | Certain, no false negatives | Certain | Certain, no false negatives |
| 'Present' answer | Probable, tunable FPP | Certain | Probable, tunable FPP |
| Deletes | No (counting variant adds it) | Yes | Yes, natively |
| List / count | No | Yes | No |
| Lookup work | O(k) hashes, scattered | O(1) average | O(1), ≤2 cache lines |
| Capacity | Degrades gracefully when overfull | Grows freely | Inserts can fail when full |
| Best for | Cheap pre-check before an expensive lookup | Exact membership, small/medium set | Like Bloom but needs deletes / lower FPP |
Where Bloom filters run in the wild
- LSM-tree storage engines. RocksDB, LevelDB, Cassandra, HBase, and ScyllaDB attach a Bloom filter to each on-disk SSTable. A point lookup checks the filter first; if it says 'not here', the whole file is skipped with zero disk I/O. This is the single most important use of Bloom filters in databases. RocksDB uses blocked filters, where all k probes hit one cache line, trading a slightly higher false-positive rate for speed.
- Google Bigtable. The original paper describes optional per-SSTable Bloom filters to avoid disk seeks for rows that don't exist.
- CDN caches. Akamai uses Bloom filters to detect 'one-hit wonders', objects requested exactly once. Only cache an object the second time it's seen, so the cache isn't polluted by URLs that never come back.
- Chrome Safe Browsing (historically). Early versions shipped a Bloom filter of malicious URL prefixes so most safe URLs were cleared locally, with no server round trip.
- Bitcoin SPV clients (BIP 37). Lightweight wallets sent a Bloom filter of their addresses to full nodes so the node returned only relevant transactions. Later deprecated over privacy and DoS concerns.
Failure modes: saturation and silent degradation
Bloom filters fail quietly. They never throw an error or return a wrong 'absent'. They just get less useful as the false-positive rate climbs, and nothing tells you.
- Saturation. Insert far more than the planned n and the array fills past 50%. Past ~80–90% fill almost every query returns 'probably present' and the filter saves nothing. Track the actual fill ratio in production, not just the insert count. Many systems sidestep this entirely: an SSTable's filter is built once at flush time for a known key count.
- Over-hashing. A k much larger than (m/n) × ln 2 sets too many bits per insert and saturates the array faster. More hashes is not always better.
- Bad or correlated hashes. Keys cluster into fewer bits than expected, and the real false-positive rate lands above what the formula predicts.
- Mistaken deletes. Clearing bits in a standard filter, or decrementing a counter for a key that was never added, creates false negatives. This is the one way to make a Bloom filter lie about absence.
In an interview
- Lead with the use case. It sits in front of something expensive, a disk read or a network call, and cheaply rules out keys that are definitely absent.
- Then the mechanism in two sentences. k hash functions map a key to k bit positions. Add sets them; query checks them. One 0 means absent, all 1s means maybe.
- State the guarantee and why it holds: no false negatives, because bits are never cleared.
- Know the sizing rule: ~10 bits per key, k ≈ 0.69 × bits per key, ~1% false positives at 50% fill.
- Name the limitation, no deletes, and the counting Bloom filter as the fix.
- If pressed on alternatives, contrast a cuckoo filter (adds deletes and lower false-positive rates) and a HyperLogLog (a different job: approximate distinct count, not membership).
Do more hash functions always reduce false positives?
No, there is an optimum. More hashes mean more bits checked on a query, which is good, but also more bits set on every insert, which fills the array faster. The sweet spot is k = (m/n) × ln 2, where about half the bits are set. Above it the array saturates and the false-positive rate climbs again.
Can a Bloom filter ever produce a false negative?
Not a standard one. If a key was added, all k of its bits were set and bits are never cleared, so a later query always sees all 1s. The only way to get one is to break the rules: clearing bits in a plain filter, or decrementing a counter for a key that was never inserted.
Can I delete from a Bloom filter?
Not from a standard one. Bits are shared between keys, so clearing one key's bits would corrupt others. Use a counting Bloom filter (counters instead of bits, ~4x memory) or a cuckoo filter. In production, the usual answer is to rebuild the filter from the source of truth.
Is the false-positive rate fixed forever?
No. It rises as you insert more keys. The advertised rate assumes you stay at or below the planned capacity n. Overfill the filter and the rate degrades silently, with no error to warn you. Monitor the fill ratio, not just the count.
References & further reading
- Burton H. Bloom — Space/Time Trade-offs in Hash Coding with Allowable Errors (CACM, 1970) — the original paper that introduced the structure
- Broder & Mitzenmacher — Network Applications of Bloom Filters: A Survey (2004) — the definitive survey of the math and applications
- Fan, Andersen, Kaminsky & Mitzenmacher — Cuckoo Filter: Practically Better Than Bloom (CoNEXT 2014) — the deletable, often-smaller modern alternative
- RocksDB Wiki — RocksDB Bloom Filter — Bloom filters per SSTable in a production LSM engine