Likelihood of collision using most significant bits of a UUID in Java

java collision uuid
dlinsin picture dlinsin · Nov 28, 2008 · Viewed 193.3k times · Source

If I'm using Long uuid = UUID.randomUUID().getMostSignificantBits() how likely is it to get a collision. It cuts off the least significant bits, so there is a possibility that you run into a collision, right?

Answer

Rasmus Faber picture Rasmus Faber · Nov 28, 2008

According to the documentation, the static method UUID.randomUUID() generates a type 4 UUID.

This means that six bits are used for some type information and the remaining 122 bits are assigned randomly.

The six non-random bits are distributed with four in the most significant half of the UUID and two in the least significant half. So the most significant half of your UUID contains 60 bits of randomness, which means you on average need to generate 2^30 UUIDs to get a collision (compared to 2^61 for the full UUID).

So I would say that you are rather safe. Note, however that this is absolutely not true for other types of UUIDs, as Carl Seleborg mentions.

Incidentally, you would be slightly better off by using the least significant half of the UUID (or just generating a random long using SecureRandom).

Related questions

What is a good 64bit hash function in Java for textual strings?

I'm looking for a hash function that: Hashes textual strings well (e.g. few collisions) Is written in Java, and widely used Bonus: works on several fields (instead of me concatenating them and applying the hash on the concatenated string) …

Read More
Java collision detection between two Shape objects?

I would like to know the best way to tell if a Shape object intersects another shape. Currently I have collision detection in my game sorted out as long as it involves a Shape intersecting a Rectangle or vice versa. …

Read More
What Exactly is Hash Collision

Hash Collision or Hashing Collision in HashMap is not a new topic and I've come across several blogs and discussion boards explaining how to produce Hash Collision or how to avoid it in an ambiguous and detailed way. I recently …

Read More