Hash Collision Probability Calculator (birthday bound)

Understanding the hash collision probability calculator — concept and principle

When you assign hash values, random IDs or short checksums to many items, sooner or later two items may get the same value. This calculator uses the birthday bound to estimate the probability of at least one collision among n items for a hash of a given size, and how many items give a 50% chance. It helps choose ID lengths, size hash tables and deduplication keys, and judge truncated hashes.

Like shared birthdays, collisions appear near the square root of the number of values.

How it is calculated

N = 2^bits, the number of possible hash values.
Collision probability p ≈ 1 − e^(−n² / 2N), shown as a percentage. The calculator uses expm1 so that very small probabilities are not lost to rounding.
Items for a 50% chance ≈ 1.1774 × √N = 1.1774 × 2^(bits/2), where 1.1774 = √(2 ln 2).

The principle

This is the birthday problem: in a room of 23 people, the chance that two share a birthday is already over 50%, because what matters is the number of pairs, n(n − 1)/2, not the number of people. Each pair collides with probability 1/N, so the expected number of colliding pairs is about n²/2N, and treating pairs as roughly independent gives the exponential formula. The key consequence is that collisions become likely at around the square root of the number of possible values: a b-bit hash offers only about b/2 bits of collision resistance.

Worked example

Inputs: 64-bit hash, n = 10^9 items.
N = 2^64 = 1.8447 × 10^19.
Exponent: n² / 2N = 10^18 ÷ (3.6893 × 10^19) = 0.027105.
Probability: 1 − e^(−0.027105) = 0.02674, about 2.67%.
50% point: 1.1774 × 2^32 = 1.1774 × 4,294,967,296 = 5,056,894,494 items.

Each point is the calculator re-run with only “Number of items” changed; the gold point is the default example. Change the inputs above and this chart follows your numbers.

Number of items	Collision probability
2.5e+08	0.17%
5e+08	0.68%
7.5e+08	1.51%
1e+09	2.67%
1.25e+09	4.15%
1.5e+09	5.92%
2e+09	10.27%

How to read the result

A 2.67% chance of any collision in a billion records is too high for unique primary keys but may be fine for a cache. As benchmarks, a 32-bit hash reaches 50% at about 77,000 items, a 64-bit hash at about 5 billion, and 122-bit random UUIDs only around 2.7 × 10^18. If collisions must be practically impossible, pick a size where p is far below the other failure risks of your system.

Common mistakes

Assuming collisions start only near 2^bits items; they start near 2^(bits/2).
Applying the formula to hashes that are not uniformly distributed, such as weak non-cryptographic hashes on structured data.
Confusing accidental collisions with deliberate attacks; an attacker may need far fewer tries against a weak hash.

Keep in mind: The approximation assumes uniformly random, independent hash values and is most accurate when n is much smaller than N. It does not describe security against chosen-input attacks on broken hash functions.

Frequently asked questions

How many bits do I need for unique random IDs?

Use the formula in reverse: for one billion items and a collision chance below one in a million, you need roughly 80 bits or more.

Why is it called the birthday bound?

It is the same mathematics as the birthday paradox, with 365 days replaced by 2^bits hash values.

Is a truncated SHA-256 hash safe as an ID?

Its collision behaviour matches the truncated length, so 64 bits of SHA-256 behaves like any good 64-bit hash.

Sources: D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching (hashing) · A. J. Menezes, P. C. van Oorschot, S. A. Vanstone, Handbook of Applied Cryptography, CRC Press

Checked 8 Nov 2026. Standard formulas and RFC/IEEE definitions, computed locally in your browser — nothing you type is sent anywhere.

Your numbers