Bloom Filter

The big picture#

Everything below expands on these points. Read the core sections top to bottom for the full mental model; the collapsible "Go deeper" boxes hold the probability math and tuning you can skip on a first pass and return to later.

Start here: the problem it solves#

Imagine a web crawler that has visited 100 million URLs. Every time it discovers a new link, it needs to ask: have I already crawled this? Storing all 100 million URLs in a hash set would take roughly 8–10 GB of RAM — more than most machines can spare for a single lookup table. And the crawler needs to do this check billions of times.

The general shape of the problem: a cheap membership test guards an expensive operation. The expensive thing might be a disk seek to an on-disk file, a round trip to a database or remote cache, a re-download, or a duplicate write. Most of the time the answer is 'no, not present' — the link is new, the key isn't in this file, the item hasn't been seen. If you could answer the easy 'no' cases in memory, you would skip the expensive lookup almost every time.

Here is the key observation: the crawler does not need a perfect answer. It can tolerate occasionally revisiting a page it already crawled (a false positive — the filter wrongly said 'maybe seen'). What it cannot tolerate is missing a new page because the filter wrongly said 'already seen' (a false negative). One direction of error is acceptable; the other is not. A Bloom filter is built to provide exactly that asymmetry.

The data structure: an array of bits#

A bit is the smallest unit of storage a computer has: it is either 0 or 1. A Bloom filter is nothing more than a large array of bits, all initialized to 0. For 100 million elements at 10 bits each, the array has 1 billion bits — 125 MB total.

Along with the bit array, you need k hash functions. A hash function takes any input — a URL, a username, a number — and maps it to a position in the bit array. With m bits in the array, each hash function returns a number in [0, m-1]. You pick k to be small — typically between 3 and 10 — and each function gives an independent, different position for the same input.

Adding a key: set k bits to 1#

To add a key to the filter, run it through all k hash functions. Each function gives you one position in the bit array. Set all k of those positions to 1.

1. ADD 'alice.com' with k=3: hash functions return positions [42, 1891, 503]
2. Set bit 42 to 1, bit 1891 to 1, bit 503 to 1
3. ADD 'bob.com': hash functions return positions [101, 42, 7]
4. Set bit 101 to 1 (new), bit 42 is already 1 — no change, bit 7 to 1 (new)

Notice that bit 42 was already set by 'alice.com' and 'bob.com' maps to it too. This is a collision — two keys share a bit. Collisions during adds are harmless. They matter only during queries, where they are the source of false positives.

Querying: what a 0 means vs what all 1s mean#

To check whether a key is in the set, run it through the same k hash functions and check the resulting positions in the array.

• If ANY of the k bits is 0: the key was definitely never added. A key that was added would have set all k of its positions to 1. Finding even one 0 proves this key was not responsible for those positions — it is absent. This answer is guaranteed correct: no false negatives ever.
• If ALL k bits are 1: the key was possibly added. Every position happens to be 1, but they might have been set by other keys rather than this one. This is a 'maybe' answer — could be a genuine match (true positive) or a coincidence (false positive).

Why false negatives are impossible#

The no-false-negatives guarantee follows from one rule: bits are never cleared, only set. Once a bit flips to 1, it stays 1 for the lifetime of the filter.

If you added a key, you set all k of its bit positions to 1 at the time of insertion. Since those bits never go back to 0, querying that same key later will always find all k positions set — always returning 'possibly present'. It is physically impossible for the filter to say 'absent' about a key that was added.

The filter can only be wrong in the other direction: saying 'possibly present' for a key that was never added. Never the reverse.

False positives: when bits lie by coincidence#

As you add more keys, more bits in the array flip to 1. After enough additions, a key that was never added might hash to k positions that are all already 1 — set by different earlier keys as coincidental collisions. Querying that key returns 'possibly present' even though it was never inserted. That is a false positive.

The more full the array, the more likely any random set of k positions is already all 1s. A nearly empty array rarely produces false positives; a nearly full one produces them constantly.

