Bloom Filters

Concept. A Bloom filter stores a set in a bit array and uses k hash functions to map each item to k bit positions. It answers membership queries in constant time with two outcomes: "definitely not in the set" or "probably in the set." It uses about 10 bits per item, far less than a hash set, and it produces no false negatives.

Intuition. A Bloom filter over Listens.song_id fits in a few KB at this scale. Before reading any page, probe the filter with "is song X here?" A "no" answer eliminates the page read. A "maybe" answer triggers the real read. True misses skip the page read in almost all cases.

Space-efficient probabilistic data structure

Tells you "definitely not in set" or "maybe in set".

Visual: How Bloom Filters Work

A 16-bit array; bits 3, 7, 9, 11, and 14 are set (orange), the rest are unset (white). INSERT "alice" hashes to bits 3, 7, 14 and sets them. LOOKUP "bob" hashes to bits 3, 9, 2; bit 2 is 0, so "bob" is definitely not in the set. Color key: orange is a set bit, grey is an unset bit, green is a guaranteed answer.

Figure 1. A Bloom filter stores a 16-bit array and k = 3 hash functions. INSERT "alice" hashes to bits 3, 7, and 14 and sets them (orange). Earlier inserts also set bits 9 and 11. LOOKUP "bob" hashes to bits 3, 9, and 2. bit[2] = 0 guarantees "bob" is not in the set (green). Any 0 bit implies "definitely not in the set." All 1s imply "probably in the set," so false positives occur and false negatives do not.

The false-positive rate is p ≈ (1 − e^−kn/m)^k, minimized at k = (m/n) · ln 2. At about 10 bits per item with optimal k ≈ 7 the rate is about 1%, so a billion-item filter needs only ~1.25 GB of bits, versus tens of GB for an equivalent in-memory hash set. That space saving, at the cost of a small false-positive rate, is why Bloom filters guard expensive lookups.

Problem-Solving Applications

For detailed examples of how Bloom filters solve real-world problems at scale, see the Data Structures Problem Solving guide, which covers:

CDN Cache Optimization (Cloudflare): How Cloudflare uses Bloom Filters to prevent "One-Hit Wonder" files (assets requested only once) from ever being written to their SSD caching layer. This intercepts billions of useless IO write operations, preventing physical hardware degradation of their global SSDs (tying back to our Storage Hierarchy constraints).
Web Crawler Efficiency: How Google and Bing prevent duplicate page crawling
Real-time Username Validation: How social platforms provide instant availability feedback

Optional

// Bloom Filter - 20 lines that save 10x space
class BloomFilter:
    bits = BitArray(size=m)      // m bits, all 0
    k = 3                         // number of hash functions

    Add(item):
        for i in 0..k-1:
            index = hash_i(item) % m
            bits[index] = 1

    Contains(item):
        for i in 0..k-1:
            index = hash_i(item) % m
            if bits[index] == 0:
                return False      // Definitely not in set
        return True               // Maybe in set

// Optimal parameters (math magic)
m = -n * ln(p) / (ln(2)^2)      // bits needed
k = m/n * ln(2)                  // hash functions

Example: 1M items, 1% false positive
→ m = 9.6M bits = 1.2MB
→ k = 7 hash functions

The Trade-off

Space per item	False positive rate	Hash functions (k)
4 bits	15%	3
10 bits	1%	7
14 bits	0.1%	10

Rule of thumb: 10 bits per item = 1% false positives = sweet spot

System Design Note: Bloom filters are the standard solution for "have we seen this?" queries at scale. For more worked examples, see the Data Structures Problem Solving guide. Case Study 2.2 puts this at planet scale: how Chrome Safe Browsing ships one Bloom filter to 3 billion devices.