A request log is still open. Product wants a count per path: /health versus /api/orders/42. The intern puts every string in a HashMap<String, Long>. Overnight the cardinality explodes — UUIDs in the path, cache-buster query strings, a bot with a new URL each hit. The map is the honest answer. The heap is the outage. You still need “about how hot is /health” — not an exact row for every junk key.
Count-Min Sketch is a d × w table of counters: hash the key once per row, increment those cells, query the MIN. Collisions only add, so typical CMS over-estimates on purpose and never under-counts.
This post is that table. Families and the catalog live on the Algorithms Roadmap. HyperLogLog estimates how many distinct keys appeared. Bloom Filters answer membership. Neither is a per-key frequency. Heavy-hitters productization and Stream-Summary are out of scope.
The job is an over-estimate you can fit
A map answers get(key) with the exact count, or zero. It stores the key. CMS answers with a number that is at least the truth. It stores d * w integers. The key is hashed and thrown away.
You pick two integers and keep them fixed: d (rows, depth) and w (columns, width). Storage does not grow with the number of distinct strings. That is the point. The error you bought is extra mass from other keys that landed in the same cells.
If the true count is 3, the sketch will not report 2. A collision can only push a cell up. Taking the min across rows throws away the dirtiest cells you can see. It cannot invent an under-count.
Note: This contract is increment-only. Decrement, decay, or “conservative update” (bump only the current min cells) are different procedures. This post increments every hashed cell by one.
d rows, w counters, one hash per row
Row i has its own hash h_i into 0 … w-1. Increment walks all d rows. Query walks the same cells and returns the smallest value.
d = 2, w = 5. Start at 0.
col 0 1 2 3 4
row 0 (h0) 0 0 0 0 0
row 1 (h1) 0 0 0 0 0Same key, same indexes, every time — otherwise you cannot find what you added. Different rows must disagree often. That is the independence bet. A teaching mix is hashCode xor a per-row salt, then floorMod into w. Production wants pairwise-independent hashes (Murmur-style), not String.hashCode alone.
One cell per row, d cells per update. You never store the string. You never iterate keys. There is no entrySet.
Query is the min, not the mean
After a collision, some cells hold your count plus someone else’s. Those cells are high. A cell that nobody else hit still holds the truth.
The min of the d cells is the least-contaminated reading you have. Average would keep the extra mass. First row alone would keep every collision on that hash. Min is the algorithm, not a polish.
Do not read one row and call it the frequency. One hash is a single counter array. Collisions there are silent extra adds with no second opinion. Depth is how you buy the second opinion.
A walk: 2×5, two keys collide
A tiny table. Two paths. They collide on row 0 and miss each other on row 1.
h0: api → 1 cdn → 1 (same cell)
h1: api → 3 cdn → 0 (clean)
increment api, api, api:
col 0 1 2 3 4
row 0 0 3 0 0 0
row 1 0 0 0 3 0
increment cdn, cdn:
col 0 1 2 3 4
row 0 0 5 0 0 0 // cell 1 is api + cdn
row 1 2 0 0 3 0
query api = min(5, 3) = 3 true 3
query cdn = min(5, 2) = 2 true 2Row 0 says api was seen five times. That is a lie by two — cdn sat in the same cell. Row 1 still holds 3. Min keeps the truth.
The dirty row over-estimates; a clean row saves the query. In a long stream both of a key’s cells can pick up leftovers. Then min is above the truth, not equal — still close relative to the table you could actually allocate. Typical CMS never reports below the true count. More rows (larger d) make “every row dirty” less likely. Wider rows (larger w) make each collision less likely in the first place.
A third key that later lands on both of api’s cells would push query(api) above 3. That is the error you accepted when you refused the map.
Not HyperLogLog, not a Bloom filter
Three sketches, three jobs. Mixing them is how “we have a sketch” becomes a wrong number.
| Structure | Question | Wrong use here |
|---|---|---|
| Count-Min Sketch | About how many times did I see this key? | Distinct cardinality; membership |
| HyperLogLog | About how many distinct keys appeared? | Per-key frequency |
| Bloom Filters | Have I maybe seen this key? | Counts |
HLL keeps registers of leading zeros. It does not have a slot you can ask for /health. Bloom keeps bits: definitely not, or maybe yes. A Bloom that “counts” is still membership with extra noise. CMS keeps integer counters and returns a min.
This page does not walk HLL or Bloom. Those labs own their own error. Do not treat this table as either.
Note: A Bloom filter is not CMS with int replaced by bits. Add vs OR, min vs “all bits set,” frequency vs membership — different contracts. The shared idea is only “hash into a small array and accept collisions.”
Java: int[][], increment, query
No java.util.CountMinSketch. Depth d rows, width w columns. Math.floorMod keeps a negative hashCode in range.
final class CountMinSketch {
private final int[][] table;
private final int d;
private final int w;
CountMinSketch(int d, int w) {
if (d < 1 || w < 1) {
throw new IllegalArgumentException("d and w must be ≥ 1");
}
this.d = d;
this.w = w;
this.table = new int[d][w];
}
void increment(String key) {
for (int i = 0; i < d; i++) {
table[i][col(key, i)]++;
}
}
int query(String key) {
int min = Integer.MAX_VALUE;
for (int i = 0; i < d; i++) {
min = Math.min(min, table[i][col(key, i)]);
}
return min;
}
private int col(String key, int row) {
int h = key.hashCode() ^ (row * 0x9e3779b9);
return Math.floorMod(h, w);
}
}The xor-salt is the lab’s “different hash per row.” It is not a proof of pairwise independence. Tests that need a known collision should inject the column function, not hope hashCode collides. The 2×5 walk above used pedagogical h0 / h1, not this mixer.
Note: int cells wrap to negative on overflow. A long stream wants long[][] or saturating adds. Query of a key never inserted returns the min of whatever leftovers sit in its cells — often 0 on a fresh table, not a reliable “absent.” Absent is Bloom’s job.
Width, depth, and the bill
Let n be events (the stream), not distinct keys. Each increment and each query touches d cells.
| What | Cost | Why |
|---|---|---|
| Increment | O(d) | One index per row |
| Query | O(d) | Min of d cells |
| Extra space | O(d · w) | The table; independent of distinct keys |
| Exact rival | O(distinct) space | HashMap stores every key |
Classic teaching sizes: width w ≈ e/ε bounds the additive over-estimate relative to the total stream (not relative to one key’s count); depth d ≈ ln(1/δ) cuts the chance that every row is unlucky. You do not need the proof to pick the primitive. You need to know the error is additive leftovers, so a rare key can look several times too hot while a heavy hitter stays relatively close.
Space is the table, not the key set. Quoting O(d) per event while d = 4 is honest. Quoting “constant memory” while w is a million 64-bit cells is also honest — and still smaller than a map of a billion strings.
When not to use Count-Min Sketch
Skip this table when the job is not “approximate per-key frequency in a fixed budget.”
- The map fits. Exact
HashMap/ConcurrentHashMapcounts are simpler. CMS is the refusal to store keys, not a fasterget. - You needed distinct cardinality. That is HyperLogLog. CMS does not answer “how many unique IPs.”
- You needed membership. That is Bloom Filters. A CMS query of 0 is not “definitely never seen” once the table is dirty.
- You needed never-over. CMS over-estimates. If a false high ships a page or a ban, pick an exact structure or a different estimator.
- You needed the top-k keys themselves. The sketch answers counts for keys you already have. Finding heavy hitters (Stream-Summary, a heap of candidates) is a product on top. Out of scope here.
- You needed to delete. Increment-only min does not undo. Count-Min with decrements can under-count. Do not subtract and keep the “never under” slogan.
Over-estimate, never under-estimate — that is the increment-only contract. Huffman coded known frequencies exactly. This sketch approximates frequencies you cannot afford to store. Do not open HLL, Bloom, or LZ77 labs here.
Cheat sheet
Job: approximate count of a key when the exact map will not fit
Layout: d rows × w counters; one hash per row into 0..w-1
Increment: table[i][h_i(key)]++ for each row i
Query: min over those d cells
Bias: over-estimate (collisions only add); never under, increment-only
Time/space: O(d) per op; O(d·w) memory, independent of distinct keys
JDK: none; int[][] + floorMod; long[][] if the stream is huge
Not this: HashMap exact counts; HyperLogLog distinct; Bloom membership;
Stream-Summary / heavy-hitters product; conservative updateDo:
- Fix
dandwat construction. Hash per row. Increment alldcells. Query the min. - Treat the result as an upper bound on the true count.
- Use a map when the key set is small enough to store.
Don’t:
- Report one row as the frequency — min is the algorithm.
- Ask CMS for distinct count or for definitely-not membership.
- Promise “never over” or subtract from cells and keep the slogan.
- Ship
String.hashCodeas production independence.
Wrap-up
Count-Min Sketch replaces a map of every key with a fixed d × w table: hash once per row, add one, return the min. Collisions push cells up, so you over-estimate on purpose. A clean row keeps the query close; a dirty table still will not under-count. It is not HyperLogLog, not a Bloom filter, and not a top-k product. When the heap cannot hold the keys, this is the frequency primitive. When the job is sliding-window compression, that is LZ77 and DEFLATE.