我知道随机UUID在理论上具有非常、非常、非常低的碰撞概率，但我想知道，在实践中，JavarandomUUID()在没有碰撞方面有多好？有人有经验可以分享吗？
问问题
188354 次
10 回答
186
UUID 使用java.security.SecureRandom，它应该是“加密强”。虽然未指定实际实现并且在 JVM 之间可能会有所不同（这意味着所做的任何具体语句仅对一个特定的 JVM 有效），但它确实要求输出必须通过统计随机数生成器测试。
实现总是有可能包含破坏所有这些的细微错误（请参阅 OpenSSH 密钥生成错误），但我认为没有任何具体理由担心 Java UUID 的随机性。
于 2010-03-25T10:43:48.950 回答
122
维基百科有一个很好的答案 http://en.wikipedia.org/wiki/Universally_unique_identifier#Collisions
为了有 50% 的概率至少发生一次冲突，需要生成的随机版本 4 UUID 的数量为 2.71 quintillion，计算如下：
...
这个数字相当于每秒生成 10 亿个 UUID 大约 85 年，一个包含这么多 UUID 的文件（每个 UUID 16 个字节）大约是 45 艾字节，比目前存在的最大数据库大很多倍，数百 PB 的数量级。
...
因此，为了有十亿分之一的重复机会，必须生成 103 万亿个版本 4 UUID。
于 2010-08-30T13:11:14.140 回答
72
有人有经验可以分享吗？
类型 4 UUID有2^122可能的值。（规范说您会丢失 2 位的类型，以及另外 4 位的版本号。）
假设您每秒生成 100 万个随机 UUID，那么在您的一生中发生重复的机会将非常小。为了检测重复，您必须解决每秒将 100 万个新 UUID 与您之前生成的所有UUID 进行比较的问题1！
任何人在现实生活中经历（即实际注意到）重复的机会甚至比消失的小得多……因为寻找碰撞的实际困难。
当然，现在您通常会使用伪随机数生成器，而不是真正随机数的来源。但我认为我们可以确信，如果您为您的加密强度随机数使用可靠的提供商，那么它将是加密强度，并且重复的概率将与理想（无偏）随机数生成器相同.
但是，如果您要使用带有“损坏的”加密随机数生成器的 JVM，那么所有的赌注都没有了。（这可能包括某些系统上“熵不足”问题的一些解决方法。或者有人在您的系统或上游修改了您的 JRE。）
1 - 假设您使用匿名评论者提出的“某种二进制 btree”，则每个 UUID 都将需要O(NlogN)RAM 内存位来表示N不同的 UUID，假设位密度低且随机分布。现在将它乘以 1,000,000 和您要运行实验的秒数。我认为这对于测试高质量 RNG 碰撞所需的时间长度是不切实际的。甚至没有（假设的）聪明的表示。
于 2010-03-25T10:33:08.910 回答
21
我不是专家，但我认为多年来有足够多的聪明人关注 Java 的随机数生成器。因此，我还假设随机 UUID 是好的。所以你真的应该有理论上的碰撞概率（对于所有可能的 UUID，它大约是 1 : 3 × 10^38。有人知道这对于随机 UUID 是如何变化的吗？是1/(16*4)上面的吗？）
根据我的实践经验，到目前为止，我从未见过任何碰撞。在我得到第一个胡须的那一天，我可能会长出惊人的长胡须；）
于 2010-03-25T08:22:27.897 回答
12
在前雇主，我们有一个包含随机 uuid 的独特列。我们在部署后的第一周就发生了碰撞。当然，几率很低，但不是零。这就是 Log4j 2 包含 UuidUtil.getTimeBasedUuid 的原因。只要您在单个服务器上生成的 UUID 不超过 10,000 个/毫秒，它将生成一个 8,925 年唯一的 UUID。
于 2017-03-09T17:50:50.607 回答
10
UUID 的原始生成方案是将 UUID 版本与生成 UUID 的计算机的 MAC 地址以及自西方采用公历以来的 100 纳秒间隔数连接起来。通过表示空间（计算机）和时间（间隔数）中的单个点，值冲突的机会实际上为零。
于 2015-09-25T11:53:29.500 回答
9
许多答案讨论了必须生成多少 UUID 才能达到 50% 的碰撞几率。但是对于必须（实际上）不可能发生碰撞的应用程序来说，50%、25% 甚至 1% 的碰撞几率是毫无价值的。
程序员是否经常将其他可能发生且确实发生的事件视为“不可能”？
当我们将数据写入磁盘或内存并再次读取时，我们理所当然地认为数据是正确的。我们依靠设备的纠错来检测任何损坏。但未检测到错误的机会实际上是 2 -50左右。
将类似的标准应用于随机 UUID 是否有意义？如果这样做，您会发现在大约 1000 亿个随机 UUID (2 36.5 ) 的集合中可能发生“不可能的”碰撞。
这是一个天文数字，但国家医疗保健系统中的分项计费或在大量设备上记录高频传感器数据等应用肯定会遇到这些限制。如果您正在编写下一篇《银河系漫游指南》，请不要尝试为每篇文章分配 UUID！
于 2017-09-24T21:04:50.853 回答
4
我去年玩彩票，我从来没有赢过....但似乎那里的彩票有中奖者...
文档：https ://www.rfc-editor.org/rfc/rfc4122
类型 1：未实施。如果同时生成 uuid，则可能发生冲突。impl 可以人为地进行异步同步以绕过这个问题。
类型 2：永远看不到实现。
类型 3：md5 散列：可能发生冲突（128 位 - 2 技术字节）
类型 4：随机：可能发生碰撞（如彩票）。请注意，jdk6 impl 不使用“真正的”安全随机，因为 PRNG 算法不是由开发人员选择的，您可以强制系统使用“差”的 PRNG 算法。所以你的 UUID 是可预测的。
类型 5：sha1 哈希：未实现：可能发生冲突（160 位 2 技术字节）
于 2015-04-23T06:36:33.600 回答
2
由于大多数答案都集中在理论上，我认为我可以通过进行实际测试来为讨论添加一些内容。在我的数据库中，我使用 Java 8 UUID.randomUUID() 生成了大约 450 万个 UUID。以下只是我发现的一些：
c0f55f62 -b990-47bc-8caa-f42313669948
c0f55f62 -e81e-4253-8299-00b4322829d5
c0f55f62 -4979-4e87-8cd9-1c556894e2bb
b9ea2498-fb32-40ef-91ef-0ba 00060fe64
be87a209-2114-45b3-9d5a-86d 00060fe64
4a8a74a6-e972-4069-b480-b dea1177b21f
12fb4958-bee2-4c89-8cf8-e dea1177b21f
如果它真的是随机的，那么拥有这些类似 UUID 的概率会相当低（见编辑），因为我们只考虑 450 万个条目。所以，虽然这个功能很好，但就没有碰撞而言，对我来说它似乎并不像理论上那么好。
编辑：
很多人似乎不理解这个答案，所以我要澄清一下我的观点：我知道相似之处“很小”，远非完全冲突。但是，我只是想将 Java 的 UUID.randomUUID() 与真正的随机数生成器进行比较，这是实际的问题。
在真正的随机数生成器中，最后一种情况发生的概率约为= 0.007%。因此，我认为我的结论成立。
此 wiki 文章 en.wikipedia.org/wiki/Birthday_problem 中解释了公式
于 2017-02-16T00:14:10.980 回答
0
一年多来，我们一直在我们的应用程序中使用 Java 的随机 UUID，而且非常广泛。但是我们从来没有遇到过碰撞。
于 2014-11-11T21:03:22.483 回答