How to Build a HyperLogLog Cardinality Estimator in Python to Count Distinct Items Without Storing Them

Suppose you need to answer a simple-sounding question: how many distinct users visited your site today? If you have ten users, you can count them by hand. If you have ten million, the obvious approach, keeping a big hash set and remembering every user you have ever seen, works but gets expensive fast. A Python set holding a million unique string IDs can burn through tens of megabytes of memory just to answer one question. Scale that up to tracking distinct visitors across dozens of dashboards, unique IP addresses hitting an API, or unique products viewed per day, and the memory bill adds up quickly.

HyperLogLog is a probabilistic data structure: instead of remembering every item it has seen, it looks at the pattern of bits produced by hashing each item and uses a small amount of statistics to estimate how many distinct items there were. It trades perfect accuracy (its estimates are typically within about 1 percent of the true answer) for a dramatic reduction in memory: you can estimate the number of distinct items in a stream of a billion events using around 16 kilobytes, whether the true answer is 10,000 or 10 billion.

This is not a theoretical curiosity. Redis ships built-in HyperLogLog support (the PFADD, PFCOUNT, and PFMERGE commands) specifically for problems like counting unique visitors or unique search queries, and documents a standard error rate of 0.81 percent using up to 12 KB of memory per counter. Elasticsearch’s cardinality aggregation, the thing that answers “how many distinct users triggered this event,” is built on HyperLogLog++, a refined version of the same algorithm. In this tutorial you will build the algorithm from scratch in Python, using nothing but the standard library, and test every claim about its accuracy and memory usage against real measurements instead of taking them on faith.

What You’ll Build

By the end of this tutorial you will have a complete HyperLogLog implementation with three operations: add() to record an item, count() to estimate how many distinct items have been seen so far, and merge() to combine two independently-built HyperLogLogs into an estimate of their combined union, without ever constructing the union itself. Along the way you will personally measure:

• How badly a naive Python set scales in memory as the number of distinct items grows
• Why a single “longest run of leading zeros” estimator is too noisy to use on its own, and how splitting the work across many small estimators fixes that
• The real accuracy of your implementation against exact counts, at two different memory budgets
• A dramatic, reproducible bug that happens when you plug in a low-quality hash function
• Why HyperLogLog is excellent at estimating unions but unreliable for estimating intersections

Prerequisites

• Python 3.10 or later installed. This tutorial was built and tested on Python 3.13.14 on Windows, but every line of code is pure standard library and will run unchanged on macOS or Linux.
• Comfortable reading basic Python: functions, classes, and list comprehensions.
• Some familiarity with binary numbers and hash functions helps, but the tutorial explains the relevant bit-level details as it goes.
• No third-party packages are required to build or run the estimator itself. Everything uses only hashlib and math from the standard library. pytest is used for the optional automated test suite in Step 9 (pip install pytest if you want to run it).

Step 1: See Why Exact Counting Doesn’t Scale

Before building anything clever, it’s worth feeling the actual pain that HyperLogLog exists to solve. The obvious way to count distinct items is to put them in a set and check its length:

"""Step 1: the naive way to count distinct items, and why it doesn't scale."""
import sys
import random

random.seed(42)

def naive_distinct_count(items):
    seen = set()
    for item in items:
        seen.add(item)
    return len(seen), seen

# Simulate a stream of user IDs visiting a site, with lots of repeats
stream = [f"user-{random.randint(1, 50_000)}" for _ in range(200_000)]

count, seen_set = naive_distinct_count(stream)
print(f"Stream length: {len(stream):,}")
print(f"Exact distinct count: {count:,}")
print(f"Memory used by the set: {sys.getsizeof(seen_set):,} bytes (getsizeof, shallow)")

# Shallow getsizeof undercounts a set of strings badly, since it doesn't count
# the strings themselves. Measure it properly.
total_bytes = sys.getsizeof(seen_set) + sum(sys.getsizeof(s) for s in seen_set)
print(f"Memory used by the set (set + all string objects): {total_bytes:,} bytes = {total_bytes / 1024:.1f} KB")

Running this against a simulated stream of 200,000 page views (with repeats) produces:

Stream length: 200,000
Exact distinct count: 49,118
Memory used by the set: 2,097,368 bytes (getsizeof, shallow)
Memory used by the set (set + all string objects): 4,591,483 bytes = 4483.9 KB