• At 10% fill (1 in 10 bits set): false positives are very rare — most queries find at least one 0 and correctly return 'absent'.
• At 50% fill (half the bits are 1): this is the optimal operating point for many configurations — a good balance of memory use and accuracy.
• At 90% fill (9 in 10 bits set): almost every query returns 'possibly present' whether or not the key was added — the filter has become nearly useless.

Choosing size: bits per key and number of hash functions#

Two numbers control everything. m/n is the number of bits allocated per key (total bits m divided by expected keys n). k is the number of hash functions. Your goal is to minimize the false-positive rate for a given memory budget.

The optimal k for a given m/n is k = (m/n) x ln 2, which equals approximately 0.69 x bits-per-key. At this k value, exactly half the bits are set on average — the sweet spot where the false-positive rate is minimized for the memory you have. Use fewer hashes and the array is under-used; use more and it fills up too fast.

Time complexity is the other half of the story and it is excellent: ADD and QUERY are both O(k) — a fixed, small number of hash computations and bit accesses, completely independent of how many keys n the filter holds. There is no tree to descend and no list to scan. Space is O(m) = O(n) bits, with the constant (bits per key) set by your target false-positive rate.

Variants: deletes, growth, and the cuckoo alternative#

The standard Bloom filter is the baseline; several variants relax its limitations at a cost.

• Counting Bloom filter — replaces each bit with a small integer counter (typically 4 bits). ADD increments the k counters; DELETE decrements them; QUERY treats any non-zero counter as 'set'. This is the standard way to support deletion, at roughly 4x the memory of a plain filter. Counters can overflow under heavy load, and deleting a key never added can corrupt the filter.
• Scalable Bloom filter — chains a sequence of filters with geometrically tightening false-positive rates. When the active filter fills past its target, a new, larger one is started. QUERY checks all filters in the chain. This removes the need to know n in advance, at the cost of slower queries and slightly more space.
• Partitioned / blocked Bloom filter — splits the bit array into k equal slices (one per hash) or into cache-line-sized blocks so all k probes for a key hit the same cache line. Blocked filters trade a slightly higher false-positive rate for a large speedup from cache locality, which is why RocksDB uses them.
• Cuckoo filter — a different structure (a cuckoo hash table of short fingerprints) that supports deletion natively, often uses less space than a Bloom filter for false-positive rates below ~3%, and has better cache locality. The trade-off: inserts can fail when the table gets too full, and it has a hard capacity limit.

Trade-offs: what you give up for the space#

A Bloom filter's superpower — storing membership in ~10 bits per key instead of hundreds — comes from throwing away the keys themselves. Once you internalize that it keeps no keys, only a fog of bits, every limitation follows.

• Space vs accuracy — the central dial. Fewer bits per key saves memory but raises the false-positive rate; the relationship is fixed (~0.6 multiplier per bit). You choose the point on that curve; you cannot beat it.
• No exact answers on 'present' — a positive result is always 'probably', never 'certainly'. If a wrong 'yes' is catastrophic (not merely a wasted lookup), a Bloom filter alone is the wrong tool.
• No deletes in standard form — membership is monotonic; you can only add. Workloads that churn keys need a counting or cuckoo filter, or periodic rebuild from the source of truth.
• Can't enumerate or count — it answers one question (is x a member?) and nothing else. No iteration, no exact cardinality (use a HyperLogLog for counting).
• Sized up front — you must estimate n to pick m. Overshoot and you waste memory; undershoot and the false-positive rate silently degrades as you overfill.

Failure modes: saturation and silent degradation#

Bloom filters fail quietly, not loudly. They never throw an error or return a wrong 'absent' — they just get less useful as the false-positive rate climbs. The dangerous cases are the ones you don't notice.

