←back to thread

The probability of a hash collision (2022)

(kevingal.com)
140 points subset | 2 comments | 22 Jun 25 03:34 UTC | HN request time: 0.396s | 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. ethan_smith ◴[25 Jun 25 17:57 UTC] No.44380082[source]▶
UUID v4 has 122 random bits giving 2^122 possible values (~5.3×10^36). Using the birthday paradox, you'd need to generate about 2^61 UUIDs (~2.3×10^18) for a 50% collision probability, which is well beyond any practical system's capacity.
replies(1): >>44380621 #
2. jandrewrogers ◴[25 Jun 25 18:46 UTC] No.44380621[source]▶
> ...which is well beyond any practical system's capacity.

Well beyond a single server but not single systems. Large analytical data models run into the tens of exabytes in practical systems already. It isn't hypothetical and probabilistic identifiers become inadvisable[0] in those systems.

Not everything is a web app and UUIDv4 does not scale infinitely.

[0] Technically you can use probabilistic identifiers if you widen them beyond 128-bits, but at that scale the compactness of unique identifiers has a large impact on performance and cost, so 128-bit deterministic identifiers are preferable.