The birthday problem in Python: estimate collision risk before IDs do

Short identifiers are easy to generate and surprisingly easy to underestimate. If a service hands out six digit codes, a million different values look like plenty. They are not, if the service creates enough of them. The risk comes from pairs of values: every new identifier has to avoid all the values that came before it.

Diagram showing birthday-style collision risk: repeated draws create pairs, with example probabilities for 23 birthdays, one thousand six-digit identifiers, and one million 128-bit identifiers — Collision risk comes from the number of pairs, not only from how full the identifier space looks.

Start with the collision

Assume there are m equally likely buckets and you draw n values independently. A collision means that at least two draws land in the same bucket. The probability of no collision is

P(no collision) = (m/m) × ((m − 1)/m) × ((m − 2)/m) × …

so the collision probability is one minus that product. For moderate values of n, a useful approximation is

P(collision) ≈ 1 − e^{−n(n−1)/(2m)}

The term that matters is n(n − 1) / 2, the number of pairs. That is why the risk rises much faster than a quick comparison between n and m suggests. A university treatment of the birthday problem gives the same product and bounds the collision probability in terms of n²/m.[4]

With 23 people and 365 equally likely birthdays, the exact probability is about 50.73%, not 23/365. In the code below, the approximation is 50.0002%, close enough to explain the surprise without multiplying a long row of fractions by hand.

What this means for identifiers

For a six digit space, m is 1,000,000. At 1,000,000 generated values, the probability of at least one collision is about 39.33%. That is not a prediction that every service will collide. It is the probability for uniform, independent draws, which is the model you should use before adding real-world complications such as biased generators, retries, multiple services and human-chosen values.

A 128 bit identifier space is a different scale. RFC 9562 specifies UUIDs as 128 bits long and describes their use when values need to be created without central coordination.[3] If a generator really samples uniformly across all 2¹²⁸ bit patterns, one million samples give a collision probability of roughly 1.47 × 10⁻²⁷. That calculation describes the size of the space, not every UUID generation method. Version, randomness quality and the way the value is stored still matter.

Cryptographic hash outputs need a separate warning. A short digest can be convenient for a cache key or display label, but collision resistance is an adversarial property, not just a question of accidental duplicates. The NIST workshop material describes the birthday attack as the generic collision attack whose work grows roughly with the square root of the hash output space.[5]

Checking a batch without doing the same work twice

Suppose the immediate task is to reject a batch containing a duplicate. The direct version compares every value with every later value. For n unique values, it performs n(n − 1) / 2 equality checks, which is quadratic time and constant extra space apart from the input.

The set version keeps the values already seen. For each new value it asks whether that value is already present, then stores it if it is new. Python’s set type represents a collection of distinct hashable objects and supports membership tests.[1] Under the usual average-case hash-table model, the scan takes linear time and uses linear extra space. That model has conditions: badly behaved hashes, adversarial input or an object whose equality check is expensive can change the cost.

Here is a complete programme. It calculates the probability, checks both versions for correctness, counts the comparisons or membership checks, and uses timeit.repeat() for the timing run. The Python documentation recommends looking at the minimum from repeated timings rather than treating every slower run as a change in the code.[2]

"""Compare pairwise duplicate detection with a set-based scan."""
from __future__ import annotations
import math
import platform
import timeit
import tracemalloc
def collision_probability(samples: int, buckets: int) -> float:
    """Exact probability of at least one collision for uniform samples."""
    if samples < 0 or buckets <= 0 or samples > buckets:
        raise ValueError("require 0 <= samples <= buckets and buckets > 0")
    log_no_collision = sum(
        math.log1p(-i / buckets) for i in range(samples)
    )
    return -math.expm1(log_no_collision)
def collision_approximation(samples: int, buckets: int) -> float:
    """Birthday approximation: 1 - exp(-n(n-1)/(2m))."""
    if samples < 0 or buckets <= 0:
        raise ValueError("require samples >= 0 and buckets > 0")
    exponent = samples * (samples - 1) / (2 * buckets)
    return -math.expm1(-exponent)
def pairwise_duplicate_check(values: list[int]) -> tuple[bool, int]:
    comparisons = 0
    for i, value in enumerate(values):
        for j in range(i + 1, len(values)):
            comparisons += 1
            if value == values[j]:
                return True, comparisons
    return False, comparisons
def set_duplicate_check(values: list[int]) -> tuple[bool, int]:
    seen: set[int] = set()
    membership_checks = 0
    for value in values:
        membership_checks += 1
        if value in seen:
            return True, membership_checks
        seen.add(value)
    return False, membership_checks
def peak_traced_bytes(function, values: list[int]) -> int:
    tracemalloc.start()
    try:
        function(values)
        _, peak = tracemalloc.get_traced_memory()
        return peak
    finally:
        tracemalloc.stop()
def main() -> None:
    print(f"Python: {platform.python_version()}")
    print(f"Platform: {platform.platform()}")
    for samples, buckets in [(23, 365), (1000, 1_000_000), (1_000_000, 2**128)]:
        exact = collision_probability(samples, buckets)
        approx = collision_approximation(samples, buckets)
        print(
            f"probability n={samples:,} m={buckets:,}: "
            f"exact={exact:.12g} approximation={approx:.12g}"
        )
    print("\nCorrectness and operation counts on unique inputs")
    for size in (1_000, 2_000, 4_000):
        values = list(range(size))
        pair_result = pairwise_duplicate_check(values)
        set_result = set_duplicate_check(values)
        pair_time = min(timeit.repeat(lambda: pairwise_duplicate_check(values), repeat=5, number=1))
        set_time = min(timeit.repeat(lambda: set_duplicate_check(values), repeat=5, number=1))
        pair_peak = peak_traced_bytes(pairwise_duplicate_check, values)
        set_peak = peak_traced_bytes(set_duplicate_check, values)
        print(
            f"n={size:,} pairwise={pair_result[0]} comparisons={pair_result[1]:,} "
            f"best_s={pair_time:.6f} set={set_result[0]} checks={set_result[1]:,} "
            f"best_s={set_time:.6f} ratio={pair_time / set_time:.1f}x "
            f"peak_bytes_pairwise={pair_peak:,} peak_bytes_set={set_peak:,}"
        )
    print("\nEarly duplicate case")
    values = list(range(3_999)) + [3_998]
    print("pairwise:", pairwise_duplicate_check(values))
    print("set:", set_duplicate_check(values))
if __name__ == "__main__":
    main()

What the run measured

On Python 3.13.5 running on the Raspberry Pi system used for this draft, both functions returned the correct answer for unique inputs and for a late duplicate. The operation counts are less machine-dependent than the clock:

Python: 3.13.5
Platform: Linux-6.12.47+rpt-rpi-v8-aarch64-with-glibc2.41
probability n=23 m=365: exact=0.507297234324 approximation=0.500001752183
probability n=1,000 m=1,000,000: exact=0.393267028559 approximation=0.393165999129
probability n=1,000,000 m=340,282,366,920,938,463,463,374,607,431,768,211,456: exact=1.46936646916e-27 approximation=1.46936646916e-27
Correctness and operation counts on unique inputs
n=1,000 pairwise=False comparisons=499,500 best_s=0.083293 set=False checks=1,000 best_s=0.000303 ratio=274.7x peak_bytes_pairwise=392 peak_bytes_set=41,256
n=2,000 pairwise=False comparisons=1,999,000 best_s=0.340007 set=False checks=2,000 best_s=0.000441 ratio=770.6x peak_bytes_pairwise=392 peak_bytes_set=164,136
n=4,000 pairwise=False comparisons=7,998,000 best_s=1.368928 set=False checks=4,000 best_s=0.000828 ratio=1654.2x peak_bytes_pairwise=392 peak_bytes_set=164,136
Early duplicate case
pairwise: (True, 7998000)
set: (True, 4000)

At 4,000 unique values, the pairwise function made 7,998,000 comparisons. The set function made 4,000 membership checks. In this run the best repeated timing was 1.37 seconds versus 0.000828 seconds, a ratio of about 1,654×. At 1,000 values the ratio was about 275×, and at 2,000 it was about 771×. Those ratios belong to this interpreter, processor, input shape and implementation. They are evidence for the growth pattern, not a promise that a set scan will be exactly that many times faster on every machine.

The trade-off is visible in the memory figures. The pairwise version did not build a second collection. The set version used about 160 KiB of Python-traced peak allocations at 4,000 values in this run. tracemalloc reports Python allocations, not total resident memory, so the number is a rough comparison rather than a systems-level memory budget.

When the simple version is the right one

For five values in a configuration check, the pairwise version is perfectly readable and its quadratic cost is irrelevant. It can also be preferable when the values are unhashable, when you need a custom comparison rather than hashing, or when a batch is so small that the extra set is needless clutter.

The set scan earns its place when the batch can grow, when duplicate detection sits on a hot path, or when input arrives incrementally and you want to reject a repeated value immediately. It does not solve uniqueness across restarts or across several machines by itself. That requires a shared constraint, an allocation service, a database uniqueness rule or an identifier design with a sufficiently large space. The formula tells you how much room you have. The application still has to enforce the rule.