The Power of Elegant Simplicity #2: Bloom Filters — The Data Structure That's Okay With Being Wrong ▪ Extiri Blog

Part of the “The Power of Elegant Simplicity” series - algorithms that hide power in plain sight

You know what’s refreshing? An algorithm that looks you in the eye, shrugs, and says: “Look, I might be wrong. But I’m never wrong in that direction.”

Welcome to Bloom Filters — a probabilistic data structure so audaciously simple that it uses a handful of hash functions and a bit array to answer membership queries at lightning speed. No linked lists, no tree traversals, no disk reads. Just bits and honesty about its own limitations.

The Problem: Checking Without Knowing Everything

Let’s say you’re building a web crawler. Every second, you’re discovering thousands of URLs. You need to know: have I visited this URL before?

One approach: keep a giant set of every URL you’ve ever seen. Query it before each visit.

Sounds fine, until you realize you’ve crawled a billion pages. Storing a billion URLs takes serious memory — often tens or hundreds of gigabytes. Suddenly your crawler is spending more time juggling memory than actually crawling.

What if you could answer “have I seen this before?” using a fraction of the memory? What if the only trade-off was occasionally a false positive — claiming you’ve seen something you haven’t?

For many applications, that’s a completely acceptable deal. You re-check false positives. You never miss true ones.

That’s Bloom Filters in a nutshell.

The Ingredients: Embarrassingly Simple

A Bloom Filter is just two things:

A bit array of size m, initialized to all zeros.
k independent hash functions, each mapping any input to an index in [0, m-1].

That’s it. No pointers. No nodes. No dynamic allocation. Just a flat array of bits and some hash functions.

![Bloom Filter diagram showing a bit array with bits set by multiple hash functions for two elements]

How It Works: Inserting an Element

When you want to add an element to the filter, you run it through all k hash functions. Each one gives you an index. You flip those k bits in the array to 1.

def add(bloom_filter, item, hash_functions, m):
    """
    Add an item to the Bloom Filter.
    
    Args:
        bloom_filter: List of m bits (integers 0 or 1)
        item: The item to add
        hash_functions: List of k hash functions
        m: Size of the bit array
    """
    for h in hash_functions:
        index = h(item) % m
        bloom_filter[index] = 1

Let’s say we have a bit array of size 16 and 3 hash functions. We add the word "apple":

h1("apple") % 16 = 3 → set bit 3
h2("apple") % 16 = 7 → set bit 7
h3("apple") % 16 = 13 → set bit 13

Now we add "banana":

h1("banana") % 16 = 0 → set bit 0
h2("banana") % 16 = 7 → set bit 7 (already set — no problem)
h3("banana") % 16 = 11 → set bit 11

Our filter after two insertions:

Index: 0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15
Bits:  1  0  0  1  0  0  0  1  0  0  0  1  0  1  0  0

How It Works: Querying an Element

To check if an element is in the set, run it through all k hash functions and look up those indices.

If any bit is 0 → the element is definitely not in the set. No way around it. You never set those bits, so the element was never added.
If all bits are 1 → the element is probably in the set.

def contains(bloom_filter, item, hash_functions, m):
    """
    Check if an item is probably in the set.
    
    Returns:
        False: Item is DEFINITELY NOT in the set.
        True:  Item is PROBABLY in the set (might be a false positive).
    """
    for h in hash_functions:
        index = h(item) % m
        if bloom_filter[index] == 0:
            return False
    return True

Let’s check for "cherry":

h1("cherry") % 16 = 3 → bit 3 is 1 ✓
h2("cherry") % 16 = 7 → bit 7 is 1 ✓
h3("cherry") % 16 = 11 → bit 11 is 1 ✓

All bits are set! But we never added "cherry". This is a false positive — "cherry" just happened to hash to positions that were already set by "apple" and "banana". The filter says “probably yes” when the truth is “definitely no.”

This is the deal you make with a Bloom Filter. You accept the occasional false positive. In return, you get blazing-fast queries and microscopic memory usage.

