我想证明一个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变体的弱实现。

GUID在定义上不一定是唯一的,它在定义上是高度唯一的。你刚才精炼了高度的意思。根据版本、实现者(MS或其他)、虚拟机的使用等不同,您的定义会发生很大变化。(见前文链接)

你可以缩短你的128位表来证明你的观点。最好的解决方案是使用哈希公式来缩短重复的表,然后在哈希发生冲突时使用完整的值,并基于此重新生成一个GUID。如果从不同的位置运行,则将哈希/完整密钥对存储在一个中心位置。

Ps:如果目标只是生成x个不同的值,那么创建一个这个宽度的哈希表,并检查哈希值。

其他回答

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

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

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

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

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

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

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

所以你可能还要再等几十亿年,希望在我们所知道的宇宙结束之前,你能击中一个。

证明GUID不是唯一的唯一解决方案是建立一个World GUID池。每次在某个地方生成GUID时,都应该将其注册到组织。或者,我们可能包括一个标准化,所有GUID生成器都需要自动注册它,为此它需要一个活跃的互联网连接!

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

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

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

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

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

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

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

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