How many distinct visitors hit a site with a billion requests? A hash set of every id would eat gigabytes. HyperLogLog answers in a few kilobytes: hash each item, count the leading zeros of the hash, keep the longest run per bucket, and the harmonic mean of those runs estimates the count — to within about 1%.
O(1) memory per bucket · ~1% error · streaming cardinality
hash → bits
Each item becomes a uniformly random bit string. Same item, same bits.
leading zeros
A run of k zeros is rare — it hints you've seen ~2ᵏ distinct hashes.
buckets
The first bits pick a bucket; each keeps the longest zero-run it has seen.
harmonic mean
Combine buckets so one lucky run can't blow up the estimate.
hll.js — hash, count zeros, keep the max per bucket
Ready
Stream of items flows in. Press Step: each item is hashed to 24 random-looking bits — the last 3 bits pick a bucket, the leading zeros of the rest give a rank ρ, and the bucket keeps the largest ρ it has seen. Duplicates hash the same, so they change nothing.
0
items seen
0
true distinct
0
estimate
How it works
The trick rests on one fact about random bits: the probability a hash starts with exactly k zeros is 1/2^(k+1). So the longest run of leading zeros you've ever seen is a noisy estimate of log₂(distinct count). Raise 2 to that and you have a cardinality — noisy, but free of storing anything but the record.
1
Hash the item
Map each element to a fixed-width, uniformly random bit string. Identical items produce identical bits — that's why duplicates are automatically ignored.
2
Pick a bucket
Use the first p bits as a bucket index (here p = 3, so 8 buckets). Splitting into many buckets is what tames the variance of a single estimate.
3
Rank the rest
On the remaining bits, count the leading zeros and add one: ρ = leadingZeros + 1. Store register[bucket] = max(register[bucket], ρ) — only the record survives.
✓
Combine the buckets
Estimate ≈ α·m²/Σ 2^(−register[j]) — a harmonic mean over buckets, times a bias constant α. More buckets, tighter estimate: error ≈ 1.04/√m.
Memory (m=16384)
~12 KB
Typical error
~0.8%
Add / query
O(1)
Merge two
O(m)
The code
# m = 2^p buckets; register[] all start at 0def add(x):
h = hash(x) # uniform bits
idx = h & (m - 1) # first p bits pick a bucket
w = h >> p # the rest
rho = leading_zeros(w) + 1 # length of the zero-run + 1
register[idx] = max(register[idx], rho)
def estimate():
Z = sum(2.0 ** -register[j] for j in range(m))
return alpha(m) * m * m / Z # harmonic-mean cardinality
Two HyperLogLog sketches merge by taking the element-wise max of their registers — so you can count distinct items across shards or time windows and combine the results exactly, without ever comparing raw ids. That mergeability is why it's everywhere: Redis PFCOUNT, Presto/BigQuery approximate COUNT(DISTINCT), and analytics pipelines all lean on it.
Quick check
1. Why does seeing the same item twice not change the estimate?
Right — HyperLogLog stores no items. A repeat produces the same hash, lands in the same bucket with the same ρ, and max leaves the register alone. That's why it counts distinct items for free.
2. Why split hashes across many buckets instead of tracking one longest run?
Right — one lucky hash with a long zero-run would wildly overcount. Many buckets, combined by a harmonic mean (which resists high outliers), shrink the error as you add buckets: ≈1.04/√m.
FAQ
What does HyperLogLog do?
Estimates how many distinct items are in a stream using a few kilobytes — a hash set would need memory proportional to the count.
Why do leading zeros count things?
With random bits, a run of k leading zeros has probability 1/2^(k+1), so the longest run observed is roughly log₂ of the number of distinct hashes.
How accurate is it?
With m = 16384 buckets it uses ~12 KB and hits ~0.8% relative error. The small m = 8 here is for visibility — it's deliberately noisy.
Can two sketches be combined?
Yes — take the element-wise max of their registers. This mergeability lets you union counts across shards or windows exactly.
SOLVE IT YOURSELF
Solve it: count a billion distinct things in 4 KB
A hash set of a billion IDs needs gigabytes. HyperLogLog needs a few thousand small counters — and answers within about 2%. It works by noticing that a rare pattern implies a large sample. Python or TypeScript.
YOUR TASK
Implement build(items, b) — 2ᵇ registers, each holding the longest run of leading zeros seen — and estimate(regs), the harmonic-mean cardinality estimate with the small-range correction.
HINTS — 6 IDEAS
The core intuition: in random hashes, a value starting with k zeros shows up about once every 2ᵏ values. So seeing 10 leading zeros suggests you have seen roughly 2¹⁰ distinct things.
One estimate like that is wildly noisy, so split into 2ᵇ registers: the first b bits pick the register, the rest supply the zero-run.
Each register keeps only the maximum run it has seen. That is why the sketch is idempotent — feeding the same item twice changes nothing, which is exactly what counting distinct requires.
Combine with a harmonic mean, not an arithmetic one — it suppresses the single lucky register that would otherwise dominate. Then multiply by the bias constant α and by m².
At low cardinality most registers are still empty and the formula reads badly high, so switch to linear counting: m · ln(m / empty_count).
Accuracy is about 1.04/√m — 4096 registers gives roughly 1.6%, in a few kilobytes, no matter how many items you feed it.