How many items can I hash with SHA-256 before a collision?

Far more than any system will ever produce. The 50% point is 1.1774 × 2 128 = 4.01×10 38 values, and even a one-in-10 18 risk allows 4.81×10 29 . For scale, hashing a trillion items per second since the beginning of the universe would produce about 4×10 29 . Accidental SHA-256 collisions are not a design consideration; the reason to care about SHA-256's collision resistance is deliberate attack, not chance.

Are UUID collisions actually possible?

Mathematically yes, practically no — provided the randomness is sound. A version-4 UUID carries 122 random bits, so the 50% point is 2.72×10 18 values and generating a billion a second would take about 86 years to reach it. Every UUID collision reported in the wild traces to a defective generator: a fork that duplicated the random state, a seed taken from the clock, or a virtual machine restored from a snapshot. The fix is a proper cryptographic random source, not a longer identifier.

Why do 64-bit identifiers keep causing problems?

Because 64 bits gives only 32 bits of collision resistance. The 50% point is 5.06×10 9 values, which a busy system reaches within months, and the probability crosses one in a million after about 6.07×10 6 values. Sixty-four bits is fine when a duplicate is detected and retried, and it is not fine when a duplicate silently corrupts data. When in doubt, 128 bits costs eight extra bytes.

Is it safe to truncate a SHA-256 hash?

It is a supported practice — NIST SP 800-107 explicitly covers truncated hashes — as long as you size the remainder for the job. Truncating to t bits leaves t bits of preimage resistance and t/2 bits of collision resistance, so a 128-bit truncation gives 64-bit collision resistance, which is inadequate against a deliberate search. Take the leftmost bits rather than a subset of your choosing, and record the truncated length wherever the value is stored.

What acceptable probability should I choose?

Match it to the consequence. If a collision is caught by a unique constraint and retried, one in 10 6 over the system's lifetime is unremarkable. If it means silent data loss or a security failure, aim for one in 10 15 or lower — and remember that the count only scales as the square root of the probability, so tightening the threshold by a factor of a million costs you a factor of a thousand in capacity. Adding bits is the cheaper lever.

Does this apply to hash tables in my code?

Not in the same way. A hash table deliberately maps a huge input space into a few thousand buckets and expects collisions, resolving them by chaining or open addressing; what you tune there is the load factor. The birthday bound applies when a collision is a correctness problem — deduplication by digest, content-addressed storage, primary keys, session tokens — rather than a performance one. The distinction is whether the system compares the full values after matching the hash.

How does partitioning reduce collision risk?

By reducing n, and the risk falls with the square of n. If identifiers only have to be unique within a tenant, a shard or a day, then the relevant count is the count within that partition, and a namespace prefix makes cross-partition collisions impossible. Splitting 10 12 global values into a thousand partitions of 10 9 reduces the pair count — and therefore the probability — by a factor of a thousand, for the cost of a few bytes of prefix.

Why does my spreadsheet return zero for the probability?

Because 1 − e −x underflows in double precision once x falls below about 10 −16 : e −x rounds to exactly 1 and the subtraction gives 0. Use an expm1 function, which is built for this and computes e x − 1 accurately for tiny arguments, or simply use x itself, since 1 − e −x ≈ x to within a part in 10 16 for small x. This calculator uses expm1, which is why it reports meaningful values down to 10 −300 .

What is the difference between a random collision and a birthday attack?

The arithmetic is the same; the intent is not. A random collision happens by chance among values you generated. A birthday attack is an adversary deliberately generating about 2 b/2 candidates to find a pair that collides, usually so that a signature over one document also validates the other. Defending against the second requires both a long enough digest and a hash function with no cryptanalytic weakness — MD5 and SHA-1 fail the second condition regardless of their length.

Hash Collision Probability Calculator (Birthday Bound)

Inputs this calculator takes, with typical values
Input	What to enter	Example
Hash or identifier length	Random bits in the value. A UUIDv4 has 122 random bits, not 128; a truncated SHA-256 has as many bits as you kept.	128 bits
Number of values generated	How many distinct items you will hash or how many identifiers you will mint over the lifetime of the system.	1 values
Acceptable collision probability	Your risk threshold over the whole lifetime of the system. 0.0001% is one chance in a million.	0.0001 %
Generation rate	New values created per second, used to convert the threshold count into a time.	1000 /s

