how good is java's UUID.randomUUID?

Question

I know randomized UUID have very very very low probability for collision in theory, but I am wondering, in practice, how good is java 5's randonUUID in terms of not having collision? Does anybody have any experience to share?

Answer 1

I'm not an expert, but I'd assume that enough smart people looked at Java's random number generator over the years. Hence, I'd also assume that random UUIDs are good. So you should really have the theoretical collision probability (which is about 1 : 3 × 10^38 for all possible UUIDs. Does anybody know how this changes for random UUIDs only? Is it 1/(16*4) of the above?)

From my practical experience, I've never seen any collisions so far. I'll probably have grown an astonishingly long beard the day I get my first one ;)

Answer 2

Does anybody have any experience to share?

There are 2^122 possible values for a type-4 UUID. (The spec says that you lose 2 bits for the type, and a further 4 bits for a version number.)

Assuming that you were to generate 1 million random UUIDs a second, the chances of a duplicate occurring in your lifetime would be vanishingly small. (And to detect the duplicate, you'd have to solve the problem of comparing 1 million new UUIDs per second against all of the UUIDs you have previously generated!)

The chances that anyone has experienced a duplicate in reality are even smaller than vanishingly small ... because of the difficulty of looking.

However, if someone were to configure their JVM to use a "broken" cryptographic random number generator, all bets are off.

Answer 3

UUID uses java.security.SecureRandom, which is supposed to be "cryptographically strong". While the actual implementation is not specified and can vary between JVMs (meaning that any concrete statements made are valid only for one specific JVM), it does mandate that the output must pass a statistical random number generator test.

It's always possible for an implementation to contain subtle bugs that ruin all this (see OpenSSH key generation bug) but I don't think there's any concrete reason to worry about Java UUIDs's randomness.

Answer 4

Wikipedia has a very good answer http://en.wikipedia.org/wiki/Universally_unique_identifier#Random_UUID_probability_of_duplicates