Bloom Filter — Part 1: Foundations & Core Concepts

maang.io System Design Series

---

What is this?

Imagine you're the bouncer at an exclusive club, and your job is to check whether each arriving guest is on the "already-banned" list. The banned list has 2 million names. You could carry a giant binder and flip through it for every single person — accurate, but slow, and the binder is too heavy to hold. So instead you do something clever. When someone gets banned, you stamp a few spots on a long paper strip of checkboxes using a set of rubber stamps keyed to their name. Later, when a guest walks up, you re-apply the same stamps and peek at those exact checkboxes. If any of them is blank, this person was definitely never banned — wave them through instantly, no binder needed. If all of them are already stamped, they're probably banned, so now (and only now) do you go check the heavy binder to be sure.

That paper strip is a Bloom filter. It can't ever wrongly clear a banned guest (a stamped spot never un-stamps itself), but it can occasionally suspect an innocent one, because two different names might happen to stamp overlapping spots. You accept that small chance of a false alarm in exchange for a check that's tiny, constant-time, and lives entirely in your pocket instead of in a warehouse.

The one-line idea: A Bloom filter is a compact, probabilistic "set membership" gadget that answers "have I seen this before?" using a fixed bit array and a few hash functions. It will sometimes say "maybe yes" when the true answer is no (a false positive), but it will never say "no" when the true answer is yes (never a false negative). You trade a little accuracy for enormous savings in memory.

We'll carry the bouncer with the stamped paper strip all the way through this topic — into the bit-twiddling internals in Part 2 and the interview table in Part 3.

---

1. Why it exists — the problem it solves

Every system eventually needs to ask "is X in this set?" — is this URL already crawled, is this user already registered, is this key possibly in this file, is this password in the breached-passwords list. The obvious tool is a real set: a hash set, a database index, a lookup table.

The problem is cost at scale. A hash set storing 1 billion 64-byte keys needs tens of gigabytes of RAM — you're storing every key in full, plus pointer and bucket overhead. And if the real set lives on disk or across the network (an SSTable file, a remote database, a CDN origin), every membership check is an expensive I/O trip. When the honest answer for the vast majority of queries is "no, not here," you're paying full price over and over to learn nothing.

That's the painful "before." You had two bad options:

• Keep the whole set in RAM → accurate but memory-hungry, often impossibly so.
• Hit disk/network for every check → memory-cheap but latency-hungry, and it hammers the thing you're querying.

The Bloom filter (invented by Burton Howard Bloom in 1970) gives you a third option: a tiny in-memory gatekeeper that filters out the "definitely not here" cases in nanoseconds, so you only pay the expensive full check on the rare "maybe" — including the occasional false alarm. For a set of a billion items you might spend a couple of gigabytes instead of tens, or even just a few megabytes if you accept a slightly higher false-alarm rate. The memory cost depends on the number of items and the error rate you tolerate, not on how big each item is.

💡 The whole value proposition is negative lookups made free. If your workload is mostly "is this thing absent?" and being absent is the common case, a Bloom filter turns a flood of expensive checks into a trickle. This is exactly why Cassandra puts one in front of every SSTable — see the Apache Cassandra topic in this tier, where the bloom filter is what keeps read amplification from exploding.

---

2. Core concepts & vocabulary — the mental model

A Bloom filter has just two moving parts. Once you hold these, everything else follows.

1. A bit array of size m. A flat row of m bits, all starting at 0. This is the stamped paper strip. It stores no keys — only 1s and 0s. That's the secret to its small size: it never remembers what you inserted, only the fingerprint of what you inserted.

2. k independent hash functions. Each hashes any input to a position in [0, m). These are the k rubber stamps. Feed a key to all k functions and you get k positions in the bit array — the key's fingerprint.

Two operations, and that's the entire API:

