1

For example if you have a single UUID with a collision probability of x, if you concatenate 2 UUIDs, does the collision probability become x^2?

val0 = generate_uuid()
val1 = generate_uuid()

final_val = val0 + val1

So with each additional uuid, does it reduce the probability of collision exponentially? My x, and x^2 might also be flawed. I don't know how to formulate it.

EDIT: Consider uuid4 from python and joining them as strings. final_val is string.

Joan Venge
  • 1,950
  • 2
  • 18
  • 24
  • 1
    It depends entirely on the algorithm. – Steve Sep 17 '20 at 13:54
  • Are you using UUID version 1, version 2, version 3, version 4, or version 5? – Jörg W Mittag Sep 17 '20 at 14:11
  • It seems v5 is not what I am looking for, v4 seems to be better (for my purposes: https://docs.python.org/3/library/uuid.html) – Joan Venge Sep 17 '20 at 14:19
  • Why do you need to know this in the first place? Just curious? Or do you have a specific application in mind, in which case you're likely overthinking the problem? – Arseni Mourzenko Sep 17 '20 at 17:38
  • Just curiosity. – Joan Venge Sep 17 '20 at 18:20
  • 1
    Please, do not change your question in a way that invalidates existing answers. That is considered to be very rude because it nullifies all the hard work that the answerers have put into their answers, especially since none of us get paid to, essentially, do your work for you. It also makes answerers look like idiots, unless you carefully inspect the question history and compare the timestamps of the edits and the answers. If you want to clarify something, edit it into your question in such a way that it does not fundamentally change the question and does not invalidate any answers. – Jörg W Mittag Sep 21 '20 at 04:17

4 Answers4

4

With version 4 (variant 1) random UUIDs there are 2^122 possible values. If we assume proper random* number generation that means that the chance of any two ids matching is around 1 in 5.32x10^36.

If you use 2 version 4 UUIDs together (let's call it a super UUID), you have 2^244 possible different values. That means the chance of 2 properly random* 'super UUIDs' the chance they collide is 1 in 2.83×10^73

So yes, having more numbers available makes it less likely but it was already incredibly unlikely in the first place. It's kind of like asking whether if you dip a cup in the ocean twice, a year separated, whether it's less likely to get the exact same set of water molecules on each attempt than you would if you did the same thing in Lake Superior.

*Unless you have special equipment to generate random numbers, then in practical terms we are really talking about psuedo-random numbers. As long as the PRNG is cryptographically secure (evenly distributed and chaotic, etc.) we can ingore that and treat them like true random numbers for this purpose.

JimmyJames
  • 24,682
  • 2
  • 50
  • 92
  • you ignore the fact that guids are not random numbers but include things like timestamps and mac addresses – Ewan Oct 10 '20 at 09:28
  • @Ewan [Uh no, I didn't](https://en.wikipedia.org/wiki/Universally_unique_identifier#Version_4_(random)). – JimmyJames Oct 11 '20 at 21:32
  • 1
    @Ewan If you aren't following: version 4 UUIDs don't contain 'things like timestamps and mac addresses' – JimmyJames Oct 12 '20 at 15:32
0

Version 5 UUIDs are guaranteed to be the same for the same input, which means that it is guaranteed that val0 and val1 are always the same.

Therefore, concatenating two, three, twenty, thirty, or a trillion UUIDs does not change the probability of a collision at all.

Jörg W Mittag
  • 101,921
  • 24
  • 218
  • 318
  • I don't know this Python module, but isn't `generate_uuid()` supposed to take the current time as part of the input? So two calls one after another will always use a different input? – Doc Brown Sep 21 '20 at 13:30
-2

You can’t reduce the expected number of collision without using more bits. What you can do: You can use consecutive UUIDs, which means it is less likely to have any collision with other UUIDs if they use the same method, but if you have any collisions, you will get lots of them.

gnasher729
  • 42,090
  • 4
  • 59
  • 119
-2

Yes, but also No.

say the collision chance is 50% obviously if you have two ids then its 0.5 * 0.5 = 0.25 if you have 3 its 0.5^3 etc

But if its 0 chance of collision, which it totally is, then its still 0 chance afterwards.

Ewan
  • 70,664
  • 5
  • 76
  • 161