AlgoInsight

System Design

What Are Bloom Filters and Where Are They Used?

A data structure that can tell you something is definitely not in a set - using a tiny fraction of the memory the set would need. The catch: it sometimes says 'maybe' when it means 'no.' Here's how that trade is brilliantly useful.

By Admin2026-06-1813 min readbloom-filterdata-structuressystem-designprobabilisticperformancedistributed-systems

Imagine you need to check whether an item is in a huge set - say, whether a URL is in a list of billions of already-crawled web pages. Storing all those URLs to check against would take an enormous amount of memory. But what if you could answer "is this in the set?" using a tiny fraction of that memory, accepting one quirky limitation: the structure can tell you "definitely no" or "probably yes," but never "definitely yes"?

That's a Bloom filter - a clever, space-efficient probabilistic data structure that trades a small, controllable chance of false positives for an enormous saving in memory. It's used all over large-scale systems precisely because that trade is so often worth it. This guide explains what a Bloom filter is, how it works (with code), the crucial properties that make it useful, and where it shows up in real systems.

The core idea: a probabilistic membership test

A Bloom filter answers one simple question: "Is this item in the set?" - but it answers in an unusual way:

That asymmetry is the whole point. A Bloom filter never misses an item that's actually present (no false negatives), but it occasionally claims an item is present when it isn't (false positives). In exchange for tolerating those rare false positives, it uses dramatically less memory than storing the actual items - often by orders of magnitude.

This makes it perfect for situations where a "definitely not" answer lets you skip expensive work, and where an occasional false "probably yes" just means you do a little unnecessary checking. As we'll see, that describes a huge number of real systems.

How it works

A Bloom filter is surprisingly simple: it's just a bit array (a row of bits, all starting at 0) plus a handful of hash functions.

To add an item: run the item through each of the hash functions. Each hash produces a position in the bit array. Set the bit at each of those positions to 1.

To check if an item might be present: run the item through the same hash functions to get the same positions. Look at the bits at those positions. If all of them are 1, the item is probably present. If any of them is 0, the item is definitely not present (because if it had been added, all its bits would have been set).

graph LR
    I["item: 'apple'"] --> H1[hash1 → pos 2]
    I --> H2[hash2 → pos 5]
    I --> H3[hash3 → pos 9]
    H1 --> B["bit array: set bits 2, 5, 9 to 1"]
    H2 --> B
    H3 --> B

This diagram shows how a Bloom filter adds an item. The item "apple" is run through three hash functions, producing positions 2, 5, and 9. The filter then sets the bits at those three positions in the bit array to 1. To check membership later, the same hashes are computed and those bit positions are examined.

Here's a working Bloom filter you can run:

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

    def _positions(self, item):
        # produce num_hashes positions for an item
        return [hash(f"{item}-{i}") % self.size for i in range(self.num_hashes)]

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

    def might_contain(self, item):
        # True only if ALL the item's bit positions are set
        return all(self.bits[pos] for pos in self._positions(item))

bf = BloomFilter()
for fruit in ["apple", "banana", "cherry"]:
    bf.add(fruit)

print("apple :", bf.might_contain("apple"))    # True  (was added)
print("banana:", bf.might_contain("banana"))   # True  (was added)
print("grape :", bf.might_contain("grape"))    # False (definitely not added)
print("mango :", bf.might_contain("mango"))    # False (definitely not added)

Run it: every item that was added returns True, and items that weren't added return False. Crucially, the structure stored no actual fruit names - just bits. That's the memory magic: it remembers "membership" without remembering the items themselves.

Why false positives happen (and why no false negatives)

Understanding the asymmetry is key. No false negatives is guaranteed: when you add an item, you set all its bit positions to 1, and those bits are never turned off. So when you check that same item, all its positions are still 1, and you correctly get "yes." An added item can never be missed.

False positives happen because different items can share bit positions. Imagine you added "apple" (setting bits 2, 5, 9) and "banana" (setting bits 1, 5, 7). Now you check "grape," whose positions happen to be 2, 7, 9. All three of those bits are already set - bit 2 from apple, bit 7 from banana, bit 9 from apple - even though "grape" was never added. The filter says "probably yes," and it's wrong. That's a false positive: the bits were set by other items that happened to overlap.

The more items you add, the more bits get set to 1, and the higher the chance that a random item's positions all happen to be set. So the false positive rate rises as the filter fills up.

Tuning the false positive rate

The beauty of a Bloom filter is that the false positive rate is controllable. It depends on three things:

The practical takeaway: you choose your false positive rate by sizing the filter appropriately for the number of items you expect. Want a 1% false positive rate for ten million items? There's a formula that tells you exactly how big the bit array and how many hash functions you need - and it'll still use a tiny fraction of the memory that storing ten million actual items would. This tunability is what makes Bloom filters practical: you decide the accuracy you need and pay only the memory required for it.

Important: The Bloom filter's superpower is its memory efficiency. It can represent membership in a set of millions of items using a small bit array - far less than storing the items themselves. The price is a controllable false positive rate. When a "definitely not" answer saves you expensive work, that trade is almost always worth it.

The one big limitation: you can't remove items

A standard Bloom filter has a notable constraint: you can't delete items. Why? Because setting a bit back to 0 to "remove" an item might also remove a bit that another item depends on (remember, items share bits). Turning off bit 5 to remove "apple" would also break "banana," which also relies on bit 5. So you'd create false negatives, which defeats the filter's core guarantee.

There's a variant called a Counting Bloom Filter that solves this by using small counters instead of single bits - incrementing on add and decrementing on remove - which allows deletion at the cost of more memory. But the standard Bloom filter is add-only, which is fine for the many use cases where you never need to remove anything.

Where Bloom filters are used

Bloom filters show up wherever a cheap "definitely not present" check can save expensive work. Some classic uses:

The pattern across all of these is identical: use the Bloom filter as a fast, cheap pre-check. A "definitely not" answer lets you skip the expensive operation; a "probably yes" triggers the expensive operation to confirm. Because the filter is so cheap and the expensive operation is avoided so often, the system runs dramatically faster and lighter.

# Demonstrating the "pre-check" pattern: skip expensive lookups for absent items
crawled = BloomFilter(size=10000, num_hashes=4)
for url in ["site.com/a", "site.com/b", "site.com/c"]:
    crawled.add(url)

def should_crawl(url):
    if crawled.might_contain(url):
        return "skip (probably already crawled)"
    return "CRAWL (definitely new)"

print("site.com/a:", should_crawl("site.com/a"))   # skip - already seen
print("site.com/z:", should_crawl("site.com/z"))   # crawl - definitely new

The filter instantly tells the crawler which URLs are definitely new and worth crawling, without storing the full list of seen URLs.

The memory savings, concretely

To feel why Bloom filters matter, consider the numbers. Suppose you want to track membership for 100 million items - say, URLs a crawler has visited. Storing the actual URLs might take many gigabytes. A Bloom filter representing the same 100 million items with a 1% false positive rate needs only around a hundred-odd megabytes - a fraction of the space. Tighten the false positive rate to 0.1% and it grows somewhat, but it's still vastly smaller than storing the items themselves. The reason is that the filter doesn't store the items at all - just a bit array recording which positions have been touched. You trade exact membership (and a small false positive rate) for an order-of-magnitude or greater reduction in memory. At the scale of billions of items, that difference is the difference between "fits in memory" and "doesn't" - which is exactly why Bloom filters are a staple of large-scale systems.

Variants worth knowing

The standard Bloom filter has inspired several useful variants:

Knowing these exist signals that you understand the standard filter's limitations and how the family addresses them.

When NOT to use a Bloom filter

A Bloom filter is the wrong tool in some situations, and recognizing that is part of using it well:

The Bloom filter shines specifically when the set is large, membership testing is the only operation you need, and an occasional false positive merely triggers a confirming check rather than causing harm.

Why it matters in interviews

Interview: Bloom filters are a favorite "show me you know an efficient trick" topic. When a design involves checking membership in a very large set - "has this user seen this post?", "has this URL been crawled?", "might this key be in this file?" - proposing a Bloom filter signals depth: "I'd use a Bloom filter as a cheap pre-check, so a 'definitely not' answer lets us skip the expensive lookup, using a fraction of the memory." Mentioning the no-false-negatives / possible-false-positives property, and that it can't easily delete items, shows you actually understand it rather than just naming it.

The bottom line

A Bloom filter is a space-efficient probabilistic data structure that answers "is this item in the set?" with either "definitely not" or "probably yes" - never a false negative, but with a small, controllable chance of false positives. It works with just a bit array and a few hash functions, using a tiny fraction of the memory that storing the actual items would require. The trade-off (occasional false positives, no deletion in the standard version) is well worth it whenever a cheap "definitely not" answer lets you skip expensive work.

That's exactly why Bloom filters appear throughout large-scale systems - in databases, caches, crawlers, and networks - as fast, lightweight pre-checks that save enormous amounts of I/O and memory. We cover data structures like this and where they fit across System Design Fundamentals.

Go deeper

More articles