GUID不是唯一的简单证明

我想证明一个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#。

当前回答

当然guid也会发生碰撞。由于guid是128位的，只需生成其中的2^128 + 1个，根据鸽子洞原理，肯定会有碰撞。

但是当我们说一个GUID是唯一的时，我们真正的意思是键空间非常大，实际上不可能意外地生成两次相同的GUID(假设我们是随机生成GUID)。

如果随机生成n个guid序列，那么至少发生一次碰撞的概率大约是p(n) = 1 - exp(-n^2 / 2 * 2^128)(这是一个生日问题，可能的生日数量为2^128)。

   n     p(n)
2^30 1.69e-21
2^40 1.77e-15
2^50 1.86e-10
2^60 1.95e-03

为了使这些数字具体化，2^60 = 1.15e+18。所以，如果你每秒生成10亿个guid，你将需要36年才能生成2^60个随机guid，即使这样，你发生碰撞的概率仍然是1.95e-03。在接下来的36年里，你更有可能在生命中的某个时刻被谋杀(4.76e-03)，而不是发现一次碰撞。祝你好运。

2009-11-10 03:47:21

其他回答

这里也有一个解决方案:

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

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

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

2011-07-14 17:50:41

你们都没抓住重点吗?

我认为guid是用两个东西生成的，这使得它们具有全局唯一性的几率相当高。一是它们以你所在机器的MAC地址作为种子，二是它们使用生成它们的时间加上一个随机数。

因此，除非您在实际的机器上运行它，并在机器用来表示GUID中的时间的最短时间内运行您的所有猜测，否则无论您使用系统调用进行多少次猜测，都不会生成相同的数字。

我想如果您知道GUID的实际生成方式，实际上会大大缩短猜测的时间。

Tony

2009-11-10 16:04:33

任何两个guid都很可能是唯一的(不相等)。

看看这个SO条目，来自维基百科

而每个生成的GUID不是保证是唯一的，总数唯一键数(2^128或 3.4×10^38)是如此之大，以至于相同数字的概率为生成两次是非常小的。为例子,考虑可观测宇宙，其中包含约5×10^22 星星;每颗恒星都有可能 6.8×10^15个通用唯一的guid。