Bloom Filters: Probabilistic Membership Testing

Key Insights

Bloom filters trade certainty for dramatic space efficiency—they can tell you “definitely not in the set” or “probably in the set,” using a fraction of the memory required for exact membership testing.
The math is surprisingly approachable: with the right parameters, you can achieve a 1% false positive rate while using only about 10 bits per element, regardless of element size.
Most production use cases involve preventing expensive operations—disk reads, network requests, or database queries—making the occasional false positive a worthwhile tradeoff.

The Membership Problem

Every system eventually faces the same question: “Have I seen this before?” Whether you’re checking if a URL has been crawled, if a username exists, or if a cache key might be valid, membership testing becomes a bottleneck at scale.

The naive approach—storing every element in a hash set—works until it doesn’t. A billion URLs at 50 bytes each consumes 50 GB of memory. That’s before accounting for hash table overhead, which typically doubles or triples the requirement.

Bloom filters offer a radical alternative: accept a small probability of false positives in exchange for massive space savings. A Bloom filter can represent that same billion URLs in roughly 1.2 GB while maintaining a 1% false positive rate. The tradeoff is asymmetric and favorable—you’ll never get a false negative, meaning if the filter says “not present,” you can trust it completely.

How Bloom Filters Work

A Bloom filter consists of two components: a bit array of m bits (initially all zeros) and k independent hash functions. Each hash function maps an input to a position in the bit array.

Insertion works by hashing the element with each hash function and setting the corresponding bits to 1. If a bit is already 1, it stays 1.

Lookup hashes the element with the same functions and checks if all corresponding bits are 1. If any bit is 0, the element was definitely never inserted. If all bits are 1, the element is probably in the set—but those bits might have been set by other elements.

This explains the asymmetry: false negatives are impossible because we never unset bits. False positives occur when different elements happen to set overlapping bits.

import hashlib
from typing import List

class BloomFilter:
    def __init__(self, size: int, num_hashes: int):
        self.size = size
        self.num_hashes = num_hashes
        self.bit_array = [False] * size
    
    def _hashes(self, item: str) -> List[int]:
        """Generate k hash values for an item."""
        positions = []
        for i in range(self.num_hashes):
            # Use SHA-256 with different seeds for each hash
            h = hashlib.sha256(f"{i}:{item}".encode()).hexdigest()
            position = int(h, 16) % self.size
            positions.append(position)
        return positions
    
    def insert(self, item: str) -> None:
        """Add an item to the filter."""
        for position in self._hashes(item):
            self.bit_array[position] = True
    
    def contains(self, item: str) -> bool:
        """Check if an item might be in the filter.
        
        Returns:
            False: Definitely not in the set
            True: Probably in the set (may be false positive)
        """
        return all(self.bit_array[pos] for pos in self._hashes(item))


# Usage
bf = BloomFilter(size=1000, num_hashes=7)
bf.insert("hello")
bf.insert("world")

print(bf.contains("hello"))  # True (correct)
print(bf.contains("world"))  # True (correct)
print(bf.contains("foo"))    # False (definitely not present)

The Math Behind the Magic

Three parameters govern Bloom filter behavior: the bit array size (m), the number of hash functions (k), and the expected number of elements (n). These determine the false positive probability (p).

The false positive probability after inserting n elements is approximately:

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

Given a target false positive rate and expected element count, the optimal parameters are:

m = -n * ln(p) / (ln(2)^2)
k = (m/n) * ln(2)

In practice, this means roughly 10 bits per element for a 1% false positive rate, or 15 bits per element for 0.1%.

import math
from dataclasses import dataclass

@dataclass
class BloomFilterParams:
    size: int           # m: bit array size
    num_hashes: int     # k: number of hash functions
    false_positive_rate: float
    memory_bytes: int

def calculate_bloom_params(
    expected_elements: int, 
    target_fp_rate: float
) -> BloomFilterParams:
    """Calculate optimal Bloom filter parameters.
    
    Args:
        expected_elements: Number of elements to insert (n)
        target_fp_rate: Desired false positive probability (p)
    
    Returns:
        Optimal filter parameters
    """
    # Optimal bit array size
    m = -expected_elements * math.log(target_fp_rate) / (math.log(2) ** 2)
    m = int(math.ceil(m))
    
    # Optimal number of hash functions
    k = (m / expected_elements) * math.log(2)
    k = int(math.ceil(k))
    
    # Actual false positive rate with these parameters
    actual_fp = (1 - math.exp(-k * expected_elements / m)) ** k
    
    return BloomFilterParams(
        size=m,
        num_hashes=k,
        false_positive_rate=actual_fp,
        memory_bytes=m // 8
    )


# Example: 1 million URLs with 1% false positive rate
params = calculate_bloom_params(1_000_000, 0.01)
print(f"Bit array size: {params.size:,} bits")
print(f"Hash functions: {params.num_hashes}")
print(f"Memory: {params.memory_bytes:,} bytes ({params.memory_bytes / 1024 / 1024:.2f} MB)")
print(f"Actual FP rate: {params.false_positive_rate:.4%}")

