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


当前回答

Go to the cryogenics lab in the New York City. Freeze yourself for (roughly) 1990 years. Get a job at Planet Express. Buy a brand-new CPU. Build a computer, run the program, and place it in the safe place with an pseudo-perpetual motion machine like the doomsday machine. Wait until the time machine is invented. Jump to the future using the time machine. If you bought 1YHz 128bit CPU, go to 3,938,453,320 days 20 hours 15 minutes 38 seconds 463 ms 463 μs 374 ns 607 ps after when you started to run the program. ...? PROFIT!!!

... 即使你的1YHz CPU是1GHz CPU的1,000,000,000,000,000倍(如果你更喜欢使用二进制前缀,则为1,125,899,906,842,624倍),也至少需要10,783,127年。

因此,与其等着计算结束,不如去喂那些因为其他n只鸽子夺走了它们的家而失去家园的鸽子。:(

或者,你可以等到128位量子计算机被发明出来。然后,您可以通过在合理的时间内(可能)使用您的程序来证明GUID不是唯一的。

其他回答

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

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

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

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

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

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

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

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

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

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

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

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

如果你想在代码的许多地方检查guid的唯一性,你可以使用一个漂亮的小扩展方法。

internal static class GuidExt
{
    public static bool IsUnique(this Guid guid)
    {
        while (guid != Guid.NewGuid())
        { }
        return false;
    }
}

要调用它,只需调用Guid。每当你生成一个新的guid…

Guid g = Guid.NewGuid();
if (!g.IsUnique())
{
    throw new GuidIsNotUniqueException();
}

...见鬼,我甚至建议打电话两次,以确保它在第一轮就得到了正确的答案。

Kai,我提供了一个程序,将做什么你想使用线程。它是根据以下条款授权的:您必须向我支付每小时每CPU内核0.0001美元的费用。费用在每个日历月的月底支付。请联系我的贝宝账户详细信息在您最早的方便。

using System;
using System.Collections.Generic;
using System.Linq;

namespace GuidCollisionDetector
{
    class Program
    {
        static void Main(string[] args)
        {
            //var reserveSomeRam = new byte[1024 * 1024 * 100];     // This indeed has no effect.

            Console.WriteLine("{0:u} - Building a bigHeapOGuids.", DateTime.Now);
            // Fill up memory with guids.
            var bigHeapOGuids = new HashSet<Guid>();
            try
            {
                do
                {
                    bigHeapOGuids.Add(Guid.NewGuid());
                } while (true);
            }
            catch (OutOfMemoryException)
            {
                // Release the ram we allocated up front.
                // Actually, these are pointless too.
                //GC.KeepAlive(reserveSomeRam);
                //GC.Collect();
            }
            Console.WriteLine("{0:u} - Built bigHeapOGuids, contains {1} of them.", DateTime.Now, bigHeapOGuids.LongCount());


            // Spool up some threads to keep checking if there's a match.
            // Keep running until the heat death of the universe.
            for (long k = 0; k < Int64.MaxValue; k++)
            {
                for (long j = 0; j < Int64.MaxValue; j++)
                {
                    Console.WriteLine("{0:u} - Looking for collisions with {1} thread(s)....", DateTime.Now, Environment.ProcessorCount);
                    System.Threading.Tasks.Parallel.For(0, Int32.MaxValue, (i) =>
                    {
                        if (bigHeapOGuids.Contains(Guid.NewGuid()))
                            throw new ApplicationException("Guids collided! Oh my gosh!");
                    }
                    );
                    Console.WriteLine("{0:u} - That was another {1} attempts without a collision.", DateTime.Now, ((long)Int32.MaxValue) * Environment.ProcessorCount);
                }
            }
            Console.WriteLine("Umm... why hasn't the universe ended yet?");
        }
    }
}

PS:我想试试并行扩展库。这很简单。

使用OutOfMemoryException作为控制流感觉是错误的。

EDIT

看来这还能吸引选票。所以我已经修复了GC.KeepAlive()问题。并将其更改为与c# 4一起运行。

澄清一下我的支持条款:支持只在2010年2月28日有效。请使用时间机器仅在当天提出支持请求。

编辑2 与往常一样,GC在管理内存方面比我做得更好;以前我自己做这件事的任何尝试都注定要失败。

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

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