Why duplicates appear at the square root of the space

The birthday problem is the standard illustration: in a room of 23 people there is a better-than-even chance two share a birthday, even though there are 365 possibilities. The reason is that you are not comparing each person against one fixed date — you are comparing every pair. Twenty-three people form 253 pairs, and 253 chances at 1-in-365 add up quickly.

The same counting applies to hashes and random identifiers. With n values there are n(n−1)/2 pairs, and each pair collides with probability 1/2^b. The expected number of collisions is therefore n(n−1)/(2·2^b), and the probability that at least one occurs is 1 − e^−that. Setting it to one half and solving gives n ≈ 1.1774·2^b/2.

That square root is the whole point. A 64-bit identifier has 1.8×10¹⁹ possible values, which sounds inexhaustible, and reaches a coin-flip chance of duplication after only 5.06×10⁹ of them — five billion, a number a busy system reaches in months. The intuition that a large space is safe fails because it compares n against 2^b when the right comparison is n against 2^b/2.

The same halving is what NIST SP 800-107 means when it says a hash function of L bits provides L/2 bits of collision resistance while providing L bits of preimage resistance. SHA-256 offers 128 bits against collisions and 256 against inverting a digest. Those are different attacks and they cost very different amounts, which is why a truncated digest that is fine for one purpose can be inadequate for the other.

The three formulas and when each applies

Probability from n. p = 1 − exp(−n(n−1)/(2·2^b)). The exponent is the expected number of colliding pairs; the exponential converts that expectation into the probability of at least one, exactly as a Poisson model does. When the exponent is very small — which it is for any well-chosen identifier length — the answer is numerically equal to the exponent itself, because 1 − e^−x ≈ x for small x. That is why a 128-bit identifier over a trillion values reports 1.47×10⁻¹⁵: it is simply 10²⁴ pairs divided by 2·2¹²⁸.

n from a probability. Invert it: n ≈ √(2·2^b·ln(1/(1−p))). At p = 0.5 the logarithm is ln 2 = 0.6931, and √(2 ln 2) = 1.1774, which gives the familiar 1.1774·2^b/2. At small p the logarithm is approximately p itself, so the count scales as √p — dropping your acceptable risk by a factor of 100 only divides the safe count by 10. Risk tolerance is a weak lever compared with bit length.

Bits from n and a probability. Rearranging for 2^b gives 2^b = n(n−1)/(2·ln(1/(1−p))), and taking a base-2 logarithm gives the bits you need. Rounding up to a whole number of bytes is what the calculator reports, because that is what implementations actually use.

A note on precision. Computing 1 − e^−x directly loses every significant digit when x is around 10⁻¹⁶, because e^−x is indistinguishable from 1 in double precision. This calculator uses the expm1 function, which computes e^x − 1 accurately for tiny x, so the probabilities stay meaningful down to 10⁻³⁰⁰. If you reproduce these figures in a spreadsheet and get exactly zero, that is the reason.

Worked example: sizing a short URL token

You are minting random tokens for a link shortener. The service will create 100 million links, and you decide that a one-in-a-million chance of ever issuing a duplicate is acceptable. How long must the token be?

Pairs. n = 10⁸, so pairs = 10⁸ × (10⁸ − 1) ÷ 2 = 4.99999995×10¹⁵, which is 5×10¹⁵ for our purposes.
Risk term. p = 10⁻⁶, so ln(1/(1−p)) = 1.0000005×10⁻⁶.
Required space. 2^b = pairs ÷ risk term = 5×10¹⁵ ÷ 10⁻⁶ = 5×10²¹.
Bits. log₂(5×10²¹) = ln(5×10²¹) ÷ ln 2 = 49.9637 ÷ 0.693147 = 72.08, so 73 bits, rounded up to 80 bits for a whole number of bytes.
Check. At 80 bits, 2⁸⁰ = 1.2089×10²⁴, and the probability over 10⁸ values is 5×10¹⁵ ÷ (2 × 1.2089×10²⁴) = 2.07×10⁻⁹ — comfortably below the 10⁻⁶ target, with three orders of magnitude of headroom for growth.
Encoding. 80 bits is 10 bytes, which is 14 base64 characters or 16 base32 characters. Choose base32 if the token has to survive being read aloud or typed.

