
The short answer
About the square root of the number of possible IDs, times 1.18 for even odds. Not the number of possible IDs.
32 random bits: 50% after about 77,000 IDs. 64 bits: after about 5 billion. UUIDv4 (122 random bits): after about 2.7 quintillion, which is 86 years at a billion IDs per second.
Every 2 extra bits of ID length doubles how many IDs you can generate at the same risk.
If a database
UNIQUEconstraint checks every new ID and you retry on conflict, the square-root rule stops being the limit. What matters then is how full the space is.
1. The question, and the wrong instinct
Say several servers each generate random 64-bit IDs for orders, with no coordination between them. A 64-bit ID has 2⁶⁴, about 1.8 × 10¹⁹, possible values. You expect to create a billion orders. That is a few billionths of a percent of the space, so collisions are impossible in practice. Right?
No. A billion random 64-bit IDs have a 2.67% chance of at least one collision, about 1 in 37.
The instinct fails because it asks the wrong question. It asks "how much of the space will I use?" The right question is "how many pairs of IDs exist?", because any pair could match.
2. The birthday paradox in one picture
The classic version: how many people do you need in a room before two probably share a birthday? Not 183 (half of 365). It is 23.
People grow linearly, but pairs grow with the square. Doubling the number of IDs quadruples the number of pairs, so it quadruples the collision risk. With N possible values and n random draws:
P(at least one collision) ≈ 1 − e^(−n² / 2N)
Set that to 50% and solve, and you get the rule of thumb:
n ≈ 1.1774 × √N
For birthdays, N = 365 gives 22.5, which rounds up to 23. For your 64-bit IDs, N = 2⁶⁴, so √N = 2³², about 4.3 billion, and the 50% point is about 5 billion IDs. At a billion IDs you are already about a fifth of the way there in terms of n, which is why the risk is a few percent and not zero.
3. How many IDs can each size hold?
This table gives the number of random IDs you can generate before the collision probability reaches each level:
| Random bits | 50% chance | 1 in a million | 1 in a billion |
|---|---|---|---|
| 32 (8 hex characters) | 77,163 | 93 | 3 |
| 48 | 1.98 × 10⁷ | 23,727 | 750 |
| 64 | 5.06 × 10⁹ | 6.07 × 10⁶ | 192,077 |
| 96 | 3.31 × 10¹⁴ | 3.98 × 10¹¹ | 1.26 × 10¹⁰ |
| 122 (UUIDv4) | 2.71 × 10¹⁸ | 3.26 × 10¹⁵ | 1.03 × 10¹⁴ |
| 128 | 2.17 × 10¹⁹ | 2.61 × 10¹⁶ | 8.25 × 10¹⁴ |
Read the last column carefully. A 32-bit random ID reaches a 1-in-a-billion collision risk after about 3 IDs, and an 8-character hex string is only 32 bits. A 64-bit ID gives you roughly 190,000 IDs at that risk level. A UUIDv4 gives you about 100 trillion.
Two things stand out. First, the numbers grow with 2^(bits/2): each extra bit multiplies your capacity by about 1.41, and each extra 2 bits doubles it. Second, UUIDv4 is not 128 random bits. It has 122, and we will check that below.
4. Don't take my word for it
The √N law, tested. With 32-bit random IDs from the operating system's cryptographic random number generator, we generated IDs until the first duplicate, 5,000 times:
| Measurement (5,000 trials) | Observed | Predicted |
|---|---|---|
| Mean IDs until the first collision | 83,160 | 82,137 |
| Median IDs until the first collision | 77,333 | 77,163 |
And the share of trials that had already collided by the predicted point for each probability level:
| Predicted probability | After this many IDs | Observed share of trials collided |
|---|---|---|
| 1% | 9,291 | 0.9% |
| 10% | 30,084 | 9.4% |
| 50% | 77,163 | 49.8% |
| 90% | 140,638 | 88.8% |
The classic birthday case agrees too: 200,000 simulated rooms of 23 people gave a shared birthday 50.86% of the time, against 50.7% from the formula.
UUIDv4 really has 122 random bits. We generated 200,000 UUIDs with crypto.randomUUID() and looked at each of the 128 bit positions. Exactly 6 bits never changed (positions 48 to 51 are the version nibble 0100, and positions 64 and 65 are the variant bits 10). The other 122 each came out as 1 between 49.7% and 50.3% of the time, which is what a fair coin does.
5. Calculate it yourself
Save this as ids.mjs. It is 14 lines:
// ids.mjs: collision math for random IDs.
// Probability that at least two of n random IDs collide, when each ID has `bits` random bits.
export function collisionProbability(n, bits) {
const N = 2 ** bits;
return -Math.expm1(-(n * (n - 1)) / (2 * N)); // expm1 keeps tiny probabilities accurate
}
// How many IDs can you generate before the collision probability reaches p?
export function idsUntil(p, bits) {
return Math.sqrt(-2 * 2 ** bits * Math.log1p(-p));
}
// How many random bits do you need so that n IDs collide with probability at most p?
export function bitsNeeded(n, p) {
return Math.log2((n * (n - 1)) / (-2 * Math.log1p(-p)));
}
import { collisionProbability, idsUntil, bitsNeeded } from './ids.mjs';
collisionProbability(1e9, 64); // 0.0267 (2.7%, the opening example)
collisionProbability(1e9, 122); // 9.40e-20 (a billion UUIDv4s)
idsUntil(0.5, 122); // 2.71e+18 (the 50% point for UUIDv4)
bitsNeeded(1e9, 1e-9); // 88.7 (1 billion IDs, 1-in-a-billion risk: use 89 bits or more)
One detail matters more than it looks: the code uses -Math.expm1(-x) instead of the textbook 1 - Math.exp(-x). For a billion UUIDv4s, x is about 10⁻¹⁹, which is smaller than a double's precision around 1. In the textbook version, Math.exp(-x) rounds to exactly 1, so 1 - 1 returns exactly 0, while expm1 returns the correct 9.40e-20. A formula that says "impossible" for a risk of one in a hundred quintillion is a bug in the calculator, not good news.
6. How long should my IDs be?
Invert the formula. To keep n IDs below collision probability p, you need about N ≥ n² / (2p) possible values, which is bits ≈ 2·log₂(n) + log₂(1/p) − 1. In code, that is bitsNeeded.
| IDs you will create | Acceptable collision risk | Random bits | Hex characters | Base62 characters |
|---|---|---|---|---|
| 1 million | 1 in a million | 59 | 15 | 10 |
| 1 million | 1 in a billion | 69 | 18 | 12 |
| 1 billion | 1 in a million | 79 | 20 | 14 |
| 1 billion | 1 in a billion | 89 | 23 | 15 |
| 1 trillion | 1 in a million | 99 | 25 | 17 |
| 1 trillion | 1 in a billion | 109 | 28 | 19 |
A rule of thumb: every doubling of the number of IDs costs 2 more bits. Going from a million IDs to a billion (about 1,000×, roughly 2¹⁰) costs 20 more bits.
Compare that with a typical short-link design. Seven base62 characters (0-9A-Za-z) is 62⁷, about 3.5 × 10¹², or 41.7 bits. If you generated those at random with no uniqueness check, you would reach a 50% chance of a collision after about 2.2 million IDs, and a 1-in-a-million risk after only about 2,654 IDs. That is nowhere near a billion links.
So how do real URL shorteners get away with 7 characters? They do not rely on the birthday bound at all.
7. Two things that change the math
7.1 Let the database be the judge
The birthday bound assumes you never check. If every new ID is inserted into a table with a UNIQUE constraint, a collision is no longer silent data corruption. It is an error you handle by drawing again:
// retry.mjs: short random IDs, with the database as the judge of uniqueness.
import { randomInt } from 'node:crypto';
const ALPHABET = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz';
const randomId = (length) =>
Array.from({ length }, () => ALPHABET[randomInt(62)]).join(''); // randomInt is unbiased, unlike byte % 62
// Assumes: db.exec('CREATE TABLE links (id TEXT PRIMARY KEY)')
export function makeCreateLink(db) {
const insert = db.prepare('INSERT INTO links (id) VALUES (?)');
return function createLink(length = 7) {
for (let attempt = 1; ; attempt++) {
const id = randomId(length);
try {
insert.run(id);
return { id, attempt }; // success
} catch (err) {
if (!err.message.includes('UNIQUE')) throw err; // a collision: draw again
}
}
};
}
Now the question changes. A new ID collides only if it matches one of the n IDs already stored, so the chance per insert is just n / N, the fraction of the space that is occupied. That grows linearly, not with the square. We tested it on a real SQLite table with a UNIQUE primary key: filling a 3-character base62 space (238,328 IDs) to 50% took an average of 165,243 insert attempts for 119,164 rows over 12 runs, against 165,196 expected from the math (every row ended up unique). For 7-character IDs:
| Links already stored | New IDs that collide | Retry rate | Average attempts per insert |
|---|---|---|---|
| 1 billion | 0.028% | 1 in 3,522 | 1.0003 |
| 10 billion | 0.284% | 1 in 352 | 1.0028 |
| 100 billion | 2.840% | 1 in 35 | 1.0292 |
| 1 trillion | 28.396% | 1 in 4 | 1.3966 |
At a billion links, 7 characters means about one retry per 3,500 inserts, which is nothing. The cost rises as the space fills, so you pick the length by how full you expect it to get, and you must keep the UNIQUE constraint. It is the safety net, and it also resolves two servers generating the same ID at the same instant.
7.2 Time-ordered IDs (UUIDv7)
UUIDv7 puts a 48-bit millisecond timestamp first, then 74 random bits. IDs with different timestamps can never collide, so only IDs stamped with the same millisecond compete for those 74 bits (assuming they are all random, since RFC 9562 also allows trading some for a counter):
| IDs created in one millisecond | Collision chance in that millisecond | Expected collisions per year at that rate, nonstop |
|---|---|---|
| 10 IDs | 0 | 0 |
| 1,000 IDs | 0 | 0 |
| 1,000,000 IDs (a billion per second) | 0 | 1 |
Even at a billion IDs per second, you would expect less than one collision a year. For ordinary systems, 74 bits per millisecond is plenty, and you gain database index locality as a bonus.
8. Gotchas
Don't truncate UUIDs to look tidy. Taking the first 8 hex characters leaves 32 bits. We measured this with real
crypto.randomUUID()output: the median number of UUIDs until two shared the same first 8 characters was 76,218 (theory: 77,163). That is about 35 trillion times less headroom than the full 122 bits.Use a cryptographically secure random source.
crypto.randomUUID()(browsers, in secure contexts only, and Node) orcrypto.getRandomValues(), notMath.random(). The formula assumes independent, uniform draws. Two processes that share random-generator state, such as a forked worker or a cloned virtual machine snapshot, can produce identical sequences and collide immediately, no matter how many bits you have.Beware modulo bias. The common shortcut
byte % 62makes 8 of the 62 characters 25% more likely, because 256 is not a multiple of 62. That raises the per-character collision odds by about 0.66%, and for 7 characters it makes a collision about 4.7% more likely than the table says. Use an unbiased function such as Node'scrypto.randomInt, or rejection sampling.Collision resistance is not secrecy. RFC 9562 treats unguessability as a separate concern from collision resistance. A UUIDv7 even embeds its creation time in plain text. Do not use IDs as tokens or passwords unless they come from a cryptographically secure source and are meant to be secret.
9. Which ID should I use?
10. The answer
How many random IDs can you generate before two collide? About the square root of the number of possible IDs, and for even odds, 1.18 times that. The reason is that collisions come from pairs, and pairs grow with the square of the count. A 32-bit ID collides after tens of thousands, a 64-bit ID after billions, and a UUIDv4 with its 122 random bits after about 2.7 quintillion, which would take roughly 86 years at a billion per second. To size your own IDs, use bits ≈ 2·log₂(n) + log₂(1/p) − 1, and compute probabilities with expm1. If a database UNIQUE constraint checks every insert, you can use much shorter IDs, because the cost of a collision becomes a cheap retry that grows with how full the space is, not with the square of the count.
Further reading
Birthday problem on Wikipedia, including a table of how many hashes you can generate at each probability for each hash size.
RFC 9562: Universally Unique IDentifiers (UUIDs). The UUID standard, including section 6.7 on collision resistance and section 6.9 on unguessability.
MDN:
Crypto.randomUUID(). The browser API for UUIDv4, available only in secure contexts.
If this post helped, send it to the teammate who just truncated a UUID to "keep the URL short."
Published via ZyVOP — Write once in Markdown, auto-backup to GitHub, and syndicate to Dev.to, Medium & Hashnode in 1 click.
About the author
- One platform to write, cross-post to Dev.to, Medium, WordPress, Hashnode, and Bluesky, and protect your SEO with canonical links. Zero paywalls and full content ownership.
Comments
Join the discussionNo comments yet. Be the first to comment.





