A browser wants to warn you before you open a malicious URL. The blocklist holds 100 million entries at roughly 100 bytes each — 10 GB. You cannot ship that to every laptop, and you cannot make a network call before every page load without adding latency to the entire web.
Notice what the check is actually for. The overwhelming majority of URLs are safe, and for those the only useful answer is "nothing to see here, carry on". Only the rare suspicious one needs the authoritative lookup.
That asymmetry is the opening. If you are willing to accept an occasional wrong "maybe" — never a wrong "no" — you can answer the common case from 125 MB held in memory.
What a Bloom filter promises
A Bloom filter is a set membership structure that stores no members. It answers one question, and gives one of two answers:
- "Definitely not in the set." Always true. You can act on it without checking anything else.
- "Possibly in the set." Usually true, occasionally wrong. You must go and verify.
The one-sided error is what makes it usable. False positives happen; false negatives cannot. So a "definitely not" is safe to trust, and the structure works as a pre-filter in front of something slow — a network call, a disk seek, a database query. Every "definitely not" is work you skipped entirely.
The price is that you can never enumerate what is inside, count how many items there are, or ask what matched. A Bloom filter is a bit array; it has forgotten the items themselves.
How the bits work
Two ingredients: a bit array of m bits, all zero to begin with, and k independent hash functions, each mapping an item to a position in that array.
To add an item, hash it k times and set every resulting bit to 1.
add "evil.com": h1 -> 2 h2 -> 5 h3 -> 7
index: 0 1 2 3 4 5 6 7
bits: 0 0 1 0 0 1 0 1To query an item, hash it the same k ways and look at those bits. If any is 0, the item was definitely never added — adding it would have set that bit. If all are 1, it is probably present.
query "safe.com": h1 -> 2 (1) h2 -> 4 (0) -> stop. Definitely absent.
query "evil.com": h1 -> 2 (1) h2 -> 5 (1) h3 -> 7 (1) -> possibly present.Both operations are O(k) and touch no more than k bits, independent of how many items the filter holds.
Diagram, as text
- URL leads to Bloom filter
- Bloom filter leads to Definitely safe: load immediately (any bit 0)
- Bloom filter leads to Possibly listed: ask the server (all bits 1)
- Possibly listed: ask the server leads to Authoritative answer
The false positive is now easy to see: an item never added can still have all its bits set, because other items happened to set them. Nothing distinguishes "your bits" from "someone else's bits" — the filter has no memory of who set what. That is also precisely why deletion is impossible, which we return to below.
Sizing: bits per item
The false positive rate depends on three numbers: array size m, items inserted n, and hash count k.
FPR ≈ (1 - e^(-k·n/m))^kTwo consequences matter in practice. More hash functions set more bits per item, which helps until the array saturates and then hurts. And the rate depends on m/n — bits per item — not on the absolute size, so the design parameter is a per-item budget.
Optimal values fall out of the formula:
optimal k = (m/n) · ln 2 ≈ 0.693 · (m/n)
bits needed for rate p: m/n = -ln(p) / (ln 2)² ≈ -1.44 · log₂(p)| Bits per item | Optimal k | Approximate FPR |
|---|---|---|
| 5 | 3 | ~9% |
| 8 | 6 | ~2% |
| 10 | 7 | ~1% |
| 15 | 10 | ~0.1% |
| 20 | 14 | ~0.01% |
The striking property is that cost is per item, not per item size. Ten bits buys 1% whether the item is a 20-byte username or a 2 KB URL, because only the hash of the item is ever used. That is where the compression comes from: the 100-million-URL list above needs 10 bits × 10⁸ = 1 Gbit = 125 MB, against 10 GB of raw data, and it would be the same 125 MB if the URLs were ten times longer.
Note also that halving the error rate costs a fixed ~1.44 bits per item, not a doubling. Very low error rates are surprisingly affordable; it is the item count that drives size.
Implementing one honestly
The structure is a dozen lines. The details that matter are in the hashing.
class BloomFilter:
def __init__(self, m_bits, k):
self.m, self.k = m_bits, k
self.bits = bytearray(m_bits // 8 + 1)
def _positions(self, item):
h1, h2 = mmh3.hash64(item) # one hash, two 64-bit halves
for i in range(self.k):
yield (h1 + i * h2) % self.m # derive k positions from two
def add(self, item):
for p in self._positions(item):
self.bits[p // 8] |= 1 << (p % 8)
def contains(self, item):
return all(self.bits[p // 8] & (1 << (p % 8)) for p in self._positions(item))Two choices are doing real work here.
A non-cryptographic hash. MurmurHash or xxHash, not MD5 or SHA-256. You need speed and even distribution, not collision resistance against an adversary, and the cryptographic functions are an order of magnitude slower for no benefit.
Two hashes, not k. Deriving positions as h1 + i·h2 gives the same false positive rate asymptotically as k independent hash functions — a result due to Kirsch and Mitzenmacher — so you pay for two hash computations instead of seven.
Store the bits packed, as above, rather than as a list of integers: a Python list costs tens of bytes per "bit" and throws away the entire point of the structure.
You cannot delete, and the filter fills up
Clearing the bits for an item would clear bits that other items rely on, silently creating false negatives — the one error the structure promises never to make. So a standard Bloom filter is append-only.
The rate also degrades as you insert. A filter sized for 10 million items at 1% is not a filter for 50 million items at 1%; it is one at roughly 90%, at which point every query says "maybe" and the pre-filter has quietly stopped filtering. And you cannot resize in place, because the positions depend on m. Growing means rebuilding from the source data.
Three variants relax these limits, each with a bill attached:
Counting Bloom filter. Replace each bit with a small counter, typically 4 bits. Deletion decrements. Costs about 4× the space and can corrupt itself if a counter overflows.
Cuckoo filter. Stores short fingerprints in a cuckoo hash table. Supports deletion, and is comparable to or smaller than a Bloom filter at low error rates, but insertion can fail when the table is nearly full.
Scalable Bloom filter. A chain of filters, each new one sized larger with a tighter error rate, so the overall rate stays bounded as the set grows. Queries must check every filter in the chain.
Where they earn their keep
Storage engines. Cassandra, HBase, LevelDB and RocksDB keep a Bloom filter per SSTable. A read must otherwise consult every file that could hold the key; the filters eliminate almost all of those without a disk seek. This is the highest-value use of the structure in production software.
CDN caching. Akamai found a large share of objects are requested exactly once, and caching them wastes the cache. A filter of previously-seen URLs means an object is only cached on its second request.
Web crawlers and feeds. A "have I already fetched this URL?" set that would otherwise be enormous; Medium uses the same trick for articles a reader has already seen. A false positive skips one page or hides one article, which nobody notices.
Browser blocklists. Chrome's Safe Browsing historically shipped a local Bloom filter for exactly the scenario that opened this lesson, before moving to a local list of truncated hash prefixes.
The pattern in every case: the false positive costs a little extra work or one lost item, never a wrong answer to the user.
Check your understanding
Common mistakes
Using it where a wrong answer is unacceptable. If a false positive means a blocked payment or a lost record, you need the real set — or a verification step you are genuinely willing to run every time.
Getting the direction backwards. Put the set in the filter such that the harmless mistake is the possible one. Filtering on the complement inverts the error into a false negative you cannot detect.
Sizing from today's data. Filters are rebuilt, not resized. Size for projected n, and monitor the fill ratio as a first-class metric.
Cryptographic hashes. MD5 and SHA-256 make the lookup an order of magnitude slower for no benefit. Use MurmurHash or xxHash and the two-hash derivation.
Forgetting the verification path. A "maybe" is not an answer. If the backing store is unreachable, you have no result — plan for that failure explicitly.
Reaching for it when a hash set fits. At a few million small items a plain in-memory set is simpler, exact, and supports deletion. Bloom filters earn their complexity when the exact set genuinely will not fit.
Practice
A key-value store checks a Bloom filter before reading from disk. Size one for 10 million keys at a 1% false-positive rate, and explain what changes at 0.1%.
Write your own answer first, on paper or in a note. Then compare.
Show a hint
Bits per item depends only on the target rate, not on the number of items.
Show a strong answer
The sizing rule: roughly 9.6 bits per item for 1%, and about 14.4 bits per item for 0.1% — each additional order of magnitude of precision costs about 4.8 more bits per item.
- At 1%: 10 million × 9.6 bits ≈ 96 Mbit ≈ 12 MB, with about 7 hash functions.
- At 0.1%: 10 million × 14.4 bits ≈ 144 Mbit ≈ 18 MB, with about 10 hash functions.
What that buys. Suppose 90% of queries are for keys that do not exist — the case this optimises. At 1%, the filter eliminates 99% of those pointless disk reads. At 0.1%, it eliminates 99.9%. Going from 1% to 0.1% removes only a further 0.9% of the original misses.
So is the extra 6 MB worth it? Almost always yes for a store like this, because 6 MB of memory is trivial against the cost of a disk read, and the filter is consulted on every single lookup. But notice the shape of the curve: the first 12 MB removes 99% of the work and the next 6 MB removes 0.9%. Beyond about 0.1% the returns are negligible, and pushing to 0.01% costs another 6 MB to remove 0.09%.
The other cost of the tighter filter is 10 hash computations per lookup instead of 7 — real CPU on a hot path, and worth measuring rather than assuming free.
Your Bloom filter cannot delete, but your dataset has items removed regularly. Give two approaches and their trade-offs.
Write your own answer first, on paper or in a note. Then compare.
Show a hint
You cannot clear a bit, because other items may depend on it.
Show a strong answer
Why deletion is impossible in the basic structure: each item sets several bits, and those bits are shared with other items. Clearing them on delete would remove other items too — creating false negatives, which destroys the one guarantee the filter offers.
Approach one — counting Bloom filter. Replace each bit with a small counter (typically 4 bits). Insertion increments, deletion decrements, and a slot is considered set when its counter is above zero.
- Trade-off: four times the memory for the same false-positive rate. Counters can also overflow if an item is inserted many times, and once overflowed the count is wrong forever.
Approach two — rebuild periodically. Keep the plain filter and regenerate it from the authoritative dataset on a schedule, or maintain two filters and rotate: writes go to both, reads consult both, and the older one is discarded and rebuilt.
- Trade-off: deleted items produce false positives until the next rebuild, so the filter is stale rather than wrong. Rebuilding costs a full scan of the dataset, which may be expensive and must not block reads.
Which to choose: if deletions are frequent and memory is available, counting. If deletions are rare or the dataset is rebuilt anyway — as in a log-structured store where files are periodically compacted — rebuilding is simpler and free, because the compaction already reads everything.
The third option worth naming: ask whether you need deletion at all. Filters are often per-file rather than global, and when a file is discarded its filter goes with it — deletion by construction.
Key takeaways
- A Bloom filter trades exactness for space, answering either "definitely not in the set" or "possibly in the set".
- The error is one-sided: false positives happen, false negatives cannot. Every design decision depends on putting the harmless mistake on the possible side.
- It is a pre-filter. Its value is the expensive work skipped on the "definitely not" path, so it only pays when most queries miss.
- Cost is bits per item, not bytes of item: ~10 bits per item for 1%, ~20 for 0.01%, regardless of item size.
- Use
k ≈ 0.693 · (m/n)hash functions, derived from two hashes rather than computed independently, using a fast non-cryptographic function. - You cannot delete, and you cannot resize. Over-fill a filter and it degrades to answering "maybe" to everything.
- Counting filters allow deletion at ~4× space, cuckoo filters allow it more compactly, scalable filters grow with the set.
- It powers SSTable lookups in Cassandra and RocksDB, CDN one-hit-wonder filtering, crawler URL sets and recommendation dedup.
Further reading
- Burton Bloom, "Space/Time Trade-offs in Hash Coding with Allowable Errors" (CACM, 1970) — the original paper.
- Andrei Broder and Michael Mitzenmacher, "Network Applications of Bloom Filters: A Survey" (Internet Mathematics, 2004) — sizing formulas and variants.
- Li Fan et al., "Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol" (SIGCOMM 1998) — counting Bloom filters.
- Bin Fan et al., "Cuckoo Filter: Practically Better Than Bloom" (CoNEXT 2014) — deletion support with better space efficiency.
- Patrick O'Neil et al., "The Log-Structured Merge-Tree (LSM-Tree)" (Acta Informatica, 1996) — where per-file filters earn their keep.