• add(x) — Hash x with all k functions to get k positions, and set all those bits to 1. (If a bit was already 1 from a previous key, it just stays 1 — bits are never cleared.)
• contains(x) — Hash x the same way to get its k positions, and check whether all k bits are 1.
  • If any of the k bits is 0 → return "definitely not in the set." (It's impossible: if x had been added, add would have set every one of those bits.)
  • If all k bits are 1 → return "probably in the set." Maybe you added x; or maybe those k bits were coincidentally set by other keys. That coincidence is a false positive.

The three vocabulary words you must be able to say precisely:

• False positive — the filter says "maybe present" but the item was never added. These happen, at a rate you can tune. This is the price of admission.
• False negative — the filter says "not present" but the item was added. In a standard Bloom filter these cannot happen, ever. This one-sided guarantee is the whole point, and it's what makes the filter safe as a pre-check: a "no" is always trustworthy.
• Saturation / fill ratio — as you add more keys, more bits flip to 1. A filter that's mostly 1s gives false positives constantly. A Bloom filter has a designed capacity; blow past it and the error rate degrades.

⚠️ A standard Bloom filter has no remove(x). Because many keys can share a bit, clearing the bits for one key would silently un-add every other key that touched those same bits — instantly creating false negatives and breaking the whole guarantee. Deletion needs a variant (the counting Bloom filter, Part 2). If your set shrinks, plain Bloom is the wrong tool.

You also can't iterate it (there are no keys to list), you can't count how many items are in it exactly, and you can't resize it after the fact. It answers exactly one question — "possibly member?" — and nothing else.

---

3. How you actually use it — a concrete example

You almost never hand-roll the bit math; you reach for a library and give it two numbers: how many items you expect (n) and what false-positive rate you can live with (p). The library computes the optimal m (bits) and k (hash count) for you (the formulas are Part 2's job).

Here's the shape of it, using Google Guava's Bloom filter in Java to dedupe seen URLs in a web crawler:

// Expecting ~10 million URLs, willing to tolerate a 1% false-positive rate.
BloomFilter<String> seenUrls =
    BloomFilter.create(Funnels.stringFunnel(UTF_8), 10_000_000, 0.01);

// When we crawl a page, record its URL.
seenUrls.put("https://example.com/page-42");

// Before crawling, cheaply skip URLs we've very likely already done.
if (seenUrls.mightContain(url)) {
    // "Maybe seen." ~1% of the time this is a false alarm and we skip a
    // fresh URL — acceptable for a crawler. Or double-check against the DB.
} else {
    crawl(url);            // Guaranteed never crawled → safe to fetch.
    seenUrls.put(url);
}

Notice the method is literally named mightContain, not contains — a good library forces you to remember the answer is probabilistic. That 10M-items-at-1% filter costs about 11.4 MB of RAM. A HashSet<String> holding 10 million ~50-byte URLs would cost well over half a gigabyte. That ~50× memory saving, for a 1-in-100 false-alarm rate, is the entire pitch.

The same two-parameter shape shows up everywhere — Redis (via the RedisBloom module) exposes it as commands:

---

4. When to reach for it — and when not

A Bloom filter earns its place when all of these are true:

• You're asking set-membership questions ("have I seen this?", "could this be here?").
• Negative answers are common and each real check is expensive (disk seek, network call, big index lookup) — so filtering negatives cheaply is a big win.
• You can tolerate occasional false positives — either they're merely a small waste (a redundant check), or you back the filter with an authoritative source that catches the rare false alarm.
• The set only grows (or you're fine rebuilding it), because plain filters can't delete.

Reach for something else when:

You need…	Use instead
The actual value/data, not just yes/no	A real hash map, cache, or DB index
Zero false positives (correctness depends on it)	An exact set / index — never a plain Bloom filter alone
To delete items as the set shrinks	A counting Bloom filter, or a cuckoo filter (Part 2)
An unknown or growing item count without pre-sizing	A scalable Bloom filter (Part 2)
To count frequencies ("how many times seen?"), not just presence	A Count-Min Sketch — its sibling topic in this tier
Small data that fits comfortably in RAM anyway	Just a HashSet — the filter's complexity isn't worth it

That last row matters: a Bloom filter is a scale tool. For a few thousand items, a plain set is simpler, exact, and plenty small. The filter pays off when "store every key exactly" becomes too expensive — millions to billions of items, or a set that must live in precious RAM in front of something slow.

🚫 The classic misuse is treating a "maybe" as a "yes." A Bloom filter is a filter, not a source of truth. If a false positive would cause a correctness bug (e.g. "the filter says this transaction ID exists, so skip it" — and you skip a real, new transaction), you've used it wrong. It's safe only where a false positive costs you a little extra work, never a wrong result.

---

5. Key takeaways

1. A Bloom filter answers "is X possibly in this set?" using a fixed bit array of size m and k hash functions — storing fingerprints, never the keys themselves, which is why it's so small.
2. It gives a one-sided guarantee: never a false negative ("not present" is always true), but occasional false positives ("present" might be a coincidence). A "no" is trustworthy; a "yes" means "go check for real."
3. Its superpower is making negative lookups free — filtering out "definitely not here" in nanoseconds so you only pay the expensive disk/network check on the rare "maybe."
4. You size it with two numbers — expected items n and tolerable error rate p — and get a huge memory win (tens of MB instead of many GB) versus storing the set exactly.
5. It can't delete, iterate, count, or return values, and a "maybe" must never be trusted as a definite "yes." Wrong tool if you need exactness, deletion of a shrinking set, or the data itself.

Next, Part 2 opens the hood: the exact bit-setting mechanics, the false-positive-probability formula and how to pick optimal m and k, a fully worked numeric example, and the variants (counting, scalable, partitioned) that fix plain Bloom's limitations.