Bloom filters: a probabilistic 'definitely not there'
A Bloom filter answers one question — “have I seen this before?” — using a bit array far too small to store the items themselves. It never misses an item that was inserted, and it sometimes cries wolf: a false positive. That trade, a tiny memory footprint in exchange for a controllable error rate, makes it one of the most deployed ideas in systems software, from database engines to network routers.
The one-sentence idea. Hash each item with k different hash functions and set those k bits in an m-bit array. To query, check the same k bits: if any is 0 the item is definitely absent; if all are 1 it is probably present — the bits may have been set by other items. No false negatives, ever; false positives at a rate you choose when you size the filter.
1 — How it works: k hashes, m bits, nothing else stored
Burton Bloom described the structure in 1970. It has exactly two ingredients: a bit array of m bits, all initially 0, and k hash functions that each map an item to a position in the array. Nothing about the item itself is stored — no key, no pointer, no copy. The array is the whole data structure, which is why it is so small.
| Insert x | Compute the k positions and set each of those bits to 1. Setting an already-set bit changes nothing — inserts are idempotent, and bits are shared between items. |
|---|---|
| Query x | Compute the same k positions. If any of them is 0, x was never inserted. If all of them are 1, report “probably present”. |
| Positions used here | Two base hashes combined by double hashing (Kirsch & Mitzenmacher, 2006) behave like k independent hash functions in practice — real implementations hash once or twice, not k times. |
Figure 1: Empty filter. m = 32 bits, k = 3 hashes, 0 items inserted
Figure 1. Insert the five fruits, one at a time, and watch which bits each one sets — banana and the others collide on shared bits, which is normal and harmless. Then query plum, which was never inserted. Its three positions (3, 10, 17) were set by date, banana and melon between them, so the filter answers “probably present” — a genuine false positive, produced live by the hash functions on this page.
How to read this
- A 0 bit is proof. If a query finds any of its k bits at 0, the item cannot have been inserted — inserting it would have set that bit, and bits are never cleared.
- All 1s is only a hint. The k bits may belong to k different other items. The filter cannot tell who set a bit.
- Collisions are the mechanism, not a bug. With 5 items × 3 hashes in 32 bits, the five fruits set 15 distinct bits — nearly half the array — so collisions are already likely. Step 2 quantifies exactly how likely.
2 — False positives: the price, and how it grows
Why can there never be a false negative? A query for an inserted item checks bits that its own insertion set to 1, and in a standard Bloom filter bits never go back to 0. The answer for a true member is therefore always “present”. The error is one-sided by construction.
A false positive needs a conspiracy: every one of the query’s k bits was set by someone else. The more items inserted, the larger the fraction of bits set — the fill — and the easier that conspiracy becomes. After inserting n items, the probability that a given bit is still 0, and the resulting false-positive probability, are:
| One bit survives one hash | |
|---|---|
| One bit survives all kn hashes | The exponential approximation is excellent for realistic m. Note the intermediate step keeps every hash insertion visible: each of the n items makes k attempts, and the bit must dodge all kn of them. |
| Fill and false-positive rate | A false positive needs all k of the query’s bits inside the filled fraction, hence fill raised to the power k. |
Figure 2: m = 1024 bits, k = 7. False-positive rate at n = 100 is 0.73%
Figure 2. The curve stays near zero, then bends sharply upward once the fill passes about half — a Bloom filter does not degrade gracefully, it falls off a cliff. That cliff is why sizing (Step 3) starts from an honest estimate of n. The gold dashed curve is the fill itself; p is the fill raised to the power k, which is why the teal curve lags below it, then catches up.
More hashes is not always better. Raising k checks more bits per query, which helps — but it also fills the array k times faster, which hurts. For a fixed m and n there is an optimal k where the two effects balance, derived in Step 3. Push k to 14 in Figure 2 with a small m and watch the cliff arrive earlier, not later.
3 — Sizing math: pick p, get m and k
In practice you design backwards: you know roughly how many items n the filter must hold, and the false-positive rate p you can tolerate. Two formulas then fix the array size m and the hash count k. The derivation of the optimal k is short enough to do in full — and the key step is kept explicit, because the result (aim for a half-full array) is the most useful intuition in this whole page.
| Step A: minimise p over k | Treat m and n as fixed and ask which k makes this smallest. |
|---|---|
| Step B: the optimum | Read Step B slowly: at the optimum the fill is exactly 1 − 1/2 = 1/2. An optimally tuned Bloom filter is half full. Each bit then carries maximum information — it is a fair coin. |
| Step C: array size for target p | |
| Worked example, fully broken down | Target: n = 1,000,000 items at p = 0.01 (1%).About 9.6 bits per item buys a 1% error rate — regardless of how large the items themselves are. A set of one million URLs stored exactly would cost tens of megabytes in hashes alone; the filter needs 1.2 MB and stores no URLs at all. |
Figure 3: Sizing for n = 100,000 items at p = 1.0%. m = 958,506 bits, k = 7
Figure 3. Bits per element depends only on the target error rate, not on n — the curve is the sizing formula with n divided out. Each tenfold improvement in p costs a constant extra slice: going from 1% to 0.1% adds about 4.79 bits per element, and 0.1% to 0.01% adds the same again. Error rate is bought linearly, in bits, for exponentially better accuracy.
| Target p | Bits per element | Optimal k | Rule-of-thumb reading |
|---|---|---|---|
| 10% | 4.79 | 3 | Good enough for a cheap pre-filter in front of a fast check |
| 1% | 9.59 | 7 | The common default — database and cache filters usually live here |
| 0.1% | 14.38 | 10 | When a false positive triggers an expensive network round trip |
| 0.01% | 19.17 | 13 | Still under 20 bits — cheaper than storing even a short fingerprint exactly |
4 — Counting Bloom filter: buying deletion with counters
The standard filter cannot delete: a bit may be shared by several items, so clearing it on one item’s removal could evict others — creating false negatives, the one thing the structure promises never to do. The counting Bloom filter (Fan et al., 2000) replaces each bit with a small counter, typically 4 bits. Insert increments the k counters; delete decrements them; a query asks whether all k counters are above 0. An item can leave when its counters are no longer needed by anyone else.
Figure 4: Counting filter. m = 16 counters, k = 2, 0 items present
Figure 4. Insert cat and dog, then bird: notice any counter reaching 2: two items share it, so deleting one of them only drops it to 1 and the other stays findable. That sharing is exactly what the plain bit array in Figure 1 could not express. Untick the checkbox for the cleaner counter-only view.
What the counters cost, and their limit
- 4× the memory of a plain filter at the same m (4-bit counters instead of 1-bit flags) — or, at fixed memory, an m four times smaller and a higher p.
- Counters can overflow. With 4-bit counters the ceiling is 15; Fan et al. showed that for typical sizing the chance any counter overflows is tiny, but implementations must still choose a policy (saturate, or size up) — a saturated counter can no longer be decremented safely.
- Deletion must be truthful. Decrementing for an item that was never inserted — or was only a false positive — steals counts from real members and can manufacture false negatives.
5 — Variants: one idea, many shapes
Almost every limitation of the 1970 design has a named descendant. The table compares the main ones on the axes that actually decide deployments: whether items can leave, whether the set can grow, and what the structure pays for it.
| Variant | Change from the classic filter | Gains | Pays |
|---|---|---|---|
| Counting Bloom (2000) | Bits become small counters | Deletion | ≈4× memory at the same m |
| Scalable Bloom (Almeida et al., 2007) | A chain of filters with growing m and tightening p; a new filter is appended when one fills | Set can grow without knowing n in advance; total p stays bounded | Queries check every filter in the chain |
| Compressed Bloom (Mitzenmacher, 2001) | Optimised for sending the filter over a network: size it larger than memory-optimal and compress for transmission | Fewer transmitted bits per query answered at the receiver | Larger uncompressed array at rest |
| Blocked Bloom | Array split into cache-line-sized blocks; all k hashes of an item land in one block | One cache miss per lookup instead of k — the variant most large in-memory systems actually run | Slightly higher p for the same m, because hashes are confined to a block |
| Quotient filter (Bender et al., 2011) | Stores a compact fingerprint of each hash inside a hash-table-like array, not just presence bits | Deletion, resizing, and merging; sequential scans are cache-friendly | More complex bookkeeping; fingerprints, not raw bits, set the error rate |
| Cuckoo filter (Fan et al., 2014) | Cuckoo hashing over short fingerprints, with partial-key relocation | Deletion, and better space than Bloom once p drops below roughly 3%; lookups touch two buckets | Inserts can fail near full load and may need a stash or a rebuild |
Choosing, in one breath. Fixed known n and no deletion: classic (usually blocked) Bloom. Deletion needed: counting Bloom, or a cuckoo filter when p must be low. Unknown or growing n: scalable Bloom, or a quotient filter if you also need merges and resizes. The classic design remains the default because its query is a handful of bit tests with zero bookkeeping.
6 — Applications: a cheap “no” that saves expensive work
Every deployment has the same shape: an expensive operation — a disk read, a decompression, a network round trip — guarded by a filter whose “definitely not” lets the system skip the work entirely. A false positive merely wastes one expensive check; a false negative would lose data, so the one-sided error is exactly the right way round.
Cache digests & admission
- Web cache digests: proxy caches such as Squid exchange Bloom-filter digests of what they hold, so a peer is only queried when the digest says “probably here” — turning an all-peers broadcast into a directed request.
- CDN and browser caches: a compact summary of a remote cache’s contents avoids fetching objects the edge cache provably does not have.
- Cache admission: “have we seen this key before?” filters keep one-hit wonders out of the cache — an item is admitted only on its second appearance, which the filter can attest cheaply.
Skipping disk reads in LSM stores
- LSM-tree SSTables: LevelDB, RocksDB, Apache Cassandra and HBase keep a Bloom filter per data file. A point lookup checks the filter first; a “no” skips opening that file at all. With data spread over many files, this is the difference between one disk read and dozens.
- Join and dedup guards: a filter over the keys already seen cheaply discards duplicates and non-matching rows before heavier join machinery runs.
- Original motivation, still running: spell-checkers and hyphenation dictionaries were among the earliest uses — a huge word list compressed into RAM-sized bits, with rare false “correct” spellings as the accepted cost.
Forwarding & light clients
- Packet forwarding: routers use Bloom filters to summarise which prefixes or subscribers sit behind an interface, compressing forwarding state that would not fit in fast memory as an exact table.
- Bitcoin light clients (BIP 37): an SPV client sends its node a Bloom filter of the addresses it cares about; the node forwards only matching transactions. The known weakness is privacy — a loosely tuned filter matches too much and leaks interest — which is itself a lesson in what p means.
- Ethereum block headers: each header carries a 2048-bit logs bloom aggregating the event-log addresses and topics in the block, so light clients can skip blocks that provably contain no log they follow.
| Setting | The expensive work avoided | What a false positive costs | What a false negative would cost |
|---|---|---|---|
| LSM database lookup | Opening and searching an SSTable on disk | One wasted file check | A live key reported missing — data loss |
| Cache digest lookup | A query to a peer cache | One wasted peer request | A cached object treated as absent and re-fetched from origin |
| Bitcoin SPV filtering | Downloading every transaction in every block | Some extra transactions downloaded | A payment to the user never seen |
| Ethereum logs bloom | Scanning a whole block’s receipts | One block scanned unnecessarily | A relevant event silently missed |
The pattern generalises beyond these three: deduplication in backup systems, safe-browsing URL checks (shipped to browsers as compact prefix filters), and “seen this event ID?” guards in streaming pipelines all use the same move. Whenever a set is huge, the negative answer is the common case, and a rare wasted check is cheap — a Bloom filter is probably already there, quietly saying no.
Bloom filter — Burton H. Bloom, “Space/Time Trade-offs in Hash Coding with Allowable Errors”, Communications of the ACM, 1970. Counting filters: Fan, Cao, Almeida & Broder, 2000. Double hashing analysis: Kirsch & Mitzenmacher, 2006. All hash positions, probabilities and sizing figures on this page are computed live from the formulas shown.