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


当前回答

for(begin; begin<end; begin)
    Console.WriteLine(System.Guid.NewGuid().ToString());

你不增加begin,所以条件begin < end总是为真。

其他回答

Well if the running time of 83 billion years does not scare you, think that you will also need to store the generated GUIDs somewhere to check if you have a duplicate; storing 2^128 16-byte numbers would only require you to allocate 4951760157141521099596496896 terabytes of RAM upfront, so imagining you have a computer which could fit all that and that you somehow find a place to buy terabyte DIMMs at 10 grams each, combined they will weigh more than 8 Earth masses, so you can seriously shift it off the current orbit, before you even press "Run". Think twice!

你可以散列guid。这样,你就能更快地得到结果。

哦,当然,同时运行多个线程也是一个好主意,这样可以增加竞态条件在不同线程上两次生成相同GUID的机会。

GUID理论上是非唯一的。下面是你的证明:

GUID是一个128位的数字 如果不重用旧的guid,就不能生成2^128 + 1或更多的guid

然而,如果太阳的全部能量输出都用于完成这一任务,那么它在完成之前就会变冷。

GUID可以使用许多不同的策略生成,其中一些策略采取特殊措施来确保给定的机器不会两次生成相同的GUID。在特定算法中发现冲突将表明生成guid的特定方法不好,但不能证明关于guid的任何一般情况。

由于部分Guid生成是基于当前机器的时间,我的理论是获得一个副本Guid:

重新安装Windows 创建一个启动脚本,在Windows启动时将时间重置为2010-01-01 12:00:00。 就在启动脚本之后,它触发应用程序生成一个Guid。 克隆此Windows安装,以便排除后续启动过程中可能出现的任何细微差异。 用此映像重新映像硬盘驱动器,并启动几次机器。

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

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

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

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

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

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

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

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