我想证明一个GUID在一个简单的测试程序中不是唯一的。 我原以为下面的代码会运行几个小时,但它不起作用。我该怎么做呢?

BigInteger begin = new BigInteger((long)0);
BigInteger end = new BigInteger("340282366920938463463374607431768211456",10);  //2^128
for(begin; begin<end; begin++)
  Console.WriteLine(System.Guid.NewGuid().ToString());

我用的是c#。


当前回答

如果生成的UUID的数量遵循摩尔定律,那么在可预见的未来永远用不完GUID的印象是错误的。

对于2^128个uuid,只需要18个月* Log2(2^128) ~= 192年,我们就会用完所有uuid。

而且我相信(虽然没有任何统计证据),自从UUID被大规模采用以来,在过去的几年里,我们生成UUID的速度比摩尔定律所规定的要快得多。换句话说,我们可能只有不到192年的时间来处理UUID危机,这比宇宙末日要快得多。

但由于我们肯定不会在2012年底之前将它们耗尽,我们将把这个问题留给其他物种来担心。

其他回答

这里也有一个解决方案:

int main()
{
  QUuid uuid;
  while ( (uuid = QUuid::createUuid()) != QUuid::createUuid() ) { }
  std::cout << "Aha! I've found one! " << qPrintable( uuid.toString() ) << std::endl;
}

注意:需要Qt,但我保证如果你让它运行足够长的时间,它可能会找到一个。

(注:实际上,现在我正在看它,可能有一些关于生成算法的东西可以防止两个随后生成的uuid发生碰撞——但我有点怀疑)。

对我来说. .单个核心生成UUIDv1所需的时间保证了它是唯一的。即使在多核情况下,如果UUID生成器一次只允许为特定资源生成一个UUID(请记住,多个资源可以完全利用相同的UUID,但不太可能,因为资源本身就是地址的一部分),那么您将拥有足够多的UUID,直到时间戳耗尽为止。在这一点上,我真的怀疑你会在乎。

这将持续不止几个小时。假设它以1 GHz的频率循环(实际上它不会—它会比1 GHz慢得多),它将运行10790283070806014188970年。大约是宇宙年龄的830亿倍。

假设摩尔定律成立,不运行这个程序,等几百年,在一台速度快数十亿倍的计算机上运行,会快得多。事实上,任何运行时间比CPU速度翻倍(大约18个月)要长的程序,如果您等待CPU速度提高并在运行之前购买一个新的CPU(除非您编写它是为了让它可以在新的硬件上挂起和恢复),那么它将更快地完成。

[Update:] As the comments below point out, newer MS GUIDs are V4 and do not use the MAC address as part of the GUID generation (I haven't seen any indication of a V5 implementation from MS though, so if anyone has a link confirming that let me know). WIth V4 though, time is still a factor though, and the odds against duplication of GUIDs remains so small as to be irrelevant for any practical usage. You certainly would not be likely to ever generate a duplicate GUID from just a single system test such as the OP was trying to do.

大多数答案都忽略了微软GUID实现的一个关键点。GUID的第一部分基于时间戳,另一部分基于网卡的MAC地址(如果没有安装网卡,则为随机数)。

如果我理解正确,这意味着复制GUID的唯一可靠方法是在多台机器上同时运行GUID生成,其中MAC地址是相同的,并且两个系统上的时钟在生成发生时处于相同的确切时间(时间戳是基于毫秒的,如果我理解正确的话)....即使如此,数字中还有很多其他的位是随机的,所以几率仍然很小。

对于所有实际目的,guid都是惟一的。

在“旧的新事物”博客上有一个关于MS GUID的很好的描述

假设你有理由相信生成guid的算法并不是生成真正的随机数,而是以周期<< 2^128为周期循环。

例如,RFC4122方法用于派生guid,该guid固定某些位的值。

循环的证明取决于周期的可能大小。

对于小周期,哈希表(GUID) -> GUID与碰撞替换 如果guid不匹配(如果匹配则终止)可能是一种方法。也可以考虑只在随机的一小部分时间内进行替换。

最终,如果两次碰撞之间的最大周期足够大(并且事先不知道),任何方法都只能产生一个概率,即如果碰撞存在的话,就会发现碰撞。

请注意,如果生成guid的方法是基于时钟的(参见RFC),那么可能无法确定是否存在冲突,因为(a)您无法等待足够长的时间让时钟转一圈,或者(b)您无法在一个时钟滴答内请求足够的guid来强制碰撞。

或者,您可以显示Guid中位之间的统计关系,或者Guid之间位的相关性。这样的关系可能使得算法很有可能是有缺陷的,而不一定能找到实际的碰撞。

当然,如果您只是想证明Guids可以碰撞,那么答案就是数学证明,而不是程序。