Bloom Filters Explained: The Probabilistic Structure Behind Fast 'Definitely Not' Checks

Most data structures are built to answer “what is this” precisely. A Bloom filter is built to answer a narrower question fast and in almost no memory: is this item definitely not here, or might it be. That narrower question turns out to be exactly what you need in front of an expensive lookup, a disk read, a network call, a cache check, and it’s why Bloom filters quietly sit inside Cassandra, Chrome, most CDNs, and a good chunk of the infrastructure that has to check “have I seen this before” at a scale where storing every item isn’t an option.

The structure, and the trick that makes it work

A Bloom filter is a fixed-size array of bits, all initialized to 0, plus a handful of independent hash functions. Adding an item runs it through each hash function and flips the corresponding bit to 1:

class BloomFilter:
    def __init__(self, size, num_hashes):
        self.size = size
        self.num_hashes = num_hashes
        self.bits = [0] * size

    def _hashes(self, item):
        # In production, use well-distributed hash functions
        # (e.g. murmurhash with different seeds), not this simplified version.
        return [hash(f"{item}{i}") % self.size for i in range(self.num_hashes)]

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

    def might_contain(self, item):
        return all(self.bits[h] == 1 for h in self._hashes(item))

Checking an item re-runs the same hash functions and looks at whether all the corresponding bits are set. If any single bit is 0, the item was definitely never added, that bit could only be 0 because nothing that hashed there was ever inserted. If every bit happens to be 1, the item is probably present, but it’s also possible several other items collectively set those exact same bits without this specific item ever being added. That’s the false positive case, and it’s the entire tradeoff the structure makes: no false negatives, ever, in exchange for a small, tunable rate of false positives.

Why the asymmetry is the whole point

A structure that can say “definitely not” with certainty, and “maybe” with a known error rate, is exactly the shape of check you want in front of something expensive. The pattern in production code looks like this:

def get_user(user_id):
    if not bloom_filter.might_contain(user_id):
        # Bloom filter proved this ID was never inserted.
        # Skip the database entirely, no query needed.
        return None

    # Bloom filter says "maybe", fall back to the real,
    # authoritative source to confirm and fetch the actual data.
    return database.query(user_id)

Every “definitely not” answer is a database query, disk read, or network round-trip you never had to make. The false positives don’t corrupt your results, because you never treat “might be present” as “confirmed present”; you always fall through to the real check for that case. The Bloom filter’s only job is to cheaply eliminate the majority of lookups that would have returned nothing anyway.

Sizing the tradeoff: memory vs false-positive rate

The false-positive rate is tunable, and it’s a direct function of three things: the size of the bit array, the number of items you insert, and the number of hash functions used. More bits per expected item and more (well-chosen) hash functions both lower the false-positive rate, at the cost of more memory and more hashing work per operation.

Bits per item	Approximate false-positive rate
4	~15%
8	~2%
10	~1%
16	~0.05%

That table is why Bloom filters scale the way they do: even at 10 bits per item, which gets you down to roughly a 1% false-positive rate, a filter covering 100 million items fits in about 125 megabytes. Storing those same 100 million items directly, as actual keys in a hash set, would cost many times that, and the gap widens the larger and more variable-length the items are, since the Bloom filter’s size depends only on the count of items and target error rate, never on how big each item is.

Where it actually earns its place

Database engines. Cassandra keeps a Bloom filter per SSTable specifically to avoid disk reads for keys it can prove aren’t in that file, which matters enormously in a log-structured storage engine where a single logical read might otherwise have to check dozens of files on disk. This is the same category of optimization behind database indexing generally: both trade a small amount of extra structure for avoiding expensive work on the common case.

Caching layers and CDNs. Checking a cold cache for content that was never cached wastes a lookup for no benefit. A Bloom filter in front of the cache cheaply answers “was this ever cached” before spending a real cache lookup on it.

Deduplication at scale. Systems processing high-volume event streams, has this event ID been seen before, use Bloom filters to catch the overwhelming majority of true duplicates without maintaining a full set of every ID ever seen, falling back to an authoritative store only for the items the filter flags as possibly-seen.

Safe browsing and blocklist checks. Checking a URL or file hash against a large blocklist without sending every checked item to a remote service is a classic Bloom filter use case: ship the filter locally, check against it, and only escalate to a real lookup for potential matches.

What it can’t do

A standard Bloom filter can’t be shrunk after items are added, can’t tell you what’s in the set (only whether a specific item might be), and can’t support deletion safely, because a single bit can be set by multiple items via hash collisions, and clearing it to “remove” one item could silently turn a different, still-present item into a false negative, which breaks the one guarantee the structure exists to provide. If your use case genuinely needs removal, a Counting Bloom Filter, which replaces each bit with a small counter, supports it at the cost of more memory per entry. If you need to enumerate what’s actually in the set, you need a different structure entirely; a Bloom filter was never designed to answer that question.

The takeaway

A Bloom filter is a narrow tool for a specific shape of problem: you’re checking membership at a scale where storing every item is too expensive, and an occasional false positive is cheap to handle because you already have (or can afford) a slower, authoritative fallback. It’s not a general-purpose set replacement, and reaching for one where you actually need deletion or exact membership is the wrong tradeoff. Where it fits, in front of a disk read, a network call, or a database query you’re trying to skip for the common “not found” case, it’s one of the highest memory-efficiency-to-complexity ratios available in a standard toolkit, and it’s worth having in your back pocket the next time a lookup path shows up as a hot spot in production. Profiling exactly that kind of hot path is part of the backend performance work our team does for clients.