What is HyperLogLog and How Does It Count Distinct Elements?
Learn what HyperLogLog is, how it estimates distinct counts with minimal memory, and where systems like Redis use it.
Expected Interview Answer
HyperLogLog is a probabilistic algorithm that estimates the number of distinct elements (cardinality) in a massive dataset using only a few kilobytes of memory, with a typical standard error around 2%, instead of storing every unique element to count them exactly.
The core insight is that if you hash every element to a uniform random bit string, the length of the longest run of leading zeros observed across all hashed values correlates with how many distinct elements were hashed — seeing a run of 20 leading zeros is rare unless roughly a million distinct values were hashed. A single such observation is noisy, so HyperLogLog splits incoming hashes into many buckets (typically thousands) based on some of their bits, tracks the longest leading-zero run seen independently in each bucket, and then combines all the bucket estimates with a harmonic mean to cancel out variance and produce one accurate cardinality estimate. Because it only stores small per-bucket counters rather than the elements themselves, it can estimate cardinalities in the billions using only a few kilobytes, which is exactly how Redis’s PFCOUNT and Google’s BigQuery APPROX_COUNT_DISTINCT work.
- Estimates cardinality of billions of elements using only a few kilobytes of memory
- Achieves a small, well-understood standard error (~2%) rather than requiring exact counts
- Supports merging multiple HyperLogLog sketches to get the combined cardinality without recomputation
- Scales to real-time unique-visitor or distinct-value counting where exact counting is infeasible
AI Mentor Explanation
HyperLogLog is like estimating how many unique bowlers a league has ever fielded by noticing the rarest possible bowling feat observed — a longer streak of consecutive dot balls suggests more bowlers have had a chance to attempt it. A single streak is unreliable, so you split observations across many separate grounds, track the longest dot-ball streak independently at each ground, and average those streak lengths together to smooth out luck. This lets you estimate the total unique bowler count from just a handful of streak numbers instead of a full roster list. That statistical estimation from rare-event patterns across many buckets is exactly how HyperLogLog counts distinct elements.
Step-by-Step Explanation
Step 1
Hash each element
Every incoming element is hashed to a uniform, effectively random bit string.
Step 2
Route to a bucket
A fixed number of leading bits of the hash select which of thousands of buckets the observation belongs to.
Step 3
Track longest zero-run per bucket
Each bucket stores only the maximum count of leading zeros seen so far among its remaining hash bits.
Step 4
Combine with a harmonic mean
All bucket max-run values are combined using a harmonic-mean-based formula (with bias correction) to produce one cardinality estimate.
What Interviewer Expects
- Explains the leading-zeros-correlate-with-cardinality intuition correctly
- Mentions bucketing (stochastic averaging) and why a single observation alone is too noisy
- States the approximate standard error (~2%) and that HyperLogLog trades exactness for tiny memory
- Names a real system that uses it (Redis PFCOUNT, BigQuery APPROX_COUNT_DISTINCT)
Common Mistakes
- Confusing HyperLogLog with a Bloom filter or Count-Min Sketch (different problems: cardinality vs membership vs frequency)
- Claiming HyperLogLog gives an exact count rather than a bounded-error estimate
- Forgetting that multiple HyperLogLog sketches can be merged to get combined cardinality without rescanning data
- Not explaining why bucketing/averaging is needed instead of relying on one hash observation
Best Answer (HR Friendly)
“HyperLogLog is a way to estimate how many unique things are in a huge dataset, like unique visitors to a website, without storing every single one. It looks at statistical patterns in hashed values across many small buckets and combines them into one estimate that is typically within about 2% of the real answer, using only a tiny amount of memory.”
Code Example
import hashlib
import math
class HyperLogLog:
def __init__(self, num_buckets_bits=10):
self.m = 1 << num_buckets_bits # e.g. 1024 buckets
self.bucket_bits = num_buckets_bits
self.registers = [0] * self.m
def _leading_zeros(self, bits):
count = 0
for bit in bits:
if bit == "0":
count += 1
else:
break
return count + 1
def add(self, item):
h = bin(int(hashlib.sha256(item.encode()).hexdigest(), 16))[2:].zfill(256)
bucket = int(h[: self.bucket_bits], 2)
rank = self._leading_zeros(h[self.bucket_bits :])
self.registers[bucket] = max(self.registers[bucket], rank)
def estimate(self):
alpha = 0.7213 / (1 + 1.079 / self.m)
harmonic_sum = sum(2 ** -r for r in self.registers)
return alpha * self.m * self.m / harmonic_sum
hll = HyperLogLog()
for visitor_id in stream_of_visitor_ids():
hll.add(visitor_id)
approx_unique_visitors = hll.estimate() # ~2% standard error, tiny memoryFollow-up Questions
- Why does the longest run of leading zeros correlate with the number of distinct elements observed?
- Why is bucketing (stochastic averaging) necessary instead of using a single hash observation?
- How can two HyperLogLog sketches be merged to get the combined cardinality of both datasets?
- How does HyperLogLog differ from a Bloom filter and a Count-Min Sketch in the problem each solves?
MCQ Practice
1. What does HyperLogLog estimate?
HyperLogLog is designed specifically to approximate the cardinality (count of distinct elements) of a large dataset.
2. What core signal does HyperLogLog use to estimate cardinality?
A longer run of leading zeros in a hash is statistically rarer and becomes more likely only as more distinct elements are hashed, which HyperLogLog exploits.
3. Why does HyperLogLog split observations into many buckets before combining them?
A single rare-event observation has high variance; bucketing and combining with a harmonic mean smooths that variance into an accurate estimate.
Flash Cards
What is HyperLogLog? — A probabilistic algorithm that estimates the number of distinct elements (cardinality) using minimal memory.
What signal drives the estimate? — The longest run of leading zeros observed in hashed values, combined across many buckets.
Typical standard error? — Around 2% for a well-configured HyperLogLog sketch.
Can HyperLogLog sketches be merged? — Yes — merging is a simple per-bucket max operation, giving the combined cardinality without rescanning data.