HyperLogLog

HyperLogLog (HLL) is a probabilistic algorithm that estimates the distinct cardinality of a multiset — how many unique items have been seen — using a fixed, tiny amount of state to count cardinalities into the billions. Flajolet et al.’s original 2007 abstract advertises ~1.5 KB of memory for ~2% relative error (Flajolet et al. 2007); the most-cited production figure — Redis’s default — is 12 KB for 0.81% standard error (Redis HLL docs, antirez 2014). Both are the same algorithm at different precisions (p). The algorithm hashes each item to a uniformly distributed bit string, splits it into a bucket index (the first p bits) and a value (the rest), records the maximum number of leading zeros in the value seen for each bucket, and combines per-bucket estimates via the harmonic mean to produce a global cardinality estimate. Introduced by Philippe Flajolet, Éric Fusy, Olivier Gandouet & Frédéric Meunier in 2007 as an improvement on Flajolet & Martin’s 1985 probabilistic-counting structure, HLL is now the basis of distinct-cardinality estimation at scale: it backs Redis’s PFADD/PFCOUNT commands, BigQuery’s APPROX_COUNT_DISTINCT, Snowflake’s HLL, Presto / Trino’s approx_distinct, Spark’s approx_count_distinct, Apache Druid’s hyperUnique, and the Reddit / Google Analytics / Facebook distinct-user-counting pipelines. The 2013 HyperLogLog++ paper from Google introduced sparse representation, bias correction, and 64-bit hashing — the variant most production systems actually deploy.

1. Intuition — The Longest Run of Heads

If you flip a fair coin until you see heads (so you record a run of tails ending in a head), the expected length of the run of tails is 1. If you do this experiment many times, the expected maximum run length grows as log₂(n) where n is the number of trials.

This means: if I see a run of k tails-before-heads in some sequence of trials, I can estimate that I performed roughly 2^k trials. This is the kernel of HLL.

To turn a deterministic stream of items into “coin flips,” we hash each item: a good hash function produces a uniformly distributed bit string, so the leading bits of hash(x) look exactly like a sequence of independent fair-coin flips (1 = “heads,” 0 = “tails,” in some convention). The number of leading zeros is the “run of tails.”

Two refinements get us from “log₂(n)” to “near-optimal”:

1. Just looking at the maximum across the whole stream is too noisy. Variance is huge — a single freak outlier with 30 leading zeros gives a single estimate of 2³⁰ even if the stream had only 100 distinct items.

2. Fix that with stochastic averaging. Use the first p bits of the hash to assign each item to one of m = 2^p buckets. Each bucket runs the leading-zero-count experiment independently on its slice of the data. Combine the per-bucket maxima via the harmonic mean. Variance shrinks as ~1/√m, giving the famous 1.04/√m relative error.

The harmonic mean (rather than arithmetic) is the trick that makes HLL beat its predecessors LogLog and SuperLogLog: it suppresses the influence of large outlier bucket values, which arithmetic mean would over-weight.

2. Tiny Worked Example (m = 4 buckets, p = 2 bits)

We use a 16-bit hash for clarity; production HLL uses 64-bit hashes.

For each item, compute its 16-bit hash, split off the first 2 bits as a bucket index in [0, 3], and count leading zeros (plus one) in the remaining 14 bits.

Item	Hash (16 bits)	Bucket (first 2)	Tail (14 bits)	Leading zeros + 1
apple	01 1010 0011 0101 00	1	10 1000 1101 0100	1
banana	11 0001 0000 1010 11	3	00 0100 0010 1011	2
cherry	00 0001 1100 0001 11	0	00 0111 0000 0111	2
apple (dup)	01 1010 0011 0101 00	1	10 1000 1101 0100	1 (no change)
date	00 0000 1111 0000 11	0	00 0011 1100 0011	3 (improves bucket 0)

Per-bucket maxima after this 5-item stream (4 distinct):

