A traffic dashboard wants unique visitors this week. The firehose is IDs, not a table you can SELECT COUNT(DISTINCT …) on at leisure. The intern puts every id in a HashSet. Exact. Also every key, forever, in RAM. Product did not ask for the keys back. Product asked about how many.
HyperLogLog estimates distinct count from a hash, a run of leading zeros, and m small registers combined with a harmonic mean. You keep maxima, not members. The answer is plus-or-minus. That is the contract, not a bug in the hash.
This post is that sketch. Families and the catalog live on the Algorithms Roadmap. Bloom Filters answer maybe-membership. Count-Min Sketch approximates frequencies. Neither is a unique count. Treating Bloom or HyperLogLog as exact is the hub’s cargo-cult line: maybe-yes and plus-or-minus are the point.
The job is approximate cardinality, not a set
Cardinality here means how many distinct keys appeared — uniques, not events. ada, bob, ada is 2, not 3. A HashSet is the exact machine: store every key, report size(). HyperLogLog reports a number near that size and throws the keys away.
You cannot ask “have I seen ada?” The registers do not remember ada. You cannot iterate members. You cannot subtract one id. You get one statistic: an estimate of how many distinct hashes have been observed.
Plus-or-minus is the product. A dashboard, a capacity plan, a “roughly 12 million uniques” alert. Not a license count, not a billing line, not “exactly one seat left.”
Note: Duplicate keys hash the same, so they do not move a register that already stored that maximum. Repeats are free. Distinct keys that collide on the same register are the error bar.
Hash, then keep the longest run of zeros
Hash each key to a bit string that looks like coin flips. Split the bits:
- First
pbits pick a register.m = 2^pregisters. - The rest are inspected for the position of the first
1— equivalently, count leading zeros and add one. Call that rankρ.
A uniform rest that starts with 1 is common (ρ = 1, probability 1/2). 001… (ρ = 3) is rarer (about 1 in 8). If the rarest pattern you have seen is a long zero run, you have probably seen on the order of 2^ρ distinct hashes. One lucky hash with an absurd run would over-count if it were the whole sketch. That is why there are m registers, not one.
For the register that this hash landed on: store the max ρ seen so far. Later hashes to that bucket only replace the value if they look rarer.
Out of scope: SHA, HMAC, “crypto-grade” hashes. Production uses a fast well-mixed hash. The lab below uses String.hashCode the same way the Bloom post does — a teaching hash, not a reason to roll a digest.
m registers, then a harmonic mean
An arithmetic mean of 2^{R[j]} rewards the luckiest bucket. HyperLogLog uses the harmonic mean of those 2^{R[j]} values, which damps a single exploding register:
Z = Σ 2^{-R[j]} over j = 0 .. m-1
E = α_m · m² / Zα_m is a constant that depends on m (about 0.7213 / (1 + 1.079/m) once m is large). It is a bias correction from the original paper, not a knob you tune per key. Small n and empty registers get a further log correction (linear counting). Large n near the hash width gets another. This post does not ship Redis-grade bias tables. The formula above is the idea.
Standard error shrinks like 1.04 / √m. m = 2^14 (16384 registers) is a common production size: a dozen kilobytes, error around one percent. Four registers are a chalkboard.
A walk: four registers
m = 4, so p = 2 index bits. Hashes below are made-up 6-bit strings, consistent the way the Bloom lab’s indexes were. ρ is the 1-based position of the first 1 in the rest. Stream: ada, bob, cy, ada, eve. Exact uniques: 4.
start: R = [0, 0, 0, 0]
add ada 01 0010 idx=1 rest=0010 ρ=3 R = [0, 3, 0, 0]
add bob 10 1001 idx=2 rest=1001 ρ=1 R = [0, 3, 1, 0]
add cy 00 0101 idx=0 rest=0101 ρ=2 R = [2, 3, 1, 0]
add ada 01 0010 same hash R unchanged (duplicate)
add eve 01 0001 idx=1 rest=0001 ρ=4 R = [2, 4, 1, 0]
(new key, same register, max)
Z = 2^{-2} + 2^{-4} + 2^{-1} + 2^{-0}
= 0.25 + 0.0625 + 0.5 + 1
= 1.8125
raw harmonic: m² / Z = 16 / 1.8125 ≈ 8.8
exact unique: ada, bob, cy, eve = 4Register 3 stayed 0 — nobody hashed there. eve and ada shared a bucket; only the larger ρ survived. The raw harmonic is in the right neighborhood, not on the integer 4. α_m and the empty-register log formula pull bias down; four buckets will still not give a number finance will sign. That gap is the lesson: plus-or-minus is the point, and m is how you buy a tighter bar.
Two sketches merge by taking max per register. You union distinct counts without ever storing the keys. That is a reason this sketch exists at size, not a second algorithm.
Not Bloom, not Count-Min
Three sketches, three jobs. Do not re-teach the Bloom lab here; do not open a Count-Min lab here.
| Sketch | Question it answers | What it keeps |
|---|---|---|
| Bloom filter | Have I maybe seen this key? | Bits (maybe-yes, definitely-no) |
| HyperLogLog | About how many distinct keys? | m maxima of leading-zero ranks |
| Count-Min Sketch | About how often did this key appear? | A table of counters |
Bloom cannot give you a unique count as its contract (fill-ratio guesses are not this algorithm). Count-Min tracks frequencies of keys you query; it does not answer “how many uniques existed.” HyperLogLog does not answer membership or frequency.
Do not treat a HyperLogLog as a set, or a Bloom filter as a counter.
Java: registers plus an estimate, not a production bias table
There is no java.util.HyperLogLog. You take a library, or you take Redis, or you write a handful of methods for a lab. p from 4 to 16 keeps m in a sane teaching range (16 … 65536). Index from the high bits; ρ from Integer.numberOfLeadingZeros on what remains.
final class HyperLogLog {
private final int p;
private final int[] R;
HyperLogLog(int p) {
if (p < 4 || p > 16) {
throw new IllegalArgumentException("p in 4..16");
}
this.p = p;
this.R = new int[1 << p];
}
void add(String key) {
int h = key.hashCode();
int idx = h >>> (32 - p);
int rho = Integer.numberOfLeadingZeros(h << p) + 1;
if (rho > R[idx]) {
R[idx] = rho;
}
}
double estimate() {
int m = R.length;
int empty = 0;
double z = 0;
for (int r : R) {
if (r == 0) {
empty++;
}
z += Math.pow(2.0, -r);
}
if (empty == m) {
return 0;
}
double alpha = 0.7213 / (1.0 + 1.079 / m);
return alpha * m * m / z;
}
}The all-empty guard is honesty, not the paper’s small-range correction. String.hashCode clusters; a real sketch uses a well-mixed 32- or 64-bit hash. α_m here is the large-m constant. It is not Redis.
HyperLogLog uniques = new HyperLogLog(10); // m = 1024
uniques.add("ada");
uniques.add("bob");
uniques.add("ada");
System.out.println(uniques.estimate()); // near 2, not exactly 2Note: h << p on an int drops the index bits so numberOfLeadingZeros sees the rest. Java masks shift counts with 0x1F; keep p off 0 and 32. Do not copy this class into a billing path.
Redis as a pointer, not a tutorial
Many production counts are Redis HyperLogLog: PFADD inserts, PFCOUNT reads the estimate, PFMERGE unions by register-wise max. Twelve kilobytes per key at the usual precision. This post does not walk redis.conf, eviction, or cluster slots. If the job is a distinct count on a stream you already keep in Redis, call those commands. If the job is “teach the registers,” stay on this page.
When not to use HyperLogLog
Skip the sketch when plus-or-minus is not an acceptable answer.
- You needed the keys. Iteration, “show me who,” membership, deletes of one id. That is a set. HyperLogLog forgot the payload on purpose.
- You needed exact cardinality. Billing unique seats, license caps, “exactly one remaining.” The error bar is a product bug there. Use
COUNT(DISTINCT), aHashSet, or the source of truth. nis small. A few thousand strings in aHashSetis exact and cheap. Registers win when storing every unique is the pain.- You needed maybe-membership. That is Bloom. A Bloom fill ratio is not HyperLogLog.
- You needed per-key frequencies. That is Count-Min Sketch, next in this family.
- You wanted a cryptographic uniqueness proof. A sketch of hashes is not a capability token.
Treating HyperLogLog as exact is cargo-cult. Size m for the error you can live with, then live with it.
Cheat sheet
Job: approximate distinct count (cardinality), not membership, not frequency
Layout: m = 2^p registers; each holds max ρ (leading zeros on the hash rest, +1)
Add: hash → index + ρ; R[idx] = max(R[idx], ρ)
Estimate: E = α_m · m² / Σ 2^{-R[j]} (plus small/large-range corrections in production)
Error: ~ 1.04 / √m (m = 2^14 → about 0.8%, a dozen KB)
Merge: max per register (union of uniques without the keys)
JDK: none — lab sketch, a library, or Redis PFADD / PFCOUNT
Not this: HashSet, Bloom maybe-yes, Count-Min frequencies, SHADo:
- Name the job: about how many distinct keys, in tiny memory.
- Pick
mfor an error bar you can publish. Plus-or-minus is the contract. - Dedup for free: the same hash does not raise a max it already owns.
- Call Redis
PFADD/PFCOUNT(or a library) when this is production, not a lab.
Don’t:
- Treat the estimate as exact and skip the source of truth on a billing path.
- Ask a HyperLogLog whether
adais a member. That is Bloom, and Bloom is not a count. - Ask it how many times
adaappeared. That is Count-Min. - Ship the teaching
α_mline as Redis-grade bias correction.
Wrap-up
HyperLogLog replaces a HashSet of every unique with m small maxima: hash, split off a register, keep the rarest leading-zero rank, combine with a harmonic mean. Duplicates vanish. Distinct keys that share a register are the error. The number is plus-or-minus; that is why the structure fits in kilobytes when the set would not. It is not membership, not frequency, and not exact. Bloom already owns maybe-yes. Count-Min owns approximate counts per key. This page owns how many keys.
The intern stored every id. The dashboard needed a neighborhood. Size the registers for the bar you can live with, then stop asking the sketch to be a set.