Bloom Filters Explained: How They Work and Where They Are Used

A Bloom filter answers one question, "have I seen this before?", using a tiny fraction of the memory a hash set needs. The trade is that it occasionally says "yes" when the true answer is "no". That one-sided error is exactly what you want when "yes" just means "go do the expensive check", which is why Bloom filters sit inside databases, browsers, crawlers and CDNs. This guide covers the mechanics with a dry run, derives the false positive formula, gives working code in Python and Java, and shows how to use them in system design answers.

What a Bloom Filter Is (and the Problem It Solves)

Suppose a web crawler has seen 1 billion URLs and needs to check each newly discovered link against that set. Storing the URLs in a hash set at an average of ~80 bytes each, plus hash table overhead, needs well over 80 GB of RAM. A Bloom filter for the same billion URLs at a 1% false positive rate needs about 1.2 GB, and the size does not depend on how long the URLs are.

The trick is that a Bloom filter does not store the items at all. It stores a few bits of evidence about each one. Introduced by Burton Bloom in 1970, it supports two operations:

• add(x): record x.
• mightContain(x): returns false if x was definitely never added, or true if x was probably added.

So a Bloom filter is a fast negative cache. It is valuable whenever a negative answer lets you skip expensive work (a disk read, a network call, a database query) and a false positive merely costs that work occasionally.

How a Bloom Filter Works: Step-by-Step Dry Run

Take a tiny filter: m = 16 bits, k = 3 hash functions. All bits start at 0. The hash outputs below are made up for illustration; a real implementation computes them from the key.

index:  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
bits:   0 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0

add("swiggy.com"): hashes give positions 1, 6, 13. Set them.

index:  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
bits:   0 1 0 0 0 0 1 0 0 0  0  0  0  1  0  0

add("zomato.com"): positions 4, 6, 11. Bit 6 is already 1, which is fine; bits are shared.

index:  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
bits:   0 1 0 0 1 0 1 0 0 0  0  1  0  1  0  0

mightContain("zomato.com"): positions 4, 6, 11 are all 1 → "probably present". Correct.

mightContain("flipkart.com"): positions 2, 6, 13. Bit 2 is 0 → "definitely not present". Correct, and we only needed to find one zero.

mightContain("razorpay.com"): positions 1, 4, 11. All three are 1, set by different items (1 by swiggy, 4 and 11 by zomato). The filter says "probably present", but razorpay.com was never added. That is a false positive. As the array fills with 1s, these collisions become more likely, which is exactly what the math below quantifies.

The False Positive Math: Sizing m and k

Deriving the false positive rate

Assume the hash functions are independent and uniformly random. Insert n items into m bits with k hashes.

1. One bit, one hash. The probability that a particular hash does not set a particular bit is 1 − 1/m.
2. After all insertions. There are kn hash evaluations in total, so a bit is still 0 with probability (1 − 1/m)^kn ≈ e^−kn/m (using (1 − 1/m)^m ≈ 1/e for large m).
3. A bit is 1 with probability 1 − e^−kn/m.
4. False positive. A query for a new item checks k bits; it is a false positive if all are 1: p ≈ (1 − e^−kn/m)^k.

(Strictly, the k bits are not independent, so this is an approximation. It is very accurate for the sizes used in practice.)

Optimal number of hash functions

For fixed m and n, minimising p over k gives k = (m/n) ln 2 ≈ 0.693 · m/n. At this k, exactly half the bits are expected to be 1, which is intuitive: a half-full array carries the most information per bit. Substituting back:

p = (1/2)^k ≈ 0.6185^m/n, and rearranging for the bits needed: m = −n · ln p / (ln 2)², i.e. bits per item = −1.44 · log₂ p.

Sizing table

Notice the pattern: each 10x reduction in false positive rate costs ~4.8 more bits per item. Item size never appears in the formula. A Bloom filter of 64-byte URLs and one of 4 KB documents cost the same per item.

Worked example: verify 10 bits per item, k = 7

kn/m = 7/10 = 0.7. e^−0.7 ≈ 0.4966, so a bit is 1 with probability 0.5034. p = 0.5034⁷ ≈ 0.0082, about 0.82%.

