我知道随机uuid在理论上有非常非常非常低的碰撞概率,但我想知道,在实践中,Java的randomUUID()在没有碰撞方面有多好?有人有经验可以分享吗?


当前回答

UUID使用java.security。SecureRandom,它被认为是“加密强的”。虽然没有指定实际的实现,并且在不同的JVM之间可能有所不同(这意味着所做的任何具体语句只对一个特定的JVM有效),但它确实要求输出必须通过统计随机数生成器测试。

实现中总是可能包含破坏这一切的细微错误(参见OpenSSH密钥生成错误),但我不认为有任何具体理由担心Java uuid的随机性。

其他回答

我不是专家,但我认为已经有足够多的聪明人研究过Java的随机数生成器。因此,我还假定随机uuid是好的。所以你应该有理论上的碰撞概率(对于所有可能的uuid,碰撞概率约为1:3 × 10^38)。有人知道这只对随机uuid有什么变化吗?是上面的1/(16*4)吗?)

从我的实际经验来看,到目前为止我还从未见过任何碰撞。我第一次留胡子的那天可能已经长出了惊人的长胡子;)

许多答案都讨论了需要生成多少uuid才能达到50%的碰撞几率。但是50%、25%甚至1%的碰撞概率对于一个必须(实际上)不可能发生碰撞的应用程序来说是毫无价值的。

程序员是否经常将其他可能发生的事件视为“不可能”?

当我们将数据写入磁盘或内存并再次读取时,我们想当然地认为数据是正确的。我们依靠设备的纠错功能来检测任何损坏。但是,未检测到错误的几率实际上在2-50左右。

对随机uuid应用类似的标准不是很有意义吗?如果您这样做,您将发现在大约1000亿个随机uuid(236.5)的集合中,“不可能”的碰撞是可能的。

这是一个天文数字,但像国家医疗保健系统中的逐项计费,或在大量设备上记录高频传感器数据等应用程序肯定会遇到这些限制。如果你正在写下一篇《银河系漫游指南》,不要试图为每篇文章分配uuid !

有人有经验可以分享吗?

type-4 UUID有2^122个可能的值。(规范说,类型损失2位,版本号损失4位。)

假设您每秒生成100万个随机uuid,那么在您的一生中出现重复uuid的几率将微乎其微。为了检测重复,您必须解决每秒将100万个新uuid与之前生成的所有uuid进行比较的问题1!

任何人在现实生活中经历(即实际注意到)一个复制品的机会甚至比消失的小得多……因为寻找碰撞的实际困难。

当然,您通常会使用伪随机数生成器,而不是真正的随机数源。但我认为我们可以确信,如果您使用可信的提供商来提供加密强度随机数,那么它将是加密强度,并且重复的概率将与理想(无偏差)随机数生成器相同。

然而,如果你要使用一个带有“坏掉的”加密随机数生成器的JVM,那么一切都是徒劳的。(这可能包括一些系统上“熵不足”问题的变通方法。或者有人在您的系统或上游对您的JRE进行了修补。)


1 - Assuming that you used "some kind of binary btree" as proposed by an anonymous commenter, each UUID is going to need O(NlogN) bits of RAM memory to represent N distinct UUIDs assuming low density and random distribution of the bits. Now multiply that by 1,000,000 and the number of seconds that you are going to run the experiment for. I don't think that is practical for the length of time needed to test for collisions of a high quality RNG. Not even with (hypothetical) clever representations.

我们已经在我们的应用程序中使用Java的随机UUID一年多了,而且使用得非常广泛。但是我们从来没有遇到过碰撞。

维基百科给出了一个很好的答案 http://en.wikipedia.org/wiki/Universally_unique_identifier#Collisions

the number of random version 4 UUIDs which need to be generated in order to have a 50% probability of at least one collision is 2.71 quintillion, computed as follows: ... This number is equivalent to generating 1 billion UUIDs per second for about 85 years, and a file containing this many UUIDs, at 16 bytes per UUID, would be about 45 exabytes, many times larger than the largest databases currently in existence, which are on the order of hundreds of petabytes. ... Thus, for there to be a one in a billion chance of duplication, 103 trillion version 4 UUIDs must be generated.