• Saturation — if you insert far more than the planned n keys, the array fills past 50% and the false-positive rate rises steeply. Past ~80–90% fill almost every query returns 'probably present' and the filter stops saving any lookups. Because there is no error, this can go unnoticed until your 'cheap pre-check' is silently doing nothing.
• Over-hashing — choosing k much larger than (m/n) ln 2 sets too many bits per insert, saturating the array faster and raising the false-positive rate. More hashes is not always better.
• Bad or correlated hashes — if hash functions aren't well-distributed (or are correlated), keys cluster into fewer bits than expected, inflating the false-positive rate above the formula's prediction.
• Mistaken deletes — clearing bits in a standard filter (or decrementing a counter for a key that was never added in a counting filter) introduces false negatives, breaking the core guarantee. This is the one way to make a Bloom filter actually lie about absence.

Bloom filter vs hash set vs cuckoo filter#

Rule of thumb: use a hash set when the set fits in memory and you need exactness, deletion, or enumeration. Use a Bloom filter when the set is huge, you only need membership, and a small false-positive rate is acceptable. Reach for a cuckoo filter when you want Bloom's space savings but also need deletes or a very low false-positive rate.

Where Bloom filters run in the wild#

The pattern is always the same: a tiny in-memory filter guards an expensive operation and answers the common 'definitely not present' case for free.

• LSM-tree storage engines — RocksDB, LevelDB, Cassandra, HBase, and ScyllaDB attach a Bloom filter to each on-disk SSTable. A point lookup checks the filter first; if it says 'not here', the entire file is skipped with zero disk I/O. This is the single most important use of Bloom filters in databases (see the LSM explainer's read path).
• Google Bigtable — the original Bigtable paper describes optional per-SSTable Bloom filters to avoid disk seeks for non-existent rows; this is where many engineers first met the idea.
• CDN and web caches — Akamai and others use Bloom filters to detect 'one-hit wonders' (objects requested exactly once). Only cache an object the second time it's seen, so the cache isn't polluted by URLs that will never be requested again.
• Chrome Safe Browsing (historically) — early versions shipped a Bloom filter of known-malicious URL prefixes to the browser so most safe URLs were cleared locally without a server round trip. Google later moved to a different prefix-set structure, but it's a classic example.
• Bitcoin SPV clients (BIP 37) — lightweight wallets sent a Bloom filter of their addresses to full nodes so the node could return only relevant transactions without learning exactly which addresses belonged to the wallet. (Later deprecated over privacy and DoS concerns, but a textbook use of the structure.)
• Databases and dedup pipelines — PostgreSQL ships a bloom index extension; data pipelines use Bloom filters to skip already-processed records and to short-circuit expensive joins.

Common misconceptions & gotchas#

In an interview#

Lead with the use case: a Bloom filter sits in front of something expensive — a disk read, a network call, a database query — and cheaply rules out items that are definitely absent. It trades a small, tunable false-positive rate for massive memory savings versus a real set.

Explain the mechanism in two sentences: k hash functions map the key to k bit positions; ADD sets those bits to 1, QUERY checks them — a single 0 means definitely absent, all 1s means possibly present. State the guarantee and why it holds (bits never cleared). Know the sizing rule: ~10 bits/key, k = 0.69 x bits-per-key, ~1% false-positive rate at 50% fill. State the headline limitation: no deletes — and name the Counting Bloom filter as the fix.

Name real uses: LSM tree SSTables skip an entire file with one bloom check (no disk read needed — exactly what you see in the LSM simulator), CDN origin checks, database index skip scans, deduplication pipelines at scale. Then open the simulator: add a handful of keys, query one that is definitely absent (watch it exit on a 0 bit), find a false positive (all k bits happen to be set), and watch the fill ratio and false-positive probability update live.

If pressed on alternatives, contrast it with a cuckoo filter (adds deletes and lower false-positive rates) and a HyperLogLog (different job — approximate distinct-count, not membership). Mention double hashing as the practical trick that avoids computing k independent hashes. Those three details signal you've used the structure, not just read about it.

References & further reading#