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#。

当前回答

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在管理内存方面比我做得更好;以前我自己做这件事的任何尝试都注定要失败。

2009-11-10 04:23:25

其他回答

这里也有一个解决方案:

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的算法并不是生成真正的随机数，而是以周期<< 2^128为周期循环。

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

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

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

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

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

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

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

2009-11-10 01:33:46