Bloom Filters: The Data Structure That's Allowed to Lie (A Little)

Chrome checks every URL you visit against a list of millions of known malicious sites, before the page loads, without a network round trip for most of them, and without storing a multi-gigabyte blocklist on your laptop. Databases like Cassandra and Google's Bigtable skip disk reads for keys that don't exist, before ever touching a file.

Both rely on the same trick: a data structure that can say "definitely not" with total confidence, and "probably yes" with a small, tunable chance of being wrong.

That structure is a Bloom filter, and once you've seen how absurdly simple it is underneath, the fact that it works at all feels like a magic trick.

The Structure: A Bit Array and a Few Hash Functions

A Bloom filter is just a bit array of size m, initialized to all zeros, plus k independent hash functions.

To insert an item, run it through all k hash functions, and set the bit at each resulting position to 1.

To check membership, run the item through the same k hash functions. If any of those bits is 0, the item was definitely never inserted. If all of them are 1, the item was probably inserted — but you can't be completely sure, because other items might have set those exact same bits by coincidence.

That asymmetry is the entire design: false positives are possible, false negatives are not. If you inserted an item, its bits are guaranteed to be set, forever. There is no mechanism by which checking it later could return "no."

A Tiny Example

Picture a 10-bit array and 3 hash functions. Insert "cat", and suppose its hashes land on positions 2, 5, and 9:

index:  0 1 2 3 4 5 6 7 8 9
bits:   0 0 1 0 0 1 0 0 0 1

Now insert "dog", hashing to positions 1, 5, and 7:

index:  0 1 2 3 4 5 6 7 8 9
bits:   0 1 1 0 0 1 0 1 0 1

Bit 5 was already set by "cat" — a shared bit now. Check "fox", which was never inserted, but happens to hash to positions 1, 7, and 9. Every one of those bits is already 1, courtesy of "cat" and "dog". The filter reports "probably present."

That's a false positive, and it's not a bug — it's the fundamental cost of representing set membership in far less space than the items themselves would take.

Proving the Math Holds, With Real Code

Standard formulas exist for choosing m and k to hit a target false-positive rate p for n expected items:

m = -(n · ln p) / (ln 2)²
k = (m / n) · ln 2

Plugging in n = 10,000 items and a target p = 1% gives m ≈ 95,851 bits and k = 7. Building an actual filter with those parameters:

import hashlib, math

class BloomFilter:
    def __init__(self, size, num_hashes):
        self.size, self.num_hashes = size, num_hashes
        self.bits = bytearray(size)

    def _hashes(self, item):
        h1 = int(hashlib.sha256(item.encode()).hexdigest(), 16)
        h2 = int(hashlib.md5(item.encode()).hexdigest(), 16)
        for i in range(self.num_hashes):
            yield (h1 + i * h2) % self.size

    def add(self, item):
        for idx in self._hashes(item):
            self.bits[idx] = 1

    def __contains__(self, item):
        return all(self.bits[idx] for idx in self._hashes(item))

That code doesn't actually call k different hash functions — it only computes two (SHA-256 and MD5), then derives the rest with h1 + i · h2. That's not a shortcut hack; it's a known result called the Kirsch–Mitzenmacher optimization, which shows this linear combination performs statistically as well as k truly independent hash functions, without the cost of computing k separate ones.

Inserting 10,000 items and testing 200,000 items that were never inserted gives:

m=95,851 bits (11.7 KB), k=7 hash functions
False negatives out of 10,000 inserted items: 0
False positives out of 200,000 unseen items: 2,013 (measured rate = 1.0065%)

Zero false negatives, exactly as guaranteed. A measured false-positive rate of 1.0065% against a target of 1% — the formula isn't a rough approximation, it's precise enough to design against.

The memory case is just as concrete: that 11.7 KB filter replaces 86.8 KB of raw string data for these particular (short) test items — roughly 7x smaller — and the gap only widens for realistic items like full URLs or UUIDs, since a Bloom filter's size depends only on n and your target p, never on how large each item actually is.

Where This Shows Up in Production

• Databases. Cassandra and Bigtable-style storage engines keep a Bloom filter per on-disk data file. Before reading a file off disk to look for a key, they check the filter first; if it says "definitely not here," the expensive disk read is skipped entirely.

• Browsers. Chrome's Safe Browsing feature historically used Bloom-filter-style structures so it could check a URL against a huge list of known-malicious sites without downloading and storing that entire list on your machine.

• Caches and distributed systems. Before making a network hop to check a remote cache or service, a local Bloom filter can cheaply rule out "definitely not cached," saving the round trip entirely for the common case.

The Catches

A Bloom filter can't tell you an item is present with certainty, only "probably." Anything that actually matters (serving a cached response, skipping a security check) still needs a real lookup to confirm a "probably yes." The filter's entire job is to cheaply and confidently rule out the "no" case.

You also can't delete an item from a standard Bloom filter. Bits are shared across items, so clearing a bit to "remove" one item could silently break membership checks for a completely different item that happens to share that bit.

The common fix is a Counting Bloom filter, which stores small counters instead of single bits, so a bit only flips back to zero once nothing else still needs it set. A newer alternative, the Cuckoo filter, supports deletion natively and is often more space-efficient at the same false-positive rate, at the cost of a trickier insertion algorithm — it can trigger a cascade of relocations, similar to cuckoo hashing, which is where the name comes from.

And the false-positive rate isn't fixed forever: insert more items than the filter was sized for, and the rate climbs, since more bits get set to 1 than the design accounted for.

The Takeaway

A Bloom filter trades a small, precisely calculable chance of a false "yes" for a dramatic reduction in memory — and in exchange offers a guarantee that's just as valuable: it will never, under any circumstances, tell you "no" about something that's actually there. That one-directional guarantee is exactly what makes it safe to use as a fast pre-check in front of something more expensive and more certain.