HyperLogLog Cardinality Estimator

Start from brute force

The obvious approach counts exactly: len(set(items)). It is correct by definition and runs in O(n) expected time, but it needs O(d) space for d distinct items, because the set stores every one of them. A billion distinct 16-byte ids take at least 16 GB before any per-entry overhead, and two machines can only combine their counts by shipping their whole sets to each other. That memory is the reason HyperLogLog exists: it answers the same question within a few percent from m small registers, and Redis’s version uses 16,384 of them in 12 KB, whether the stream holds a thousand distinct values or a billion.

The approach

A good hash makes every bit a fair coin flip, so a hash that starts with r - 1 zeros and then a 1, rank r, turns up with probability 2^-r; a rank of 10 hints at about 2¹⁰ distinct values. One maximum is noisy, so HyperLogLog splits the stream into m registers by the hash’s top bits, keeps the maximum rank per register, and combines them with a harmonic mean, which stops one lucky register from dominating. Duplicates hash identically, so they change nothing.

In the reference solution, m = 1 << p and bits = 32 - p. For each item, bucket = h >> bits takes the top p bits of hash32(it), w keeps the rest, and the inner loop counts the leading zeros of w to get rank; regs[bucket] keeps the maximum. Then it sums Z = sum(2.0 ** (-r) for r in regs) and computes E = alpha * m * m / Z. When E <= 2.5 * m and V registers are still 0, linear counting, m * math.log(m / V), replaces the raw estimate, which is biased in that range.

Walk through an example

The examples stream hundreds of items, so trace a small call, hll_estimate(['a', 'b', 'a', 'c'], 4), with m = 16 registers and bits = 28.

Complexity

Optimal: O(n · L) time to hash n strings of length L, plus a leading-zero scan of at most 32 - p bits per item and O(m) to combine the registers; O(m) space, fixed however many items stream past. Brute force (an exact set): O(n · L) expected time too, but O(d) space that grows with every distinct item.

Edge cases to test

• hll_estimate([], 8) → 0. All 256 registers are 0, so the raw estimate is alpha · m, below 2.5m, and linear counting gives m · ln(m / m) = 0.
• Duplicates: hll_estimate(["x"] * 500, 8) → 1, the same as hll_estimate(["x"], 8). Every copy has the same hash, register and rank.
• A remainder of all zeros: when w == 0 the rank is bits + 1, the largest possible, and the leading-zero loop must not run off the end looking for a 1.
• Too few registers: with p = 4 the standard error is about 1.04 / √16 = 26%; with p = 8 it is 6.5%, and the p = 14 that Redis uses gives 0.81%.
• Huge cardinalities: a 32-bit hash starts colliding as the count approaches 2³², which biases the estimate low. The original paper adds a large-range correction above 2³²/30, and HyperLogLog++ moves to a 64-bit hash instead; the reference has neither.
• Order: hll_estimate(["a","b","c","d"], 6) and the same call on the reversed list both return 4, because each register keeps a maximum and maximum does not care about order.

Common mistakes

• Exact counting with a set — that defeats the purpose; HLL trades a small error for O(1) memory.
• Too few buckets, so the estimate has high variance.
• Skipping the small-range bias correction, which HLL needs at low cardinalities.
• Counting leading zeros over the whole 32-bit hash instead of the bits left after the bucket index. The top p bits already chose the register, so reusing them ties the rank to the bucket number.

Follow-ups an interviewer asks next

How do you merge two HyperLogLog sketches?

Take the element-wise maximum of their registers. If both used the same p and the same hash, the result is exactly the sketch you would have built from the union of the two streams, so counting distinct users across a thousand servers means shipping a thousand small register arrays rather than the users themselves. This is what Redis PFMERGE does.

Can HyperLogLog estimate the size of an intersection?

Only indirectly, through inclusion–exclusion: |A ∩ B| = |A| + |B| − |A ∪ B|, with the union taken from a merged sketch. Each term’s error is relative to the large sets, so a small intersection can come out with a huge relative error, or even negative. For overlap and similarity between sets, MinHash is the better tool.

How much memory does a production HyperLogLog use?