Bucket	Max leading zeros + 1
0	3
1	1
2	0 (never visited)
3	2

The raw HLL estimate for cardinality n is:

$\text{Estimate}={\alpha }_m\cdot m^2\cdot {\left({\sum }_{j=0}^{m-1}{2}^{-M_j}\right)}^{-1}$

with α_m a bias-correction constant (≈ 0.673 for m=16, ≈ 0.697 for m=32, → 0.7213/(1+1.079/m) for large m).

Uncertain

Verify: the value α_4 ≈ 0.5251 used in the toy below. Reason: Flajolet et al. 2007 tabulate α_m only for m ∈ {16, 32, 64} plus the large-m asymptotic 0.7213/(1+1.079/m); the exact constant for m=4 must be obtained by evaluating the defining integral α_m = (m ∫₀^∞ (log₂((2+u)/(1+u)))^m du)^{-1} directly, and secondary sources disagree (values of ~0.52–0.62 are quoted). The large-m formula is not valid this far from the asymptotic regime. To resolve: numerically evaluate the integral for m=4. The toy is illustrative only — production HLL never runs at m=4. uncertain

For our toy m=4, taking α_m ≈ 0.5251 (see caveat above). Plugging in:

Σ 2^(-M_j) = 2^-3 + 2^-1 + 2^0 + 2^-2 = 0.125 + 0.5 + 1.0 + 0.25 = 1.875
Estimate = 0.5251 × 4² × (1 / 1.875) = 0.5251 × 16 × 0.5333 ≈ 4.48

True cardinality is 4 — the toy estimate is 4.48, error ~12%. With m=4 and only 5 inserts the algorithm is well outside its asymptotic regime. Production HLLs use m=2¹² to 2¹⁶ buckets and run on much bigger streams — that’s where the ~2% error materializes.

The mental model: each bucket is one of m parallel coin-flip experiments. Each experiment estimates cardinality via the longest run it has seen. The harmonic-mean combiner tells the global cardinality from the m local estimates.

3. The Algorithm

3.1 Construction

• Choose p ∈ [4, 18] (typical: 11–14). Number of buckets is m = 2^p.
• Allocate an array M of m small counters (typically 6 bits each — sufficient for hashes up to 2⁶⁴).
• Fix a hash function h: items → {0, 1}^L with L ≥ 32 (production: L = 64 in HyperLogLog++).

3.2 Insertion — add(x)

function add(x):
    hash_bits = h(x)                       # L bits
    j = first p bits of hash_bits          # bucket index in [0, m)
    w = remaining (L - p) bits
    rho_w = 1 + position of leftmost 1-bit in w  # i.e., (leading zeros in w) + 1
    if rho_w > M[j]:
        M[j] = rho_w

rho(w) returns one plus the number of leading zeros in w. If w is all zeros, rho(w) = L − p + 1 by convention.

3.3 Cardinality Estimate

function count():
    Z = sum over j of 2^(-M[j])            # raw indicator function
    raw = alpha_m * m^2 / Z                # raw estimate

    # Small-range correction (LinearCounting):
    if raw <= (5/2) * m:
        V = number of zero registers in M
        if V > 0:
            return m * ln(m / V)            # LinearCounting
        else:
            return raw

    # Large-range correction (only for 32-bit hashes; HLL++ skips this):
    if raw > (1/30) * 2^L:
        return -2^L * ln(1 - raw / 2^L)

    return raw

Bias correction at the boundary cardinalities is crucial:

• Small N (n ≲ m/2) — many buckets are still 0 (never received an item with that prefix). The raw estimator is heavily biased. Fall back to LinearCounting: estimate as m · ln(m/V) where V is the number of zero buckets (this is just the “balls in bins” cardinality estimator).
• Large N (n approaching 2^L) — for 32-bit hashes the hash space saturates and the estimator under-counts. Apply the −2^L · ln(1 − raw/2^L) correction. With 64-bit hashes (HLL++) this never occurs at any practical cardinality, so the correction is omitted.