Notice the first, tempting measurement (sys.getsizeof(seen_set)) is wrong on its own: it only reports the size of the set’s internal hash table, not the string objects the set holds pointers to. Once you add those in, roughly 49,000 short strings cost about 4.5 megabytes. That ratio only gets worse as the strings get longer (imagine full email addresses or UUIDs) or the count climbs into the millions. This is the exact problem HyperLogLog exists to sidestep: it never keeps the items at all, only a tiny, fixed-size summary of what it has seen.

Step 2: The Core Trick, Counting Leading Zeros in Random Bits

Here is the idea the whole algorithm is built on. Philippe Flajolet and Nigel Martin first described the core “count leading zeros” trick in 1984, it was refined into the LogLog algorithm in 2003, and it reached its modern form when Flajolet, Fusy, Gandouet, and Meunier published the HyperLogLog paper in 2007. If you run a good hash function over every item, the output bits behave like a long sequence of fair coin flips: each bit is 0 or 1 with equal probability, independent of the others.

Now imagine you flip a coin repeatedly and count how many heads you get in a row before your first tails. Most of the time that streak is short. Occasionally, if you flip enough times, you get lucky and see a long streak, say, 10 heads in a row. A streak of 10 heads has roughly a 1-in-1,024 chance on any given attempt (2^-10), so seeing one at all is a hint that you tried on the order of 1,024 times. That’s the whole insight: the length of the longest “streak” you observe is a rough proxy for how many times you tried.

Translated to hashing: treat each hashed item’s bits as a run of coin flips, and measure the number of leading zero bits before the first 1-bit (the streak of “heads” before your first “tails”). If the longest such run across every item you’ve hashed is n bits, then 2n is a rough estimate of how many distinct items you hashed.

Why a Single Estimator Isn’t Enough

“Rough” is doing a lot of work in that sentence. A single longest-run estimator has enormous variance, because it depends entirely on the one luckiest hash value you happened to see. Test it directly:

"""Step 2: the core trick behind HyperLogLog, and why a single estimator is too noisy."""
import hashlib
import random

random.seed(42)
HASH_BITS = 64


def hash64(item):
    digest = hashlib.sha256(str(item).encode("utf-8")).digest()
    return int.from_bytes(digest[:8], "big")


def leading_zero_run(x, width):
    """Count leading zero bits in the width-bit representation of x, then add 1.

    This is the 'rank' of a hash value: how many bits until the first 1.
    """
    bit_length = x.bit_length()
    leading_zeros = width - bit_length
    return leading_zeros + 1


for true_n in [1_000, 10_000, 100_000]:
    estimates = []
    for trial in range(5):
        max_rank = 0
        for i in range(true_n):
            h = hash64(f"trial{trial}-item-{i}")
            r = leading_zero_run(h, HASH_BITS)
            if r > max_rank:
                max_rank = r
        estimates.append(2 ** max_rank)
    print(f"true n = {true_n:>7,}  single-estimator guesses across 5 trials: {estimates}")

true n =   1,000  single-estimator guesses across 5 trials: [8192, 2048, 2048, 1024, 2048]
true n =  10,000  single-estimator guesses across 5 trials: [16384, 4096, 32768, 8192, 16384]
true n = 100,000  single-estimator guesses across 5 trials: [32768, 262144, 131072, 262144, 32768]

For a true count of 1,000 items, the single-run estimator guesses anywhere from 1,024 to 8,192, off by up to 8x. For 100,000 true items, guesses range from 32,768 to 262,144, again off by up to 8x in either direction. A single “longest streak” is simply too dependent on chance to trust. HyperLogLog’s actual contribution is not the leading-zero trick itself (that’s the older Flajolet-Martin algorithm); it’s a clever way of running many small versions of this experiment at once and averaging them so the lucky and unlucky outliers cancel out.

Step 3: Build the Real HyperLogLog: Bucketing With Stochastic Averaging

Instead of one giant estimator, HyperLogLog keeps m small estimators, called registers, where m is a power of two (say 16,384). Every hashed item is deterministically routed into exactly one of the m registers using some of its hash bits, and that register keeps track of the longest leading-zero run seen among only the items routed to it. Averaging across thousands of small, independent estimators (instead of trusting one big one) is what tames the variance you just measured.

The Hash and Rank Primitives

Start with two small, testable building blocks: a 64-bit hash function, and a function that computes the “rank” (leading zeros plus one) of a fixed-width bit string.

import hashlib
import math

HASH_BITS = 64


def _hash64(item):
    digest = hashlib.sha256(str(item).encode("utf-8")).digest()
    return int.from_bytes(digest[:8], "big")


