GUID不是唯一的简单证明

小开

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

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

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

小开

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

你没有增加begin，所以条件begin < end始终为真。

小开

这将持续不止几个小时。假设它以1 GHz的频率循环(实际上它不会—它会比1 GHz慢得多)，它将运行10790283070806014188970年。大约是宇宙年龄的830亿倍。

假设摩尔定律成立，不运行这个程序会快得多，等待几百年，然后在速度快数十亿倍的计算机上运行它。事实上，任何运行时间比CPU速度翻倍(大约18个月)要长的程序，如果您等待CPU速度提高并在运行之前购买一个新的CPU(除非您编写它是为了让它可以在新的硬件上挂起和恢复)，那么它将更快地完成。

小开

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

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

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

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

小开

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

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

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

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

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

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

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

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

小开

你有没有试过用begin = begin + new BigInteger((long)1)代替begin++?

小开

当然guid也会发生碰撞。由于guid是128位的，只需生成它们的2^128 + 1，并且通过鸽子洞原理必须发生碰撞。

但是当我们说一个GUID是唯一的时，我们真正的意思是键空间非常大，实际上不可能意外地生成两次相同的GUID(假设我们是随机生成GUID)。

如果你随机生成一个n guid序列，那么至少发生一次碰撞的概率大约是p(n) = 1 - exp(-n^2 / 2 * 2^128)(这是生日问题，可能的生日的数量是2^128)。

   n     p(n)
2^30 1.69e-21
2^40 1.77e-15
2^50 1.86e-10
2^60 1.95e-03

为了使这些数字具体化，2^60 = 1.15e+18.;所以，如果你每秒生成10亿个guid，你将需要36年才能生成2^60个随机guid，即使这样，你发生碰撞的概率仍然是1.95e-03。在接下来的36年里，你更有可能是在你人生的某个阶段被谋杀了 (4.76e-03)，而不是发现一次碰撞。祝你好运。

小开

如果你担心独特性，你可以购买新的guid，这样你就可以扔掉旧的guid。如果你愿意，我可以把一些放在易趣网上。

小开

数到2^128，雄心勃勃。

让我们想象一下，每台机器每秒可以计算2^32个id——这不是那的野心，因为它甚至不到每秒43亿。让我们用2^32台机器来完成这个任务。此外，让2^32个文明各自投入相同的资源来完成任务。

到目前为止，我们每秒可以计数2^96个id，这意味着我们将计数2^32秒(136年多一点)。

现在，我们所需要的是获得4294967296个文明，每个文明都有4294967296台机器，每台机器每秒能计算4294967296个id，在未来136年左右的时间里，纯粹是为了这项任务——我建议我们现在就开始这项基本任务;-)

小开

最佳答案

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作为控制流感觉是错误的。

编辑

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

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

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

小开

如果你想在代码的许多地方检查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();
}

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

小开

你们都没抓住重点吗?

我认为guid是用两个东西生成的，这使得它们具有全局唯一性的几率相当高。一是它们以你所在机器的MAC地址作为种子，二是它们使用生成它们的时间加上一个随机数。

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

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

托尼

小开

你可以用量子bogosort算法的变体在O(1)时间内显示出来。

Guid g1 = Guid.NewGuid();
Guid g2 = Guid.NewGuid();
if(g1 != g2) Universe.Current.Destroy();

小开

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

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

小开

(更新:) 正如下面的评论所指出的，新的MS GUID是V4的，并且不使用MAC地址作为GUID生成的一部分(不过，我还没有看到MS的V5实现的任何迹象，所以如果有人有确认链接，请告诉我)。但是对于V4，时间仍然是一个因素，并且防止guid重复的几率非常小，以至于与任何实际使用无关。当然，您不可能仅仅从一个系统测试中生成一个重复的GUID，就像OP试图做的那样。

大多数答案都忽略了微软GUID实现的一个关键点。GUID的第一部分基于时间戳，另一部分基于网卡的MAC地址(如果没有安装网卡，则为随机数)。

如果我理解正确，这意味着复制GUID的唯一可靠方法是在多台机器上同时运行GUID生成，其中MAC地址是相同的，并且两个系统上的时钟在生成发生时处于相同的确切时间(时间戳是基于毫秒的，如果我理解正确的话)....即使如此，数字中还有很多其他的位是随机的，所以几率仍然很小。

对于所有实际目的，guid都是惟一的。

在“新旧事物”博客中有一个很好的MS GUID描述

小开