3.4 The Constant α_m

The α_m constant comes from integrating the per-bucket distribution to make the estimator asymptotically unbiased:

m	α_m
16	0.673
32	0.697
64	0.709
≥ 128	0.7213 / (1 + 1.079/m)

Don’t try to derive α_m on a whiteboard — quote the formula. The Flajolet et al. 2007 paper has the full derivation in §3.

4. Python Implementation

import math
from hashlib import blake2b
 
 
class HyperLogLog:
    """Classic HyperLogLog (Flajolet et al. 2007). For production use the
    HyperLogLog++ variant with sparse representation and bias tables
    (Heule, Nunkesser & Hall 2013)."""
 
    def __init__(self, p: int = 14):
        if not (4 <= p <= 18):
            raise ValueError("p must be in [4, 18]")
        self.p = p
        self.m = 1 << p              # number of buckets
        self.M = [0] * self.m         # 6-bit counters in principle; ints here for clarity
        self.alpha = self._alpha(self.m)
 
    @staticmethod
    def _alpha(m: int) -> float:
        if m == 16: return 0.673
        if m == 32: return 0.697
        if m == 64: return 0.709
        return 0.7213 / (1.0 + 1.079 / m)
 
    def _hash64(self, item: bytes) -> int:
        # 64-bit hash: take first 8 bytes of BLAKE2b-128 digest as a uint64.
        return int.from_bytes(blake2b(item, digest_size=8).digest(), "big")
 
    def add(self, item: str) -> None:
        x = self._hash64(item.encode())
        # Bucket index: top p bits.
        j = x >> (64 - self.p)
        # Tail: remaining (64 - p) bits, padded with a leading 1 to ensure
        # rho is well-defined when the tail is all zeros.
        w = (x << self.p) & ((1 << 64) - 1) | (1 << (self.p - 1))
        # rho = 1 + count of leading zeros in the (64 - p)-bit tail.
        rho = 64 - w.bit_length() + 1
        if rho > self.M[j]:
            self.M[j] = rho
 
    def count(self) -> int:
        Z = sum(2.0 ** (-r) for r in self.M)
        raw = self.alpha * self.m * self.m / Z
        if raw <= 2.5 * self.m:
            V = self.M.count(0)
            if V > 0:
                return int(round(self.m * math.log(self.m / V)))
        # 64-bit hash: large-range correction not needed at practical scales.
        return int(round(raw))
 
    def merge(self, other: "HyperLogLog") -> None:
        """Merge two HLLs by taking elementwise max — exact, no error inflation."""
        if self.p != other.p:
            raise ValueError("HLLs with different p cannot be merged")
        self.M = [max(a, b) for a, b in zip(self.M, other.M)]
 
 
# --- demo ----------------------------------------------------------------
if __name__ == "__main__":
    import random, string
    hll = HyperLogLog(p=14)         # m = 16,384 buckets, ~12 KB
    distinct = set()
    for _ in range(1_000_000):
        item = "".join(random.choices(string.ascii_letters, k=10))
        hll.add(item)
        distinct.add(item)
    print(f"true distinct = {len(distinct)}")
    print(f"HLL estimate  = {hll.count()}")
    print(f"relative error = {abs(hll.count() - len(distinct)) / len(distinct):.4%}")

A few implementation notes:

1. 6-bit counters in production. A 64-bit hash with p=14 leaves 50 bits for the tail, so rho ranges over [1, 51]. Six bits per counter (max value 63) suffice. With m = 16,384 and 6 bits each, total state is 12,288 bytes ≈ 12 KB — and this p=14 is exactly Redis’s hardcoded default (HLL_P 14, HLL_BITS 6, per hyperloglog.c). The often-quoted 1.5-KB figure is the original paper’s abstract example at p=11 (m=2,048), not Redis’s configuration.

