Bloom Filter: Space-Efficient Set Membership

Key Insights

Bloom filters trade perfect accuracy for massive space savings—a filter storing 1 million items uses roughly 1.2 MB versus 40+ MB for a hash set, with only a 1% false positive rate.
The optimal number of hash functions is k = (m/n) * ln(2), where m is bit array size and n is expected elements—getting this wrong dramatically increases false positives.
Use Bloom filters when false positives are acceptable but false negatives are catastrophic, such as cache lookups, URL deduplication, or avoiding expensive disk operations.

What is a Bloom Filter?

A Bloom filter is a probabilistic data structure that answers one question: “Is this element possibly in the set, or definitely not?” It’s a space-efficient way to test set membership when you can tolerate occasional false positives but cannot accept false negatives.

The core trade-off is simple. When you query a Bloom filter, it returns one of two answers: “definitely not in the set” or “probably in the set.” The first answer is guaranteed correct. The second might be wrong—the element might not actually exist, but the filter thinks it does.

Think of it like a nightclub bouncer with a fuzzy memory. If the bouncer says “you’re definitely not on the list,” you’re not getting in. But if they say “yeah, I think I remember you,” they might be confusing you with someone else. The bouncer never forgets someone who’s actually on the list, but occasionally lets in someone who isn’t.

This asymmetry makes Bloom filters incredibly useful. In systems where checking the real data is expensive (disk reads, network calls, database queries), a Bloom filter acts as a cheap first pass. If it says “no,” you skip the expensive operation entirely. If it says “maybe,” you proceed with the full check.

How Bloom Filters Work

A Bloom filter consists of two components: a bit array of m bits (all initially set to 0) and k independent hash functions.

Insertion works as follows: when you add an element, you run it through all k hash functions. Each hash function produces an index into the bit array. You set all k corresponding bits to 1.

Lookup follows the same process: hash the element with all k functions, check all k bit positions. If any bit is 0, the element was definitely never added. If all bits are 1, the element is probably in the set—but those bits might have been set by different elements.

Here’s a basic implementation:

import hashlib

class SimpleBloomFilter:
    def __init__(self, size: int, num_hashes: int):
        self.size = size
        self.num_hashes = num_hashes
        self.bit_array = [False] * size
    
    def _get_hash_values(self, item: str) -> list[int]:
        """Generate k hash values for an item."""
        hashes = []
        for seed in range(self.num_hashes):
            # Create unique hash by combining item with seed
            data = f"{seed}:{item}".encode('utf-8')
            hash_value = int(hashlib.sha256(data).hexdigest(), 16)
            hashes.append(hash_value % self.size)
        return hashes
    
    def add(self, item: str) -> None:
        """Add an item to the filter."""
        for index in self._get_hash_values(item):
            self.bit_array[index] = True
    
    def contains(self, item: str) -> bool:
        """Check if item is possibly in the filter."""
        return all(self.bit_array[index] for index in self._get_hash_values(item))


# Usage
bf = SimpleBloomFilter(size=1000, num_hashes=3)
bf.add("apple")
bf.add("banana")

print(bf.contains("apple"))   # True (definitely added)
print(bf.contains("cherry"))  # False (definitely not added)
print(bf.contains("grape"))   # Might be True (false positive) or False

Understanding False Positive Probability

The false positive probability depends on three variables: bit array size (m), number of hash functions (k), and number of inserted elements (n).

After inserting n elements, the probability that a specific bit is still 0 is approximately:

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

The false positive probability—the chance that all k bits are set for an element not in the set—is:

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

The optimal number of hash functions that minimizes false positives is:

k_optimal = (m/n) * ln(2) ≈ 0.693 * (m/n)

Here’s how to calculate optimal parameters:

import math

def calculate_bloom_parameters(
    expected_items: int,
    false_positive_rate: float
) -> dict:
    """
    Calculate optimal Bloom filter parameters.
    
    Args:
        expected_items: Number of items you expect to insert
        false_positive_rate: Desired false positive probability (e.g., 0.01 for 1%)
    
    Returns:
        Dictionary with optimal size and hash count
    """
    # Optimal bit array size: m = -n * ln(p) / (ln(2)^2)
    m = -expected_items * math.log(false_positive_rate) / (math.log(2) ** 2)
    m = int(math.ceil(m))
    
    # Optimal number of hash functions: k = (m/n) * ln(2)
    k = (m / expected_items) * math.log(2)
    k = int(math.ceil(k))
    
    # Actual false positive rate with these parameters
    actual_fp_rate = (1 - math.exp(-k * expected_items / m)) ** k
    
    return {
        'bit_array_size': m,
        'num_hash_functions': k,
        'memory_bytes': m // 8,
        'memory_mb': m / 8 / 1024 / 1024,
        'actual_false_positive_rate': actual_fp_rate
    }


# Example: 1 million items with 1% false positive rate
params = calculate_bloom_parameters(1_000_000, 0.01)
print(f"Bit array size: {params['bit_array_size']:,} bits")
print(f"Hash functions: {params['num_hash_functions']}")
print(f"Memory: {params['memory_mb']:.2f} MB")
# Output:
# Bit array size: 9,585,059 bits
# Hash functions: 7
# Memory: 1.14 MB

Compare that 1.14 MB to a Python set storing 1 million strings, which would consume 40-80 MB depending on string lengths.

Implementing a Production-Ready Bloom Filter