这个程序虽然有错误，但证明了GUID不是唯一的。那些试图证明相反情况的人没有抓住重点。这句话只是证明了一些GUID变体的弱实现。

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

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

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

小开

好吧，如果830亿年的运行时间还没有吓到你，那么你还需要将生成的guid存储在某个地方，以检查是否有一个副本;存储2^128个16字节的数字只需要你预先分配4951760157141521099596496896 tb的RAM，所以想象你有一个可以容纳所有这些的计算机，并且你以某种方式找到一个地方购买10克的tb内存，它们的重量将超过8个地球质量，所以你可以在你甚至按下“运行”之前，严重地改变它当前的轨道。三思而后行!

小开

我不明白为什么没人提到升级显卡…当然，如果你有一个高端的NVIDIA Quadro FX 4800或其他(192 CUDA核)，这将会更快…

当然，如果你能买得起一些NVIDIA Qadro Plex 2200 s4(每个960 CUDA内核)，这个计算将真的< em > < / em >尖叫。也许NVIDIA愿意借给你一些作为“技术演示”的公关噱头?

当然他们想要成为历史计算的一部分…

小开

如果GUID冲突是一个问题，我建议使用ScottGuID代替。

小开

就我个人而言，我认为“大爆炸”是由两个guid相撞引起的。

小开

在GUID生成代码中出现错误的几率比算法生成冲突的几率要高得多。在测试guid的代码中出现错误的可能性更大。放弃。

小开

guid是124位，因为4位保存版本号。

小开

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

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

小开

但是你必须一定你有一个副本，还是你只关心是否有一个副本。为了确保有两个人生日相同，你需要366个人(不包括闰年)。如果有超过50%的概率有两个人同一天生日，你只需要23个人。这是生日问题。

如果你有32位，你只需要77163个值就有超过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位已经很多了，所以你仍然在谈论大量的物品，但碰撞的几率很低。对于给定的概率，您需要使用近似值获得以下记录数:

碰撞发生的概率是1/1000
217亿亿亿，50%的几率发生碰撞
396亿亿，90%的碰撞概率

每年大约发送1E14封电子邮件，所以在这个水平上大约需要40万年，你才能有90%的机会拥有两个具有相同GUID的电子邮件，但这与说你需要运行宇宙年龄830亿倍的计算机或太阳变冷才能找到副本有很大不同。

小开

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

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

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

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

小开

对我来说. .单个核心生成UUIDv1所需的时间保证了它是唯一的。即使在多核情况下，如果UUID生成器一次只允许为特定资源生成一个UUID(请记住，多个资源可以完全利用相同的UUID，但不太可能，因为资源本身就是地址的一部分)，那么您将拥有足够多的UUID，直到时间戳耗尽为止。在这一点上，我真的怀疑你会在乎。

小开

这里也有一个解决方案:

int main()
{
QUuid uuid;
while ( (uuid = QUuid::createUuid()) != QUuid::createUuid() ) { }
std::cout << "Aha! I've found one! " << qPrintable( uuid.toString() ) << std::endl;
}

注意:需要Qt，但我保证如果你让它运行足够长的时间，它可能会找到一个。

(注:实际上，现在我正在看它，可能有一些关于生成算法的东西可以防止两个随后生成的uuid发生碰撞——但我有点怀疑)。

小开

去纽约的低温实验室。
把自己冷冻(大约)1990年。
在星球快递找份工作。
买一个全新的CPU。造一台电脑，运行程序，然后把它放在一个安全的地方用一个像末日机器一样的伪永动机。
等到时间机器被发明出来。
使用时间机器跳转到未来。如果你买了1YHz 128bit CPU，在你开始运行程序后，去3,938,453,320 days 20 hours 15 minutes 38 seconds 463 ms 463 μs 374 ns 607 ps。
……?
利润! !

．.．它至少需要10,783,127年，即使你有1YHz的CPU，它是1,000,000,000,000,000(或1,125,899,906,842,624，如果你喜欢使用二进制前缀)倍于1GHz CPU。

所以与其等着计算结束，不如去喂那些因为其他n鸽子拿走了它们的家而失去家的鸽子。：(

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

小开

不是在篝火上的p**在这里，但它确实发生了，是的，我理解你一直给这个家伙的玩笑，但GUID是唯一的，只是在原则上，我碰到这个线程，因为在WP7模拟器中有一个bug，这意味着每次它启动它给出相同的GUID第一次被调用!所以，理论上你不会有冲突，如果生成GUI有问题，那么你会得到副本

http://forums.create.msdn.com/forums/p/92086/597310.aspx#597310

小开

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