hard Bloom Filters: false positives & sizing

The mechanism: a shared bit array that only ever says “maybe” or “no”

A Bloom filter is an array of m bits, all starting at 0, checked through k independent hash functions. ADD(x) hashes x with each of the k functions to get k positions and sets every one of those bits to 1. CHECK(x) hashes x the same way and looks at the same k positions: if any bit is 0, x was definitely never added — that bit could only be 0 if nothing that hashed there ever set it. If all k bits are 1, the filter answers “probably present,” because those bits could have been set by x, or by pure coincidence from other items whose hashes happened to land on the same positions. That asymmetry is the entire contract: zero false negatives, some false positives — never the other way around.

Add / check, traced on a tiny filter

• ADD(cat) on an m=16-bit array with k=3 hashes to bits {2, 5, 9} → set them to 1.
• ADD(dog) hashes to bits {2, 7, 13} → set them to 1 (bit 2 is now shared by both items — a real collision, harmless so far).
• CHECK(fox), never added, hashes to bits {5, 9, 13}. All three happen to already be 1 (5 and 9 from cat, 13 from dog) → the filter reports “maybe present.” That is a false positive: fox was never added, but the union of cat's and dog's bits accidentally covered its hash positions.
• CHECK(owl), also never added, hashes to bits {1, 4, 11}. Bit 1 is still 0 → the filter reports “definitely absent,” correctly, with certainty.

Why the error only ever goes one way

ADD only ever sets bits; CHECK only ever reads them; nothing ever clears a bit back to 0. So once x is added, its k bits are 1 forever, and a later CHECK(x) always finds all k of them — a Bloom filter can never produce a false negative. The only way CHECK can be wrong is the false-positive direction: some other combination of adds happened to set all k of a not-added item's bit positions by coincidence.

Sizing: turning “how wrong” into a dial

For n items inserted into an m-bit array with k hash functions, the probability that a random bit is still 0 after n inserts is approximately e^−kn/m, so the probability all k of a queried item's bits are (coincidentally) 1 — the false-positive rate — is:

FP ≈ (1 − e^(−kn/m))^k

Two derived quantities matter more in practice than that raw formula: the bits you need for a target FP rate p, and the optimal number of hashes k for a given m and n:

m = −(n · ln p) / (ln 2)²        (required bits, for target false-positive rate p)
k = (m / n) · ln 2                (optimal hash count for that m, n)

The bits-per-item ratio (m/n) is independent of the item's actual size or content — sizing a filter for a billion 200-byte URLs costs exactly the same bits per item as a billion 8-byte integers. As a rule of thumb, m/n ≈ 1.44 · log₂(1/p), which gives ≈9.6 bits/item for a 1% target FP and ≈14.4 bits/item for 0.1%.

Traced example: 1,000,000 items, 1% target false-positive rate

1. Inputs. n = 1,000,000 items, target p = 0.01 (1%).
2. Bits. m = −(n · ln p) / (ln 2)² = −(1,000,000 · ln 0.01) / 0.4805 ≈ 9,585,058 bits (≈ 9.6 Mbit) — about 9.6 bits per item, matching the rule of thumb.
3. Bytes. 9,585,058 / 8 ≈ 1,198,132 bytes ≈ 1.2 MB total, to hold a probabilistic membership test over a million items.
4. Hash count. k = (m/n) · ln 2 = 9.585 · 0.6931 ≈ 6.64 → round to k ≈ 7 hash functions.
5. Check the arithmetic. Plugging k=7, n=1,000,000, m=9,585,058 back into FP ≈ (1 − e^−kn/m)^k gives kn/m ≈ 0.730, e^−0.730 ≈ 0.482, (1−0.482)⁷ ≈ 1.00% — the design closes the loop on the 1% target.

Where this shows up in real systems

• LSM-tree stores (Cassandra, RocksDB, HBase). Each on-disk SSTable carries its own Bloom filter over its keys; a point lookup checks the filter first and skips the disk/network read entirely for SSTables the filter says definitely don't contain the key. Since most SSTables don't contain most keys, this eliminates the majority of wasted disk seeks.
• CDN / cache admission (“one-hit wonders”). A Bloom filter tracks “have I seen this URL requested before?” so a cache doesn't waste space caching objects that are fetched exactly once.
• Web crawler / dedup pipelines. Before crawling or processing an item, check the filter; a false positive just means an occasional skip-check that turns out to be new (cheap to detect), while true dedup catches the overwhelming majority.
• Malicious-URL / spam checks (browser Safe Browsing style). A local Bloom filter answers “could this URL be on the blocklist?” instantly and offline; only a maybe-hit escalates to a real (expensive) lookup against the full list.

The shared shape: the Bloom filter is a cheap gate in front of an expensive lookup. It never gives a wrong answer by itself — a false positive just costs one extra fallback check; a false negative (which cannot happen) would have silently produced a wrong result, which is why the asymmetry is designed the way it is.

Pitfalls

