What Is a Bloom Filter? Explained Visually
A Bloom filter trades certainty for space: "definitely not in the set" is guaranteed, "probably in the set" is not. Learn the core asymmetry and how it works.
Why this, first. “A probabilistic set” earns nothing. Lead with the asymmetry: “definitely not here” is certain, “probably here” is not.
The picture: k hashes, one bit array
m-bit array. Insert sets k bits; a query checks those k bits, and only one answer is certain.1Structure
1 m-bit array
no stored keys
→
add(x)
set k bits
k hashes → k positions
→
query(x)
read k bits
all 1? ↓
The asymmetry is the whole point
| Filter says… | What you actually know | Can it be wrong? |
|---|---|---|
| Not present | The item was never added | No — a negative is certain |
| Present | The item is probably there | Yes — a false positive |
A Bloom filter never lies about absence; it only ever exaggerates presence. A “no” lets you skip expensive work safely, every time.
Three operations — and the one that’s missing
| Operation | What it does | Wrong? |
|---|---|---|
add(x) | Set the k bits that x hashes to | — |
contains(x) | “no” if any bit is 0, else “probably” | FP only |
delete(x) | Not supported — bits are shared | n/a |
A counting Bloom filter swaps bits for small counters to allow deletes. 2
The one piece of math to carry in
(1−e−kn/m)k
false-positive rate
k = (m/n)·ln 2
optimal hash count
(0.5)k
FP rate at optimal k
| Bits per item (m/n) | Optimal k | ≈ False-positive rate |
|---|---|---|
| 8 | 6 | ~2% |
| 10 | 7 | ~1% |
| 16 | 11 | ~0.05% |
That formula is an excellent approximation, not an exact law — worth saying out loud. 3 The headline: ~10 bits/item buys ~1% FP — a few bytes to skip a disk read, which is why LSM-tree stores like RocksDB and Cassandra use them. 4
Retrieval practice
Answer from memory — feedback is instant.
Q1. Which kind of error can a standard Bloom filter make?
- It may say present when the item is absent
- It may say absent when the item is present
- It may be wrong in both possible directions
- It is always exactly correct on membership
Q2. Why can't a standard Bloom filter support delete?
- The hash functions cannot be run in reverse
- Deletion is disabled to keep queries faster
- A cleared bit may belong to another element
- The bit array is stored in read-only memory
Q3. Optimal hash count for m bits and n items is…
- k = (n / m) × ln 2
- k = m × n ÷ ln 2
- k = (m + n) × ln 2
- k = (m / n) × ln 2
Q4. A query returns "not present." What is true?
- The item may still be there in the set
- The item is definitely not in the set
- The item is probably in the set right
- The result cannot be trusted at all now
Rehearse out loud
Interviewer: "Where would you put a Bloom filter in a read-heavy database, and what does it buy you?" ~60 seconds, from memory — then reveal and compare.
Reveal model answer
Put a small per-segment Bloom filter in front of the on-disk lookup — in an LSM-tree store like RocksDB or Cassandra, one per SSTable. On a read, check the filter first: a “not present” lets you skip that disk/SSD read entirely, and because there are no false negatives you never skip a key that’s actually there. It buys a large cut in read amplification for absent keys, at the cost of a few bits of RAM per key and the occasional wasted lookup on a false positive. I’d size it for ~1% FP (about 10 bits/key) and revisit if the filter saturates as segments grow — at which point I’d rebuild or partition rather than let the FP rate climb.
Why this scores: leads with the asymmetry (no false negatives → safe to skip), names a real system, and picks a sizing with a stated trade-off.
I’m your teacher — ask me anything. Want to go to Core next and size one for a target FP rate, be grilled on why the FP rate climbs as the filter fills, or have your rehearsal answer graded? Just say so.
Primary source (read this next)
📖 “Space/Time Trade-offs in Hash Coding with Allowable Errors” — Burton H. Bloom (1970)1 . The original four-page paper; it frames the whole idea as trading a small, controllable error for a large space saving.
Interview — pick your bar
Answer out loud in ~60s, then reveal. Core = recall · Senior = trade-offs & failure modes · Staff = synthesis under ambiguity · System Design = open design round (a different axis, not a harder level).
What is a Bloom filter, in one sentence, and what does it store?
Hit these points: a space-efficient probabilistic set-membership structure → it stores no keys, just one
m-bit array → add(x) sets the k bits that x hashes to; contains(x) reads those k bits → the whole point is the asymmetry: it answers "definitely not here" or "probably here," never the reverse → you trade exactness for a tiny, controllable footprint.Which error can a standard Bloom filter make — and which can it never make?
Hit these points: it can return a false positive — "probably present" for something never added → it can never return a false negative — a "not present" is certain → reason: a "no" requires at least one checked bit to be 0, which only happens if the item was never inserted → "all k bits set" can be a coincidence from other items, so "present" is only a probability → this is why a "no" is always safe to act on.
Walk through what add and contains actually do at the bit level.
Hit these points:
add(x): run k independent hashes of x, take each mod m, set those k bits to 1 (some may already be 1) → contains(x): hash the same way, read those k bits → if any is 0 → "definitely absent"; if all are 1 → "probably present" → no comparison against stored keys ever happens — there are none → cost is k hashes and k bit-probes, independent of how many items are in the set.Why can't a standard Bloom filter support delete?
Hit these points: bits are shared across items → clearing a bit to "remove"
x might un-set a bit that a still-present key y also relies on → that would introduce false negatives, which breaks the one guarantee the structure offers → so deletion is simply unsupported in the standard form → if you need deletes, reach for a counting Bloom filter (bits → small counters) or a cuckoo filter, or periodically rebuild from the live set.Where would you put a Bloom filter in a read-heavy database, and what does it buy you?
Hit these points: put a small per-segment filter in front of the on-disk lookup — in an LSM store like RocksDB or Cassandra, one per SSTable → on a read, check the filter first: a "not present" lets you skip that disk/SSD read entirely → because there are no false negatives, you never skip a key that's actually there → it cuts read amplification for absent keys, at the cost of a few bits of RAM per key and the occasional wasted lookup on a false positive → size for ~1% FP (~10 bits/key, illustrative) and rebuild/partition if it saturates as segments grow.
"Probably present" is useless — why bother if you still have to verify?
Hit these points: the value isn't in the "yes," it's in the certain "no" → in workloads dominated by absent-key lookups, the filter eliminates the expensive path for most queries with a cheap RAM check → only the small fraction that come back "maybe" pay the real lookup, and even there the FP rate is bounded by design → so you swap "every query hits disk/DB" for "only true hits plus a few-percent false positives hit disk/DB" → the win scales with how often the answer is genuinely "not here."
What is the optimal hash count, and what's the catch with using too many hashes?
Hit these points: optimal
k = (m/n)·ln 2, which minimizes the FP rate for a given array size → at that k the FP rate is about (0.5)k → intuition: too few hashes means too few independent bits checked; too many hashes fills the array faster, so each query trips over more set bits → there's a sweet spot — past it, adding hashes raises the FP rate and costs more CPU per op → also: real hashes must be well-mixed and effectively independent, or you fall short of the theoretical rate (double-hashing is the common cheap trick).The textbook FP formula — what is it, and why call it an approximation, not a law?
Hit these points: FP rate ≈
(1−e−kn/m)k → it assumes bit-set events are independent, which isn't strictly true — bits set by different items are correlated → so it's an excellent estimate, slightly optimistic, not an exact identity (NIST has a more precise analysis) → saying this out loud signals you understand the model's assumptions, not just the formula → practically it's accurate enough to size with, but don't treat the last decimal as gospel, and always add headroom for hash quality and growth.Make the case for a Bloom filter over just caching, then steelman the opposite.
For: a Bloom filter answers "is it absent?" in a few bits/key with a certain "no," so it kills the expensive path for misses at a fraction of a cache's memory; it doesn't store values, so it stays tiny even for billions of keys. Steelman against: if your workload is dominated by hits, the filter says "maybe" almost every time and buys nothing; a cache that actually returns values would serve those hits. Synthesis: Bloom for negative-lookup-heavy workloads (LSM reads, dedup, "have I seen this?"); a real cache when repeated hits dominate — they're complementary, often layered (filter to skip misses, cache to serve hits).
A teammate proposes a Bloom filter as the source of truth for "has this user already claimed the coupon?" Where does this break?
Hit these points: a false positive here means a legitimate user is wrongly told "already claimed" — a correctness/UX defect, not a perf nuisance → the filter is only safe as a negative filter: "no" → certainly not claimed, fast path; "maybe" → must verify against the authoritative store → never let "maybe" become the final answer for anything user-visible or money-touching → also flag: no deletes (can't un-claim), and saturation drives the FP rate up silently over time → the principal move: filter in front of an exact store, sized so the verify path is cheap, with a rebuild plan — not the filter as the store.
When would you NOT use a Bloom filter at all?
Hit these points: when false positives are unacceptable and you can't afford a verify step — use an exact set/index → when you must enumerate or return the items — the filter stores no keys, so it can't list anything → when the set is tiny (a few thousand) — a plain hash set is smaller, exact, and supports deletes, so there's no win → when the dominant query is a hit rather than a miss — "maybe" every time buys nothing → the staff framing: a Bloom filter earns its keep only when negative answers are common and a cheap, certain "no" removes real work.
Design-round framework — drive any "use a Bloom filter here" prompt through these, out loud:
- Clarify the workload: how often is the answer "absent"? Hits vs misses ratio decides if a filter helps at all.
- Pick the guarantee you need: a certain "no" (Bloom fits) vs an exact yes/no (needs a real index).
- Size it: choose target FP
p, countn, derivem = −(n·ln p)/(ln 2)2andk = log₂(1/p). - Place it: in front of the expensive/authoritative path; "maybe" always falls through to verify.
- Plan for growth: rebuild/shard/scalable variant before saturation pushes the FP rate up.
- Handle deletes/churn: counting or cuckoo variant, or periodic rebuild from the live set.
- Observe it: track measured FP rate, bits-set fraction, and verify-path hit rate, not just "it's there."
Design a "have we already crawled this URL?" check for a web crawler seeing billions of URLs.
A strong answer covers: the workload is miss-heavy early and the cost of re-crawling is real, so a Bloom filter as a cheap negative filter fits → "no" → definitely unseen, schedule the crawl; "maybe" → check the authoritative seen-set/store before crawling → size from a tolerable FP rate (a false positive just skips a URL — acceptable if rare; numbers illustrative) and from the expected
n → n grows unboundedly, so use a scalable Bloom (chained layers) or shard filters by URL hash so the FP rate stays capped → no deletes needed (URLs don't un-crawl), so standard/scalable beats counting → instrument bits-set fraction and FP rate to trigger a new layer before saturation → name the trade-off: a false positive silently drops a page vs the memory of an exact set of billions of URLs.Design a "weak / breached password" rejection check at signup using a Bloom filter.
A strong answer covers: goal — reject any password in a huge known-breached list without shipping or querying the full list per request → load the breached set into a Bloom filter: "maybe present" → reject (ask for another password); "definitely absent" → allow → here the asymmetry flips in your favor: a false positive just makes a user pick a different password (mildly annoying, safe); a false negative would let a breached password through — and Bloom has none → size for a low FP rate so you rarely over-reject (illustrative), from the known
n of the breach corpus → the set is static and rebuilt on corpus updates, so no deletes and a simple rebuild pipeline → ship the filter to the edge/client for latency, since it stores no actual passwords → name the trade-off: occasional over-rejection (false positive) vs the privacy/size cost of querying or shipping the raw list.📄 Keep handy:
Bloom filters reference