def _rho(w, width):
    """Rank of a hash remainder: 1 + number of leading zero bits in a
    `width`-bit window. w=0 (all zero bits) correctly yields width + 1."""
    return width - w.bit_length() + 1

The _rho function deserves a moment of attention because the edge case is easy to get wrong. Python’s int.bit_length() returns the number of bits needed to represent a number, which is also the position of its highest set bit. If a width-bit value w has a shorter bit length than width, the difference is exactly the number of leading zeros. And if w is zero (bit_length() == 0, meaning every bit in the window is zero), the formula still works without a special case: width - 0 + 1 = width + 1, correctly treating an all-zero window as the longest possible run.

The Add Operation

To add an item, hash it, use the top p bits of the hash to choose which of the m = 2p registers to update, and use the rank of the remaining bits to (possibly) raise that register’s value:

def _alpha(m):
    if m == 16:
        return 0.673
    if m == 32:
        return 0.697
    if m == 64:
        return 0.709
    return 0.7213 / (1 + 1.079 / m)


class HyperLogLog:
    def __init__(self, p=14):
        if not (4 <= p <= 18):
            raise ValueError("p must be between 4 and 18")
        self.p = p
        self.m = 1 << p
        self.registers = bytearray(self.m)  # one byte per register, plenty for HASH_BITS

    def add(self, item):
        x = _hash64(item)
        j = x >> (HASH_BITS - self.p)          # top p bits select the register
        w = x & ((1 << (HASH_BITS - self.p)) - 1)  # remaining bits feed the rank
        r = _rho(w, HASH_BITS - self.p)
        if r > self.registers[j]:
            self.registers[j] = r

The _alpha(m) constant corrects a small systematic bias that the harmonic-mean formula below would otherwise introduce because of hash collisions between registers. The original 2007 paper gives exact values for small m and an approximation for larger m, both used verbatim above.

The Count Operation

To estimate the cardinality, combine all m registers using a harmonic mean, not an arithmetic mean. A harmonic mean is dominated by small values, which matters here because a single register that never got a long run (perhaps because it only received one or two items) would otherwise drag an arithmetic average down disproportionately less than it should.

    def count(self):
        m = self.m
        a = _alpha(m)
        z = sum(2.0 ** (-r) for r in self.registers)
        estimate = a * m * m / z

        if estimate <= 2.5 * m:
            zeros = self.registers.count(0)
            if zeros > 0:
                estimate = m * math.log(m / zeros)

        return estimate

Ignore the if estimate <= 2.5 * m block for a moment (Step 6 explains exactly why it’s there and what breaks without it). The core formula, Z = (sum of 2^-register)^-1 and E = alpha_m * m^2 * Z, is the harmonic-mean combination described in the original paper: each register’s value estimates log2(n/m), so scaling the harmonic mean of 2^register back up by m should land close to the true count n.

Step 4: Test Accuracy Against Real Exact Counts

Theory is convincing only once you’ve measured it. Run the estimator against real Python sets across five orders of magnitude, at two different values of p:

"""Step 3: empirically measure HyperLogLog's accuracy against real exact counts."""
import random
from hyperloglog import HyperLogLog

random.seed(42)


def run_trial(true_n, p, salt):
    hll = HyperLogLog(p=p)
    exact = set()
    for i in range(true_n):
        item = f"user-{salt}-{i}"
        hll.add(item)
        exact.add(item)
    estimate = hll.count()
    error_pct = (estimate - len(exact)) / len(exact) * 100
    return len(exact), estimate, error_pct


print(f"{'true n':>10} {'p':>3} {'m (regs)':>9} {'estimate':>10} {'error %':>9}")
for p in (10, 14):
    for true_n in (100, 1_000, 10_000, 100_000, 1_000_000):
        exact_n, estimate, error_pct = run_trial(true_n, p, salt=p)
        print(f"{exact_n:>10,} {p:>3} {1 << p:>9,} {estimate:>10,.0f} {error_pct:>8.2f}%")

    true n   p  m (regs)   estimate   error %
       100  10     1,024        101     0.80%
     1,000  10     1,024      1,010     0.97%
    10,000  10     1,024     10,490     4.90%
   100,000  10     1,024     99,362    -0.64%
 1,000,000  10     1,024  1,048,819     4.88%
       100  14    16,384        100     0.31%
     1,000  14    16,384        999    -0.12%
    10,000  14    16,384     10,048     0.48%
   100,000  14    16,384     99,212    -0.79%
 1,000,000  14    16,384    974,373    -2.56%

