Bloom filters

What this chapter covers

The final tier turns to structures that make a bargain the earlier ones refused: give up exactness or a worst-case guarantee, and get an enormous win in space or simplicity. The Bloom filter is the purest example. It answers "have I seen this item?" using a tiny fraction of the memory a real set needs, by accepting a small, tunable rate of false positives — occasionally saying "probably yes" for something it never saw. Crucially, it never produces a false negative: if it says "no," the item is definitely absent. That asymmetry is exactly what a huge class of systems wants — a fast, tiny pre-filter that reliably rejects the common case (never seen) and only rarely triggers an unnecessary expensive check. This chapter builds one from a bit array and a few hash functions, watches items set bits and a query produce a false positive, and shows the payoff: representing a million items at a 1% error rate in 1.2 megabytes where a real set needs 122 — a hundredfold saving.

A bit of history

Burton Howard Bloom introduced the filter in a 1970 paper with the wonderfully practical title "Space/Time Trade-offs in Hash Coding with Allowable Errors." His motivating example was a hyphenation program: most words follow simple hyphenation rules, and only a small dictionary of exceptions needs the expensive lookup, so a compact filter that reliably says "this word is not an exception" (rejecting the common case) saved most of the disk accesses. That's the archetype of every Bloom-filter use since — a cheap in-memory gate in front of an expensive operation. The structure stayed a specialist tool for decades, then became ubiquitous with the rise of large-scale distributed systems in the 2000s: Google's Bigtable and its descendants (Cassandra, HBase, LevelDB, RocksDB) use Bloom filters to avoid disk reads for keys that aren't present, saving vast numbers of I/O operations. Bloom's 1970 space/time trade-off — accept a little error to save a lot of memory — turned out to be one of the most consequential ideas in systems engineering, and it launched a whole family of probabilistic data structures (counting Bloom filters, cuckoo filters, HyperLogLog, count-min sketch) built on the same bargain.

The intuition

Start with an array of m bits, all zero, and pick k hash functions that each map an item to a bit position. To add an item, hash it k ways and set all k of those bits to 1. To query an item, hash it the same k ways and look at those k bits: if all of them are 1, report "probably present"; if any is 0, report "definitely absent." The absence guarantee is airtight and worth dwelling on: adding an item only ever sets bits, never clears them, so if a bit is still 0, no item that would have set it was ever added — a single 0 is proof of absence. That's why there are no false negatives, ever.

The false positives come from the flip side. A query's k bits might all happen to be 1 not because this item was added, but because other items collectively set those bits. The animation shows this: after adding cat, dog, and fox, the word hycr — never added — hashes to three positions that other items already lit, so the filter says "probably present." That's a false positive, and its probability is tunable: more bits (larger m) means fewer collisions and fewer false positives; more items (larger n) means more bits set and more false positives. The remarkable part is what the space doesn't depend on: the items themselves. Whether you store 8-character words or 8-kilobyte documents, each costs the same handful of bits, because only its hash positions are recorded, never the item. A real set must store every element in full; a Bloom filter stores none of them, only the shadow they cast on the bit array. That's the source of the hundredfold memory win — and the reason you can never get the items back out or delete one (clearing a bit might unset a bit some other item needs).

Complexity: how it scales

Add and query are both O(k) — a handful of hash computations and bit accesses, independent of how many items are stored. The space is the striking part: for a target false-positive rate p, the optimal filter uses m = −n·ln(p)/(ln2)² bits for n items, which is about 1.44·log₂(1/p) bits per item — roughly 9.6 bits per item for a 1% rate, or 14.4 for 0.1%, regardless of item size. The face-off compares that against a real set holding the same items:

