The Bloom filter answers "have I seen this?" and the Count-Min Sketch answers "roughly how many times?" — both in fixed memory. HyperLogLog answers a third narrow question in the same spirit, also in fixed memory no matter how many items go in: "roughly how many distinct items have I seen?" Not "which ones," not "how many times each" — just the count of unique items in a stream that, done exactly, would need to remember every item it has ever seen.
HyperLogLog remembers none of them. Instead it keeps m small counters, called
registers, all starting at 0. Adding an item hashes it once, uses the hash's top
few bits to pick one register (out of m), and looks at the leading-zero run in the
rest of the hash's bits — call that run's length ρ (rho), 1-indexed so a
hash with no leading zeros at all in that field still scores ρ = 1. If ρ
beats whatever that register already holds, the register is raised to ρ; otherwise
nothing happens. That's the entire add — one hash, one register, a single
"is this bigger" comparison.
The trick is what a long leading-zero run implies. Each bit in a uniform random hash is a fair
coin flip, so the probability of seeing at least k leading zeros is
2⁻ᵏ — a run of length 3 should show up roughly once every 8 items, a run of 5 roughly
once every 32. The longest run any register has seen is therefore a clue to how many
distinct items have hashed into that register: a long run is unlikely with only a few distinct
items, likely with many. HyperLogLog spreads this trick across m registers and
combines their maxima with a harmonic mean (which, unlike an arithmetic mean, is dominated by the
smallest — least optimistic — readings), scaled by a bias-correction constant
αm worked out for exactly this estimator. No register, and no hash,
ever has to be kept around after it updates its one register — that's the whole memory saving.
Sixteen adds have already run, in this order: cat, dog, cat, bird, cat, dog, fish, cat,
owl, lion, dog, wolf, cat, hawk, bird, owl — 8 distinct animals, some added up to four
times (m = 16 registers, 4 bits for the register index, 28 bits left over for
ρ). Watch the register table: repeat adds of cat land on register 0 every time
but only the first one raises it (to ρ=2); the other three are logged as "no change."
Add your own words and watch which register lights up and whether it's a new max.
b bits (m =
2^b) pick a register, the remaining bits give ρ (position of the first 1-bit, 1-indexed);
raise that register to ρ if ρ is bigger than what's there. O(1), independent of how
many items or how many distinct items have been added.2^(-register[i])
across all m registers, scale by αm·m². Also O(1) in the
number of registers, which is fixed. If the raw result is small relative to m and any
register is still 0, a small-range correction (linear counting:
m · ln(m / zeros)) replaces it — the raw harmonic-mean formula is badly biased in
exactly that regime (see Pitfalls).function fnv1a(s) {
let h = 0x811c9dc5;
for (let i = 0; i < s.length; i++) {
h ^= s.charCodeAt(i);
h = Math.imul(h, 0x01000193);
}
return h >>> 0;
}
class HyperLogLog {
#registers;
#b; // bits used for register index
#m; // number of registers = 2^b
#alpha; // bias-correction constant for this m
constructor(b) {
this.#b = b;
this.#m = 1 << b;
this.#registers = new Uint8Array(this.#m);
if (this.#m === 16) this.#alpha = 0.673;
else if (this.#m === 32) this.#alpha = 0.697;
else if (this.#m === 64) this.#alpha = 0.709;
else this.#alpha = 0.7213 / (1 + 1.079 / this.#m);
}
// position of the first 1-bit in a `width`-bit value, 1-indexed
#rho(w, width) {
if (w === 0) return width + 1;
const leadingZeros = Math.clz32(w) - (32 - width);
return leadingZeros + 1;
}
add(item) {
const h = fnv1a(String(item));
const idx = h >>> (32 - this.#b);
const restWidth = 32 - this.#b;
const rest = h & ((1 << restWidth) - 1);
const r = this.#rho(rest, restWidth);
if (r > this.#registers[idx]) this.#registers[idx] = r;
}
estimate() {
const m = this.#m;
let sum = 0, zeros = 0;
for (let i = 0; i < m; i++) {
sum += Math.pow(2, -this.#registers[i]);
if (this.#registers[i] === 0) zeros++;
}
const raw = (this.#alpha * m * m) / sum;
if (raw <= 2.5 * m && zeros > 0) return m * Math.log(m / zeros); // small-range correction
return raw;
}
}Verified four ways, all in Node, self-tested before being trusted: (1) the exact shipped demo
trace — all sixteen add calls reproduced standalone, register-by-register, confirming
the final table [2,0,0,0,0,0,0,1,0,2,2,0,0,3,2,3], the raw estimate
≈16.03, and the corrected estimate ≈9.21 against a true count of 8.
(2) An accuracy sweep at this exact configuration (m = 16): 2,000 randomized streams
of 5-205 distinct items gave a mean relative error of 19.4%, close to (and under)
the theoretical standard error 1.04/√m ≈ 26.0% the HyperLogLog paper derives for this
m — a small register count is expected to be noisy, and the measurement landed where the theory
says it should. (3) A targeted comparison at small cardinalities (3-42 distinct items, the regime
where the small-range correction is supposed to matter most): across 3,000 trials, the
uncorrected raw formula had a 42.8% mean relative error against the corrected formula's
18.9% — confirming the correction isn't cosmetic, it roughly halves the error exactly where the
demo's own 8-distinct-item example lives. (4) Proved the checks would catch a broken implementation
first: a sabotaged version that pins every register to a constant instead of tracking a real max
pushed the mean relative error up to 64.8% on the same randomized streams used for check (2) — the
"real implementation lands near the theoretical error bound" result means something rather than the
check being toothless. See /tmp/hll/impl.js, /tmp/hll/sweep.js, and
/tmp/hll/correction_check.js, scratch, not committed.
The raw estimator badly overshoots when the true count is small relative to
m — this demo hits that regime directly. With m = 16 and only 8 distinct
items added, the uncorrected harmonic-mean formula gives ≈16.03 — roughly double
the true count — because with so few distinct items, most of the 16 registers are still at 0, and
0-registers contribute the maximum possible term (2⁰ = 1) to the harmonic mean,
dragging the whole estimate up. The small-range correction (linear counting,
m · ln(m / zeros)) uses the count of untouched registers directly instead,
and lands at ≈9.21 — much closer to the true 8. Real implementations always
include this correction; an implementation that skips it "because the formula works" will quietly
double-count at small scale, exactly as the raw column in this page's own verification did.
Small m means real variance, not just a rounding error. The standard error is
1.04/√m — about 26% for this demo's m = 16, dropping to about 3.3% at
the m = 1024 a byte-frugal production sketch might actually use (1KB of registers, one
byte each), or under 1% at m = 16384 (16KB). The trade is direct: more registers, less
noise, more memory — and unlike a Bloom filter's k or a Count-Min Sketch's
d and w, there's no way to shrink the error after the fact without
starting a new sketch, because past hashes were never kept.
No membership test, no per-item count, no way to remove — cardinality only. Same absence of per-item information the Bloom filter and Count-Min Sketch both have, for the same underlying reason (a register update erases which item caused it), but sharper here: even the Bloom filter can say "probably in," and the Count-Min Sketch can estimate one item's frequency. HyperLogLog can answer exactly one question — how many distinct items, in total — and nothing about any individual one.
This implementation omits the large-range correction. The original HyperLogLog paper adds a second correction for cardinalities approaching a meaningful fraction of the 32-bit hash space (roughly above 2²⁹ items for a 32-bit hash) — a regime this fnv1a-based, browser-JS demo cannot reach and so doesn't implement. Production sketches (Redis, database engines) handle it; a from-scratch implementation that only ports the small-range correction, as this page's reference does, would silently misbehave at that extreme.
PFADD / PFCOUNT / PFMERGE
commands — built into Redis core (not a module, unlike the RedisBloom package the
Count-Min Sketch page mentions), using
12KB fixed per key regardless of how many elements were added, with PFMERGE
implementing exactly the elementwise-max merge described above.APPROX_COUNT_DISTINCT functions —
BigQuery, Presto/Trino's approx_distinct, and similar engines use HyperLogLog
variants under the hood for exactly the case where an exact COUNT(DISTINCT ...)
would need a full shuffle or a set the size of the data.A different fixed-memory question over the same kind of unbounded stream: instead of "how many distinct items," Reservoir Sampling answers "give me a fair random sample of them," also in one pass without knowing the stream's length up front.
Time: both add and estimate are O(1)
in the number of registers, which is fixed — like the Bloom filter's O(k) and the
Count-Min Sketch's O(d), the cost never grows with how many items, distinct or
otherwise, have gone in. Space: a fixed O(m) single-byte registers
(one byte comfortably covers any realistic ρ), chosen once from the tolerable error
1.04/√m — independent of whether 10 or 10 billion distinct items are added, which is
the entire reason to reach for this structure over an exact Set whose memory grows
with every new distinct item.
This site's guide, Choosing a Probabilistic Structure, compares this entry against Count-Min Sketch, Reservoir Sampling, and the site's other fixed-memory unbounded-stream structures side by side.