GUID不是唯一的简单证明

Question

GUID不是唯一的简单证明

323

我想证明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

107

作为一名软件开发者，如果用户向您反映“它不工作了”，您会怎么回答？ - JoshJordan

152

等待数万亿年。 - hobbs

67

因为这是我今天在网上看到最有趣的事情，所以点了个赞。 - jrockway

32

@jrockway - 哈哈。我发现关于这个问题的任何信息都基本上是错误的，让我看得越久就越好笑。 - tylerl

243

它只是全局唯一的，因此它只在我们的星球上是唯一的。如果您想要一个真正唯一的ID，您需要使用全局唯一标识符（UUID）。我猜您只对我们的宇宙内的唯一性感兴趣。 :-) - tvanfosson

显示剩余24条评论

30个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user180247 · Answer 1

数到2^128 - 雄心勃勃。

假设我们可以每秒在一台机器上计算2^32个ID - 这并不是太雄心勃勃，因为这甚至不到43亿个/秒。让我们把2^32台机器都用于这项任务。此外，让我们让2^32个文明各自将相同的资源用于此任务。

到目前为止，我们每秒可以计算2^96个ID，这意味着我们将计算2^32秒（略超过136年）。

现在，我们只需要让4,294,967,296个文明各自分配4,294,967,296台机器，每台机器能够每秒计算4,294,967,296个ID，纯粹地用于这项任务，持续接下来的136年左右 - 我建议我们立即开始这项重要任务 ;-)

- kibitzer · Answer 2

如果 830 亿年的运行时间并不让你感到害怕，那么请考虑一下，你还需要在某个地方存储生成的 GUID，以检查是否有重复；要存储 2^128 个 16 字节的数字，你需要预先分配 4951760157141521099596496896 TB 的内存。如果你有一台足够大的计算机，并且你能够找到一个地方以每个 10 克的价格购买到 TB DIMM，则它们的总重量将超过 8 个地球质量，这甚至在你按下“运行”按钮之前就已经足以使它严重偏离当前轨道。三思而后行！

- Nathan Taylor · Answer 3

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

你没有增加 begin 的值，所以条件 begin < end 总是为真。

- Matt Peterson · Answer 4

如果担心 GUID 冲突，我建议使用 ScottGuID 代替。

- MZB · Answer 5

你可能有理由认为生成 Guid 的算法并没有产生真正随机的数字，而是循环周期小于 2^128。

例如，RFC4122 方法用于派生 GUID，它固定了一些位的值。

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

对于较小的周期，可以使用哈希表的哈希（GUID）-> GUID，如果 GUID 不匹配，则进行替换（如果匹配则终止），这可能是一种方法。还要考虑仅在随机时间内进行替换。

最终，如果碰撞之间的最大周期足够长（且事先未知），则任何方法都只会产生如果存在碰撞，则找到碰撞的概率。

请注意，如果生成 Guid 的方法基于时钟（请参见 RFC），则可能无法确定是否存在碰撞，因为（a）您无法等待足够长的时间使时钟回绕，或者（b）您无法在一个时钟滴答中请求足够的 Guid 来强制发生碰撞。

或者，您可以显示 Guid 中的位之间的统计关系或位之间的相关性。这样的关系可能会使算法存在缺陷变得高度可能，而不必实际找到碰撞。

当然，如果您只想证明 Guid 可能会发生碰撞，那么数学证明而不是程序就是答案。

- Jason Goemaat · Answer 6

你是否必须确定是否有一个副本，或者只关心是否可能有一个副本。要确保你有两个生日相同的人，你需要366个人（不包括闰年）。为了有超过50％的机会有两个生日相同的人，你只需要23个人。这就是生日悖论。

如果你有32位，你只需要77,163个值就可以有超过50％的机会出现重复。试一试：

Random baseRandom = new Random(0);

int DuplicateIntegerTest(int interations)
{
    Random r = new Random(baseRandom.Next());
    int[] ints = new int[interations];
    for (int i = 0; i < ints.Length; i++)
    {
        ints[i] = r.Next();
    }
    Array.Sort(ints);
    for (int i = 1; i < ints.Length; i++)
    {
        if (ints[i] == ints[i - 1])
            return 1;
    }
    return 0;
}

void DoTest()
{
    baseRandom = new Random(0);
    int count = 0;
    int duplicates = 0;
    for (int i = 0; i < 1000; i++)
    {
        count++;
        duplicates += DuplicateIntegerTest(77163);
    }
    Console.WriteLine("{0} iterations had {1} with duplicates", count, duplicates);
}

1000 iterations had 737 with duplicates

现在128位是非常大的，因此您仍然需要大量的项目才能使碰撞几率降低。使用近似值，以下是为了给定的几率需要的记录数量：

80万亿亿次方，以便有1/1000的碰撞几率
2170亿亿次方，以获得50％的碰撞几率
3960亿亿次方，以获得90％的碰撞几率

每年发送约1E14封电子邮件，因此在这个级别上，您需要大约400,000年才能有90％的机会拥有两个具有相同GUID的电子邮件，但这与您需要运行计算机83亿倍于宇宙年龄或太阳变冷之前找到重复项的说法有很大不同。

- Dad · Answer 7

我不明白为什么没有人提到升级您的图形卡...... 如果您有一款高端的NVIDIA Quadro FX 4800或类似产品（192 CUDA核心），这将使计算速度更快......

当然，如果您能负担得起几个NVIDIA Qadro Plex 2200 S4（每个具有960个CUDA核心），那么这个计算就会非常快。也许NVIDIA愿意借给您一些作为“技术演示”的公关噱头？毕竟他们肯定希望参与这个“历史性”的计算过程中......

- AnthonyLambert · Answer 8

难道你们都忽略了一个重要的点吗？

我认为GUID是使用两个东西生成的，这使得它们被全球范围内视为唯一的机会相当高。其中一个是用您所在机器的MAC地址作为种子，另一个是使用生成时间加上一个随机数。

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

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

Tony

- Michael Stum · Answer 9

您可以对GUID进行哈希处理。这样，您应该会更快地得到结果。

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

- JiminP · Answer 10

前往纽约的低温实验室。
冷冻自己大约1990年。
在星球快递公司找一份工作。
购买一个全新的CPU。构建一台计算机，运行程序，并将其放置在像末日机器这样的准永动机保险柜中。
等待时光机的发明。
使用时光机跳到未来。如果你购买了1YHz 128位CPU，则需要跳到程序开始运行后3,938,453,320天20小时15分钟38.463秒463微秒374纳秒607皮秒。
...？
利润！！！

即使你拥有1YHz CPU，也需要至少10,783,127年才能完成计算，这意味着你可以喂那些失去家园的鸽子而不是等待计算结束。:(

或者，你可以等待128位量子计算机的发明。然后，你可以在合理的时间内使用你的程序证明GUID不是唯一的。