Two things are worth noticing. First, the errors are small: mostly under 1 percent at p=14, and never wildly off even at the smaller p=10. Second, more registers means better accuracy: HyperLogLog’s expected standard error follows the formula 1.04 / sqrt(m), so quadrupling m (say from 1,024 to 4,096) roughly halves the expected error. That formula is exactly what determines how much memory a real deployment needs for a target accuracy, which Step 8 turns into a concrete table.

Step 5: Measure the Actual Memory Savings

Return to the motivating problem from Step 1 and measure the memory difference directly, at a scale where it actually matters:

"""Step 4: how much memory does this actually save?"""
import sys
from hyperloglog import HyperLogLog

N = 1_000_000

hll = HyperLogLog(p=14)
exact = set()
for i in range(N):
    item = f"visitor-{i}"
    hll.add(item)
    exact.add(item)

set_bytes = sys.getsizeof(exact) + sum(sys.getsizeof(s) for s in exact)
hll_bytes = hll.size_bytes()

print(f"Distinct items added: {N:,}")
print(f"HyperLogLog estimate: {hll.count():,.0f}")
print(f"Python set memory:    {set_bytes:,} bytes  ({set_bytes / 1024 / 1024:.1f} MB)")
print(f"HyperLogLog memory:   {hll_bytes:,} bytes  ({hll_bytes / 1024:.1f} KB)")
print(f"Ratio: the set uses {set_bytes / hll_bytes:,.0f}x more memory")

Distinct items added: 1,000,000
HyperLogLog estimate: 994,948
Python set memory:    88,443,538 bytes  (84.3 MB)
HyperLogLog memory:   16,384 bytes  (16.0 KB)
Ratio: the set uses 5,398x more memory

For an estimate that lands within 0.5 percent of the true 1,000,000, the HyperLogLog sketch uses 16 KB against the set’s 84.3 MB, a 5,398x difference. That gap only widens as the true cardinality grows, since the set’s memory use is proportional to the number of distinct items while the HyperLogLog’s memory use never changes at all.

Step 6: Fix the Small-Cardinality Bias With Linear Counting

Go back to the if estimate <= 2.5 * m block from Step 3 and see what breaks without it. With 16,384 registers and only 40 true distinct items, almost every register will still be at its initial value of zero, since most registers never received a single item:

"""Step 5: why small cardinalities need the linear-counting correction."""
import math
from hyperloglog import HyperLogLog, _alpha

p = 14
m = 1 << p
true_n = 40

hll = HyperLogLog(p=p)
exact = set()
for i in range(true_n):
    item = f"item-{i}"
    hll.add(item)
    exact.add(item)

# Recompute the RAW harmonic-mean estimate, with no small-range correction,
# to see what the uncorrected formula alone would have said.
a = _alpha(m)
z = sum(2.0 ** (-r) for r in hll.registers)
raw_estimate = a * m * m / z

zeros = hll.registers.count(0)
corrected_estimate = m * math.log(m / zeros) if zeros else raw_estimate

print(f"True distinct count:                {len(exact)}")
print(f"Registers still at zero:             {zeros} of {m} ({zeros / m:.1%})")
print(f"RAW harmonic-mean estimate:          {raw_estimate:,.0f}  <- wildly wrong")
print(f"Linear-counting corrected estimate:  {corrected_estimate:,.1f}")
print(f"HyperLogLog.count() (uses the fix):  {hll.count():,.1f}")

True distinct count:                40
Registers still at zero:             16344 of 16384 (99.8%)
RAW harmonic-mean estimate:          11,835  <- wildly wrong
Linear-counting corrected estimate:  40.0
HyperLogLog.count() (uses the fix):  40.0

Without the correction, the raw harmonic-mean formula claims there are 11,835 distinct items when the true answer is 40, off by nearly 300x. This happens because the harmonic-mean formula assumes every register has meaningfully participated in the estimate, an assumption that only holds once the true cardinality is comfortably larger than the number of registers. When most registers are still empty, a different, much simpler estimator called linear counting takes over: E = m * ln(m / zeros), which is just the classic coupon-collector-style estimate of how many balls you’ve thrown into m bins given how many bins are still empty. The 2007 paper documents that the harmonic-mean estimator is biased below a threshold of 2.5 * m distinct items, and recommends switching to linear counting in that range, exactly the threshold implemented above.

Step 7: Merge Two HyperLogLogs Into Their Union

