Bloom Filters

Overview

A Bloom filter is a space-efficient probabilistic data structure that answers the question “Is this element in the set?” with two possible responses:

• “Definitely not in the set” — guaranteed correct
• “Probably in the set” — might be wrong (false positive)

This asymmetry makes Bloom filters incredibly useful as a cheap first check before performing an expensive operation. If the Bloom filter says “no,” you can skip the expensive lookup entirely. If it says “probably yes,” you do the full lookup to confirm.

Think of it like a bouncer at a club who checks a guest list. The bouncer might occasionally let someone in who isn’t on the list (false positive), but will never turn away someone who is on the list (no false negatives).

The Problem It Solves

Imagine you’re building a web crawler that has already visited 10 billion URLs. Before fetching a new URL, you need to check: “Have I already crawled this?” Your options:

A Bloom filter uses roughly 10 bits per element (vs 80+ bytes for storing the actual URL), achieving a 600x space reduction with only a 1% false positive rate.

How It Works

Structure

A Bloom filter consists of:

1. A bit array of m bits, all initialized to 0
2. k independent hash functions, each mapping an element to one of the m positions

Insert Operation

To add element x to the filter:

1. Compute h₁(x), h₂(x), ..., hₖ(x) — k hash positions
2. Set all k positions in the bit array to 1

Query Operation

To check if element x is in the set:

1. Compute h₁(x), h₂(x), ..., hₖ(x) — same k hash positions
2. If all k positions are 1 → “probably in the set”
3. If any position is 0 → “definitely not in the set”

graph TD
    subgraph "Bloom Filter (m=10 bits, k=3 hash functions)"
        BA["Bit Array: [0,1,0,1,0,0,1,0,1,0]"]
    end

    subgraph "Insert 'apple'"
        H1A["h₁('apple') = 1"] --> BA
        H2A["h₂('apple') = 3"] --> BA
        H3A["h₃('apple') = 6"] --> BA
    end

    subgraph "Insert 'banana'"
        H1B["h₁('banana') = 3"] --> BA
        H2B["h₂('banana') = 8"] --> BA
        H3B["h₃('banana') = 1"] --> BA
    end

    subgraph "Query 'cherry'"
        H1C["h₁('cherry') = 1 → bit=1 ✓"]
        H2C["h₂('cherry') = 4 → bit=0 ✗"]
        H3C["h₃('cherry') = 6 → bit=1 ✓"]
        Result["Result: DEFINITELY NOT in set"]
    end

Why False Positives Happen

When multiple elements are inserted, their hash positions can overlap. An element that was never inserted might have all its hash positions set to 1 by other elements — a false positive.

The false positive probability p depends on:

• m — number of bits in the array
• n — number of elements inserted
• k — number of hash functions

The optimal number of hash functions is: k = (m/n) × ln(2) ≈ 0.693 × (m/n)

The false positive rate is approximately: p ≈ (1 - e^(-kn/m))^k

Practical Sizing

Rule of thumb: ~10 bits per element for 1% false positive rate.

Variations

Counting Bloom Filter

Replaces each bit with a counter (usually 4 bits). This allows deletions — decrement the counters for the element’s hash positions. Standard Bloom filters cannot support deletion because clearing a bit might affect other elements.

Cuckoo Filter

A more modern alternative that:

• Supports deletion (without counters)
• Has better space efficiency for false positive rates below 3%
• Uses cuckoo hashing with fingerprints
• Often preferred over Bloom filters in practice

Scalable Bloom Filter

Dynamically grows by adding new Bloom filter layers when the false positive rate exceeds a threshold. Each new layer has a tighter false positive rate to maintain the overall guarantee.

Partitioned Bloom Filter

Divides the bit array into k partitions, one per hash function. Each hash function only sets bits in its partition. Slightly worse false positive rate but better cache performance.

When to Use / When Not to Use

Use Bloom Filters When

• Avoiding expensive lookups: Check a Bloom filter before querying a database or making a network call
• Saving space: You need to track membership of a very large set with limited memory
• False positives are tolerable: A small percentage of unnecessary lookups is acceptable
• Deletion is not required: Standard Bloom filters are insert-only (use Cuckoo filters if you need deletion)

