Bloom Filters

1The core idea#

A Bloom filter answers exactly one question: is this item possibly in the set, or is it definitely not?

That phrasing is the whole structure. It is a probabilistic membership test, and it gives one of two honest answers:

• "Definitely not." Trust it completely. The item was never added.
• "Probably yes." It might be in the set, or it might be a false positive. You do not know yet.

The asymmetry is the point, not a weakness.

• It never produces a false negative. It can produce a false positive.
• Most of the time you are not trying to prove something is present.
• You are trying to cheaply rule out the common case, so you only pay for expensive work when you have to.

The mental model I hand juniors: a bouncer with a bad memory who only ever errs toward letting people in.

• "Never seen you, go home" is final. That is the "definitely not."
• "Yeah, maybe, go check inside" means you still check inside. That is the "probably yes."
• The win: the bouncer clears the overwhelming majority of obvious rejections for almost no cost.

And the cost really is almost nothing.

• A filter for 100 million items at a 1% false positive rate fits in roughly 114 MB.
• The raw items (100 million 64-character strings) are north of 6 GB just for the bytes.
• A hash set holding them runs two or three times that again once you count pointers and load factor.
• The price for that compression from gigabytes to 114 MB is the occasional false positive.

2How it works#

Under the hood it is almost embarrassingly simple: a big array of bits, all starting at 0, plus a handful of hash functions.

To add an item:

• Run it through k independent hash functions. Each returns a position in the bit array.
• Set those k bits to 1.
• Adding "alice@example.com" with 3 hash functions might light up bits 17, 4902, and 88211.

To check an item:

• Hash it the same way and look at those same k positions.
• If any one of them is 0, the item was never added (adding it would have set every one), so you get a rock-solid "definitely not."
• If all k bits are 1, you say "probably yes." Those bits could have been set by other items that collided, and that is exactly where false positives come from.

A few things fall out of this design that matter in the room:

• You cannot delete items. Clearing bits for one item might clear a bit another item still needs. If you need deletes, reach for a Counting Bloom filter (small counters instead of single bits) or a Cuckoo filter, which supports deletion directly.
• You tune three knobs: n (expected items), m (number of bits), k (number of hash functions). Given n and a target false positive rate, the math hands you optimal m and k. The optimal hash count is roughly k = (m/n) * ln(2).
• As the filter fills, false positives climb. Once most bits are 1, nearly everything reads "probably present." So you size for expected load up front.
• You do not need k separate hash functions. The standard trick is double hashing: compute two good hashes and derive the rest as h1 + i*h2. Cheaper, and accuracy holds up fine in practice.

A worked example with real numbers#

Let me size one end to end, because this is the calculation an interviewer loves to watch on the whiteboard. Say I am guarding a user-lookup path. I expect n = 10 million registered users, and I will accept a 1% false positive rate (p = 0.01).

The bit count: m = -(n * ln(p)) / (ln(2)^2).

• Plugging in: -(10,000,000 * -4.605) / 0.4805, which is about 95.8 million bits.
• That is roughly 9.6 bits per item, or about 11.4 MB. Tiny. It lives in RAM on every node with room to spare.

The hash count: k = (m/n) * ln(2) = 9.58 * 0.693, which rounds to 7 hash functions. So each add or check touches 7 bit positions.

Now the payoff, stated in numbers:

• The filter returns "definitely not" for essentially all 95% of non-existent lookups and skips the database.
• The 5% that are real all pass through, plus the 1% false positive rate adds a trickle of unnecessary lookups.
• Net: existence checks drop by about 94%. At 50,000 requests per second that is roughly 47,000 queries per second that never leave the application node.

One number to internalize: size that same 11.4 MB filter and then load 100 million users into it, and the false positive rate climbs past 60%. The filter becomes worthless. Sizing for the real n is not optional.

3Trade-offs#

The central trade is memory versus accuracy, and both are dials you set deliberately.

A rough feel for the numbers:

• About 10 bits per item buys roughly a 1% false positive rate.
• Push to about 15 bits per item and you are near 0.1%.
• Each extra factor of 10 in accuracy costs a few more bits per item, which is a great deal. Not free, though, and in a hot path with billions of items those bits add up.

Here is how I weigh a Bloom filter against the obvious alternatives.

The thing people miss: a Bloom filter is rarely the whole answer.