For production use, swap SHA-256 for faster non-cryptographic hashes like MurmurHash3 or xxHash. The mmh3 library provides excellent performance:

import mmh3
import math
from typing import Union

class BloomFilter:
    def __init__(
        self,
        expected_items: int,
        false_positive_rate: float = 0.01
    ):
        # Calculate optimal parameters
        self.size = self._optimal_size(expected_items, false_positive_rate)
        self.num_hashes = self._optimal_hash_count(self.size, expected_items)
        self.bit_array = bytearray(math.ceil(self.size / 8))
        self.count = 0
    
    @staticmethod
    def _optimal_size(n: int, p: float) -> int:
        """Calculate optimal bit array size."""
        return int(-n * math.log(p) / (math.log(2) ** 2))
    
    @staticmethod
    def _optimal_hash_count(m: int, n: int) -> int:
        """Calculate optimal number of hash functions."""
        return max(1, int((m / n) * math.log(2)))
    
    def _get_hash_values(self, item: Union[str, bytes]) -> list[int]:
        """
        Generate k hash values using double hashing technique.
        Uses two hash functions to simulate k functions:
        h_i(x) = h1(x) + i * h2(x)
        """
        if isinstance(item, str):
            item = item.encode('utf-8')
        
        h1 = mmh3.hash(item, seed=0, signed=False)
        h2 = mmh3.hash(item, seed=h1, signed=False)
        
        return [(h1 + i * h2) % self.size for i in range(self.num_hashes)]
    
    def _set_bit(self, index: int) -> None:
        """Set a bit in the byte array."""
        byte_index = index // 8
        bit_offset = index % 8
        self.bit_array[byte_index] |= (1 << bit_offset)
    
    def _get_bit(self, index: int) -> bool:
        """Get a bit from the byte array."""
        byte_index = index // 8
        bit_offset = index % 8
        return bool(self.bit_array[byte_index] & (1 << bit_offset))
    
    def add(self, item: Union[str, bytes]) -> None:
        """Add an item to the filter."""
        for index in self._get_hash_values(item):
            self._set_bit(index)
        self.count += 1
    
    def contains(self, item: Union[str, bytes]) -> bool:
        """Check if item is possibly in the filter."""
        return all(self._get_bit(index) for index in self._get_hash_values(item))
    
    def __contains__(self, item: Union[str, bytes]) -> bool:
        """Support 'in' operator."""
        return self.contains(item)
    
    @property
    def memory_usage_bytes(self) -> int:
        """Return memory usage in bytes."""
        return len(self.bit_array)

The double hashing technique (h1 + i * h2) is a standard optimization that generates k hash values from just two hash computations, significantly improving performance.

Real-World Use Cases

Database query optimization: Before hitting disk, check if a key exists in the Bloom filter. LevelDB and RocksDB use this to avoid unnecessary SSTable reads.

Web crawlers: Track visited URLs without storing millions of full URLs in memory.

class WebCrawler:
    def __init__(self, max_urls: int = 10_000_000):
        self.visited = BloomFilter(
            expected_items=max_urls,
            false_positive_rate=0.001  # 0.1% false positives acceptable
        )
        self.queue = []
    
    def should_crawl(self, url: str) -> bool:
        """Check if URL should be crawled."""
        normalized = self._normalize_url(url)
        
        if normalized in self.visited:
            # Possibly visited - skip (false positive means we miss a page)
            return False
        
        return True
    
    def mark_visited(self, url: str) -> None:
        """Mark URL as visited."""
        normalized = self._normalize_url(url)
        self.visited.add(normalized)
    
    def _normalize_url(self, url: str) -> str:
        """Normalize URL for consistent hashing."""
        # Remove trailing slashes, lowercase, etc.
        return url.lower().rstrip('/')
    
    def crawl(self, seed_urls: list[str]) -> None:
        """Main crawl loop."""
        self.queue.extend(seed_urls)
        
        while self.queue:
            url = self.queue.pop(0)
            
            if not self.should_crawl(url):
                continue
            
            self.mark_visited(url)
            # ... fetch page, extract links, add to queue

CDN cache filtering: Quickly determine if content might be cached before checking the actual cache.

Spell checkers: Store a dictionary of valid words; any word not in the filter is definitely misspelled.

Variants and Extensions

Counting Bloom filters replace single bits with counters, enabling deletions. When you add an element, increment the counters; when you delete, decrement them. The trade-off is 3-4x more memory.

Scalable Bloom filters grow dynamically by chaining multiple filters. When one fills up, create a new one with a tighter false positive rate. Query all filters; if any says “no,” the element isn’t present.

Cuckoo filters offer better space efficiency for the same false positive rate and support deletions without the memory overhead of counting filters. Use them when you need deletion support and can accept slightly more complex implementation.

Trade-offs and When Not to Use

Bloom filters are wrong for several scenarios:

When false positives are unacceptable: Security checks, financial transactions, or anywhere a false positive causes real harm.
When you need the actual data back: Bloom filters only answer membership questions; they don’t store values.
When the set is small: Below a few thousand items, a regular hash set is simpler and often faster.
When deletion is frequent: Standard Bloom filters don’t support deletion. Use counting Bloom filters or Cuckoo filters instead.

Decision framework: Use a Bloom filter when (1) you’re checking membership before an expensive operation, (2) false positives just mean extra work rather than incorrect results, (3) the set is large enough that memory savings matter, and (4) you rarely or never need to delete elements.

For everything else, use a hash set. Simplicity wins when the constraints don’t demand otherwise.