What Is HyperLogLog?

HyperLogLog is a probabilistic algorithm for estimating the number of distinct elements in a dataset — its cardinality — using a tiny, fixed amount of memory regardless of how large the dataset actually is. Counting unique visitors, unique search queries, or unique IP addresses exactly requires storing every distinct value you’ve seen; HyperLogLog gets within about 1–2% of the true count using a few kilobytes, whether the real answer is a thousand or a billion.

The problem with counting exactly

Counting distinct items the obvious way means keeping a set: for every new item, check whether it’s already in the set, and add it if not. That works fine at small scale, but a set of a billion unique 64-bit values needs many gigabytes of memory just to hold the values themselves, and that cost scales linearly with cardinality — count more distinct things, use proportionally more memory. For a service tracking unique visitors across a large website, or unique values across a firehose of event data, that’s often not a viable amount of memory to dedicate to what is, in the end, just one number.

HyperLogLog trades exactness for a fixed, tiny memory footprint. It’s part of the same family of probabilistic data structures as the Bloom filter (which answers “have I seen this before?”) and the Count-min sketch (which estimates how many times an item has been seen) — all three sacrifice perfect accuracy for memory that doesn’t scale with the size of the data they’re summarizing.

The core idea: rare patterns imply large counts

HyperLogLog’s trick starts from a simple observation about hashing. Hash every incoming item to a uniform random-looking bit string. Now look at how many leading zeros that hash has before the first 1 bit. A hash starting with zero leading zeros happens about half the time. One leading zero happens about a quarter of the time. Two leading zeros, an eighth of the time, and so on — each additional leading zero is half as likely as the last.

That means if you’ve hashed a lot of distinct items, you’d expect to have seen at least one hash with a long run of leading zeros purely by chance — and the longer the longest run you’ve actually observed, the more distinct items you probably hashed to produce it. Track only the maximum number of leading zeros seen so far, and that single small number lets you estimate cardinality: roughly, 2 raised to the power of that maximum.

Why one estimate alone isn’t enough

A single “longest run of leading zeros” estimate is extremely noisy — one unlucky or lucky hash can throw the whole estimate off by a wide margin. HyperLogLog fixes this the same way most estimation techniques do: run many independent estimates and average them.

It does this efficiently by splitting incoming hashes across many small buckets (typically a few thousand) using a few bits of each hash to pick the bucket, and tracking the longest run of leading zeros independently within each one. Averaging the per-bucket estimates — using a harmonic mean and a bias-correction constant, which is where most of the algorithm’s mathematical detail actually lives — cancels out much of the noise any single bucket would have on its own, without needing anywhere near as much memory as tracking full item lists in each bucket would require.

What you get in exchange

	Exact set / hash table	HyperLogLog
Accuracy	Perfect	~1–2% typical error
Memory usage	Grows with cardinality	Fixed (a few KB), regardless of cardinality
Supports “has X been seen”	Yes	No — only cardinality
Mergeable across machines	Requires merging full sets	Yes, cheaply — union buckets

That last row matters more in practice than it might look. Because each HyperLogLog structure is just a fixed-size array of small counters, two of them covering separate portions of a distributed dataset can be merged into an accurate combined estimate just by taking the max of each corresponding bucket — no need to ship raw data between machines. This is exactly the shape of problem that shows up in distributed OLAP systems and stream-processing pipelines: estimate unique counts on many machines independently, then combine the estimates cheaply at the end.

Where it’s actually used

HyperLogLog is a standard tool anywhere “roughly how many distinct X” is good enough and exact counting would be too expensive: unique visitor counts on high-traffic websites, unique query estimation in analytics databases, distinct-value estimation inside query planners deciding how to execute a query, and network monitoring tools estimating unique flows or addresses. Redis ships HyperLogLog as a built-in data type for exactly this reason — approximate cardinality at a cost of a few kilobytes per counter is a trade nearly every large-scale counting problem is happy to make.

The takeaway

HyperLogLog turns “how many distinct things have I seen” from a problem that scales with your data into one that fits in a few kilobytes, by exploiting a statistical shortcut — the length of the longest run of leading zeros in a hash implies roughly how many distinct items produced it — and averaging that estimate across many small buckets to keep the error small. The trade-off is a small, well-understood margin of error in exchange for memory usage that never grows, which is exactly the trade most large-scale counting problems are willing to make.