Crucially, there are no false negatives. If an element was added, every bit it set stays set — they’ll all be 1 when you query. The filter will never tell you “not in set” when it actually is.

The Math Behind the Trade-Off

Here’s where it gets surprisingly elegant. The false positive rate is not arbitrary or unpredictable — it’s precisely calculable.

Given:

m = size of the bit array
n = number of elements inserted
k = number of hash functions

The probability of a false positive is approximately:

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

This formula is beautiful because it tells you exactly how to tune your filter:

The optimal number of hash functions for a given m and n is:

1	k = (m/n) * ln(2) ≈ 0.693 * (m/n)

The required bit array size to achieve a target false positive rate p:

1	m = -n * ln(p) / (ln(2))²

Let’s say you want to track 1 million URLs with a 1% false positive rate. How much memory do you need?

import math

n = 1_000_000  # elements
p = 0.01       # 1% false positive rate

m = -n * math.log(p) / (math.log(2) ** 2)
k = (m / n) * math.log(2)

print(f"Bit array size: {m:,.0f} bits ({m / 8 / 1024 / 1024:.2f} MB)")
print(f"Optimal hash functions: {k:.1f}")

Output:

Bit array size: 9,585,059 bits (1.14 MB)
Optimal hash functions: 6.6

1.14 megabytes to track a million URLs with 1% false positives. A naive Python set of those same URLs would consume hundreds of megabytes. Often an order of magnitude or more of memory reduction.

A Complete Implementation

Here’s a clean, practical Bloom Filter using Python:

import math
import hashlib


class BloomFilter:
    """
    A space-efficient probabilistic data structure for set membership queries.
    
    Guarantees:
        - No false negatives: if an item was added, contains() always returns True.
        - Bounded false positives: probability is calculable from n, m, and k.
    """
    
    def __init__(self, capacity: int, error_rate: float = 0.01):
        """
        Initialize a Bloom Filter.
        
        Args:
            capacity: Expected number of elements to insert.
            error_rate: Desired false positive probability (e.g., 0.01 = 1%).
        """
        self.capacity = capacity
        self.error_rate = error_rate
        
        # Calculate optimal parameters
        self.m = self._optimal_m(capacity, error_rate)
        self.k = self._optimal_k(self.m, capacity)
        
        # Bit array using a bytearray for memory efficiency
        self.bit_array = bytearray(math.ceil(self.m / 8))
        self.count = 0
        
        print(f"Bloom Filter initialized:")
        print(f"  Bit array size: {self.m:,} bits ({self.m / 8 / 1024:.1f} KB)")
        print(f"  Hash functions: {self.k}")
    
    @staticmethod
    def _optimal_m(n: int, p: float) -> int:
        """Optimal bit array size for n elements and false positive rate p."""
        return math.ceil(-n * math.log(p) / (math.log(2) ** 2))
    
    @staticmethod
    def _optimal_k(m: int, n: int) -> int:
        """Optimal number of hash functions."""
        return max(1, round((m / n) * math.log(2)))
    
    def _hash_indices(self, item: str):
        """Generate k hash indices for an item using double hashing."""
        # Two base hashes from different algorithms
        h1 = int(hashlib.md5(item.encode()).hexdigest(), 16)
        h2 = int(hashlib.sha1(item.encode()).hexdigest(), 16)
        
        # Generate k indices using linear combination (Kirsch-Mitzenmacher)
        for i in range(self.k):
            yield (h1 + i * h2) % self.m
    
    def _set_bit(self, index: int):
        byte_index = index // 8
        bit_offset = index % 8
        self.bit_array[byte_index] |= (1 << bit_offset)
    
    def _get_bit(self, index: int) -> bool:
        byte_index = index // 8
        bit_offset = index % 8
        return bool(self.bit_array[byte_index] & (1 << bit_offset))
    
    def add(self, item: str):
        """Add an item to the filter."""
        for index in self._hash_indices(item):
            self._set_bit(index)
        self.count += 1
    
    def contains(self, item: str) -> bool:
        """
        Check if item is in the set.
        
        Returns:
            False → item is DEFINITELY NOT in the set.
            True  → item is PROBABLY in the set (may be a false positive).
        """
        return all(self._get_bit(index) for index in self._hash_indices(item))
    
    @property
    def estimated_false_positive_rate(self) -> float:
        """Estimated current false positive rate based on elements inserted."""
        return (1 - math.e ** (-self.k * self.count / self.m)) ** self.k


