20. Probabilistic Data Structures
1
The picture to keep in your head2
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 breaks11
Practice: five levels12
Interview questions13
Solutions14
Sources15
Code lab20. Probabilistic Data Structures
20.1 Why is "approximately right, fast and tiny" a good trade?
3 min read+10 XP
At the door: The bouncer could keep a perfect, alphabetised guest list and check every single person against it. That's exact, but slow, and the queue backs up down the street. The card of marks is wrong in one known, harmless way, and it's a hundred times faster.
In the system: Exact answers often need memory that grows with the data:
- "Is this username taken?" exactly means keeping all 10 million names, about 200 MB or more with overhead, in memory or hitting the database every time.
- "How many unique visitors this month?" exactly means storing every visitor ID seen, for every day you want to compare.
- "How many times was each search term used?" exactly means a counter for every distinct term ever typed, including millions of one-off typos.
Probabilistic structures answer these in fixed, small memory, with an error you choose up front:
| Question | Structure | Typical memory | Kind of error |
|---|---|---|---|
| Is X in the set? | Bloom filter | ~12 MB for 10 million items at 1% | False "maybe"; never a false "no" |
| How many distinct? | HyperLogLog | ~12 KB (Redis), any count | About ±0.81% |
| How many times X? | Count-min sketch | Tens of KB | Overcounts a little; never under |
| Most frequent? | Top-K | Sketch + K entries | Rare items may be miscounted |
When it's a good trade:
- The answer is used for speed or display, not money: "probably new", "about 2.1 million visitors", "trending now".
- A wrong guess is cheap, or can be checked: a Bloom filter's "maybe" is confirmed by the database.
- The data is huge or streaming and you can't keep it all.
When it isn't: balances, inventory, billing, anything where "about right" is wrong.
Memory code: "Small and nearly right beats huge and exact, when nearly is enough."