←back to thread

The probability of a hash collision (2022)

(kevingal.com)
140 points subset | 1 comments | 22 Jun 25 03:34 UTC | HN request time: 0.208s | source
Show context
rienbdj ◴[25 Jun 25 06:09 UTC] No.44374088[source]▶
How many values can a UUID v4 take?

How many do you have to generate before a collision becomes a remote possibility?

replies(5): >>44374322 #>>44374323 #>>44375553 #>>44379431 #>>44380082 #
1. NickHoff ◴[25 Jun 25 06:55 UTC] No.44374323[source]▶
A UUID v4 is a 128 bit number, but 4 bits are reserved to specify the version number and 2 more bits are reserved to specify the variant, which leaves 122 bits of randomness. That means it can take on 5 x 10^36 possible values. Following the birthday math, you'd have to generate about 103 trillion UUIDs to have a one-in-a-million chance of having a collision.