我知道发生冲突的可能性很小，但是如果我生成了一批 1000 个 GUID（例如），是否可以安全地假设它们都是唯一的以保存对每个 GUID 的测试？
奖金问题
测试 GUID 唯一性的最佳方法？布隆过滤器可能吗？
问问题
52991 次
7 回答
373
是的你可以。由于 GUID 的长度为 128 位，诚然存在冲突的微小可能性——但“分钟”这个词还远远不够强大。有如此多的 GUID，如果您随机生成数万亿个 GUID，那么您被陨石击中的可能性仍然高于一次碰撞（来自Wikipedia）。如果您不是随机生成它们，而是使用例如MAC 地址和时间戳算法，那么它们也将是唯一的，因为 MAC 地址在计算机中是唯一的，而时间戳在您的计算机上是唯一的计算机。
编辑 1：要回答您的奖励问题，测试一组 GUID 的唯一性的最佳方法是假设它们都是唯一的。为什么？因为，鉴于您正在生成的 GUID 的数量，GUID 碰撞的几率小于宇宙射线在您的计算机内存中翻转一点并搞砸您所关心的任何“准确”算法给出的答案的几率跑步。（有关数学，请参阅此 StackOverflow 答案。）
那里有大量的 GUID。引用道格拉斯·亚当斯的《银河系漫游指南》：
“太空，”它说，“很大。真的很大。你简直不会相信它有多么大得令人难以置信。我的意思是，你可能认为通往化学家的道路还有很长的路要走，但这对太空来说只是小菜一碟， 听…”
并且由于宇宙中大约有 7×10 22颗恒星，并且不到 2 128个GUID，那么每颗恒星大约有 4.86×10 15 ——几乎是五万亿——的 GUID。如果这些恒星中的每一颗都拥有像我们这样人口众多的世界，那么在每一颗恒星周围，每个曾经生活过的人类或外星人都将有权获得超过四万五千个 GUID。对于宇宙中每颗恒星的历史上的每一个人。GUID 空间与整个宇宙的大小处于同一水平。您无需担心。
（编辑 2：反思这一点：哇。我自己还没有意识到这意味着什么。GUID 空间大得难以理解。我有点敬畏它。）
于 2010-06-04T20:38:10.747 回答
44
简短的回答：出于实际目的，是的。
但是，您必须考虑生日悖论！
我计算了一些有代表性的碰撞概率。使用Wikipedia 文章中指定的 122 位 UUID，如果您至少生成2.71492e18UUID，则冲突概率为 1/2。使用 10^19 个 UUID，概率为 0.999918。使用 10^17 个 UUID，0.000939953。
可以在 Wikipedia 上找到一些用于比较的数字。因此，您可以安全地为每个活过的人类、可观测宇宙中的每个星系、海洋中的每条鱼以及地球上的每只蚂蚁分配一个 UUID。然而，如果你为人类一年生产的每个晶体管、地球上的每只昆虫、地球上的每一粒沙子、可观测宇宙中的每颗恒星或任何更大的东西生成一个 UUID，碰撞几乎是肯定的。
如果每秒生成 10 亿个 UUID，大约需要 36 年才能获得 10% 的碰撞概率。
最终，在人类历史进程中生成的一组 UUID 之间可能会发生冲突。尽管如此，碰撞的 UUID 将被用于相同目的的可能性非常小，因此在实践中没有问题。
于 2011-09-30T08:52:24.627 回答
8
维基百科上提供了对碰撞可能性的分析：http ://en.wikipedia.org/wiki/Uuid#Random_UUID_probability_of_duplicates
如链接中所述，这将受到随机数生成器的属性的影响。
GUID 生成器代码中也可能存在错误；虽然几率很低，但它们可能高于基于数学的碰撞几率。
布隆过滤器可能是合适的；它可以快速告诉您 GUID 是否唯一，但有可能会错误地指示碰撞。如果您一次测试一个批次，另一种方法是对批次进行排序并比较每个连续的元素。
于 2010-06-04T21:17:54.083 回答
5
一般来说，是的，可以安全地假设。
如果您的 GUID 生成器是真正随机的，那么 1000 个 GUID 内发生冲突的可能性非常小。
当然，这假设有一个好的 GUID 生成器。所以问题实际上是关于您对用于生成 GUID 的工具的信任程度以及它是否有自己的测试？
于 2010-06-04T20:33:43.267 回答
0
虽然可能发生碰撞，但可能性极小。（这里是数学。）可以安全地假设它们实际上是不同的。
于 2010-06-04T20:33:24.493 回答
0
于 2010-06-04T20:34:55.997 回答
0
这个话题让我想起了纸牌场景。也就是说，一副 52 张牌的排列方式有很多种，几乎可以肯定，从来没有 2 副正确洗过的牌的顺序是相同的。
如果你现在拿一副牌然后洗牌，这个顺序将是独一无二的，并且可能永远不会再出现在全人类中。事实上，安排 52 种任何东西的潜在方法数量之多令人难以想象，以至于任何 2 个套牌发生相同顺序的可能性几乎为零。
在这个有 40 个洗牌的套牌并想确定它们都是独一无二的例子中，其中 2 个是相同的并非不可能，但如果你能够每 10 次洗牌一次所有套牌，这很可能不会发生一秒钟，你就开始了宇宙的诞生。
于 2021-03-25T12:48:17.940 回答