Don’t Use Bloom Filters When

• You need exact answers: No false positives allowed
• The set is small: If the set fits in a hash set, just use a hash set
• You need deletion: Standard Bloom filters can’t delete (use Counting Bloom or Cuckoo filters)
• You need to enumerate elements: Bloom filters don’t store elements, only membership information

Real-World Examples

Cassandra (SSTable Lookups)

When Cassandra reads a key, it might need to check multiple SSTables (sorted string tables) on disk. Each SSTable has an associated Bloom filter in memory. Before performing an expensive disk read, Cassandra checks the Bloom filter:

• If the Bloom filter says “no” → skip this SSTable entirely (saves a disk seek)
• If the Bloom filter says “maybe” → read the SSTable index to confirm

This turns most negative lookups from O(disk seek) to O(1 in-memory check).

Google Chrome (Malicious URL Detection)

Chrome checks every URL the user visits against a list of known malicious URLs. The full list is too large to download to every browser. Instead:

1. A Bloom filter of malicious URLs is shipped with Chrome (~25MB for millions of URLs)
2. Every URL is checked against the local Bloom filter
3. If the Bloom filter says “no” → the URL is safe (instant, no network call)
4. If the Bloom filter says “maybe” → Chrome queries Google’s Safe Browsing API to confirm

This avoids a network roundtrip for 99%+ of URL checks.

Medium (Article Recommendations)

Medium uses Bloom filters to avoid recommending articles a user has already read. For each user, a Bloom filter tracks read article IDs. When generating recommendations, articles that match the Bloom filter are excluded.

A false positive means occasionally hiding an unread article (minor issue), but a false negative would mean re-recommending an already-read article (poor UX). Bloom filters’ guarantee of no false negatives makes them ideal here.

HBase / LevelDB / RocksDB (LSM Tree Storage)

LSM tree-based storage engines use Bloom filters at each level to avoid unnecessary reads during compaction and point lookups. Since LSM trees can have data spread across many levels, Bloom filters dramatically reduce the number of levels that need to be checked.

Bitcoin (SPV Clients)

Lightweight Bitcoin clients use Bloom filters to request only transactions relevant to their wallet from full nodes, without revealing exactly which addresses they own. The full node applies the Bloom filter to each transaction and sends matches (plus false positives for privacy).

Implementation

A simple Bloom filter implementation in Python:

import hashlib
import math

class BloomFilter:
    def __init__(self, expected_elements: int, fp_rate: float = 0.01):
        # Calculate optimal size and hash count
        self.size = int(-expected_elements * math.log(fp_rate) / (math.log(2) ** 2))
        self.hash_count = int(self.size / expected_elements * math.log(2))
        self.bit_array = [0] * self.size

    def _hashes(self, item: str) -> list[int]:
        """Generate k hash positions using double hashing."""
        h1 = int(hashlib.md5(item.encode()).hexdigest(), 16)
        h2 = int(hashlib.sha1(item.encode()).hexdigest(), 16)
        return [(h1 + i * h2) % self.size for i in range(self.hash_count)]

    def add(self, item: str):
        for pos in self._hashes(item):
            self.bit_array[pos] = 1

    def might_contain(self, item: str) -> bool:
        return all(self.bit_array[pos] for pos in self._hashes(item))

Interview Questions

Bloom filter concepts appear in system design and data structure interviews:

• “Design a web crawler — how do you avoid re-crawling URLs?” — Bloom filter for the visited URL set
• “How does Cassandra optimize read performance?” — Bloom filters on SSTables to skip unnecessary disk reads
• “Design a spam filter” — Bloom filter for known spam signatures
• “What’s the trade-off between a hash set and a Bloom filter?” — Space (10 bits/element vs 80+ bytes/element) vs accuracy (probabilistic vs exact)
• “Can you delete from a Bloom filter?” — No from standard Bloom filter; yes from Counting Bloom filter or Cuckoo filter
• “How do you choose the size of a Bloom filter?” — m = -n×ln(p) / (ln2)², k = (m/n)×ln(2)