Why do leading zeros estimate a count?

If hashes are uniformly random bits, the chance a hash begins with k zeros is 1/2^(k+1). So seeing a run of k leading zeros hints you've drawn roughly 2^k distinct hashes. The longest run of leading zeros observed is a rough log2 of the number of distinct items.

Why split into buckets and use a harmonic mean?

A single longest-run estimate has huge variance — one lucky hash throws it off. HyperLogLog uses the first bits of each hash to pick one of m buckets, tracks the longest zero-run per bucket, and combines the buckets with a harmonic mean (which suppresses outliers). More buckets means lower variance: the standard error is about 1.04 / sqrt(m).

Is HyperLogLog exact?

No — it's a probabilistic estimate, not an exact count. With m = 16384 buckets it uses about 12 KB and achieves roughly 0.8% relative error. Small-m demos (like m = 8) have large variance by design; the accuracy comes from using thousands of buckets.

Algorithms · Probabilistic

Count a Crowd by Its Longest Coin-Flip Streak.

Q: What does HyperLogLog do?

HyperLogLog estimates the number of distinct elements (the cardinality) in a stream using a tiny, fixed amount of memory — a few kilobytes can count billions of distinct items to within about 1% error. It trades exactness for enormous memory savings versus a hash set.

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.

items seen

true distinct

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.

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.

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.

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 0 def 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?

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.

Keep going

Finished this one? 0 / 62 Algorithms done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA

Count a Crowd by Its Longest Coin-Flip Streak.

How it works

Hash the item

Pick a bucket

Rank the rest

Combine the buckets

The code

Quick check

FAQ

Keep going

Explore the topic

More Algorithms

Explore more from Vibe Engines

How it works

Hash the item

Pick a bucket

Rank the rest

Combine the buckets

The code

Quick check

FAQ

Keep going

Reservoir Sampling →

Hash Tables →

Rabin–Karp Hashing →

The DSA Roadmap →

Explore the topic

More Algorithms

Explore more from Vibe Engines

Get the next one in your inbox.