The standard error is about 1.04 / √m, so accuracy improves with the square root of memory. With a 64-bit hash a rank never exceeds 64, so each register fits in 6 bits: Redis stores 16,384 of them in 12 KB per key for a 0.81% standard error, and keeps small sets in a sparse encoding until they grow.

What does HyperLogLog++ change?

Google’s HyperLogLog++ uses a 64-bit hash, so the large-range correction is unnecessary. It corrects the raw estimate’s bias in the low and middle range with empirically measured values and chooses the switch to linear counting from measured thresholds. And it stores small sketches sparsely, so a set with few items costs far less than the full register array.

Where this shows up

HyperLogLog counts unique users, IPs, or search queries at massive scale in kilobytes — it is the engine behind Redis PFCOUNT and BigQuery’s APPROX_COUNT_DISTINCT, which uses the HyperLogLog++ variant. Redis spends 12 KB per key for a 0.81% standard error whether the key has seen a thousand distinct values or billions: one of the great space-for-accuracy deals in systems.

Reference solution

import math

def hash32(s):                      # provided (xmur3 32-bit, matches TypeScript)
    h = (1779033703 ^ len(s)) & 0xffffffff
    for ch in s:
        h = ((h ^ ord(ch)) * 3432918353) & 0xffffffff
        h = ((h << 13) | (h >> 19)) & 0xffffffff
    h = ((h ^ (h >> 16)) * 2246822507) & 0xffffffff
    h = ((h ^ (h >> 13)) * 3266489909) & 0xffffffff
    return (h ^ (h >> 16)) & 0xffffffff


def hll_estimate(items, p):
    m = 1 << p
    bits = 32 - p
    regs = [0] * m
    for it in items:
        h = hash32(it)
        bucket = h >> bits              # top p bits select the register
        w = h & ((1 << bits) - 1)       # remaining bits
        rank = 1
        for b in range(bits - 1, -1, -1):
            if (w >> b) & 1:
                break
            rank += 1                    # count leading zeros
        if w == 0:
            rank = bits + 1
        if rank > regs[bucket]:
            regs[bucket] = rank          # keep the max rank per register

    Z = sum(2.0 ** (-r) for r in regs)
    alpha = 0.7213 / (1 + 1.079 / m)
    E = alpha * m * m / Z
    if E <= 2.5 * m:                     # small-range correction
        V = regs.count(0)
        if V > 0:
            E = m * math.log(m / V)
    return int(E)


print(hll_estimate([str(i) for i in range(1000)], 8))   # -> about 1000

function hash32(s: string): number {   // provided (xmur3 32-bit, matches Python)
  let h = (1779033703 ^ s.length) >>> 0;
  for (let i = 0; i < s.length; i++) {
    h = Math.imul(h ^ s.charCodeAt(i), 3432918353);
    h = (h << 13) | (h >>> 19);
  }
  h = Math.imul(h ^ (h >>> 16), 2246822507);
  h = Math.imul(h ^ (h >>> 13), 3266489909);
  h ^= h >>> 16;
  return h >>> 0;
}

function hllEstimate(items: string[], p: number): number {
  const m = 1 << p;
  const bits = 32 - p;
  const regs = new Array(m).fill(0);
  for (const it of items) {
    const h = hash32(it);
    const bucket = h >>> bits;           // top p bits pick the register
    const w = h & ((1 << bits) - 1);     // remaining bits
    let rank = 1;
    for (let b = bits - 1; b >= 0; b--) {
      if ((w >>> b) & 1) break;
      rank++;                            // count leading zeros
    }
    if (w === 0) rank = bits + 1;
    if (rank > regs[bucket]) regs[bucket] = rank;
  }

  let Z = 0;
  for (const r of regs) Z += Math.pow(2, -r);
  const alpha = 0.7213 / (1 + 1.079 / m);
  let E = (alpha * m * m) / Z;
  if (E <= 2.5 * m) {                     // small-range correction
    const V = regs.filter((r) => r === 0).length;
    if (V > 0) E = m * Math.log(m / V);
  }
  return Math.floor(E);
}

console.log(hllEstimate(Array.from({ length: 1000 }, (_, i) => "" + i), 8)); // -> about 1000