java的UUID.randomUUID有多好?

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

199409 次浏览
小开

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

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

小开

有人有经验可以分享吗?

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

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

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

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

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

1 -假设您使用匿名评论者建议的“某种二进制btree”，每个UUID将需要__ABC0位RAM内存来表示N个不同的UUID，假设比特的低密度和随机分布。现在乘以1,000,000和你要运行实验的秒数。我不认为这对于测试高质量RNG碰撞所需的时间长度是实际的。即使是用(假设的)聪明的表述也不行。

小开

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

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

小开
维基百科有一个很好的答案 http://en.wikipedia.org/wiki/Universally_unique_identifier#Collisions < / p >

为了有至少一次碰撞的50%概率，需要生成的随机版本4 uuid的数量为2.71 quintillion，计算如下:

.．.

这个数字相当于在大约85年的时间里每秒生成10亿个UUID，而包含这么多UUID的文件(每个UUID 16个字节)大约是45艾字节，比目前存在的最大数据库(几百pb量级)大很多倍。

.．.

因此，为了有十亿分之一的复制机会，必须生成103万亿版本4 uuid。

小开

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

小开

我去年买彩票，但我从来没有中过....

doc: https://www.rfc-editor.org/rfc/rfc4122

类型1:未实现。如果uuid在同一时刻生成，则可能发生冲突。Impl可以人为地实现a同步，以绕过这个问题。

类型2:从未看到实现。

类型3:md5哈希:可能发生冲突(128位-2技术字节)

类型4:随机:可能发生碰撞(如抽签)。注意jdk6的impl不使用“true”;安全随机，因为PRNG算法不是由开发人员选择的，您可以强制系统使用“;poor"PRNG算法。所以UUID是可预测的。

类型5:sha1哈希:未实现:可能发生冲突(160位-2技术字节)

小开

UUID的原始生成方案是将UUID版本与生成UUID的计算机的MAC地址以及自西方采用格里高利历法以来的100纳秒间隔数连接起来。通过表示空间(计算机)和时间(间隔数)中的单个点，值碰撞的机会实际上为零。

小开

由于大多数答案都集中在理论上，我认为我可以通过给出我所做的实际测试来为讨论添加一些东西。在我的数据库中，我使用Java 8 UUID.randomUUID()生成了大约450万个uuid。以下是我发现的一些:

c0f55f62-b990-47bc-8caa-f42313669948

__abc0 - e81e - 4253 - 8299 - 00 - b4322829d5

__abc0 - 8英镑- 4979 - 4 -共有财产占有一席之地cd9 c556894e2bb——1

< p > < br > b9ea2498 - fb32 40 - ef - 91 - ef - 0 - ba__abc0 < / p >

be87a209 - 2114 - 45 - b3 - 9 - d5a - 86 d__abc0

< p > < br > 4 a8a74a6 - e972 - 4069 b480 b__abc0 < / p >

12 fb4958-bee2-4c89-8cf8-e__abc0

如果它真的是随机的，那么拥有这种类似uuid的概率将相当低(参见编辑)，因为我们只考虑450万个条目。所以，虽然这个函数很好，但就没有碰撞而言，对我来说，它似乎并不像理论上那样好。

编辑:

很多人似乎不理解这个答案，所以我要澄清我的观点:我知道相似之处是“小”的，远远不是完全的碰撞。但是，我只是想将Java的UUID.randomUUID()与真正的随机数生成器进行比较，这是实际的问题。

在真随机数发生器中，最后一种情况发生的概率约为 = 0.007%。因此，我认为我的结论是成立的。

公式解释在这个维基文章en.wikipedia.org/wiki/Birthday_problem

小开

在以前的雇主那里，我们有一个包含随机uuid的唯一列。在部署后的第一周就发生了碰撞。当然，几率很低，但也不是零。这就是为什么Log4j 2包含UuidUtil.getTimeBasedUuid。只要在一台服务器上每毫秒生成的UUID不超过10,000个，它就会生成一个在8,925年内惟一的UUID。

小开

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

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

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

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

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


提交答案