2. The | (1 << (p - 1)) trick in the bit-twiddling: ensures the tail is never all zeros, which would make the “position of leftmost 1” undefined. The Python implementation handles this with bit_length; in C, __builtin_clzll is the standard primitive.

3. Mergeability via element-wise max. Two HLLs with the same p and hash function can be merged in O(m) by taking the elementwise maximum: M_merged[j] = max(M_A[j], M_B[j]). This is exact — there’s no error inflation from merge. Because of this, HLL is a natural fit for MapReduce: each mapper computes a local HLL, the reducer merges. This is why BigQuery, Spark, and Druid all deploy HLL — distributed cardinality is otherwise hard.

5. Math — Why the 1.04/√m Error Bound Holds

This is the section that interviewers love and the section most candidates skip. The full proof is involved (Flajolet et al. 2007 spans 30+ pages); here is the structural sketch.

5.1 Setting up the random variable

Let n be the true cardinality. For each bucket j, let M_j be the maximum value of rho(w) over the items hashing to bucket j. Each item independently lands in bucket j with probability 1/m, so the number of items in bucket j is approximately Poisson with mean n/m.

For a bucket with k items, M_j has the same distribution as the maximum of k IID geometric(1/2) random variables. The CDF is:

$P(M_j\le r\mid k)=(1-2^{-r}{)}^k$

5.2 The harmonic-mean estimator

Define the indicator function:

$Z={\sum }_{j=0}^{m-1}{2}^{-M_j}$

Each term 2^(-M_j) is, in expectation, roughly m/n (one over the per-bucket cardinality). So Z ≈ m · m/n = m²/n, and m²/Z ≈ n. The constant α_m corrects the asymptotic bias.

The use of the harmonic mean (m / Σ 2^{-M_j} is structurally a harmonic mean of the 2^{M_j}) is what gives HLL its name and its variance reduction over LogLog. LogLog combines its per-bucket estimates with the geometric mean of the 2^{M_j} — equivalently, the arithmetic mean of the register exponents M_j followed by exponentiation — yielding a relative error of 1.30/√m (Durand & Flajolet 2003). The harmonic mean, by contrast, is dominated by small terms — exactly the buckets with small M_j, which are the well-behaved ones. Large outliers (high M_j) contribute a small 2^{-M_j} to the sum, so they barely move the estimate; this taming of the slow-decaying right tail is what cuts HLL’s error to 1.04/√m.

5.3 Variance and standard error

Flajolet et al. 2007 prove (Theorem 1) that the relative standard error of the HLL estimator is asymptotically:

$\frac{{\sigma }_n}{n}\approx \frac{1.04}{\sqrt{m}}$

For m = 2^p (computing 1.04/√(2^p)):

• p = 10 → σ ≈ 3.25%
• p = 11 → σ ≈ 2.30% (the original paper’s 1.5 KB / ~2% regime)
• p = 12 → σ ≈ 1.62%
• p = 14 → σ ≈ 0.81% (Redis default — HLL_P 14, 16,384 registers, per hyperloglog.c)
• p = 15 → σ ≈ 0.57% (BigQuery default for HLL_COUNT.INIT, per BigQuery HLL++ docs)
• p = 16 → σ ≈ 0.41%

Doubling m halves the variance, but only doubles the memory. At p=14 you get sub-1% error in 12 KB regardless of cardinality. This is the magic — and it is exactly what Redis ships: “Redis uses 16384 registers, so the standard error is 0.81%” (antirez 2014).

5.4 Why the variance shrinks as 1/m, not 1/√m

The “stochastic averaging” trick: each bucket independently estimates n/m with a (high-variance) 2^{M_j} estimator, and we have m such estimators. The variance of the combined estimator is the per-bucket variance divided by m — same logic as averaging m IID samples cuts variance by m. Take square root → standard error 1/√m.

5.5 Memory bound