• Sizing for the wrong n. The filter is sized for a design-time n. If the real dataset grows well past that (more inserts than planned, or a filter that's never resized), kn/m grows and the false-positive rate rises non-linearly toward 1 — a filter that was “1% FP at launch” can quietly become 20–50% FP as data grows, silently destroying the whole point of using it. Fix: size with headroom for expected growth, monitor actual n vs. design n, or use a scalable/expanding Bloom filter variant that adds new filter layers as it fills.
• You cannot delete from a plain Bloom filter. Clearing a bit to represent a deletion can un-set a bit another (still-present) item also relies on, silently reintroducing false negatives — which the data structure promises can never happen. If deletes are required, use a counting Bloom filter (small counters instead of single bits) or a cuckoo filter (see Judgment below), not bit-clearing on the original structure.
• A false positive is not free on the fallback path. The whole design assumes the fallback (disk read, network call, full-list lookup) is cheap relative to the savings. If that fallback is itself very expensive (e.g., a slow remote call, or a fallback triggered per false positive at high volume), even a well-tuned 1% FP rate can add real, measurable cost or latency at scale — sizing the filter is only half the decision; the fallback's cost must be priced in too.

Judgment: how a senior engineer decides

Bloom filter vs. an exact hash set

A hash set gives an exact answer with no false positives ever — but it must store (or hash-and-store) every actual key, so memory grows with the size of the keys, not just the count. A Bloom filter trades that exactness for roughly an order-of-magnitude-or-more memory reduction (≈1.2 MB vs. many times that for a million real keys), at the cost of an occasional, bounded, tunable false positive that only ever triggers an extra fallback check — never a wrong final answer. Use the Bloom filter when n is huge, the items themselves are non-trivial to store, and a false positive just costs one avoidable-but-cheap lookup. Use the exact set when you truly cannot afford any extra work on the fallback path, or when the data is small enough that the exact structure is cheap anyway.

Bloom filter vs. counting Bloom filter vs. cuckoo filter

The plain Bloom filter's fatal restriction is no deletes. A counting Bloom filter replaces each bit with a small counter (commonly 4 bits): ADD increments the k counters, DELETE decrements them, and CHECK still reads “all k counters > 0.” This supports deletion at roughly 4× the space of the plain filter, with a small added risk of counter overflow if too many items collide on one slot. A cuckoo filter takes a different approach: it stores a short fingerprint of each item in a cuckoo hash table (each item has two candidate buckets; on collision, an existing fingerprint is evicted and relocated to its alternate bucket). This supports exact deletion (remove the matching fingerprint) with better space efficiency than a counting Bloom filter at the same false-positive rate, at the cost of occasional insert-time relocations and a small chance of insert failure when the table is nearly full (fixed by growing the table or falling back to a stash). Choose the plain Bloom filter when the set is append-only or rebuilt wholesale (SSTables are exactly this — a new SSTable gets a fresh filter, an old one is dropped whole). Choose counting Bloom or cuckoo when individual items are added and removed continuously and you need the filter to track that in place.

When the space saving beats the false-positive cost

The decision is really a cost comparison: (space saved by using a Bloom filter) vs. (probability of FP × cost of the fallback lookup it triggers). Because a false positive only ever causes one extra real lookup — never a wrong answer returned to the caller — it is safe to accept a nonzero rate as long as that lookup is cheap relative to the savings. That is why Bloom filters are ubiquitous in front of disk and network I/O (where the fallback is a real but bounded cost) and rare in front of, say, an in-memory correctness check where doing the exact check is already nearly free.

Takeaways

• ADD sets k hashed bits and never clears them; CHECK reads the same k bits — a single 0 is a guaranteed absence, all-1s is only ever “maybe.” False negatives are structurally impossible; false positives are the tunable, accepted cost.
• Sizing is arithmetic, not guesswork: m = −(n·ln p)/(ln 2)² bits and k = (m/n)·ln 2 hashes. For 1,000,000 items at a 1% target, that's ≈9.6 Mbit (≈1.2 MB) and k≈7 — ≈9.6 bits/item, independent of the item's actual size.
• Use a Bloom filter when the space saved outweighs the cost of the fallback lookup a false positive triggers — it is a gate in front of an expensive check, never the source of truth itself.
• Deletes need a different structure: a counting Bloom filter (simple, ≈4× space) or a cuckoo filter (more space-efficient, supports exact removal) — never clear a bit on the plain array.

---

Synthesized from Burton Bloom's original 1970 paper, Broder & Mitzenmacher's “Network Applications of Bloom Filters: A Survey,” the Cassandra/RocksDB SSTable Bloom-filter documentation, and Fan et al.'s Cuckoo Filter paper (2014). Re-authored/Deepened for this guide.

I just read a lesson on **Bloom Filters: false positives & sizing** (System Design) and want to truly understand it. Explain Bloom Filters: false positives & sizing from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Teach me **Bloom Filters: false positives & sizing** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Quiz me on **Bloom Filters: false positives & sizing** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Help me remember **Bloom Filters: false positives & sizing** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.