Bloom Filters

A Bloom filter tells you, in O(1) time and a few bits per item, whether an element is definitely not in a set or probably is. No false negatives. A small, tunable rate of false positives. That asymmetric guarantee is exactly what large systems need to avoid expensive lookups.

If you've ever wondered how Cassandra avoids hitting disk for every read, how Chrome's Safe Browsing historically checked URLs without downloading the whole blocklist locally, or how Bitcoin's original SPV clients worked — a Bloom filter is involved in each answer.

The problem it solves

Suppose you have a billion-row database. Most queries are for keys that don't exist — lookups from a cold cache, or a web crawler checking if a URL has already been seen.

Without a Bloom filter, every one of those misses pays full price:

flowchart LR
    Q[Query: 'is key K here?'] --> DISK[(Disk lookup<br/>~1ms per miss)]
    DISK -->|not found| RESULT[Return false]
    style DISK fill:#ff2e88,color:#fff

Billions of disk reads, all returning "no." With a Bloom filter in front of that disk, almost all of those reads vanish:

flowchart LR
    Q[Query: 'is key K here?'] --> BF{Bloom filter<br/>in RAM, ~10ns}
    BF -->|definitely not| FAST[Return false<br/>NO DISK READ]
    BF -->|maybe| DISK[(Disk lookup)]
    DISK -->|confirm| RESULT[Final answer]
    style BF fill:#15803d,color:#fff
    style FAST fill:#15803d,color:#fff

We skip disk for 99%+ of negative queries. The disk only sees real positives plus a small false-positive rate.

How it works

A Bloom filter is just two things: a bit array of size m (initialized to all zeros), and k independent hash functions, each mapping any input to a position in [0, m).

Insert(x): hash x with each of the k functions; set those k bits to 1.

Lookup(x): hash x with each of the k functions; check those k bits. If all are 1, return maybe. If any is 0, return definitely not.

flowchart TD
    subgraph "Insert 'apple'"
    A[apple] --> H1["h1=3"]
    A --> H2["h2=7"]
    A --> H3["h3=11"]
    end
    subgraph "Bit array (m=16)"
    BITS["0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0"]
    end
    H1 -.set.-> BITS
    H2 -.set.-> BITS
    H3 -.set.-> BITS
    style BITS fill:#ff6b1a,color:#0a0a0f

That's the entire data structure.

Why no false negatives

If we inserted x, we set bits at positions h1(x), h2(x), h3(x) to 1. Those bits are still 1 — we never unset them. A lookup checks the same positions and sees all 1s. So every inserted element always returns maybe; the filter can never tell you an item is absent when it isn't.

Why false positives happen

A query for y (never inserted) could hash to positions that other inserts already set to 1. If all k bits happen to be 1 even though y was never added, the filter says maybe when the truth is no.

flowchart TD
    subgraph "After inserting apple, banana, cherry"
    BITS["bits: 0111011101010100"]
    end
    Q[query: 'durian'] --> H1["h1=3 → 1"]
    Q --> H2["h2=11 → 1"]
    Q --> H3["h3=13 → 1"]
    BITS -.-> H1
    BITS -.-> H2
    BITS -.-> H3
    H3 --> FP[All set!<br/>False positive]
    style FP fill:#ff2e88,color:#fff

The false-positive rate is tunable: more bits and more hashes lower it, at the cost of memory and compute.

Here's what the two paths look like side by side — insert on the left, lookup on the right — so you can see how the same hash positions link them:

flowchart LR
    subgraph INSERT["Insert: add x to filter"]
        I[item x] --> IH["compute h1(x), h2(x) ... hk(x)"]
        IH --> IB["set bits at those positions = 1"]
    end
    subgraph LOOKUP["Lookup: is x in filter?"]
        L[item x] --> LH["compute h1(x), h2(x) ... hk(x)"]
        LH --> LB{check bits}
        LB -->|"any bit = 0"| DEF["Definitely NOT in set"]
        LB -->|"all bits = 1"| MAY["Maybe in set"]
    end
    style IB fill:#0e7490,color:#fff
    style DEF fill:#15803d,color:#fff
    style MAY fill:#ffaa00,color:#0a0a0f

Notice that "definitely not" is the certain answer; "maybe" is the uncertain one. The filter is designed to protect that certainty about absence.

The math (with no calculus)

For a Bloom filter holding n items, with m bits and k hash functions, the false-positive probability is approximately:

fpp ≈ (1 - e^(-k·n/m))^k

The practical takeaways are simpler than that formula looks:

• Bits per item m/n is what matters. 10 bits per item → ~1% false-positive rate.
• For a given m/n, there is an optimal k: k = (m/n) · ln(2) ≈ 0.693 · (m/n).