# Example: URL deduplication for a web crawler
bf = BloomFilter(capacity=1_000_000, error_rate=0.01)

urls_to_crawl = [
    "https://example.com/page-1",
    "https://example.com/page-2",
    "https://example.com/page-1",  # Duplicate!
]

for url in urls_to_crawl:
    if bf.contains(url):
        print(f"Skipping (already seen): {url}")
    else:
        bf.add(url)
        print(f"Crawling: {url}")

# Output:
# Crawling: https://example.com/page-1
# Crawling: https://example.com/page-2
# Skipping (already seen): https://example.com/page-1

Note, this implementation uses cryptographic hashes for simplicity, but in production, you should use other faster hash functions.

Notice the use of the Kirsch-Mitzenmacher trick: instead of implementing k fully independent hash functions (expensive and complex), we use two base hashes and linearly combine them: h(i) = h1 + i * h2. It’s been mathematically proven to achieve asymptotically the same error rate as truly independent hashes — another layer of elegance.

Why This is Actually Mind-Blowing

Memory efficiency that borders on magical: You’re representing the possible presence of millions of items in a structure orders of magnitude smaller than the items themselves. You’re storing shadows of items, not the items.

Constant time, always: Both add and contains are O(k) — constant with respect to the number of elements in the filter. Whether you’ve inserted ten items or ten billion, each query runs through exactly k hash functions and looks up k bits. No searching, no sorting, no tree traversal.

Tunable trade-offs: The relationship between memory, speed, and accuracy is explicit and mathematical. You’re not guessing — you’re engineering. Want 0.1% false positives instead of 1%? The formula tells you exactly how many more bits you need.

Asymmetric error: False negatives are impossible. This asymmetry is often exactly what you want. In caching, in spam filtering, in security — you’d much rather occasionally check something twice than miss something you should have caught.

The Real-World Roster

Bloom Filters aren’t academic curiosities. They’re quietly running in systems you use every day:

Google Chrome’s Safe Browsing: Before making a network call to check if a URL is malicious, Chrome checks a local Bloom Filter. If it’s definitely not in the filter, no network call needed. Only potential hits require verification. This makes Safe Browsing both fast and private.

Apache Cassandra and other databases: Cassandra uses Bloom Filters to avoid disk reads. Before checking whether a row exists in an SSTable (which requires an expensive I/O operation), it checks the filter. A definite miss skips the disk entirely.

Bitcoin: Bitcoin’s SPV (Simple Payment Verification) nodes use Bloom Filters to request only relevant transactions from full nodes, without revealing exactly which addresses they’re interested in.

Akamai CDN: One of the largest CDN operators uses Bloom Filters to avoid caching “one-hit-wonders” — URLs requested exactly once, which would pollute the cache without providing value to future users. The filter tracks whether a URL has been seen before; it only gets cached on the second hit.

Medium, Reddit, and recommendation systems: To avoid showing you the same article twice, these platforms can use Bloom Filters to track what you’ve already seen — per user, at scale, with negligible memory overhead.

The Limitations (Honesty Is Part of the Package)

No deletions (mostly): Once a bit is set to 1, you can’t safely set it back to 0 — other elements might share that bit. If you need deletions, you need a Counting Bloom Filter, which stores counters instead of bits (incrementing on add, decrementing on remove). This trades some memory efficiency for mutability.

No retrieval: A Bloom Filter tells you whether something is in the set, not what is in the set. You can’t iterate over elements. You can’t get an element back. It’s pure membership testing.