Each counter needs ⌈log₂(L − p + 1)⌉ bits (since rho ranges over [1, L − p + 1]). With L = 64 and p = 14, that’s ⌈log₂(51)⌉ = 6 bits. Total: m × 6 bits = 16,384 × 6 / 8 = 12,288 bytes ≈ 12 KB for sub-1% error on cardinalities up to 2⁵⁰.

For p = 11: m × 6 = 2,048 × 6 / 8 = 1,536 bytes ≈ 1.5 KB — the famous figure from the original paper’s abstract. Error is ~2.3%. (Note: Redis does not use p=11; its default is p=14 / 12,288 bytes for the dense form, plus an 8-byte cached-cardinality tail = 12,296 bytes total, per antirez 2014. The 1.5 KB number is frequently — and incorrectly — attributed to Redis.)

The space-error tradeoff is m bits ≈ 6 · (1/error)². To halve the error you quadruple the memory — but the absolute numbers are so small that doubling m from 12 KB to 24 KB to chase 0.5% error is usually worth it.

5.6 Why this is near-optimal

A cardinality-counting algorithm must store something about the past — and information-theoretic lower bounds (Alon-Matias-Szegedy 1999, Indyk-Woodruff 2003) show that approximating cardinality up to N with relative error ε requires Ω(ε⁻² + log N) bits in the worst case. HLL uses O(ε⁻² · log log N + log N) bits — the + log N is for the registers to be able to hold leading-zero counts up to log N, and the per-register state grows as log log N because each register stores a value (a leading-zero count, which is itself at most ~log N, hence log log N bits) (HyperLogLog, Wikipedia; Indyk & Woodruff 2003). HLL is therefore optimal except for a log log N factor on the dominant ε⁻² term — that single extra log log N is precisely the gap between HLL and the information-theoretic optimum, and is the meaning of “near-optimal” in the paper’s title. (The truly optimal Θ(ε⁻² + log N) algorithm of Kane-Nelson-Woodruff 2010 closes that gap but is impractical — see §8.6.)

6. HyperLogLog++ — What’s Different in Production

Heule, Nunkesser & Hall’s 2013 EDBT paper (Google) is the variant deployed in BigQuery, Stratosphere, and most production systems. Three improvements:

6.1 64-bit Hashing

Original HLL used 32-bit hashes, requiring large-range bias correction at cardinalities > 2³⁰. HLL++ uses 64-bit hashes (BLAKE2, MurmurHash3 128-bit, xxHash64), making the large-range correction unnecessary for any realistic n.

6.2 Bias Correction Tables

For low cardinalities (n ≲ 5m), Heule et al. measured the empirical bias of the raw estimator at many test points and stored the bias-vs-raw-estimate curve as a lookup table. At query time, look up the bias for the current raw estimate and subtract. Cuts low-N error by ~2×.

6.3 Sparse Representation

For very low cardinalities (n ≪ m), most of the m buckets are still 0 — wasteful. HLL++ stores a run-length-encoded list of (bucket_index, rho) pairs while the sketch is small (sparse mode), and only switches to the dense m-register array once the sparse encoding would grow to roughly the size of the dense form. The Heule et al. design promotes to dense when the sparse list would exceed the dense representation; for a sketch that ends up tracking a small number of distinct items, sparse mode means the memory footprint is proportional to actual cardinality, not the worst-case dense size.

Redis makes the threshold explicit and configurable. Its hll-sparse-max-bytes directive defaults to 3000 bytes: a Redis HLL stays sparse (run-length-encoded zero runs) while its serialized length is below that, and hllSparseSet() promotes to the fixed 12,288-byte dense form (16384 × 6 bits) once sdslen + deltalen > server.hll_sparse_max_bytes (hyperloglog.c; Redis HLL docs). Note the threshold is measured in bytes of the encoded sketch, not in number of distinct elements — a common confusion.

7. Production Use Cases

• Redis PFADD / PFCOUNT / PFMERGE. Native HLL data type. Precision is hardcoded p=14 (16,384 registers, 6 bits each → 12,288-byte dense form + 8-byte cached-cardinality tail = 12,296 bytes); standard error 0.81% (hyperloglog.c, antirez 2014). Used by countless apps for distinct-user counting, deduplication of events, and unique-IP tracking.

• Google BigQuery APPROX_COUNT_DISTINCT(col) and HLL_COUNT.*. Explicitly the HLL++ algorithm from the 2013 paper. HLL_COUNT.INIT defaults to precision 15 and accepts a precision argument in the range 10–24 (BigQuery HLL++ docs). Used in dashboards over petabyte tables where exact distinct counts would scan TBs.

• Snowflake HLL and APPROX_COUNT_DISTINCT. Same approach.

• Presto / Trino approx_distinct(col, e). Allows specifying error budget directly; selects p automatically.

• Apache Spark approx_count_distinct(col, rsd). Uses HLL++ under the hood.

• Apache Druid hyperUnique / HLL Sketch. Time-series cardinality at column level.

• Reddit “unique visitors per post.” Reddit’s engineering blog (~2017) describes per-post HLLs for unique-viewer counts — billions of posts, ~12 KB each → manageable storage.

• Facebook unique-user campaign reporting. A canonical HLL-at-scale deployment.

• Google Analytics distinct-user counts. Reportedly HLL-based; verify against current GA documentation.

• Apache DataSketches library — production HLL implementation alongside Count-Min Sketch and others.

• Network monitoring distinct-flow counting. Per-port HLL counters for “how many distinct flows have we seen in the last hour” without storing the flows.

Uncertain

Verify: Snowflake’s exact algorithm variant (the docs say “HyperLogLog”; whether it is plain HLL or HLL++ with bias correction is not stated in a primary source consulted here), Reddit’s current per-post HLL pipeline (the ~2017 engineering write-up is dated), and whether Google Analytics 4’s distinct counts use HLL++ specifically. Reason: not directly addressed by a primary source fetched during this revision; vendor docs describe the function but not always the precise variant or parameters. To resolve: read each vendor’s current SQL reference and engineering blog at quote time. The Redis (p=14) and BigQuery (p=15, range 10–24) figures are primary-source-confirmed above. uncertain

8. Variants

8.1 LogLog and SuperLogLog (Durand & Flajolet 2003)

HLL’s immediate predecessors, introduced in the same paper. LogLog combines its per-bucket maxima with the geometric mean of the 2^{M_j} (i.e. the arithmetic mean of the exponents M_j, then exponentiate), giving a relative error of 1.30/√m. SuperLogLog discards the largest ~30% of register values before averaging — retaining only the 70% smallest — which improves the error to 1.05/√m (Durand & Flajolet 2003). This truncation is effective but ad-hoc. HyperLogLog replaces it with the principled harmonic mean, reaching 1.04/√m without any truncation heuristic — slightly better than SuperLogLog and simpler to analyze and merge.

8.2 PCSA / Flajolet-Martin (1985)

The 1985 ancestor: instead of “max leading zeros,” use a bit vector per bucket and union over inserts. Larger memory; conceptually similar.

8.3 HyperLogLog Sketch (Streaming-Algorithms, Chassaing-Gerin)

A theoretical refinement reducing the constant by a few percent. Rarely used in production.

8.4 KMV (k-Minimum Values)

An alternative cardinality sketch: keep the k smallest hash values, estimate n ≈ k · 2^L / max_in_kept. Mergeable; lower memory at small k; higher variance than HLL at large k. Used in Apache DataSketches’ Theta Sketch family.

8.5 Theta Sketch (Apache DataSketches)

Generalizes KMV with set operations (union, intersection, difference) at well-defined error bounds. Hard with HLL; native in Theta Sketch. The choice between HLL and Theta is: HLL for raw distinct count; Theta if you need set arithmetic.

8.6 Compressed HyperLogLog (Kane-Nelson-Woodruff 2010)

Information-theoretically optimal Θ(ε⁻² + log log N) bits. Practical implementations are awkward; standard HLL++‘s slight constant-factor inefficiency is rarely worth the engineering complexity.

8.7 Sliding-Window HLL

HLL doesn’t natively support deletions or windows. Sliding-window variants maintain multiple HLLs over time slices and merge windowed unions. There are also “decaying HLL” approaches that periodically downscale all counters.

9. Pitfalls

9.1 HLL Doesn’t Estimate Frequency

HLL answers “how many distinct items?” not “how many times did x appear?” — that’s Count-Min Sketch. Confusing the two leads to wrong tool selection in interviews.

9.2 Hash Quality Matters

The error bound assumes uniform hashes. A biased hash function (e.g., hash(x) = x mod 2^32 on a non-uniform key distribution) inflates collision rates and breaks the analysis. Use MurmurHash, xxHash, or BLAKE2 — universal hash families. See Hash Function Design.

9.3 Same Hash Function for Merge

Two HLLs can only be merged if they were built with the same hash function and same p. A common production bug: rolling out a hash-function change while maintaining historical HLLs that were built with the old hash. Result: silently incorrect merged cardinalities. Version your hash function and refuse to merge across versions.

9.4 Confidence Intervals Aren’t Absolute Bounds

The 1.04/√m is a standard deviation, not an absolute error. An HLL with p=14 has σ ≈ 0.81%, but the worst-case error for any single estimate is much higher — 3σ events occur ~0.3% of the time. If you need an absolute error guarantee, you need a bigger HLL than the σ formula implies.

9.5 Set Operations Beyond Union Are Lossy

Union via merge is exact (in the sense that error doesn’t compound). Intersection of two HLLs is computed as |A| + |B| − |A ∪ B|, which suffers from cancellation error when A ≈ B (the “small difference of large numbers” problem). For interesection-heavy workloads use Theta Sketch (Apache DataSketches), where intersection is a first-class operation with bounded error.

9.6 Low-Cardinality Bias

Without the LinearCounting fallback (or HLL++‘s bias tables), the raw HLL estimator overshoots dramatically for n ≲ m/2 — when most registers are still zero. Work the worst case: with 1 distinct item, exactly one register holds a small value (say M_j = 1) and the other m − 1 hold 0, so Z = Σ 2^{−M_j} = (m−1)·2^0 + 2^{−1} = m − 0.5, and raw = α_m·m²/Z ≈ 0.7213·m²/(m−0.5) ≈ 0.7213·m. For m = 16,384 that is ≈ 11,800 — the raw estimator reports nearly twelve thousand distinct items when there is one. This is why the small-range branch is mandatory: LinearCounting (m·ln(m/V) with V = m − 1 zero registers) gives 16384·ln(16384/16383) ≈ 1.0 — the correct answer. Always apply the small-range correction below raw ≤ (5/2)·m.

9.7 The Birthday Paradox Boundary

At cardinality n ≈ √(2 · 2^L) (about 2³² for L=64), hash collisions become non-negligible. HLL++ with 64-bit hashes is fine up to cardinalities of ~2⁵⁰ before the assumption “different items → different hashes” starts breaking. For larger n, use 128-bit hashes.

9.8 Memory Underestimation

The famous “1.5 KB for billions of items” figure is the original paper’s p=11 / 2.3%-error case, and is not what Redis ships. Production systems usually want better error and use p=14 (16,384 × 6 bits = 12,288 bytes ≈ 12 KB, Redis’s default) or p=16 (65,536 × 6 bits = 49,152 bytes ≈ 48 KB). Don’t quote the smallest number when sizing your fleet.

9.9 Distributed Drift

