Count-Min Sketch
maang.io System Design Series
A count-min sketch is a small 2D array of counters and a few hash functions that estimates how many times you've seen an item — using far less memory than a real hash map. It may overestimate (from collisions) but never underestimates, which makes it perfect for frequency counting and "heavy hitters" (top-K) over streams too big to store exactly.
This deep dive comes in three parts:
- Foundations & Core Concepts — the counter grid, the MIN trick, and the accuracy-vs-space bargain.
- Internals — the error bounds
ε/δ, sizing the width and depth, and contrasts with Bloom filters and HyperLogLog, with worked numbers. - Interview — Staff/Principal Q&A: when approximate counting wins, sizing, and streaming trade-offs.
Count-Min Sketch — Part 2: Internals & The Math
maang.io System Design Series
What is this?
Back to our three bouncers and their racks of numbered clickers. In Part 1 we saw the shape: each bouncer bumps one clicker per guest, and to answer "how many times did Alice come in?" you trust the smallest of the three readings. That's the intuition. This chapter makes it exact — we'll open up the rack, watch a single guest ripple through all three racks (the write path), watch a query pull the three numbers and take the min (the read path), and then do the thing that separates a Staff answer from a Wikipedia summary: prove how big the racks need to be to hit an accuracy target, with real numbers.
The one-line idea: The sketch is
dindependent hash tables sharing one job — each maps every item to one counter, so each row is an over-count with independent noise; sizing the widthwcontrols how much each row over-counts, and the depthdcontrols the odds that every row is unlucky at once. Two knobs, two guarantees.
Let's build it from the counters up.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson