Skip to content
Omnikalc

Hash and ID collision probability calculator

Estimate the chance that two of n random IDs or hash values collide for a given number of bits, how many items give a 50% chance, and how many keep the risk below one in a million.

Updated on
Your inputs
bits

Value out of range

Value out of range

Results

Probability of at least one collision

2.674 %

Above one in a million: acceptable only if collisions are harmless or detected
Expected number of colliding pairs
0.02711
Items for a 50% chance of collision
5,056,894,494
Items keeping the risk under one in a million
6,074,001
Possible values, as a power of ten (10^x)
19.27

The birthday problem for computers

How many people must be in a room before two share a birthday with 50% probability? Only 23, far fewer than the 365 days of the year. The same surprise applies to hashes, random IDs and checksums: collisions appear long before the space of possible values is anywhere near full. This is the birthday bound.

The formula

With b bits, there are 2^b possible values. For n random items, the expected number of colliding pairs is n(n − 1) ÷ 2^(b+1), and the probability of at least one collision is approximately:

p ≈ 1 − e^(−n² ÷ 2^(b+1))

The number of items that gives a 50% chance is about 1.1774 × 2^(b/2): the square root of the space, not the space itself.

Example

One billion random 64-bit IDs: n² ÷ 2^65 ≈ 0.0271, so p ≈ 2.7%. A 50% chance is reached at about 5.06 billion items, and staying under one in a million limits you to about 6 million items.

Bits 50% collision after One-in-a-million risk after
32 77,000 93
64 5.1 billion 6.1 million
128 (UUID v4 has 122) 2.2 × 10¹⁹ 2.6 × 10¹⁶
256 4 × 10³⁸ 4.8 × 10³⁵

Practical conclusions

  • 32-bit hashes (CRC-32, short IDs) collide quickly: never use them as unique keys.
  • 64-bit random IDs are fine for millions of rows, risky for billions.
  • A random UUID v4 has 122 random bits: you would need about 2.7 quintillion of them for a 50% chance.
  • Truncating a SHA-256 hash to 8 hexadecimal characters leaves only 32 bits.

Accidental versus deliberate collisions

These figures assume random values. An attacker looking for collisions also needs about 2^(b/2) attempts, which is why cryptographic hashes need at least 256 bits for 128-bit security. Broken algorithms such as MD5 and SHA-1 allow collisions far faster than the birthday bound.

Frequently asked questions

Why do collisions happen so early?

Every new item can collide with every item already stored, so the number of pairs grows as n squared. Collisions become likely around the square root of the number of possible values.

Can two UUIDs ever be the same?

In theory yes, but a version 4 UUID has 122 random bits. You would need about 2.7 quintillion UUIDs for a 50% chance of a single duplicate, so in practice it does not happen with a good random generator.

Is a 32-bit hash enough for a cache key?

Only for small sets. With 32 bits, a collision becomes likely after about 77,000 items, so a cache must still compare the full key or use a 64-bit or larger hash.

Does this apply to cryptographic hashes?

Yes for random collisions, and an attacker also needs about 2^(b/2) attempts against a sound hash. That is why 256-bit hashes such as SHA-256 are used for 128-bit security.

Was this calculator helpful?

Thanks for your feedback!

Results are estimates provided for information purposes. They do not replace professional advice.

Related calculators