Art of Codeartofcode
Lesson 3 of 15

20. Probabilistic Data Structures

1
The picture to keep in your head
2
20.1 Why is "approximately right, fast and tiny" a good trade?
3
20.2 How does a Bloom filter work?
4
20.3 What is a counting Bloom filter?
5
20.4 How does HyperLogLog count unique visitors?
6
20.5 What is a count-min sketch?
7
20.6 How do you find the top K and heavy hitters?
8
20.7 How do you choose size vs error rate?
9
20.8 Where does each one show up in interviews?
10
Memory card and where the analogy breaks
11
Practice: five levels
12
Interview questions
13
Solutions
14
Sources
15
Code lab
20. Probabilistic Data Structures

20.2 How does a Bloom filter work?

3 min read+10 XP

At the door: The bouncer's card is a row of empty boxes. For each invited guest, they work out three box numbers from the name (always the same three for the same name) and tick them. When someone arrives, the bouncer checks their three boxes. Any box empty? Definitely not invited. All ticked? Maybe invited: check the real list.

In the system: A Bloom filter is an array of m bits, all 0, and k hash functions:

  • Add an item: hash it k ways, set those k bits to 1.
  • Check an item: hash it the same k ways. If any bit is 0, the item was definitely never added. If all are 1, it was probably added.

asha and ravi each set three bits; kiran hits a 0, meera hits only 1s set by others.

Figure: a "no" is always right; a "yes" means "probably", because other items may have set those bits.

Why "probably": bits are shared. Other items may have set all k of your bits between them. That's a false positive. There are no false negatives: an item that was added always finds its bits set.

For the bookstore: keep a Bloom filter of all 10 million usernames. When someone types a new username at signup:

  • Filter says no → the name is free; skip the database.
  • Filter says maybe → check the database to be sure.

Sized for 1% false positives, the filter is about 12 MB with 7 hashes (computed in 20.7), and 99% of free names never touch the database. In the chapter's code, 20,000 names are added; all 20,000 are found, and 20,000 new names give a 0.97% false-positive rate, right on target.

Where they're used for real:

  • Databases like Cassandra and RocksDB keep a Bloom filter per on-disk file (the LSM-tree's SSTables, Chapter 9), to skip files that can't contain a key.
  • Web crawlers: "have I already seen this URL?" (Chapter 36).
  • Caches and CDNs: only cache an object the second time it's requested, to stop one-off requests filling the cache.
  • Recommendations: "have we already shown this user this book?"

Limits: you can't remove items (20.3), you can't list what's inside, and the error rate rises if you add more items than you sized for.

Memory code: "No means no; yes means maybe."