• It sits in front of an exact source of truth. It is a filter, not a replacement.
• Treat "probably yes" as a final answer and you have a correctness bug waiting to happen.
• What you give up: enumerating the set, cheap deletes, and trusting a positive.
• What you gain: speed and a footprint small enough to keep on every node.

4Where it is used#

This shows up in production more than most people realize. The pattern is always the same: a cheap probabilistic gate protecting an expensive exact system.

• Databases skipping disk reads. LSM-tree stores like Cassandra, RocksDB, and HBase keep a Bloom filter per SSTable. Before reading a file from disk, they ask the filter. "Definitely not" means skip that file entirely. On a store with 20 SSTables, a point read that would otherwise touch all 20 narrows to the one or two that might hold the key.
• Caches avoiding useless lookups. The classic cache-penetration problem: attackers (or bad luck) request keys that do not exist, so every request misses the cache and hammers the database. A Bloom filter of known-valid keys in front means "definitely not" rejects without touching the backend.
• Web and content systems. "Have I already shown this user this article?" or "is this URL already in the crawl frontier?" answered cheaply across billions of items. Early Chrome used one to check URLs against a safe-browsing list before the expensive exact check.
• Deduplication at scale. Log pipelines and analytics systems drop likely-duplicate events before the expensive exact dedup stage.

5Common pitfalls and gotchas#

• Undersizing the filter. Expect 1 million, build for 1 million, then load 10 million, and your false positive rate goes through the roof. We saw it: built for 10 million, loaded with 100 million, past 60%. Size for your real peak with headroom. When you genuinely do not know n in advance, use a scalable Bloom filter that chains new filters as it fills.
• Treating a positive as truth. Say it with me: "probably yes" always means go verify. The only time you can act on a positive is when a false positive is harmless, like "might have seen this ad, so skip it," which costs one missed impression, not a bug.
• Forgetting it cannot shrink. No deletes. If your set churns (items come and go), a plain filter slowly saturates and becomes useless. Rebuild periodically, or use a Counting or Cuckoo filter.
• Weak or correlated hashes. Poorly distributed hashes make bits cluster and push false positives above the theoretical rate. Use a solid non-cryptographic hash like MurmurHash or xxHash with the double-hashing trick.
• Serialization and sharing. In a distributed system the filter has to live somewhere consistent. If every node builds its own from a different data snapshot, they disagree. Decide up front: per-node, shared, or rebuilt from a source of truth, and version it.
• The empty-filter edge case. A brand new filter says "definitely not" to everything, which is correct but gives zero protection until populated. During a cold start or rebuild, make sure the fallback path can take full load.

6How it shows up in interviews#

Interviewers bring up Bloom filters two ways. Sometimes directly ("explain a Bloom filter and its trade-offs"). More often they are waiting to see if you reach for one unprompted when the design is screaming for it.

Watch for these triggers in the prompt:

• A high-volume existence check.
• Cache penetration from non-existent keys.
• Dedup across a huge stream.
• "We cannot fit the whole set in memory but we check membership constantly."

The contrast I listen for.

A weak answer: "A Bloom filter is a probabilistic data structure. It can have false negatives but no false positives, so it tells you if something is in a set using hash functions."

• That fails twice. It recites the definition and stops, and it gets the asymmetry backwards.
• False negatives are the one thing a Bloom filter never produces. Flipping that is an instant red flag.

A strong answer quantifies and places it:

• "Ninety-five percent of these lookups are for users who do not exist, so I would put an 11 MB filter sized for 10 million users at a 1% false positive rate in front of the database."
• "That drops roughly 94% of existence checks before they touch storage, about 47,000 queries per second off the database at our load."
• "A 'probably present' still goes to the real index, so correctness holds. I would size for peak with headroom, and because this key set only grows I am fine with a plain filter and no deletes."
• "The one thing I would watch is the cold start: an empty filter protects nothing, so the fallback has to survive full load during a rebuild."

To really land it, name one concrete alternative and why you did or did not pick it. "Plain Bloom filter here because the key set only grows. If we had heavy churn I would switch to a Cuckoo filter for the deletes." That one sentence shows you treat the structure as an engineering choice, not a party trick.

A Bloom filter trades a small, bounded, well-understood error for a large, unbounded cost saving. You only take the trade when the false positive is cheap to absorb.

Next up, try the System Design Question walkthrough on designing a web crawler, where a Bloom filter keeps the URL frontier from re-visiting billions of pages.