Compare that with a naive choice. A 48-bit token — eight base64 characters, which looks generous — has a 50% point at 1.1774 × 2²⁴ = 1.975×10⁷. At 100 million tokens the exponent is 5×10¹⁵ ÷ (2 × 2.815×10¹⁴) = 8.88, so the probability of at least one duplicate is 1 − e^−8.88 = 0.99986. Not a risk — a certainty.

How to read the number and what to do about it

First decide what a collision costs. Two different files hashing to the same value in a deduplication store means silent data loss. Two users receiving the same session token means account takeover. Two rows in a table colliding on a primary key means a constraint violation and a retry — irritating, not dangerous. The acceptable probability differs by many orders of magnitude between those cases, and the calculation is only as good as that judgement.

Then check whether a collision is even detectable. A database with a unique index will reject the second insert and your code can retry, so a 10⁻⁹ probability is a 10⁻⁹ chance of an extra round trip. Content-addressed storage with no uniqueness check silently returns the wrong object. The same probability means completely different things in the two systems, and the second deserves several more bytes.

Where the number is too high, you have three levers and they are not equally strong. Adding bits is exponential: eight more bits divides the probability by 256. Reducing n is quadratic: halving the number of values divides the probability by four. Loosening the risk threshold is the weakest, because the safe count only scales as its square root. In almost every case the right answer is more bits, and bits are cheap.

A fourth lever is often overlooked: partition the space. If identifiers only need to be unique within a tenant, a customer, or a day, then n is the count within that partition rather than the global total, and a namespace prefix removes cross-partition collisions entirely. Splitting a global 10¹² into a thousand partitions of 10⁹ reduces the pair count by a factor of a thousand. This is why database keys are usually scoped to a table and why time-ordered identifiers embed a timestamp.

If you are choosing an encoding for the value once you know its bit length, the base64 encoded size calculator converts bytes into characters, and the database table size calculator shows what those extra bytes cost per row and per index once you multiply by the row count.

How many values before a collision becomes likely

Counts are √(2·2^b·ln(1/(1−p))) evaluated at each probability. The 50% column is 1.1774·2^b/2; the 10⁻⁹ column is 4.4721×10⁻⁵·2^b/2; the 10⁻¹⁸ column is 1.4142×10⁻⁹·2^b/2.
Bits	Distinct values 2^b	n at 50%	n at 1 in 10⁹	n at 1 in 10¹⁸
32	4.295×10⁹	77,163	2.93	0.0000927
48	2.815×10¹⁴	1.975×10⁷	750.3	0.0237
64	1.845×10¹⁹	5.057×10⁹	1.921×10⁵	6.07
122 (UUIDv4)	5.317×10³⁶	2.715×10¹⁸	1.031×10¹⁴	3.261×10⁹
128	3.403×10³⁸	2.172×10¹⁹	8.249×10¹⁴	2.609×10¹⁰
160 (SHA-1)	1.462×10⁴⁸	1.423×10²⁴	5.407×10¹⁹	1.710×10¹⁵
256 (SHA-256)	1.158×10⁷⁷	4.007×10³⁸	1.522×10³⁴	4.812×10²⁹

Read the 64-bit row carefully: only six values are needed before the collision probability exceeds one in 10¹⁸. That is the sense in which a 64-bit identifier is not usable when a duplicate would be a correctness failure, even though five billion look safe at a glance.

A UUIDv4 has 122 random bits, not 128

RFC 4122 fixes four bits for the version and two for the variant, so a version-4 UUID carries 122 bits of randomness in its 128-bit form. The 50% point is therefore 1.1774 × 2⁶¹ = 2.715×10¹⁸ rather than 2.172×10¹⁹ — a factor of eight fewer values. It does not change any practical conclusion, because 2.7 quintillion is still far beyond what any system generates, but it is the correct figure and it matters if you are truncating.

What does change conclusions is the source of randomness. The birthday bound assumes uniform, independent draws. A generator seeded from the clock, one that reseeds identically after a fork, or a pool that is drained at boot produces correlated values, and the effective bit count collapses. Every real-world UUID collision on record traces to a weak generator rather than to the birthday bound. Use the platform's cryptographic random source, not a general-purpose pseudo-random number generator.