Now overfill it: insert 2n items into the same filter. kn/m = 1.4, e^−1.4 ≈ 0.2466, p = 0.7534⁷ ≈ 13.8%. Doubling the load made the filter about 17x worse. Undersizing is the most common Bloom filter bug in production.

Estimating how many items are in a filter

If X bits are set, the number of inserted items can be estimated as n ≈ −(m/k) · ln(1 − X/m). Useful for monitoring: alert when the estimated count approaches the design capacity.

Bloom Filter Implementation in Python and Java

Real implementations do not run k independent hash functions. The Kirsch–Mitzenmacher technique (2006) shows that two hashes h1 and h2 are enough: g_i(x) = h1(x) + i · h2(x) mod m, for i = 0..k−1, with no meaningful loss in false positive rate. Guava's BloomFilter uses this approach with a 128-bit MurmurHash3.

import hashlib
import math


class BloomFilter:
    def __init__(self, expected_items: int, fp_rate: float):
        if not (0 < fp_rate < 1) or expected_items <= 0:
            raise ValueError("bad parameters")
        self.m = math.ceil(-expected_items * math.log(fp_rate) / (math.log(2) ** 2))
        self.k = max(1, round(self.m / expected_items * math.log(2)))
        self.bits = bytearray((self.m + 7) // 8)

    def _positions(self, item: str):
        digest = hashlib.blake2b(item.encode("utf-8"), digest_size=16).digest()
        h1 = int.from_bytes(digest[:8], "little")
        h2 = int.from_bytes(digest[8:], "little") | 1   # odd, so steps never stall
        for i in range(self.k):
            yield (h1 + i * h2) % self.m

    def add(self, item: str) -> None:
        for pos in self._positions(item):
            self.bits[pos >> 3] |= 1 << (pos & 7)

    def might_contain(self, item: str) -> bool:
        return all(self.bits[pos >> 3] & (1 << (pos & 7))
                   for pos in self._positions(item))


if __name__ == "__main__":
    bf = BloomFilter(expected_items=100_000, fp_rate=0.01)
    print(bf.m, bf.k)                      # 958506 bits (~117 KB), k = 7
    for i in range(100_000):
        bf.add(f"user:{i}")
    assert all(bf.might_contain(f"user:{i}") for i in range(100_000))  # no false negatives
    fps = sum(bf.might_contain(f"other:{i}") for i in range(100_000))
    print(f"observed FP rate: {fps / 100_000:.4f}")   # close to 0.01

import java.nio.charset.StandardCharsets;

public final class BloomFilter {
    private final long[] words;
    private final int m;   // number of bits
    private final int k;   // number of hash functions

    public BloomFilter(int expectedItems, double fpRate) {
        if (expectedItems <= 0 || fpRate <= 0 || fpRate >= 1)
            throw new IllegalArgumentException("bad parameters");
        double ln2 = Math.log(2);
        long bits = (long) Math.ceil(-expectedItems * Math.log(fpRate) / (ln2 * ln2));
        if (bits > Integer.MAX_VALUE) throw new IllegalArgumentException("too large");
        this.m = (int) bits;
        this.k = Math.max(1, (int) Math.round((double) m / expectedItems * ln2));
        this.words = new long[(m + 63) / 64];
    }

    // 64-bit FNV-1a over UTF-8 bytes, then SplitMix64 to derive two hashes
    private static long fnv1a(byte[] data) {
        long h = 0xcbf29ce484222325L;
        for (byte b : data) { h ^= (b & 0xff); h *= 0x100000001b3L; }
        return h;
    }

    private static long mix(long z) {
        z = (z ^ (z >>> 30)) * 0xbf58476d1ce4e5b9L;
        z = (z ^ (z >>> 27)) * 0x94d049bb133111ebL;
        return z ^ (z >>> 31);
    }

    private int[] positions(String item) {
        long base = fnv1a(item.getBytes(StandardCharsets.UTF_8));
        long h1 = mix(base);
        long h2 = mix(base + 0x9e3779b97f4a7c15L) | 1L;
        int[] pos = new int[k];
        for (int i = 0; i < k; i++) {
            long combined = h1 + i * h2;
            pos[i] = (int) Long.remainderUnsigned(combined, m);
        }
        return pos;
    }

    public void add(String item) {
        for (int p : positions(item)) words[p >>> 6] |= 1L << (p & 63);
    }

    public boolean mightContain(String item) {
        for (int p : positions(item))
            if ((words[p >>> 6] & (1L << (p & 63))) == 0) return false;
        return true;
    }

    public static void main(String[] args) {
        BloomFilter bf = new BloomFilter(100_000, 0.01);
        for (int i = 0; i < 100_000; i++) bf.add("user:" + i);
        int fp = 0;
        for (int i = 0; i < 100_000; i++) if (bf.mightContain("other:" + i)) fp++;
        System.out.printf("m=%d k=%d observed FP=%.4f%n", bf.m, bf.k, fp / 100_000.0);
    }
}

Complexity: add and query are O(k) time, independent of n. Space is O(m) bits. Queries for absent items often exit after the first zero bit, so negatives are usually faster than positives.

In production, use a tested library: Guava's BloomFilter.create(Funnels.stringFunnel(UTF_8), n, p) in Java, BF.RESERVE/BF.ADD/BF.EXISTS in Redis via RedisBloom, or the filters built into RocksDB and Cassandra.

# Redis (RedisBloom, included in Redis Stack)
BF.RESERVE seen_urls 0.01 100000000     # error rate, capacity
BF.ADD seen_urls "https://example.com/a"
BF.EXISTS seen_urls "https://example.com/a"   # 1
BF.MEXISTS seen_urls "https://example.com/a" "https://example.com/b"

Where Bloom Filters Are Used in Real Systems

1. LSM-tree databases: skipping SSTables

In Cassandra, HBase, RocksDB, LevelDB and ScyllaDB, data is spread across many immutable sorted files (SSTables). A point read for a key could, in the worst case, touch every file. Each SSTable carries a Bloom filter of its keys, held in memory. The read path checks the filter first and only reads files that "probably" contain the key. With a 1% false positive rate, a read across 10 SSTables wastes about 0.1 disk reads on average instead of up to 9. Cassandra exposes this per table as bloom_filter_fp_chance, so you can trade memory for fewer wasted reads. More on LSM trees in database indexing explained and key-value store design.

2. Web crawlers: the URL-seen test

A crawler's frontier must not re-enqueue URLs it already fetched. With billions of URLs, an exact set does not fit in memory on one machine. A Bloom filter makes the check in-memory; a false positive means skipping a page that was actually new, which for a crawler is an acceptable small loss. See web crawler system design.

3. CDNs: not caching one-hit wonders

Akamai engineers have described (in Maggs and Sitaraman's paper "Algorithmic Nuggets in Content Delivery") that a large fraction of objects requested from their edge servers are requested only once. Caching those wastes disk and evicts useful content. Their approach: cache an object only on its second request, using a Bloom filter to remember what has been requested once. The same "admission filter" idea appears in modern cache designs such as TinyLFU (used by Caffeine in Java).

4. Avoiding expensive lookups for non-existent keys

Cache penetration is a classic problem: attackers or bugs request IDs that do not exist, so every request misses the cache and hits the database. Putting a Bloom filter of all valid IDs in front means requests for impossible IDs are rejected without touching the database. This is a common answer in distributed cache design interviews.

5. Other uses

• "Already shown" filtering: recommendation and feed systems avoid re-showing items a user has seen. Medium's engineering blog described using Bloom filters this way.
• Username availability: a quick "definitely available" check before hitting the database.
• Distributed joins: Spark and many query engines build a Bloom filter on the small side of a join and push it to the large side to discard non-matching rows early ("runtime filters").
• Postgres bloom extension: an index type useful for equality queries on arbitrary combinations of many columns.
• Weak password or malicious URL checks: ship a compact filter to clients so most checks are local, and confirm positives with a server.

Limitations and Pitfalls

• No deletion. Clearing an item's bits may clear bits other items rely on, creating false negatives.
• No enumeration. You cannot list what is in the filter or retrieve values; it only answers membership.
• Fixed capacity. You must estimate n up front. Overfilling degrades accuracy sharply (the 0.82% → 13.8% example above). Scalable Bloom filters chain progressively larger filters with tighter error rates; RedisBloom supports this via its expansion setting.
• Hash quality matters. Java's String.hashCode() is 32-bit and weakly distributed; using it directly inflates the false positive rate. Use MurmurHash3, xxHash or similar.
• Adversarial inputs. If attackers know your hash functions, they can craft items that are false positives. Use a keyed hash (secret seed) when inputs are untrusted.
• Union is easy, intersection is approximate. Two filters with the same m, k and hashes can be OR-ed to get the union exactly. AND-ing gives a filter for the intersection with a higher false positive rate than building it directly.
• Distributed use. A filter in one process does not help other servers. Either share it via Redis, rebuild it on each node from a data source, or distribute serialized snapshots.

Counting Bloom Filters, Cuckoo Filters and Other Variants

Counting Bloom filter

Replace each bit with a small counter (typically 4 bits). Add increments k counters; delete decrements them; query checks that all k counters are non-zero. This supports deletion at about 4x the memory. Risks: counter overflow (rare with 4 bits at sane loads, but implementations must saturate rather than wrap), and deleting an item that was never added corrupts the filter, so only delete items you know were inserted.

Cuckoo filter

Proposed by Fan, Andersen, Kaminsky and Mitzenmacher (2014). Instead of bits, it stores a short fingerprint (say 8–16 bits) of each item in a hash table with buckets of 4 slots. Each item has two candidate buckets: i1 = hash(x) and i2 = i1 XOR hash(fingerprint). If both are full, it evicts an existing fingerprint to that fingerprint's alternate bucket, cuckoo-style.

• Supports deletion (remove the fingerprint).
• Lookups touch at most 2 buckets, so they are cache-friendly.
• More space-efficient than a Bloom filter when the target false positive rate is below about 3%, per the original paper.
• Inserts can fail when the table is very full (high load factors around 95% are achievable with 4-slot buckets), and inserting the same item many times can overflow its buckets.

Other relatives

How Bloom Filters Come Up in Interviews

Bloom filters appear in two ways: as a direct question ("explain a Bloom filter, derive the false positive rate, implement it"), and as a building block you introduce during a design round. The second is where strong candidates differentiate themselves.

System design problems where a Bloom filter is a good addition

• Web crawler: URL dedup at billions of URLs.
• Key-value store or time-series DB: per-SSTable filters to cut read amplification.
• Cache in front of a DB: block lookups for non-existent IDs (cache penetration).
• URL shortener: quickly check whether a generated short code is likely taken before querying the database.
• Feed / recommendations: filter out already-seen items per user.
• Distributed joins: reduce shuffle by pre-filtering.

How to introduce it in a design round

"Before checking the database for whether this URL was crawled, I'd consult an in-memory Bloom filter. At 5 billion URLs and 1% false positives that's about 6 GB, which I'd shard across the frontier workers by URL hash. A false positive means we skip a new page about 1% of the time, which is acceptable for a crawler; if it weren't, I'd confirm positives against the database."

That answer states the size with math, explains which error is tolerable, and offers a fallback. That is what interviewers listen for.

Follow-up questions to prepare

1. Why are there no false negatives? (Bits only go from 0 to 1.)
2. Derive the optimal k. (Minimise (1 − e^−kn/m)^k; result k = (m/n) ln 2.)
3. How would you support deletes? (Counting Bloom or cuckoo filter.)
4. How would you handle growth beyond the planned size? (Rebuild larger, scalable Bloom filter, or time-partitioned filters, e.g. one per day.)
5. How do you distribute a Bloom filter across servers? (Partition by key hash, or replicate a read-only snapshot; RedisBloom for a shared one.)
6. When would you not use one? (When false positives are unacceptable and confirmation is costly, when the set is small enough for an exact hash set, or when you need deletes and counts.)

For more hashing fundamentals behind all of this, see hashing and HashMap interview problems, and for Redis's built-in probabilistic structures see the Redis deep dive.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.