HyperLogLog Cardinality Estimation in Python

A small HyperLogLog implementation using MD5 hashing and 256 registers to estimate the number of unique items in a large stream with fixed memory.

Medium Python 3.9+ Aug 9, 2026 Big data & Spark 14 views 0 copies

hyperloglog cardinality estimation probabilistic hashing

Python code

31 lines

Python 3.9+

import hashlib
import math

class HyperLogLog:
    def __init__(self, b=8):
        self.b = b
        self.m = 1 << b
        self.registers = [0] * self.m
        self.alpha = 0.7213 / (1 + 1.079 / self.m)

    def add(self, item):
        h = int(hashlib.md5(str(item).encode()).hexdigest(), 16)
        idx = h & (self.m - 1)
        w = h >> self.b
        rho = (w & -w).bit_length()
        self.registers[idx] = max(self.registers[idx], rho)

    def count(self):
        raw = self.alpha * self.m * self.m / sum(2 ** -r for r in self.registers)
        if raw <= 2.5 * self.m:
            V = sum(1 for r in self.registers if r == 0)
            if V > 0:
                return int(self.m * math.log(self.m / V))
        return int(raw)


if __name__ == "__main__":
    hll = HyperLogLog()
    for i in range(5000):
        hll.add(f"user_{i}")
    print(f"{hll.count()}")

Output

stdout

How it works

This classic HyperLogLog estimator hashes each item with MD5, splits the hash into a bucket index and a leading-zero count, and keeps the maximum leading-zero count per bucket. The harmonic-mean formula converts register values into an estimate of unique cardinality. When the estimate is small, a linear-counting correction handles the zero registers that dominate. The result stabilizes around the true 5000 unique items with modest variance, demonstrating the trade-off between memory and accuracy.

Common mistakes

Forgetting to convert the hash to an integer before bit operations
Using the raw rho value instead of the leading-zero count when registers are empty
Ignoring the linear-counting correction for small cardinalities where zero registers dominate

Variations

Replacing MD5 with a 64-bit hash (e.g., some robust hashing library) to reduce collision bias at higher cardinalities.
Increasing the register count via a larger b value (e.g., b=12) to improve accuracy at the cost of more memory.

Real-world use cases

Estimating the number of unique visitors to a website from millions of log lines in near-constant memory.
Counting distinct SKUs scanned across a warehouse's real-time inventory feed without storing every ID.
Approximating the unique users in an ad-impression stream before joining with a costly exact identity store.

HyperLogLog Cardinality Estimation in Python

Python code

Output

How it works

Common mistakes

Variations

Real-world use cases

More from Big data & Spark

Tutorials

Quizzes

Python code

Output

How it works

Common mistakes

Variations

Real-world use cases

More from Big data & Spark

Keep learning

Tutorials

Quizzes