Problem 93 · Data Engineering & Streaming

HyperLogLog Cardinality Estimation

HardClassic DSA & systems

01Problem

Implement a simplified HyperLogLog that estimates the number of distinct items in a stream, supports merging, and corrects for small cardinalities.

02Key insight

Hash each item; the first p bits pick one of m=2^p registers and each register keeps the max leading-zero rank of the remaining bits. The harmonic mean of 2^-register gives the estimate with ~1.04/sqrt(m) relative error; fall back to linear counting when many registers are empty. Merge = elementwise max, which is why APPROX_COUNT_DISTINCT parallelises.

03Solution

solution.pypython32 lines

import hashlib
import math
from typing import Hashable


class HyperLogLog:
    def __init__(self, p: int = 12) -> None:
        if not 4 <= p <= 16:
            raise ValueError("p must be in [4, 16]")
        self.p, self.m = p, 1 << p
        self.registers = bytearray(self.m)
        self._alpha = 0.7213 / (1 + 1.079 / self.m)

    def add(self, item: Hashable) -> None:
        x = int.from_bytes(hashlib.blake2b(repr(item).encode(), digest_size=8).digest(), "big")
        idx = x >> (64 - self.p)                 # top p bits choose the register
        rest = x & ((1 << (64 - self.p)) - 1)
        rank = (64 - self.p) - rest.bit_length() + 1  # position of first 1-bit
        if rank > self.registers[idx]:
            self.registers[idx] = rank

    def count(self) -> float:
        raw = self._alpha * self.m * self.m / sum(2.0 ** -r for r in self.registers)
        zeros = self.registers.count(0)
        if raw <= 2.5 * self.m and zeros:
            return self.m * math.log(self.m / zeros)  # linear counting for small n
        return raw

    def merge(self, other: "HyperLogLog") -> None:
        if other.p != self.p:
            raise ValueError("precision mismatch")
        self.registers = bytearray(max(a, b) for a, b in zip(self.registers, other.registers))

Try it first.

TimeO(1) per add, O(m) per count

SpaceO(m) bytes (4 KB at p=12)

tests.py · 3 passing

tests.pypython14 lines

h = HyperLogLog(p=12)
for i in range(50000):
    h.add(f"user-{i}")
    h.add(f"user-{i}")  # duplicates do not change the estimate
assert abs(h.count() - 50000) / 50000 < 0.05
small = HyperLogLog(p=12)
for i in range(100):
    small.add(i)
assert abs(small.count() - 100) < 5
x, y = HyperLogLog(10), HyperLogLog(10)
for i in range(0, 6000): x.add(i)
for i in range(3000, 9000): y.add(i)
x.merge(y)
assert abs(x.count() - 9000) / 9000 < 0.1

04Staff-level follow-up

Why can't you compute distinct-count of an intersection reliably with HLL? Only union merges are native; intersection via inclusion-exclusion compounds errors badly for small overlaps - use MinHash/theta sketches when set operations matter.