If two HLLs are maintained on different shards and merged periodically, both must use the same hash function, p, and (for HLL++) sparse-mode threshold. Without coordination, merged outputs are silently wrong.

10. Diagram — Bucket Selection and Leading-Zero Counting

flowchart LR
    X["Item x"] --> H["64-bit hash<br/>h(x) = 0110 1011 0001..."]
    H --> P["First p bits<br/>(p=4 here) → bucket index"]
    H --> W["Remaining (64-p) bits → tail"]
    P --> J["j = 0110 = bucket 6"]
    W --> RHO["ρ(w) = 1 + leading zeros<br/>e.g. tail = 0001..., ρ = 4"]
    J --> M["Bucket array M"]
    RHO --> M
    M --> UPD["M[6] = max(M[6], 4)"]

    Q["count() query"] --> SUM["Z = Σ_j 2^(-M[j])"]
    SUM --> EST["estimate = α_m · m² / Z"]
    EST --> CORR{n_raw ≤ 2.5·m?}
    CORR -->|yes| LIN["LinearCounting:<br/>m · ln(m/V)"]
    CORR -->|no| OUT[return raw]

What this diagram shows. A single insertion path: hash the item, slice off the first p bits as the bucket index, count leading zeros in the rest to get rho, take the max into that bucket. The count() path: combine all m bucket maxima via the harmonic-mean-like formula α_m·m²/Z, then apply small-range correction if appropriate. Two key features: (1) per-bucket state is tiny (6 bits), (2) all m buckets are independent — making merge across HLLs an elementwise max. The independence is what gives HLL its mergeability and its variance bound; the tiny per-bucket state is what gives it the famous memory footprint.

11. Common Interview Problems

Problem	Why HLL
Design a “unique visitors” counter at scale	The canonical HLL application — billions of users, ~12 KB
Design BigQuery / Snowflake APPROX_COUNT_DISTINCT	HLL++ as the default implementation
Design a real-time analytics pipeline with distinct counts	Per-shard HLL + merge in reducer
Design a YouTube view counter for unique viewers	Per-video HLL; cheap merge across edge nodes
Design Twitter follower-count distinct-mention tracker	HLL per user; merges across regions
Design a distinct-flow counter for network monitoring	Per-port / per-VLAN HLL
Design an A/B testing platform with distinct-user metrics	One HLL per (variant, day) cell
Design an ad-impression deduplication system	HLL per (campaign, segment)

For coding rounds HLL is almost never asked at full implementation depth — but the intuition (hash + leading-zero count + bucketed harmonic mean) is interview gold for senior+ system-design rounds, especially when the interviewer presses on “but how does that actually work mathematically?“

12. Open Questions

• At what cardinality regime do KMV / Theta Sketch beat HLL in practice for raw distinct-count? Theory says HLL is optimal for that single operation; benchmarks would be welcome.
• Is there a clean way to extend HLL to time-decayed cardinality without maintaining separate sketches per time bucket?
• How does HLL’s behavior degrade under adversarial input (an attacker who can choose items to produce systematic bias)? Most analyses assume random hashes are uniform; real hash functions like xxHash have known attack patterns.
• When does HLL++‘s sparse representation lose to a plain sorted set for tiny cardinalities (< 100)? Empirically the crossover is around 50–100 distinct items, but I haven’t seen rigorous calibration.

13. See Also

• Bloom Filter — sister probabilistic structure (membership, not cardinality)
• Count-Min Sketch — sister probabilistic structure (per-item frequency, not cardinality)
• Hash Function Design — uniform hashing is the substrate for HLL’s analysis
• Theta Sketch — alternative cardinality + set-operations sketch family
• KMV Sketch — k-minimum-values sister sketch
• Reservoir Sampling — sister streaming algorithm (sampling, not counting)
• MapReduce — HLL’s mergeability is what makes it work in distributed settings
• Big-O Notation
• SWE Interview Preparation MOC