The feature that makes HyperLogLog genuinely useful in distributed systems, not just memory-efficient on a single machine, is that two independently-built sketches can be combined into an estimate of their union with a single, cheap operation: take the elementwise maximum of their registers.

    def merge(self, other):
        if self.p != other.p:
            raise ValueError("cannot merge HyperLogLogs with different precision")
        merged = HyperLogLog(self.p)
        merged.registers = bytearray(
            max(a, b) for a, b in zip(self.registers, other.registers)
        )
        return merged

    def size_bytes(self):
        return len(self.registers)

This works because a register’s value is the longest leading-zero run seen among the items routed to it, and the longest run seen by the union of two streams is exactly the max of the longest runs seen by each stream individually. Test that claim against a realistic scenario: two overlapping daily visitor sets, where you want to know the union (total unique visitors across both days) without ever building that union directly.

"""Step 6: merging two HyperLogLogs to estimate the size of their union,
without ever building the union itself."""
from hyperloglog import HyperLogLog

p = 14

# Two overlapping "daily visitor" sets: day 1 and day 2 share some visitors.
day1_ids = [f"user-{i}" for i in range(0, 120_000)]          # users 0..119999
day2_ids = [f"user-{i}" for i in range(80_000, 200_000)]     # users 80000..199999
true_union = set(day1_ids) | set(day2_ids)

hll_day1 = HyperLogLog(p=p)
for item in day1_ids:
    hll_day1.add(item)

hll_day2 = HyperLogLog(p=p)
for item in day2_ids:
    hll_day2.add(item)

merged = hll_day1.merge(hll_day2)

print(f"Day 1 exact distinct:   {len(set(day1_ids)):,}   HLL estimate: {hll_day1.count():,.0f}")
print(f"Day 2 exact distinct:   {len(set(day2_ids)):,}   HLL estimate: {hll_day2.count():,.0f}")
print(f"True union distinct:    {len(true_union):,}")
print(f"Merged HLL estimate:    {merged.count():,.0f}")
error_pct = (merged.count() - len(true_union)) / len(true_union) * 100
print(f"Merge error: {error_pct:+.2f}%")

# Prove the merge is exact register-for-register max, not an approximation of
# an approximation: build a THIRD HyperLogLog directly from the true union and
# compare its registers to the merged one.
hll_direct_union = HyperLogLog(p=p)
for item in true_union:
    hll_direct_union.add(item)

identical_registers = hll_direct_union.registers == merged.registers
print(f"Merged registers byte-identical to a fresh HLL built from the real union: {identical_registers}")

Day 1 exact distinct:   120,000   HLL estimate: 119,399
Day 2 exact distinct:   120,000   HLL estimate: 119,913
True union distinct:    200,000
Merged HLL estimate:    200,697
Merge error: +0.35%
Merged registers byte-identical to a fresh HLL built from the real union: True

The last line is the important one: the registers you get from merging two independently-built sketches are byte-for-byte identical to the registers you would get from building a fresh HyperLogLog directly over the true union. Merging is not “an approximation of an approximation” that compounds error; it’s an exact operation on the sketches, and any error in the final estimate comes only from the same statistical estimation you already measured in Step 4, not from the act of merging itself. This is exactly why Redis’s PFMERGE command can combine per-day, per-shard, or per-server counters into a combined estimate for a week, a month, or an entire cluster, without ever centralizing the underlying event data.

Step 8: How Much Memory Should You Actually Use?

The precision parameter p is a direct trade of memory for accuracy, governed by the same 1.04 / sqrt(m) standard error formula from Step 4. Since each register in this implementation is a single byte, memory usage in bytes is just m itself:

p  |  m = 2^p (registers)  |  memory (bytes)  |  std error = 1.04/sqrt(m)
 8 |                   256 |              256 |                    6.500%
10 |                 1,024 |            1,024 |                    3.250%
12 |                 4,096 |            4,096 |                    1.625%
14 |                16,384 |           16,384 |                    0.812%
16 |                65,536 |           65,536 |                    0.406%
18 |               262,144 |          262,144 |                    0.203%

The p=14 row is not a coincidence: it lands on 0.812 percent, almost exactly matching the 0.81 percent standard error Redis documents for its own HyperLogLog implementation. Redis actually uses the same 16,384 registers, but packs each one into 6 bits instead of a full byte (the largest register value that ever needs storing fits comfortably in 6 bits), for a total of 12 KB rather than 16 KB. This implementation uses a full byte per register for clarity; production implementations like Redis’s squeeze out that extra 25 percent with bit-packing once the algorithm itself is working correctly, which is a reasonable next optimization once you trust the math.

Step 9: Common Mistakes and Gotchas

Gotcha 1: Weak Hash Functions Silently Destroy Accuracy

Every claim in this tutorial depends on one assumption: the hash function’s output bits look uniformly random. It is tempting, especially under time pressure, to reach for a “good enough” homemade hash instead of a real one. Prove why that’s dangerous:

"""Step 7: HyperLogLog lives or dies by hash quality. Prove it with a weak hash."""
import math
from hyperloglog import _rho, _alpha, _hash64

HASH_BITS = 64
p = 14
m = 1 << p


def weak_hash(item):
    """A tempting shortcut: sum the character codes. Looks like a hash,
    behaves nothing like one, because similar strings produce similar,
    clustered sums instead of uniformly-spread bits."""
    total = sum(ord(c) for c in str(item))
    return (total * 0x9E3779B97F4A7C15) & ((1 << HASH_BITS) - 1)


def count_with_hash(items, hash_fn):
    registers = bytearray(m)
    for item in items:
        x = hash_fn(item)
        j = x >> (HASH_BITS - p)
        w = x & ((1 << (HASH_BITS - p)) - 1)
        r = _rho(w, HASH_BITS - p)
        if r > registers[j]:
            registers[j] = r

    a = _alpha(m)
    z = sum(2.0 ** (-r) for r in registers)
    estimate = a * m * m / z
    zeros = registers.count(0)
    if estimate <= 2.5 * m and zeros > 0:
        estimate = m * math.log(m / zeros)
    return estimate, m - zeros


items = [f"session-{i:08d}" for i in range(200_000)]
true_n = len(set(items))

good_estimate, good_used = count_with_hash(items, _hash64)
bad_estimate, bad_used = count_with_hash(items, weak_hash)

print(f"True distinct count: {true_n:,}")
print(f"SHA-256-based hash  -> estimate {good_estimate:>10,.0f}  ({good_used:,}/{m:,} registers touched, "
      f"error {((good_estimate - true_n) / true_n) * 100:+.2f}%)")
print(f"Weak sum-of-chars   -> estimate {bad_estimate:>10,.0f}  ({bad_used:,}/{m:,} registers touched, "
      f"error {((bad_estimate - true_n) / true_n) * 100:+.2f}%)")

True distinct count: 200,000
SHA-256-based hash  -> estimate    200,026  (16,384/16,384 registers touched, error +0.01%)
Weak sum-of-chars   -> estimate         47  (47/16,384 registers touched, error -99.98%)

This is not a subtle degradation, it’s total collapse. The weak hash sums character codes, and because the test items are zero-padded, fixed-width strings (session-00000000 through session-00199999), the character-code sums barely vary across the whole range: most 8-digit zero-padded numbers use a similar mix of digits, so their ASCII sums cluster tightly together. Only 47 of the 16,384 registers ever get touched at all, and the estimate comes out at 47 instead of 200,000, a 99.98 percent error. This is precisely why production implementations use hash functions specifically designed to avalanche (where changing one input bit flips roughly half the output bits unpredictably): Redis’s own HyperLogLog implementation uses MurmurHash2 internally for exactly this reason. A cryptographic hash like SHA-256 is overkill for this use case in terms of security, but its output is exactly the kind of uniformly-distributed bit pattern the algorithm requires, which is why it’s used throughout this tutorial.

Gotcha 2: HyperLogLog Is Excellent at Unions and Unreliable at Intersections

Step 7 showed that merging (union) is exact at the register level. It’s tempting to assume you can get intersection sizes just as cleanly using the inclusion-exclusion identity, |A ∩ B| = |A| + |B| - |A ∪ B|, since you already have HyperLogLog estimates for all three quantities. Test that assumption directly, on two sets that genuinely overlap by exactly 500 items:

"""Step 8: why HyperLogLog is great at unions and bad at intersections."""
from hyperloglog import HyperLogLog

p = 14

# Two nearly-disjoint sets sharing the same "item-N" namespace, with a small
# overlap of exactly 500 shared items (item-99500 .. item-99999).
set_a = [f"item-{i}" for i in range(100_000)]
set_b = [f"item-{i}" for i in range(99_500, 199_500)]  # overlaps set_a on 500 items

true_a = set(set_a)
true_b = set(set_b)
true_intersection = true_a & true_b
true_union = true_a | true_b

hll_a = HyperLogLog(p=p)
for item in set_a:
    hll_a.add(item)
hll_b = HyperLogLog(p=p)
for item in set_b:
    hll_b.add(item)
merged = hll_a.merge(hll_b)

est_a = hll_a.count()
est_b = hll_b.count()
est_union = merged.count()
# |A ∩ B| = |A| + |B| - |A ∪ B|
est_intersection = est_a + est_b - est_union

print(f"True |A ∩ B|:        {len(true_intersection):,}")
print(f"True |A ∪ B|:        {len(true_union):,}")
print(f"HLL estimate |A|:            {est_a:,.0f}  (error {((est_a - len(true_a)) / len(true_a)) * 100:+.2f}%)")
print(f"HLL estimate |B|:            {est_b:,.0f}  (error {((est_b - len(true_b)) / len(true_b)) * 100:+.2f}%)")
print(f"HLL estimate |A ∪ B| (merge): {est_union:,.0f}  (error {((est_union - len(true_union)) / len(true_union)) * 100:+.2f}%)")
print(f"HLL estimate |A ∩ B| (inclusion-exclusion): {est_intersection:,.0f}  "
      f"(true is {len(true_intersection)}, absolute error {abs(est_intersection - len(true_intersection)):,.0f})")

True |A ∩ B|:        500
True |A ∪ B|:        199,500
HLL estimate |A|:            99,865  (error -0.13%)
HLL estimate |B|:            99,840  (error -0.16%)
HLL estimate |A ∪ B| (merge): 199,957  (error +0.23%)
HLL estimate |A ∩ B| (inclusion-exclusion): -252  (true is 500, absolute error 752)

The inclusion-exclusion estimate comes out negative, a nonsensical answer for a cardinality, even though every individual input (|A|, |B|, and |A ∪ B|) was accurate to well under half a percent. The problem is arithmetic, not implementation: intersection here is computed as a small difference between three large, similarly-sized numbers, and each of those numbers carries its own independent estimation error. When you subtract two numbers around 200,000 to recover a true answer of only 500, even a fraction-of-a-percent error on each side is large relative to the small true difference. Wikipedia’s own summary of the algorithm notes that intersection and set-difference cardinalities can technically be derived this way via inclusion-exclusion, but does not claim it’s accurate, and this measurement shows why: treat any HyperLogLog-derived intersection or difference estimate as a rough sanity check at best, never as a number you’d report with confidence, especially when the true overlap is small relative to the sets themselves.

Step 10: Verify Everything With a Test Suite

Manual demonstration scripts are convincing, but an automated test suite is what keeps this code honest as you refactor it. Save the following as test_hyperloglog.py alongside hyperloglog.py:

import math
import pytest
from hyperloglog import HyperLogLog, _rho, _alpha


def test_rho_all_zero_bits_gives_max_rank():
    assert _rho(0, 10) == 11


def test_rho_single_leading_one_gives_rank_one():
    assert _rho(0b1000000000, 10) == 1


def test_rho_matches_manual_count():
    # 10-bit window, value 0b0001000000 -> 3 leading zeros -> rank 4
    assert _rho(0b0001000000, 10) == 4


def test_alpha_known_constants():
    assert _alpha(16) == 0.673
    assert _alpha(32) == 0.697
    assert _alpha(64) == 0.709
    assert abs(_alpha(16384) - 0.7213 / (1 + 1.079 / 16384)) < 1e-12


def test_invalid_precision_rejected():
    with pytest.raises(ValueError):
        HyperLogLog(p=2)
    with pytest.raises(ValueError):
        HyperLogLog(p=20)


def test_empty_hll_counts_zero():
    hll = HyperLogLog(p=10)
    assert hll.count() == 0.0


def test_accuracy_within_expected_standard_error():
    p = 14
    m = 1 << p
    true_n = 50_000
    hll = HyperLogLog(p=p)
    for i in range(true_n):
        hll.add(f"item-{i}")
    estimate = hll.count()
    error = abs(estimate - true_n) / true_n
    # 3 standard errors ~= 3 * 1.04/sqrt(m), generous bound to avoid flakiness
    bound = 3 * 1.04 / math.sqrt(m)
    assert error < bound


def test_duplicates_do_not_change_count():
    hll = HyperLogLog(p=12)
    for _ in range(10):
        for i in range(500):
            hll.add(f"item-{i}")
    estimate = hll.count()
    assert abs(estimate - 500) / 500 < 0.1