One-way resizing: Unlike a hash table, you can’t cleanly resize a Bloom Filter. If you add far more elements than planned, your false positive rate degrades. You’d need to rebuild from scratch. Plan your capacity upfront, or use scalable Bloom Filters — a layered approach that adds new filter layers as capacity fills.

Hash function quality matters: Poor hash functions lead to clustering — many items mapping to the same bits — which inflates the false positive rate. Use cryptographic or well-tested non-cryptographic hashes (MurmurHash3, xxHash, FNV-1a) in production. The Kirsch-Mitzenmacher trick helps you get away with two good hashes instead of implementing k fully independent ones.

The Philosophical Bit

Here’s what I find most elegant about Bloom Filters: they institutionalize the right kind of uncertainty.

Most data structures pretend certainty. Hash tables say “definitely yes” or “definitely no.” Binary search trees say “this is exactly where it is.” That’s usually what you want.

But Bloom Filters say something more nuanced: “I can tell you for certain when something is NOT here. As for whether it IS here — I’m probably right, but you might want to double-check.”

This asymmetric honesty is surprisingly powerful. In many real systems, a definite “no” is more valuable than a certain “yes” — because “no” lets you skip expensive work entirely.

It’s a bit like a good bouncer who never lets innocent people through by mistake — but occasionally turns away someone with a slightly unusual ID. The asymmetry is the feature, not the bug.

Try It Yourself

Here’s a small experiment to make the math tangible:

import math
import hashlib
import random
import string


def make_bloom_filter(capacity, error_rate):
    m = math.ceil(-capacity * math.log(error_rate) / (math.log(2) ** 2))
    k = max(1, round((m / capacity) * math.log(2)))
    bits = bytearray(math.ceil(m / 8))
    
    def hashes(item):
        h1 = int(hashlib.md5(item.encode()).hexdigest(), 16)
        h2 = int(hashlib.sha1(item.encode()).hexdigest(), 16)
        return [(h1 + i * h2) % m for i in range(k)]
    
    def add(item):
        for idx in hashes(item):
            bits[idx // 8] |= (1 << (idx % 8))
    
    def contains(item):
        return all(bits[idx // 8] & (1 << (idx % 8)) for idx in hashes(item))
    
    return add, contains, m, k


# Create a filter for 10,000 items at 1% false positive rate
add, contains, m, k = make_bloom_filter(10_000, 0.01)
print(f"Bit array: {m:,} bits | Hash functions: {k}")

# Add 10,000 random "known" items
known = set()
for _ in range(10_000):
    word = ''.join(random.choices(string.ascii_lowercase, k=10))
    known.add(word)
    add(word)

# Test 10,000 "unknown" items and count false positives
false_positives = 0
trials = 10_000
for _ in range(trials):
    word = ''.join(random.choices(string.ascii_lowercase, k=12))  # longer = unlikely to collide
    if word not in known and contains(word):
        false_positives += 1

print(f"False positive rate: {false_positives / trials:.2%}  (target: 1.00%)")
print(f"False negatives: 0  (guaranteed by construction)")

Run it yourself and watch the false positive rate hover right around 1% — not by luck, but by math.

The Takeaway

Bloom Filters are the rare algorithm that teaches you something philosophical alongside something practical.

Practically: you can represent set membership for millions of items in kilobytes of memory, with constant-time operations, by accepting a controllable, asymmetric error rate.

Philosophically: sometimes the most powerful thing you can do is clearly define what kind of wrong you’re willing to be — and build that honesty into your system’s architecture.

A bit array and some hash functions. Probabilistic guarantees that hold up under mathematical scrutiny. Deployed at Google, Cassandra, Bitcoin, and your browser.

Elegant. Simple. Hiding something powerful in plain sight.

Further Reading:

Burton Howard Bloom’s original 1970 paper — only 3 pages long, and surprisingly readable
Kirsch & Mitzenmacher (2006) — proof that double hashing works as well as independent hashes
Network Applications of Bloom Filters: A Survey — an exhaustive look at real-world applications