Both grow linearly with the item count, but the Bloom filter's line sits far below the set's, and the gap is what matters. At a million 16-character keys with a 1% false-positive rate, the Bloom filter used about 1.2 megabytes (9.6 bits per item) while a real Python set needed about 122 megabytes — a hundredfold difference. And that gap widens with item size: the Bloom filter's 9.6 bits per item is fixed, so storing longer keys or whole documents makes the set balloon while the filter stays flat. This is the space/time trade-off Bloom named: you're not saving time (a set's lookup is already O(1)), you're saving memory, by an order of magnitude or more, in exchange for a controlled sprinkle of false positives. For a filter that lives in RAM to guard a database on disk, fitting in a hundredth of the memory is the difference between feasible and not.

What it's good at, what it isn't

Bloom filters are the right tool as a cheap pre-filter in front of an expensive operation, when the common answer is "not present" and a rare false positive only costs an unnecessary check (never a wrong result, if the expensive check is authoritative). The canonical uses: databases and storage engines (Bigtable, Cassandra, HBase, LevelDB, RocksDB) checking whether a key might be in an on-disk table before reading it, skipping the disk I/O for keys that definitely aren't there; CDNs and caches avoiding lookups for uncached objects; web browsers checking URLs against malicious-site lists (Google Safe Browsing); spell-checkers and word filters; distributed systems reducing network calls (does this node possibly have the data?); and deduplication (probably seen this already?). Anywhere memory is tight and a small false-positive rate is acceptable because it only triggers a fallback, the Bloom filter's order-of-magnitude space saving is decisive.

Where it's the wrong tool is when you need exactness (no tolerance for false positives), when you need to delete items (a standard Bloom filter can't — clearing a bit could break other items; a counting Bloom filter, which replaces bits with small counters, supports deletion at the cost of more space), when you need to enumerate or retrieve the stored items (impossible — only the bit shadows remain), or when you need to store associated values (it's a set, not a map). It also can't be resized easily once built (the hash positions assume a fixed m), and its false-positive rate degrades if you add more items than you sized it for. And for small item counts a real set is simpler and the memory saving is irrelevant. The Bloom filter is a specialist: approximate membership, no deletion, no enumeration, in exchange for tiny fixed space.

The data, or the inputs

The face-off compares the memory of an optimally-sized Bloom filter (1% false-positive rate) against a real Python set of 16-character keys, as the item count grows to a million. Correctness is checked hard: across many random filters, every added item must test present (a false negative would be impossible and a bug), and the measured false-positive rate — from tens of thousands of never-added queries — must stay close to the theoretical (1 − e^(−kn/m))^k. The animation builds a tiny 24-bit, 3-hash filter, adds cat, dog, and fox (watching bits turn on), then queries a member (all bits set → probably present), a true non-member (a 0 bit → definitely absent), and a word that's a false positive (all bits coincidentally set).

Build it, one function at a time

The Bloom filter — a bit array, k hashes by double hashing, add and query:

class BloomFilter:
    """A Bloom filter with m bits and k hash functions. The k hashes are derived from two base hashes
    by DOUBLE HASHING (h_i = h1 + i·h2), which behaves like k independent hashes without computing k
    of them."""

    def __init__(self, m_bits, k):
        self.m = m_bits
        self.k = k
        self.bits = bytearray((m_bits + 7) // 8)   # m bits, packed 8 per byte

    def _positions(self, item):
        data = repr(item).encode()
        h1 = int.from_bytes(hashlib.sha256(data).digest()[:8], "big")
        h2 = int.from_bytes(hashlib.md5(data).digest()[:8], "big") | 1   # odd, so it's coprime-ish with m
        for i in range(self.k):
            yield (h1 + i * h2) % self.m

    def add(self, item):
        """Set the k bits this item hashes to. Adding only ever turns bits ON — which is exactly why
        a Bloom filter can never produce a false negative."""
        for pos in self._positions(item):
            self.bits[pos >> 3] |= 1 << (pos & 7)

    def __contains__(self, item):
        """Probably-present if ALL k bits are set; definitely-absent if ANY is 0."""
        return all(self.bits[pos >> 3] & (1 << (pos & 7)) for pos in self._positions(item))

    def fill_ratio(self):
        """Fraction of bits currently set — used to sanity-check against the theoretical prediction."""
        return sum(bin(byte).count("1") for byte in self.bits) / self.m

Sizing it — the optimal bits and hash count for a target error rate, and the false-positive formula:

def optimal_params(n, target_fpr):
    """Given the expected number of items n and a target false-positive rate, the size m and hash
    count k that minimize memory. m = -n·ln(p) / (ln2)^2 bits, and the optimal k = (m/n)·ln2 — which
    works out to roughly 1.44·log2(1/p) bits per item, independent of the items' own size. Returns
    (m_bits, k)."""
    m = max(1, math.ceil(-n * math.log(target_fpr) / (math.log(2) ** 2)))
    k = max(1, round((m / n) * math.log(2)))
    return m, k


def theoretical_fpr(m, k, n):
    """The predicted false-positive rate after inserting n items into m bits with k hashes:
    (1 - e^(-k·n/m))^k. This is the formula a Bloom filter is designed around."""
    return (1 - math.exp(-k * n / m)) ** k

Watch it work

Here's a 24-bit Bloom filter with 3 hash functions. It starts all zeros. Adding cat sets its three hash positions to 1 (blue); dog and fox set three more each — bits only ever turn on. Now the queries. Asking for cat checks its three positions: all are 1 (green), so the filter reports "probably present" — correctly. Asking for a true non-member finds at least one position still 0 (red), which proves it was never added — the no-false-negatives guarantee, visible. And then the interesting case: a word that was never added, but whose three hash positions all happen to be bits that cat, dog, or fox already set. The filter checks them, finds all three are 1, and reports "probably present" — a false positive. Nothing is wrong; those bits are genuinely set, just by other items. That's the error the filter trades exactness for, and its rate is exactly what the sizing formula controls:

The complete code

The from-scratch tab is the Bloom filter plus the optimal-sizing math; the library tab is a real set — the exact reference the filter approximates and the memory baseline it beats — with a note on the production rbloom library. Flip between them: the set is exact and stores every item; the Bloom filter is approximate and stores none of them, which is the entire trade.

"""Bloom filter — a probabilistic set that answers "have I seen this?" using a tiny fraction of the
memory a real set needs, at the cost of occasional false positives (but NEVER false negatives). It's
the first of the tier's structures that trade exactness for a dramatic resource win, and the trade is
often worth it: a Bloom filter can represent millions of items in a few megabits and reject
never-seen items instantly, which is why it guards databases, caches, and browsers against expensive
lookups.

The structure is startlingly simple: a bit array of m bits, all zero, and k independent hash
functions. To ADD an item, hash it k ways and set those k bits to 1. To QUERY an item, hash it the
same k ways and check whether ALL k bits are 1. If any is 0, the item was definitely never added (no
false negatives — adding only ever sets bits). If all k are 1, the item is PROBABLY present, but
might be a false positive: those bits could have been set by other items. There's no way to remove an
item (clearing a bit might unset a bit another item needs) and no way to list what's stored. In
exchange, the space is a handful of bits per item regardless of how large the items themselves are.
"""
import hashlib
import math


# region: bloom
class BloomFilter:
    """A Bloom filter with m bits and k hash functions. The k hashes are derived from two base hashes
    by DOUBLE HASHING (h_i = h1 + i·h2), which behaves like k independent hashes without computing k
    of them."""

    def __init__(self, m_bits, k):
        self.m = m_bits
        self.k = k
        self.bits = bytearray((m_bits + 7) // 8)   # m bits, packed 8 per byte

    def _positions(self, item):
        data = repr(item).encode()
        h1 = int.from_bytes(hashlib.sha256(data).digest()[:8], "big")
        h2 = int.from_bytes(hashlib.md5(data).digest()[:8], "big") | 1   # odd, so it's coprime-ish with m
        for i in range(self.k):
            yield (h1 + i * h2) % self.m

    def add(self, item):
        """Set the k bits this item hashes to. Adding only ever turns bits ON — which is exactly why
        a Bloom filter can never produce a false negative."""
        for pos in self._positions(item):
            self.bits[pos >> 3] |= 1 << (pos & 7)

    def __contains__(self, item):
        """Probably-present if ALL k bits are set; definitely-absent if ANY is 0."""
        return all(self.bits[pos >> 3] & (1 << (pos & 7)) for pos in self._positions(item))

    def fill_ratio(self):
        """Fraction of bits currently set — used to sanity-check against the theoretical prediction."""
        return sum(bin(byte).count("1") for byte in self.bits) / self.m
# endregion


# region: params
def optimal_params(n, target_fpr):
    """Given the expected number of items n and a target false-positive rate, the size m and hash
    count k that minimize memory. m = -n·ln(p) / (ln2)^2 bits, and the optimal k = (m/n)·ln2 — which
    works out to roughly 1.44·log2(1/p) bits per item, independent of the items' own size. Returns
    (m_bits, k)."""
    m = max(1, math.ceil(-n * math.log(target_fpr) / (math.log(2) ** 2)))
    k = max(1, round((m / n) * math.log(2)))
    return m, k


def theoretical_fpr(m, k, n):
    """The predicted false-positive rate after inserting n items into m bits with k hashes:
    (1 - e^(-k·n/m))^k. This is the formula a Bloom filter is designed around."""
    return (1 - math.exp(-k * n / m)) ** k
# endregion

"""The contrast and the reference. A Bloom filter approximates a set, so the natural comparison is a
REAL set — exact membership, no false positives, but storing every element in full. Python's built-in
`set` is that reference: it's the correctness oracle (a Bloom filter must never report absent for
something a set contains) and the memory baseline the Bloom filter beats by orders of magnitude.

In production you'd use a maintained implementation like `rbloom` (a fast Rust-backed Bloom filter):

    from rbloom import Bloom
    bf = Bloom(1_000_000, 0.01)   # expected items, target false-positive rate
    bf.add("key"); "key" in bf

`exact_set_bytes` estimates the memory a real set would need, for the memory face-off.
"""
import sys


# region: exact_set
def exact_set_bytes(items):
    """A rough measure of the memory a real Python set of these items uses: the set's own overhead
    plus each element's object size. This is what a Bloom filter replaces with a fixed, tiny bit
    array — and it grows with both the number of items AND the size of each item, where the Bloom
    filter is independent of item size."""
    s = set(items)
    total = sys.getsizeof(s)
    for item in s:
        total += sys.getsizeof(item)
    return total
# endregion

Scratch vs library

The Bloom filter reframes what a data structure can be. Every structure before this tier was exact — it stored your data and answered questions about it correctly. The Bloom filter stores no data at all, only a lossy bit shadow, and answers a slightly weaker question (maybe-present) using a fraction of the space. That's a profound and useful bargain, and it's the founding idea of probabilistic data structures: HyperLogLog counts distinct elements in kilobytes regardless of the count, count-min sketch estimates frequencies in fixed space, cuckoo and quotient filters refine the Bloom trade-off. The lesson is that exactness is a resource you can spend — when a small, controlled error is acceptable, trading it away buys space (or time) you can't get any other way. The face-off's hundredfold memory saving is what that trade is worth in practice, and it scales further with item size because the filter's cost is item-size-independent. In production you'd use rbloom or a database's built-in filter; building one yourself is what makes "no false negatives, tunable false positives, item-size- independent space" concrete rather than a list of properties.

Where you'll actually meet it

Bloom filters run in the infrastructure under nearly every large system. Storage engines and databases — Cassandra, HBase, Bigtable, LevelDB, RocksDB, PostgreSQL extensions — use them to skip disk reads for absent keys, one of the highest-impact I/O optimizations in data systems. Web browsers use them (Google Safe Browsing) to check URLs against huge malware/phishing lists locally. CDNs and caches use them to avoid lookups for uncached content. Distributed systems use them to reduce network round-trips ("might this replica have the key?"). Cryptocurrency clients (Bitcoin SPV) used them to request relevant transactions without downloading everything. Spell-checkers, weak-password blocklists, ad-click deduplication, and recommendation systems ("has this user seen this item?") all use them. And the broader family — HyperLogLog for cardinality, count-min sketch for frequencies — powers analytics at scale (Redis, Presto, and streaming systems ship them). Anywhere a tiny approximate membership test can gate an expensive operation, a Bloom filter is likely doing it.

Takeaways

A Bloom filter is a bit array plus k hash functions that stores approximate set membership in a few bits per item — independent of item size — by setting k bits on add and checking them on query. A 0 bit proves absence (no false negatives, ever); k all-1 bits mean probably-present but may be a false positive, at a rate you tune with the sizing formula (~1.44·log₂(1/p) bits per item). It trades exactness, deletion, and enumeration for an order-of-magnitude space saving — a hundredfold at a 1% error rate for a million keys — which is why it guards databases, caches, and browsers as a cheap pre-filter. It's the founding example of trading exactness for resources, the theme of probabilistic data structures.

The next chapter keeps the theme of clever trade-offs but returns to exact structures, trading determinism for simplicity. Skip lists get the O(log n) search, insert, and delete of a balanced tree using nothing but linked lists and coin flips — randomization replacing the intricate rotations of AVL and red-black trees with a structure that's far easier to build and reason about, and that's used in real databases (Redis sorted sets, LevelDB) precisely for that simplicity.