def test_merge_matches_direct_union():
    p = 12
    a_items = [f"a-{i}" for i in range(3000)]
    b_items = [f"b-{i}" for i in range(2000, 5000)]  # overlaps a_items 2000..2999

    hll_a = HyperLogLog(p=p)
    for item in a_items:
        hll_a.add(item)
    hll_b = HyperLogLog(p=p)
    for item in b_items:
        hll_b.add(item)
    merged = hll_a.merge(hll_b)

    direct = HyperLogLog(p=p)
    for item in set(a_items) | set(b_items):
        direct.add(item)

    assert merged.registers == direct.registers


def test_merge_rejects_mismatched_precision():
    hll_a = HyperLogLog(p=10)
    hll_b = HyperLogLog(p=12)
    with pytest.raises(ValueError):
        hll_a.merge(hll_b)

Run it with:

pytest test_hyperloglog.py -v

============================= test session starts =============================
platform win32 -- Python 3.13.14, pytest-9.1.1, pluggy-1.6.0
collecting ... collected 10 items

test_hyperloglog.py::test_rho_all_zero_bits_gives_max_rank PASSED        [ 10%]
test_hyperloglog.py::test_rho_single_leading_one_gives_rank_one PASSED   [ 20%]
test_hyperloglog.py::test_rho_matches_manual_count PASSED                [ 30%]
test_hyperloglog.py::test_alpha_known_constants PASSED                   [ 40%]
test_hyperloglog.py::test_invalid_precision_rejected PASSED              [ 50%]
test_hyperloglog.py::test_empty_hll_counts_zero PASSED                   [ 60%]
test_hyperloglog.py::test_accuracy_within_expected_standard_error PASSED [ 70%]
test_hyperloglog.py::test_duplicates_do_not_change_count PASSED          [ 80%]
test_hyperloglog.py::test_merge_matches_direct_union PASSED              [ 90%]
test_hyperloglog.py::test_merge_rejects_mismatched_precision PASSED      [100%]

============================= 10 passed in 0.09s ==============================

The test_merge_matches_direct_union test is the one worth reading twice: it doesn’t just check that the merged estimate is “close enough,” it asserts the merged registers are byte-identical to a fresh HyperLogLog built directly from the real union, exactly the claim demonstrated in Step 7. If a future refactor ever breaks that exactness, this test catches it immediately instead of letting a subtle accuracy regression slip through.

How to Confirm It All Works End to End

You now have three independent forms of verification, and all three should agree before you trust this code with anything real:

1. The accuracy demo (Step 4) shows the estimator tracking real exact counts within a few percent across five orders of magnitude, matching the theoretical 1.04 / sqrt(m) error bound.
2. The merge proof (Step 7) shows merged registers are byte-identical to a directly-built union, not just approximately close.
3. The automated test suite (Step 10) encodes both of those properties, plus the small edge cases (empty sketch, duplicate items, mismatched precision), as regression tests you can rerun after any change.

If you change anything, the hash function, the precision, the bias-correction constants, rerun the accuracy demo and the test suite together. A change that still passes test_accuracy_within_expected_standard_error but produces wildly different numbers in the manual demo is a sign that your test’s bound is too loose, not that the change is safe.

Next Steps

• Try bit-packing the registers into 6 bits each, the way Redis does, to shrink a p=14 sketch from 16 KB to 12 KB. You’ll need to implement your own bit-level array indexing since Python’s bytearray only addresses whole bytes.
• Persist a HyperLogLog’s registers bytes to disk or a database and reload it later; since the whole state is just m small integers, serialization is trivial and this is exactly how Redis stores an HLL as an ordinary string value.
• If you want to see the same “probabilistic sketch that trades certainty for memory” idea applied to a different problem (testing set membership instead of estimating set size), read How to Build a Bloom Filter From Scratch in Python to Skip Expensive Lookups, built on this site with the same from-scratch, stdlib-only approach.
• For a deeper look at how real systems shard and route data across many nodes, another building block that HyperLogLog sketches are often combined with in distributed counting pipelines, see How to Build Consistent Hashing in Python to Stop Cache Stampedes.
• Read the original 2007 paper, Flajolet, Fusy, Gandouet, and Meunier’s “HyperLogLog: The Analysis of a Near-Optimal Cardinality Estimation Algorithm” (summarized with full citation on its Wikipedia page), for the derivation of the alpha_m bias constant this tutorial used without proof.
• Look at how Redis’s own HyperLogLog documentation exposes this exact algorithm as three commands, PFADD, PFCOUNT, and PFMERGE, backed by a production C implementation with 6-bit register packing and both a sparse and dense on-disk encoding.