Mistakes that make this calculation misleading

Counting the full identifier length when part of it is fixed. Version and variant bits, a constant prefix, a checksum character and a hyphenated format all reduce the random portion. Count only bits that vary.
Using the design volume instead of the lifetime volume. The n that matters is every value ever generated that could still be compared, not the number live at one moment. Systems that never delete accumulate risk for as long as they run.
Assuming a good random source. The formula assumes uniform independent draws. A biased or predictable generator is worth far fewer effective bits, and no amount of length compensates.
Comparing n against 2^b. The relevant threshold is 2^b/2. This single confusion is what makes 64-bit identifiers look safe when they are not.
Ignoring that a truncated hash halves twice. Truncating SHA-256 to 128 bits leaves 64 bits of collision resistance, not 128. Truncation is legitimate — NIST SP 800-107 permits it — but the security strength follows the truncated length.
Treating an accidental collision and a deliberate one as the same problem. This calculator models random collisions. An attacker who can choose inputs mounts a directed search, and against a broken hash function that search can be far cheaper than 2^b/2.
Forgetting that hash tables collide by design. A hash table maps a large space into a few thousand buckets and resolves collisions with chaining or probing. Load factor, not the birthday bound, is what you tune there.

Key terms

Birthday bound: The rule that a collision in a space of 2^b values becomes likely after about 2^(b/2) draws, because n values form n(n−1)/2 pairs rather than n comparisons.
Collision resistance: The difficulty of finding any two inputs with the same digest. For an ideal b-bit hash it is about b/2 bits of work — half the preimage resistance.
Preimage resistance: The difficulty of finding an input that produces a given digest. For an ideal b-bit hash it is b bits of work, which is why the same function offers two different strengths depending on the attack.
Pigeonhole principle: If you place more than 2^b items into 2^b slots, at least two must share a slot. It is the point at which collision probability becomes exactly 1 rather than merely large.
Truncated hash: A digest cut to fewer bits than the function produces. Its collision resistance is half the retained length, so a SHA-256 truncated to 128 bits gives 64-bit collision resistance.

Accidental collisions versus deliberate ones

Everything above concerns collisions arising by chance. A deliberate attack is a different calculation with the same exponent. A generic birthday attack against a b-bit hash costs about 2^b/2 operations and, in its naive form, 2^b/2 memory — which is why the memory-efficient cycle-finding variants matter in practice. Against SHA-256 that is 2¹²⁸, which is out of reach for the same reasons set out in the key brute-force time calculator.

The distinction that matters is whether the hash function is sound. MD5 and SHA-1 both fell to cryptanalytic collision attacks far cheaper than their birthday bounds — chosen-prefix collisions against them are practical rather than theoretical — so neither is acceptable where an adversary chooses inputs. Both remain perfectly serviceable as non-cryptographic checksums for accidental corruption, where this calculator's arithmetic is the whole story. Knowing which of the two situations you are in is the decision; the arithmetic is the easy part.

One structural consequence follows from the halving. Because collision resistance is b/2, a digest must be twice as long as the security strength you want. A system targeting 128-bit security needs a 256-bit hash, which is precisely why SHA-256 pairs with AES-128 in standard cipher suites, and why SHA-384 or SHA-512 accompanies AES-256. When you see a hash length that looks excessive next to a key length, this halving is the reason.

Finally, if the identifier you are sizing also has to be unguessable rather than merely unique, the relevant quantity is entropy against a search, not the birthday bound — and the safe length is larger. Estimate it with the password entropy calculator.

Hash Collision Probability Calculator

Calculator

It returns

The formula

Why duplicates appear at the square root of the space

The three formulas and when each applies

Worked example: sizing a short URL token

How to read the number and what to do about it

How many values before a collision becomes likely

Mistakes that make this calculation misleading

Key terms

Accidental collisions versus deliberate ones

Frequently asked questions

References

Hash Collision Probability Calculator

Calculator

It returns

The formula

Why duplicates appear at the square root of the space

The three formulas and when each applies

Worked example: sizing a short URL token

How to read the number and what to do about it

How many values before a collision becomes likely

Mistakes that make this calculation misleading

Key terms

Accidental collisions versus deliberate ones

Frequently asked questions

References

Related calculators