Lesson 1 · Foundation

A Bloom filter trades certainty for space

~7 min · visual-first · retrieval practice at the end

Published

Bloom filterBloom filtersData structuresFalse positiveProbabilistic

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

add("apple") k = 3 hashes h1 h2 h3 0 1 0 0 0 0 1 0 0 1 0 0 m-bit array — insert sets the k bits the hashes point to query(z): any checked bit = 0 ? YES → definitely NOT in set query(z): all checked bits = 1 ? PROBABLY → maybe present, verify
The filter stores no keys — just one m-bit array. Insert sets k bits; a query checks those k bits, and only one answer is certain.1
Structure
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

One decision: is ANY checked bit 0? query(x): check k bits any bit = 0? YES, a 0 NO, all 1 DEFINITELY ABSENT certain — no false negatives PROBABLY PRESENT maybe a false positive — verify One missing bit is proof; all bits set can be coincidence.
If any of x's k bits is 0, x was never added. All k bits set can coincide from other items, so "present" is only a probability.1
Filter says…What you actually knowCan it be wrong?
Not presentThe item was never addedNo — 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

OperationWhat it doesWrong?
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

Optimal k and the (0.5)k rate below are from the canonical survey. 2

(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
86~2%
107~1%
1611~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?

Q2. Why can't a standard Bloom filter support delete?

Q3. Optimal hash count for m bits and n items is…

Q4. A query returns "not present." What is true?

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.


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:
  1. Clarify the workload: how often is the answer "absent"? Hits vs misses ratio decides if a filter helps at all.
  2. Pick the guarantee you need: a certain "no" (Bloom fits) vs an exact yes/no (needs a real index).
  3. Size it: choose target FP p, count n, derive m = −(n·ln p)/(ln 2)2 and k = log₂(1/p).
  4. Place it: in front of the expensive/authoritative path; "maybe" always falls through to verify.
  5. Plan for growth: rebuild/shard/scalable variant before saturation pushes the FP rate up.
  6. Handle deletes/churn: counting or cuckoo variant, or periodic rebuild from the live set.
  7. 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.
Sources
1. Bloom, B. H. (1970), "Space/Time Trade-offs in Hash Coding with Allowable Errors", CACM 13(7) — acm.org. ↩
2. Mitzenmacher & Broder, "Network Applications of Bloom Filters: A Survey" — harvard.edu. ↩
3. Christensen, Roginsky, Jimeno (NIST), "A New Analysis of the False-Positive Rate of a Bloom Filter" — nist.gov. ↩
4. RocksDB Wiki — Bloom Filter — github.com. ↩
Was this lesson helpful? Thanks — noted.

These notes reflect my current understanding and are updated as I learn, build, and discover better explanations.