# Output:
# Bit array size: 9,585,059 bits
# Hash functions: 7
# Memory: 1,198,132 bytes (1.14 MB)
# Actual FP rate: 1.0015%

Practical Implementation Considerations

The naive implementation above has problems: SHA-256 is slow, and generating k independent hashes is wasteful. Production implementations use faster hash functions and a technique called double hashing.

Double hashing generates two base hashes and combines them to produce k values:

hash_i(x) = hash1(x) + i * hash2(x) mod m

This is mathematically sound and dramatically faster.

import mmh3  # pip install mmh3
from bitarray import bitarray  # pip install bitarray

class ProductionBloomFilter:
    """Memory-efficient Bloom filter using MurmurHash3."""
    
    def __init__(self, expected_elements: int, fp_rate: float = 0.01):
        params = calculate_bloom_params(expected_elements, fp_rate)
        self.size = params.size
        self.num_hashes = params.num_hashes
        self.bit_array = bitarray(self.size)
        self.bit_array.setall(0)
        self._count = 0
    
    def _hashes(self, item: str) -> list:
        """Generate k positions using double hashing with MurmurHash3."""
        # Get two 64-bit hashes from mmh3
        h1 = mmh3.hash64(item, seed=0, signed=False)[0]
        h2 = mmh3.hash64(item, seed=1, signed=False)[0]
        
        return [(h1 + i * h2) % self.size for i in range(self.num_hashes)]
    
    def insert(self, item: str) -> None:
        for pos in self._hashes(item):
            self.bit_array[pos] = True
        self._count += 1
    
    def contains(self, item: str) -> bool:
        return all(self.bit_array[pos] for pos in self._hashes(item))
    
    def save(self, filepath: str) -> None:
        """Serialize filter to disk."""
        with open(filepath, 'wb') as f:
            self.bit_array.tofile(f)
    
    @classmethod
    def load(cls, filepath: str, expected_elements: int, fp_rate: float = 0.01):
        """Load filter from disk."""
        bf = cls(expected_elements, fp_rate)
        with open(filepath, 'rb') as f:
            bf.bit_array = bitarray()
            bf.bit_array.fromfile(f)
        return bf

Real-World Use Cases

Database query optimization is the canonical use case. Before hitting disk to check if a key exists, consult an in-memory Bloom filter. A false positive means an unnecessary disk read; a true negative saves one entirely. LevelDB and RocksDB use this technique for each SSTable.

Web crawlers need to track billions of visited URLs. A Bloom filter lets you skip URLs you’ve definitely seen while occasionally re-crawling a URL (false positive manifests as skipping a new URL that hashes similarly to visited ones).

from urllib.parse import urlparse
import requests

class WebCrawler:
    def __init__(self, max_urls: int = 10_000_000):
        self.visited = ProductionBloomFilter(max_urls, fp_rate=0.001)
        self.queue = []
    
    def normalize_url(self, url: str) -> str:
        """Normalize URL for consistent hashing."""
        parsed = urlparse(url.lower())
        # Remove fragments, normalize path
        return f"{parsed.scheme}://{parsed.netloc}{parsed.path}"
    
    def should_crawl(self, url: str) -> bool:
        """Check if URL should be crawled."""
        normalized = self.normalize_url(url)
        if self.visited.contains(normalized):
            return False  # Probably visited (or false positive)
        return True
    
    def mark_visited(self, url: str) -> None:
        """Mark URL as visited."""
        self.visited.insert(self.normalize_url(url))
    
    def crawl(self, url: str) -> None:
        if not self.should_crawl(url):
            return
        
        self.mark_visited(url)
        # Actual crawling logic here
        print(f"Crawling: {url}")

CDN caching uses Bloom filters to track which objects are worth caching. An object must be requested multiple times before caching, and a Bloom filter efficiently tracks “seen once” status without storing actual keys.

Variants and Extensions

Counting Bloom filters replace each bit with a counter, enabling deletions. When inserting, increment counters; when deleting, decrement them. The tradeoff is 3-4x memory overhead.

Scalable Bloom filters chain multiple filters together, adding new ones as capacity fills. This handles unknown cardinality at the cost of slightly higher false positive rates.

Cuckoo filters offer an alternative with better space efficiency, deletion support, and faster lookups in many cases. They use cuckoo hashing with fingerprints instead of multiple hash functions. Consider them for new projects where deletion is required.

When Not to Use Bloom Filters

Bloom filters aren’t universal. Avoid them when:

You need deletions from a standard Bloom filter. Once a bit is set, you can’t safely unset it without potentially breaking other elements. Use counting Bloom filters or cuckoo filters instead.

False positives are unacceptable. If a false positive causes security issues, data corruption, or significant cost, you need exact membership testing.

The element set is small. Below a few thousand elements, a hash set is simpler and the memory savings are negligible.

You need to enumerate members. Bloom filters are write-only in a sense—you can’t retrieve what’s been inserted.

The decision comes down to economics: how expensive is a false positive versus the memory cost of exact membership testing? When checking membership gates an expensive operation—disk I/O, network requests, database queries—Bloom filters almost always win. When the downstream cost of a false positive exceeds the memory savings, stick with exact data structures.