Memorable numbers:

Bits per item (m/n)	Optimal k	False positive rate
4	3	~14.7%
8	6	~2.1%
10	7	~0.82% (≈ 1%)
16	11	~0.05%
20	14	~0.007%

10 bits per item ≈ 1% false-positive rate is the rule of thumb to memorize. (The formula gives ~0.82% at exactly 10 bits/item with k=7; "≈1%" is a safe upper bound.)

A Bloom filter for a billion items at 1% fpp: the formula gives ~9.6 Gbits ≈ 1.2 GB (the "10 bits/item" rule of thumb rounds this up to 10 Gbits / 1.25 GB — close enough for back-of-the-envelope). That's tiny compared to the billion items themselves.

Pseudocode

class BloomFilter:
    def __init__(self, m: int, k: int):
        self.m = m
        self.k = k
        self.bits = bytearray((m + 7) // 8)

    def _positions(self, key: str):
        # double-hashing trick: derive k hashes from 2
        h1 = hash(("a", key)) % self.m
        h2 = hash(("b", key)) % self.m
        for i in range(self.k):
            yield (h1 + i * h2) % self.m

    def add(self, key: str):
        for p in self._positions(key):
            self.bits[p // 8] |= 1 << (p % 8)

    def __contains__(self, key: str) -> bool:
        return all(
            self.bits[p // 8] & (1 << (p % 8))
            for p in self._positions(key)
        )

Real implementations use MurmurHash3 or xxHash and the "double hashing" trick so you don't actually compute k independent hashes — you compute two and combine.

What Bloom filters cannot do

The asymmetry is fundamental: the filter is a one-way summary, which means it trades a few capabilities for its speed and size.

You cannot delete. Unsetting a bit might unset bits that other inserts depend on, and false negatives appear — which breaks the one guarantee the filter provides. The fix is a Counting Bloom Filter, where each "bit" is a small counter you can increment and decrement.

You cannot enumerate. There is no way to reconstruct which items are in the filter from the bit array alone.

You cannot get an exact count. If you need cardinality, reach for a HyperLogLog instead.

You cannot identify which item caused a collision. You only know that some inserted item hashes to those positions.

Where Bloom filters live in production

Cassandra / HBase / RocksDB / LevelDB — avoid disk reads

Every SSTable (a sorted file on disk) has a Bloom filter kept in RAM. Before reading the file, the database checks the filter. A "definitely not" skips the disk read entirely — and this is the rule, not the exception, because most reads are for keys that live in only a handful of SSTables.

flowchart LR
    R[Read key K] --> M[MemTable]
    M -->|miss| F1{SSTable 1<br/>Bloom?}
    F1 -->|no| F2{SSTable 2<br/>Bloom?}
    F1 -->|maybe| D1[(Disk read 1)]
    F2 -->|maybe| D2[(Disk read 2)]
    F2 -->|no| F3{SSTable N<br/>Bloom?}
    style F1 fill:#15803d,color:#fff
    style F2 fill:#15803d,color:#fff

Without Bloom filters, every read might touch every SSTable. With them: typically zero or one disk read.

Chrome Safe Browsing — block bad URLs

Chrome historically shipped a local Bloom filter of known phishing/malware URLs. When you clicked a link, Chrome checked the filter locally. Definitely not → safe, instant. Maybe → call Google's API for the real answer. This saved bandwidth and avoided sending every visited URL to Google's servers.

In 2024, Google shifted Chrome's Standard mode from the local-list approach to real-time server-side checks (using Oblivious HTTP via a Fastly privacy proxy to strip identifying information), blocking ~25% more phishing attempts since malicious pages often live for under 10 minutes — shorter than the 30–60 minute local list update cycle. The local Bloom filter approach is the textbook example of how it worked and still illustrates the design trade-off clearly; the real-time path replaced it as the default.

Web crawlers — skip already-seen URLs

Crawl trillions of URLs without checking a database for each. Maybe seen → quick DB check. Definitely not seen → enqueue immediately. The web crawler design on this site uses one.

Bitcoin SPV clients

A light Bitcoin node (BIP 37) sends a Bloom filter to a full node saying "send me transactions matching these addresses." The full node only forwards potential matches — bandwidth-saving, but not truly private: a spying node can probe the filter with candidate addresses to statistically infer the wallet's keys. Bitcoin Core disabled BIP 37 serving by default in v0.19 (2019), and the modern replacement (BIP 157/158, "compact block filters") inverts the model: the full node publishes a deterministic per-block filter, and the light client downloads and scans it locally. Still a great interview example of the trade-off between filter fidelity, privacy, and bandwidth.

Medium — has user seen this article?

Medium reportedly uses Bloom filters to avoid recommending articles you've already read. Maybe seen → suppress. The cost of a false positive (skipping a fresh article) is tiny.

CDN cache — has this object been requested?

Before going to origin, check a Bloom filter of cached objects. Skip the cache lookup for known-cold objects.

Database join optimization

PostgreSQL, Oracle, and others use Bloom filters in hash joins to skip rows that can't match.

Variants worth knowing

The classic Bloom filter has one annoying gap: no deletes. Each variant below targets a specific weakness.

Counting Bloom Filter. Replace each bit with a small (typically 4-bit) counter. add increments; remove decrements. This buys deletion at the cost of roughly 4× the memory. The risk is counter overflow — if a position is incremented more than 15 times (2⁴ − 1) the count wraps and deletions produce false negatives. In practice, a 4-bit counter overflows with negligible probability at reasonable load factors.

Scalable Bloom Filter. Start small. When you hit the target fpp, start a second filter (larger, lower fpp) and chain them. Queries check both. The set grows dynamically without ever degrading fpp — you just add more links to the chain.

Cuckoo Filter. A drop-in replacement that supports deletion, is far more memory-efficient than the counting variant (~10–12 bits/item vs ~38 bits), and is cache-friendlier. In optimized configurations (Fan et al. 2014) it can beat Bloom at very low false-positive rates, but in typical bucket-based implementations at ~1% fpp it uses comparable or slightly more memory than a standard Bloom filter (~10–12 vs ~9.6 bits/item). Slightly more complex to implement but the right default when you need dynamic deletes.

XOR Filter (2020) / Binary Fuse Filter (2022). These newer static designs beat Bloom filters at the same fpp using less memory and faster lookups. XOR filters (Graf & Lemire, JEA 2020) use ~9.8 bits/item for 8-bit fingerprints (~0.4% fpp) — about 1.23× the fingerprint size. Binary Fuse filters (Graf & Lemire, JEA 2022) improved construction speed by more than 2× and use slightly less memory (~9 bits/item for 8-bit fingerprints). Both must be built once from the complete key set — no dynamic inserts. They're ideal when the set is known upfront and read-heavy: static blocklists, package signing databases, that sort of thing.

Which one should you reach for?

flowchart TD
    Q{Do you need\nto delete items?} -->|yes| DEL{Is memory\ntight?}
    Q -->|no| STATIC{Is the set\nfixed at build time?}
    DEL -->|yes| CUCK[Cuckoo filter]
    DEL -->|no| COUNT[Counting Bloom filter]
    STATIC -->|yes| FUSE[Binary Fuse filter]
    STATIC -->|no| BLOOM[Classic Bloom filter]
    style CUCK fill:#a855f7,color:#fff
    style COUNT fill:#0e7490,color:#fff
    style FUSE fill:#15803d,color:#fff
    style BLOOM fill:#ff6b1a,color:#0a0a0f

Filter	Insert	Delete	Memory @ ~1% fpp	Notes
Bloom	✓	✗	~9.6 bits/item	10 bits/item rule of thumb
Counting Bloom	✓	✓	~38 bits/item	4-bit counters; counter overflow risk
Cuckoo	✓	✓	~10–12 bits/item	Cache-friendlier; supports deletion; optimized configs can match Bloom memory (Fan et al. 2014)
XOR (8-bit)	static	✗	~9.8 bits/item	~0.4% fpp; faster lookups
Binary Fuse	static	✗	~9 bits/item	Fastest build; recommended for static sets

For new code in 2026, Cuckoo (dynamic) or Binary Fuse (static) is usually a better default than classic Bloom. But Bloom is everywhere because it's been standard since 1970.

Tuning a Bloom filter for production

To pick parameters, you need two inputs: the expected number of items n, and the acceptable false-positive rate fpp. From those two numbers:

m = -n · ln(fpp) / (ln 2)^2
k = (m / n) · ln(2)

A Python snippet:

import math

def bloom_params(n: int, fpp: float):
    m = math.ceil(-n * math.log(fpp) / (math.log(2) ** 2))
    k = max(1, round((m / n) * math.log(2)))
    return m, k

print(bloom_params(1_000_000, 0.01))  # → (9_585_059, 7)

For a million items at 1% fpp: ~9.6 Mbits ≈ 1.2 MB. Trivial.

Production failure modes

The math is honest — if you use the filter within its design parameters, it behaves predictably. Most real-world problems come from stepping outside those parameters.

The most common trap is exceeding design capacity. The fpp formula assumes at most n items are inserted. Past that, false-positive rate climbs superlinearly — a filter sized for 10M items filled to 20M can easily jump from 1% to 10%+ fpp. The graph is steep: at 1.2× capacity fpp has already nearly doubled (from ~0.82% to ~1.9%), and it reaches ~6% by 1.5× and spikes to ~16% at 2×. Always size with 1.5–2× headroom, monitor fill-ratio in long-lived systems, and plan a periodic rebuild.

flowchart LR
    N1["n = design capacity\nfpp ≈ 1%"] --> N15["n × 1.5\nfpp ≈ 6%"]
    N15 --> N2["n × 2.0\nfpp ≈ 15–16%"]
    N2 --> N3["n × 3+\nfilter is effectively broken"]
    style N1 fill:#15803d,color:#fff
    style N15 fill:#ffaa00,color:#0a0a0f
    style N2 fill:#ff6b1a,color:#0a0a0f
    style N3 fill:#ff2e88,color:#fff

Hash function uniformity matters more than people expect. A biased hash bunches bits, effectively reducing the useful size of m. Use MurmurHash3 or xxHash; avoid Java's String.hashCode() or similar weak hashes that produce poor uniformity across string inputs.

Shared filters across incompatible key spaces create subtle bugs. Two subsystems sharing one filter — say, user IDs and product IDs both stored as integers — can produce accidental collisions where a user ID falsely matches a product ID. Namespace your keys (prefix "u:" and "p:") or use separate filters.

Stale filters after bulk deletes are easy to forget. A Bloom filter is append-only. If you delete 30% of a dataset (expired rows, for instance), the filter still "remembers" those keys and routes some queries to disk that could have been skipped. Plan a periodic rebuild cadence matched to your data churn rate.

Cold startup can also surprise you. At startup, if the filter is loaded from disk and not yet in the CPU's L3 cache, the first wave of lookups can be slower than expected. This matters for latency-sensitive paths at startup or after filter replacement.

When not to use a Bloom filter

The filter earns its place when negative lookups are expensive and common. Take it away when that's not true: if the negative case is rare, the overhead adds complexity for nothing. If you need to enumerate items, use a real set — the filter can't reconstruct what's in it. If you need frequent deletes and don't want to manage a counting variant, Cuckoo filters are cleaner. And if you need exact answers, a Bloom filter is the wrong tool by design.

Worked example: protecting a key-value store

Cassandra-style: each SSTable holds millions of keys; you have hundreds of SSTables per node. A read for key K asks "which SSTables might contain K?"

Without filters, the answer is "check all of them" — open and binary-search every SSTable. Hundreds of disk reads per missing key.

With filters at 10 bits/item (~1% fpp), the math is simple: expected disk reads per missing key = 0.01 × num_sstables. Even with 100 SSTables, you average roughly one disk read for keys that don't exist. This is why LSM-tree databases are usable at all.

flowchart LR
    K[Read key K] --> ALL{Check Bloom<br/>for each SSTable}
    ALL --> M1{SSTable 1<br/>maybe}
    ALL --> M2{SSTable 2<br/>no}
    ALL --> MN{SSTable N<br/>no}
    M1 --> D1[(Disk read)]
    M2 -.skipped.-> X[ ]
    MN -.skipped.-> X
    D1 --> R[K not found]
    style M1 fill:#ffaa00,color:#0a0a0f
    style M2 fill:#15803d,color:#fff
    style MN fill:#15803d,color:#fff

Things you should now be able to answer

• Why does a Bloom filter never produce false negatives?
• How many bits per item for a ~1% false-positive rate, and what is the optimal k?
• Why can't a standard Bloom filter support deletes, and what variants fix this?
• Where in Cassandra/RocksDB is a Bloom filter, and what disk I/O does it save?
• When would you reach for a Cuckoo filter or Binary Fuse filter instead?
• What happens to fpp if you insert 2× your design capacity?
• Why did Bitcoin deprecate BIP 37 Bloom-filter SPV, and what replaced it?
• Name two production failure modes that have nothing to do with the math.

Further reading

• Burton Bloom, "Space/time trade-offs in hash coding with allowable errors" (1970) — the original paper
• Mitzenmacher, "Compressed Bloom Filters" (2002)
• Fan et al., "Cuckoo Filter: Practically Better Than Bloom" (2014)
• Graf & Lemire, "Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters" (JEA 2020)
• Graf & Lemire, "Binary Fuse Filters: Fast and Smaller Than Xor Filters" (JEA 2022)
• Dillinger & Walzer, "Ribbon Filter: practically smaller than Bloom and Xor" (2021) — another static alternative worth knowing
• BIP 157/158 (Osuntokun et al.) — compact block filters, the successor to BIP 37 Bloom-filter SPV
• This project's web crawler design — a Bloom filter in action