java的UUID.randomUUID有多好？
我知道随机UUID在理论上具有非常非常非常低的碰撞概率,但我想知道,在实践中,Java 5 randomUUID()在没有碰撞方面有多好？有没有人有经验可以分享？
Mic*_*rdt 164
UUID使用java.security.SecureRandom,应该是"密码强".虽然未指定实际实现,并且JVM之间可能有所不同(意味着所做的任何具体语句仅对一个特定JVM有效),但它确实要求输出必须通过统计随机数生成器测试.
实现总是可能包含破坏所有这些的微妙错误(请参阅OpenSSH密钥生成错误),但我认为没有任何具体的理由担心Java UUID的随机性.
- *"实施总是有可能包含微妙的错误..."* - 或(戴上锡箔帽)......故意微妙的缺陷.<:-) (33认同)
- 密码强度与碰撞问题完全无关. (22认同)
- @osa:不产生碰撞(超过完全随机性的预期)几乎是RNG的最低质量要求,而加密强度最高.换句话说,加密强RNG*绝对*不会产生比预期更多的碰撞. (13认同)
- 但是,如果你在https://blogs.vmware.com/cto/the-amazing-vm-recordreplay-feature-in-vmware-workstation-6/中运行一个JVM来生成UUID,那么可能会有用. ,你可能会遇到很多很多碰撞.所有软件RNG都是PRNG,它们最终只能与它们的熵源一样好; 两个以相同方式播种的PRNG也会表现相同,并且经常会出现一致的,完全重复的服务器设置和启动过程. (3认同)
she*_*eki 111
维基百科有一个非常好的答案 http://en.wikipedia.org/wiki/Universally_unique_identifier#Collisions
需要生成的随机版本4 UUID的数量为至少一次碰撞的概率为50%是2.71 quintillion,计算如下:
...
这个数字相当于大约85年每秒产生10亿UUID,包含这么多UUID的文件,每个UUID 16字节,大约45艾字节,比目前存在的最大数据库大很多倍,它们都在数百PB的数量级.
...
因此,为了有十亿分之一的重复机会,必须生成103万亿版本的4UUID.
- 我还要从该页面引用"如果地球上每个人拥有6亿UUID,那么一次重复的概率约为50%." (54认同)
- 这仅适用于真正的随机性,而不适用于像javas UUID这样的伪随机数. (22认同)
- 这不回答问题.问题是Java的"UUID.randomUUID()"中随机性的质量,而不是给定完美随机数生成器的理论机会. (12认同)
- @Markus:完全错了.良好的伪随机RNG(尤其是密码强的RNG)的碰撞概率与"真实"随机性没有什么不同. (9认同)
- @Eric - 我认为你有责任支持你的断言.FWIW,我能想到的唯一情况是4型UUID会更频繁地发生碰撞,概率理论认为它们应该是:1)加密随机数的不良来源,或者2)已被入侵的UUID库. (6认同)
Ste*_*n C 68
有没有人有经验可以分享？
有2^122用于4型UUID可能的值.(规范说你输入的类型为2位,版本号又输了4位.)
假设您每秒产生100万个随机UUID,那么在您的生命中发生重复的可能性将会非常小.要检测重复,您必须解决每秒比较100万个新UUID与您之前生成的所有UUID 1的问题!
任何人在现实生活中经历(即实际注意到)重复的机会甚至小于消失的小......因为寻找碰撞的实际困难.
当然,您通常会使用伪随机数生成器,而不是真正随机数的源.但我认为,我们可以相信,如果你正在使用你的加密强度随机数的可信供应商,那么它就会被加密强度,并重复的概率是相同的理想(不带偏见的)随机数发生器.
但是,如果您使用带有"损坏"加密随机数生成器的JVM,则所有投注均已关闭.(这可能包括某些系统上"熵短缺"问题的一些解决方法.或者有人在您的系统或上游对您的JRE进行修改的可能性.)
1 - 假设您使用了匿名评论者提出的"某种二进制btree",每个UUID将需要O(NlogN)一些RAM内存来表示N不同的UUID,假设低密度和比特的随机分布.现在乘以1,000,000以及您要运行实验的秒数.我认为测试高质量RNG碰撞所需的时间长度并不实用.甚至没有(假设的)聪明的表示.
- "(为了检测重复,您必须解决每秒比较100万个新UUID与您之前生成的所有UUID的问题!)" - 假设您已将某些UUID存储在某些UUID中,该部分相对简单一种二叉树结构,它只是每个新的uuid一棵树下降.您不需要将它与所有先前生成的uuid进行实际比较. (4认同)
sfu*_*ger 20
我不是专家,但我认为多年来有足够聪明的人看着Java的随机数生成器.因此,我还假设随机UUID是好的.因此,您应该确实具有理论冲突概率(对于所有可能的UUID ,大约为1:3×10 ^ 38.是否有人知道这对于随机UUID的变化情况如何？是1/(16*4)上述吗？)
根据我的实际经验,到目前为止我从未见过任何碰撞.我得到第一个胡子的那天,我可能已经长了一个令人惊讶的长胡子;)
- 来自维基百科:...换句话说,只有在接下来的100年中每秒产生10亿UUID之后,创建一个副本的概率大约为50%. (10认同)
rgo*_*ers 11
在前雇主,我们有一个包含随机uuid的独特列.我们在部署后的第一周发生了碰撞.当然,赔率很低但不是零.这就是Log4j 2包含UuidUtil.getTimeBasedUuid的原因.只要您在单个服务器上生成的UUID /毫秒数不超过10,000 UUID,它将生成8,925年唯一的UUID.
- 是。但问题是询问随机（即4型）UUID。 (2认同)
- （这次碰撞很可能是由于 PRNG 播种的随机性来源被破坏。我想这可能是纯粹的偶然。） (2认同)
小智 9
UUID的原始生成方案是将UUID版本与生成UUID的计算机的MAC地址连接起来,并且自西方采用公历以来,其间隔数为100纳秒.通过表示空间中的单个点(计算机)和时间(间隔的数量),值中发生碰撞的可能性实际上为零.
许多答案讨论了为达到50%的碰撞几率而必须生成多少UUID.但是,对于必须(几乎)不可能发生碰撞的应用,50%,25%甚至1%的碰撞几率毫无价值.
程序员是否经常将可能发生的事件视为"不可能"的其他事件？
当我们将数据写入磁盘或内存并再次读回时,我们理所当然地认为数据是正确的.我们依靠设备的纠错来检测任何损坏.但是,未检测到错误的可能性实际上在2到50左右.
将类似标准应用于随机UUID是否有意义？如果你这样做,你会发现在大约1000亿随机UUID(2 36.5)的集合中可能发生"不可能"的碰撞.
这是一个天文数字,但是在国家医疗保健系统中逐项计费或在大量设备上记录高频传感器数据等应用肯定会遇到这些限制.如果您正在编写下一个Hitchhiker银河系指南,请不要尝试为每篇文章分配UUID!
由于大多数答案都集中在理论上，我认为我可以通过进行实际测试来为讨论添加一些内容。在我的数据库中，我使用 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 中解释了公式
- 这不是真的。即使在 4.5M uuid 上使用真正的随机数生成器，也会出现这些相似之处。您提供的 UUID 之间的相似性很小而且很远，距离完全碰撞还很远。 (9认同)
- 你的期望是什么？相似不相同，不是吗？ (2认同)
- 您已匹配 11 个*十六进制*数字，即 16^11 或 2^44。这表明在 450 万次试验中发生碰撞的概率为 62.5%。1 - e^(-2^44.2/2^45) (2认同)
| 归档时间： |
|
| 查看次数： |
163453 次 |
| 最近记录： |