The Problem a Bloom Filter Solves

Imagine checking whether a username is taken among 500 million accounts. Or whether a URL is on a list of known malicious sites. Or whether a database file contains a key, before paying for a slow disk read.

You could store every item in a set, but that takes a lot of memory. A Bloom filter answers "is this item in the set?" using a tiny fraction of the memory, with one catch: it can sometimes say "maybe yes" when the answer is no. It never says "no" when the answer is yes.

🎯 Quick Answer (30-Second Read)

  • A Bloom filter is a bit array plus several hash functions.
  • Add an item: hash it k times and set those k bits to 1.
  • Check an item: if any of its k bits is 0, it's definitely not in the set. If all are 1, it's probably in the set.
  • No false negatives, some false positives. You choose the false positive rate by choosing the size.
  • About 9.6 bits per item gives a 1% false positive rate, no matter how big each item is.
  • Used in databases (Cassandra, RocksDB, HBase), caches, web crawlers and spam checks.

How It Works

flowchart LR A["add('mango')"] --> H1["hash1 → 2"] A --> H2["hash2 → 5"] A --> H3["hash3 → 9"] H1 --> B["Bit array
0 0 1 0 0 1 0 0 0 1 0 0"] H2 --> B H3 --> B Q["check('apple')"] --> Q1["hash1 → 2 ✓"] Q --> Q2["hash2 → 7 ✗ (0)"] Q2 --> R["Definitely NOT in set"]

Adding "mango": three hash functions give positions 2, 5 and 9. Set those bits to 1.

Checking "apple": positions 2, 7 and 11. Bit 7 is 0, so "apple" was never added. If it had been, bit 7 would be 1.

Checking "grape": suppose its positions are 2, 5 and 9, all already set by "mango." The filter says "probably yes," even though grape was never added. That's a false positive.

Why "Maybe Yes" but Never a False "No"

✅ No false negatives
Adding an item always sets its bits. Bits are never cleared, so a real member always finds all its bits set.
⚠️ Possible false positives
Other items may have set all of a non-member's bits by coincidence. The fuller the array, the more likely this is.

The Math

With m bits, n items and k hash functions, the false positive probability is approximately:

p ≈ (1 − e^(−kn/m))^k

The best number of hash functions is:

k = (m / n) × ln 2

And the bits needed for a target false positive rate p:

m = −n × ln(p) / (ln 2)²

Target false positive rate Bits per item (m/n) Hash functions (k)
10% 4.8 3
1% 9.6 7
0.1% 14.4 10

Worked example: 100 million usernames at 1% false positives need 100M × 9.6 ≈ 960 million bits ≈ 120 MB. Storing the usernames themselves (say 20 bytes each) would take about 2 GB, before any hash-table overhead.

Key takeaway: a Bloom filter's size depends only on the number of items and the error rate you accept, not on how big each item is. That's why it's so memory-efficient for long strings like URLs.

Python Code

import hashlib, math

class BloomFilter:
    def __init__(self, n_items: int, fp_rate: float):
        self.m = math.ceil(-n_items * math.log(fp_rate) / math.log(2) ** 2)
        self.k = max(1, round(self.m / n_items * math.log(2)))
        self.bits = bytearray((self.m + 7) // 8)

    def _positions(self, item: str):
        # double hashing: derive k positions from two hashes
        d = hashlib.sha256(item.encode()).digest()
        h1, h2 = int.from_bytes(d[:8], "big"), int.from_bytes(d[8:16], "big")
        return [(h1 + i * h2) % self.m for i in range(self.k)]

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

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

bf = BloomFilter(n_items=1_000_000, fp_rate=0.01)
bf.add("anurag")
print(bf.might_contain("anurag"))   # True
print(bf.might_contain("someone"))  # almost certainly False
print(bf.m, bf.k)                   # 9585059 bits (~1.2 MB), 7 hashes

Where Bloom Filters Are Used

sequenceDiagram participant Q as Query: get("user:42") participant BF as Bloom filter (in memory) participant D as Data file on disk Q->>BF: Might this file contain user:42? alt Bloom says NO BF-->>Q: Skip this file (no disk read) else Bloom says MAYBE BF-->>Q: Check it Q->>D: Read from disk end
  • Databases (Cassandra, RocksDB, HBase): each data file on disk has a Bloom filter, so lookups skip files that can't contain the key. This saves a lot of disk reads in LSM-tree databases.
  • Caches: avoid looking up keys that were never stored.
  • Web crawlers: "Have I already visited this URL?" for billions of URLs.
  • Security: quick checks against lists of known bad URLs or leaked passwords, with a slower exact check on a "maybe."

Limitations

  • Can't delete items (clearing a bit might remove others). Counting Bloom filters or cuckoo filters solve this.
  • Can't list the items stored, only test membership.
  • Size must be planned: adding far more items than designed for makes false positives soar.
  • Always verify "maybe" answers when false positives matter.

Frequently Asked Questions

Can a Bloom filter give false negatives?

No. Adding an item sets all of its bits, and a standard Bloom filter never clears bits, so a member's bits are always set. A Bloom filter can only give false positives, saying an item might be present when it isn't.

How much memory does a Bloom filter need?

About 9.6 bits per item for a 1% false positive rate, and about 14.4 bits per item for 0.1%, regardless of item size. For 100 million items at 1%, that's roughly 120 MB.

Why do databases like Cassandra use Bloom filters?

LSM-tree databases store data across many files on disk. A Bloom filter per file tells the database which files definitely don't contain a key, so it can skip reading them. That avoids many unnecessary disk reads on lookups.

Conclusion

A Bloom filter trades a small, controllable false positive rate for huge memory savings. It uses a bit array and several hash functions to answer "definitely not" or "probably yes," which is perfect for skipping expensive work. Size it with the formulas above, and always double-check a "maybe" when it matters.

Sources

Last verified: 2 November 2026.

Related reads: Consistent Hashing Explained · Password Hashing Explained · Redis Explained · SQL vs NoSQL

I explain the tech and math behind products. Follow on LinkedIn or X, or invite me to speak.