System Design Key Concepts
The problem: membership checks that outgrow memory
Say you are building a web crawler that has already visited a billion URLs. Before fetching a new one you need to answer a simple question: have I seen this before? The honest data structure is a hash set, but a billion URLs is tens of gigabytes, far more than you want to hold in RAM on every worker. Push the set to disk or a remote store and now every check is an I/O, including the overwhelming majority that come back "no, never seen it."
This is exactly the situation a Bloom Filter is built for: a huge set, a membership question asked constantly, and a need to skip the expensive lookup whenever the answer is clearly negative.
What a Bloom Filter gives you
A Bloom Filter is a compact, probabilistic structure that tracks set membership in a tiny fraction of the space the real set would take. The catch is that its answer is not always exact.
Ask it whether an item is present and you get one of two answers:
- Definitely not. The item was never added, and this answer is always correct.
- Possibly yes. The item was probably added, but it might be a false positive.
The asymmetry is the whole point. A Bloom Filter never returns a false negative, so a "no" is final and you can trust it to skip work. A "yes" is a strong hint that you confirm against the real store. You trade a small rate of wasted confirmations for never having to touch the expensive store on a true negative.
How it works: bit array and hash functions
A Bloom Filter has two parts: a bit array of m bits, all starting at 0, and k independent hash functions, each of which maps an item to one position in that array.
To add an item, run it through all k hash functions to get k positions and set the bit at each of them to 1. Adding "apple" might set bits 2, 5, and 9.
To check an item, run it through the same k hash functions and look at those positions:
- If any of the bits is 0, the item was definitely never added. At least one of its bits would have been set on insertion, and it isn't.
- If every one of the bits is 1, the item is probably present. Every bit it would have set is set, although other items may have set them too.
Why false positives happen
A false positive is when the filter reports "possibly yes" for an item that was never added. It happens because bits are shared. Different items hash to overlapping positions, and the filter keeps no record of which item set which bit.
Suppose you add "apple" and "orange", and between them they set bits 2, 4, 5, and 7. Now you check "grapes", which happens to hash to bits 2, 5, and 7. All three are already 1, so the filter says "possibly yes" even though "grapes" was never added. The more items you insert, the more bits flip to 1, and the higher this collision rate climbs.
Sizing it: the math that matters
Two parameters control a Bloom Filter: the size of the bit array (m) and the number of hash functions (k). Choose them well and you hit your target false-positive rate at minimum memory. Choose them badly and you either waste space or let the error rate blow up.
For n items in an m-bit array with k hash functions, the false-positive probability is roughly:
p ≈ (1 - e^(-kn/m))^k
For a given m and n, there is an optimal number of hash functions:
k = (m / n) · ln 2
The intuition is a balance. Too few hash functions and items are not distinctive enough, so unrelated items collide. Too many and each insert sets too many bits, saturating the array faster. The sweet spot leaves the array roughly half filled with 1s.
Working backward from a target false-positive rate p, the array size you need is:
m = -(n · ln p) / (ln 2)²
Worked example: a million items at 1% error
Plug in n = 1,000,000 and p = 0.01:
- Bit array:
m = -(10^6 · ln 0.01) / (ln 2)²is about 9.6 million bits, roughly 1.2 MB. - Hash functions:
k = (m / n) · ln 2is about 7.
That is around 9.6 bits per item to track a million of them at 1-in-100 error. A real hash set holding the same keys runs into tens of megabytes, commonly 20x more once you count per-entry object overhead. Want 0.1% error instead of 1%? Memory grows by only about half, to roughly 14 bits per item. The error rate falls exponentially as you add bits, which is what makes the structure so cheap.
Time and space complexity
Insertion and lookup are both O(k): you compute k hashes and touch k bits, nothing more. Critically, k does not depend on n. Checking membership in a set of a billion items costs exactly what it costs for a set of ten. There is no tree to descend and no list to scan.
Space is the headline win. A Bloom Filter needs a constant number of bits per item, about 10 bits per item for 1% error, regardless of how large the items themselves are. A set of million-character documents and a set of three-letter words cost the same per entry, because only hash positions are recorded, never the items.
Why you can't delete (and the fix)
There is one operation a standard Bloom Filter cannot do: remove an item. To delete "apple" you would clear its bits back to 0, but those same bits may have been set by "orange" as well. Clearing them would make the filter report "definitely no" for "orange", which is a false negative, the one error a Bloom Filter is supposed to never produce.
The fix is a Counting Bloom Filter. Replace each bit with a small counter, often 4 bits wide. Insertion increments the k counters, deletion decrements them, and a position counts as set when its counter is above 0. Deletes are now safe, at the cost of several times the memory. Reach for it only when you genuinely need removal.
Bloom Filter vs the alternatives
| Property | Bloom Filter | Counting Bloom | Hash Set | Cuckoo Filter |
|---|---|---|---|---|
| Space per item | ~10 bits | ~40 bits | Full key + overhead | ~12 bits |
| Supports delete | No | Yes | Yes | Yes |
| False positives | Yes | Yes | No | Yes |
| False negatives | No | No | No | No |
| Can list members | No | No | Yes | No |
| Best for | Huge sets, no deletes | Huge sets with churn | Exact, fits in RAM | Deletes plus better locality |
Choosing a membership structure
When to reach for one
Implementation in Python
Real-world use cases
- Signup username and email checks: type a handle and the form tells you instantly whether it is taken. A Bloom Filter of existing usernames is often the first stop. A "definitely not in the set" is an instant "available" with no database query, which covers most attempts, while a "maybe" falls back to a real lookup. The database's unique index is still the source of truth at submit time, so a rare false positive costs one extra query, never a bad signup.
- Databases (Cassandra, HBase, Bigtable): an LSM-tree spreads data across many on-disk SSTables. Before reading one to find a key, the engine checks a per-SSTable Bloom Filter held in RAM. A "no" skips the disk read entirely, turning a random disk seek into a memory probe.
- Browsers (Chrome Safe Browsing): the browser holds a local Bloom Filter of known-malicious URLs. Most sites get an instant "no" with no network call. A "maybe" triggers a confirmation request to Google, so the rare false positive costs one round trip rather than your privacy on every page.
- CDNs and caches: to avoid caching one-hit wonders that are never requested again, a Bloom Filter records first sightings. An item is admitted to the cache only on its second access, keeping space for genuinely popular content.
What this costs in production
A Bloom Filter is sized for a specific number of items. As the real count approaches that capacity, more bits flip to 1 and the false-positive rate climbs toward 1, quietly degrading until the filter is useless. You cannot resize a standard filter in place, because the bits encode no item identities and there is nothing to rehash. The options are to size generously for peak load up front, rebuild from the source data when you outgrow it, or use a Scalable Bloom Filter that chains progressively larger filters as it fills. Monitor your fill ratio the way you monitor a cache hit rate.
Interview tradeoffs
A few follow-ups separate a surface answer from a senior one:
- Sizing. Be ready to derive
mandkfrom the item count and a target false-positive rate, and to explain the half-full-array intuition behind the optimalk. - The deletion gotcha. State plainly that a standard filter cannot delete, explain why (shared bits risk false negatives), and offer the Counting Bloom Filter as the fix.
- No enumeration. A Bloom Filter answers membership only. It cannot list its members or even report how many it holds, because it stores hash positions, not items.
- Saturation and scaling. Note that filters degrade as they fill and that resizing means rebuilding, or reaching for a Scalable Bloom Filter.
- Distribution. In a sharded system each node usually keeps its own filter over its own data, rather than one shared filter, to avoid a network hop on every check.
Summary
A Bloom Filter answers "is this in the set?" using a constant handful of bits per item, no matter how large the items are or how many there are. It says no with certainty and yes only with probability, which makes it the standard front line ahead of any expensive lookup: databases, caches, crawlers, and safe-browsing all lean on it. Know how to size it, know that it cannot delete or enumerate, and know when an exact structure is the better call.
Frequently asked questions
Can you delete an item from a Bloom Filter?
Not from a standard one. Clearing an item's bits could also clear bits that another item set, which would turn that item's lookup into a false negative. If you need deletes, use a Counting Bloom Filter, which keeps a small counter per slot and decrements on removal.
Can a Bloom Filter return a false negative?
No. If an item was added, every one of its bits was set to 1, so a lookup can never miss it. A "definitely no" is always correct. The only error a Bloom Filter makes is a false positive, where it reports "possibly yes" for an item that was never added.
What causes a Bloom Filter false positive?
Shared bits. Different items hash to overlapping positions, and the filter keeps no record of which item set which bit. If every bit an item checks was already set by other items, the filter reports "possibly yes." The more items you insert, the more bits flip to 1 and the higher the false-positive rate climbs.
How do you choose the size and number of hash functions?
Pick a target false-positive rate p and the number of items n. The bit-array size is m = -(n · ln p) / (ln 2)² and the optimal number of hash functions is k = (m / n) · ln 2. As a rule of thumb that is about 10 bits per item for a 1% rate, with 7 hash functions.
Bloom Filter or hash set: which should I use?
Use a hash set when the full set fits in memory and you need exact answers or the ability to list members. Reach for a Bloom Filter when the set is too large to hold and you can tolerate a small, tunable rate of false positives in exchange for a large memory saving.