简单certificateGUID不是唯一的
我想certificate一个简单的testing程序中的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＃。
凯，我提供了一个程序，将使用线程来做你想做的事情。 它是根据以下条款获得许可的：您必须为每个运行它的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作为控制stream只是感觉不对。
编辑
那么，这似乎仍然吸引了选票。 所以我修复了GC.KeepAlive（）问题。 并将其更改为使用C＃4运行。
并澄清我的支持条款：支持仅在28 / Feb / 2010。 请仅在当天使用时间机器提出支持请求。
编辑2一如既往，GC做的比我在内存pipe理方面做得更好; 以前的任何尝试都是注定要失败的。
这将会持续数小时以上。 假设它以1 GHz的频率循环（不会 – 这将会比这慢很多），它将运行10790283070806014188970年。 这比宇宙年龄长约830亿倍。
假设摩尔定律成立，那么不运行这个程序要快很多，等待几百年，然后在数十亿倍的计算机上运行。 实际上，如果你等到CPU速度提高，并且在运行之前购买一个新的CPU，那么任何运行时间比CPU速度翻倍（大约18个月）的程序都会更快完成（除非你编写它，可以暂停并在新的硬件上恢复）。
一个GUID在理论上是非唯一的。 这是你的certificate：
- GUID是一个128位的数字
- 无法重新使用旧的GUID，无法生成2 ^ 128 + 1或更多的GUID
然而，如果太阳的整个输出功率被指挥完成这个任务，它会在完成之前很长一段时间。
可以使用多种不同的策略来生成GUID，其中一些策略采取特殊的措施来保证给定的机器不会两次生成相同的GUID。 在一个特定的algorithm中发现碰撞会表明你的特定的GUID生成方法是不好的，但是一般来说并不能certificateGUID。
当然，GUID可能会发生碰撞。 由于GUID是128位的，只需要生成2^128 + 1的数据，并且按照原理就必须有碰撞。
但是当我们说GUID是唯一的时候，我们真正的意思是关键空间是如此之大，以至于无意中产生两次相同的GUID（假设我们随机产生GUID）实际上是不可能的。
如果随机生成一个n GUID序列，那么至less有一次碰撞的概率大概是p(n) = 1 - exp(-n^2 / 2 * 2^128) （这是生日问题 ，可能的生日是2^128 ）。
np(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 。 在你生命中的某个时候 （ 4.76e-03 ），你很可能会被谋杀，而不是在未来的36年里发现一个碰撞。 祝你好运。
如果你担心独特性，你可以随时购买新的GUID，这样你就可以扔掉旧的GUID。 如果你愿意，我会把一些东西放在eBay上。
就我个人而言，我认为这个“大爆炸”是两个GUID相撞造成的。
你可以在O（1）时间内用一个量子波动algorithm的变体来表明 。
Guid g1 = Guid.NewGuid(); Guid g2 = Guid.NewGuid(); if(g1 != g2) Universe.Current.Destroy();
任何两个GUID都可能是唯一的（不等于）。
看到这个SO条目 ，并从维基百科
尽pipe每个生成的GUID不能保证是唯一的，但是唯一键（2 ^ 128或3.4×10 ^ 38）的总数非常大，以致相同数字两次产生的概率非常小。 例如，考虑包含5×10 ^ 22星的可观测宇宙; 每颗恒星可以拥有6.8×10 ^ 15个通用唯一GUID。
所以可能你要等上十几亿年，希望你在宇宙之前击中了一个，因为我们知道它已经结束了。
[更新：] 下面的评论指出，更新的MS GUID是V4，不使用MAC地址作为GUID生成的一部分（我还没有看到从MS的V5实现的任何迹象，所以如果任何人有链接确认，让我知道）。 尽pipe如此，时间仍然是一个因素，而且重复GUID的可能性仍然很小，与任何实际的用法无关。 你当然不可能从一个单一的系统testing中产生一个重复的GUID，比如OP正在做的事情。
这些答案中的大多数都缺less关于微软的GUID实现的一个重要的观点。 GUID的第一部分基于时间戳，另一部分基于网卡的MAC地址（如果没有安装网卡，则为随机数）。
如果我正确地理解了这一点，则意味着复制GUID的唯一可靠方法是在MAC地址相同的多台机器上运行同时生成的GUID，并且在两台系统上的时钟处于同一时间的同一时间（如果我理解正确的话，时间戳是以毫秒为单位的）。即便如此，数字中还有很多是随机的，所以它的可能性还是很小。
对于所有的实际目的，GUID是普遍唯一的。
在“旧新事物”博客中 ，对MS GUID的描述非常好
这里有一个漂亮的小扩展方法，你可以使用，如果你想在代码中的许多地方检查guid的唯一性。
internal static class GuidExt { public static bool IsUnique(this Guid guid) { while (guid != Guid.NewGuid()) { } return false; } }
要调用它，只要在生成新的GUID时调用Guid.IsUnique …
Guid g = Guid.NewGuid(); if (!g.IsUnique()) { throw new GuidIsNotUniqueException(); }
…呃，我甚至build议两次调用它，以确保它在第一轮正确。
数到2 ^ 128 – 雄心勃勃。
让我们想象一下，每台机器每秒可以计算2 ^ 32个ID – 没那么大 ，因为它甚至不到每秒43亿个。 让我们把2 ^ 32的机器用于这个任务。 而且，让每个人得到2 ^ 32个文明，把相同的资源用于任务。
到目前为止，我们可以计算每秒2 ^ 96个ID，这意味着我们将计算2 ^ 32秒（有点超过136年）。
现在我们所需要的就是每个专用的4294967296台机器，每台机器能够计算4294967296个ID，完全是为了接下来的136年这个任务，我们需要的是4294967296个文明，我build议我们现在开始这个重要任务; – ）
那么如果830亿年的运行时间不会吓倒你，那么你也需要将生成的GUID存储在某处，以检查是否有重复; 存储2 ^ 128个16字节的数字只需要你预先分配4951760157141521099596496896兆兆字节的RAM，所以想象你有一台能适应这一切的计算机，并且你以某种方式find一个地方购买10克每个千兆字节的DIMM，结合起来超过8个地球的质量，所以你可以认真把它从当前的轨道，甚至在你按“运行”之前。 再想一想！
for(begin; begin<end; begin) Console.WriteLine(System.Guid.NewGuid().ToString());
你并没有增加begin所以条件begin < end始终是真的。
如果GUID冲突是一个问题，我会build议使用ScottGuID来代替。
大概你有理由相信制作Guids的algorithm不会产生真正的随机数，而是实际上是以<2 ^ 128的周期进行循环的。
例如RFC4122方法，用于派生固定某些位的值的GUID。
骑自行车的证据将取决于时间的可能的大小。
对于小的时间段，如果GUID不匹配（终止，如果它们是这样的话），散列表（GUID） – > GUID的散列表可能是一种方法。 考虑也只是做一个随机部分的时间更换。
最终，如果碰撞之间的最大周期足够大（并且事先不知道），那么任何方法只会产生一个存在碰撞的概率。
请注意，如果生成Guids的方法是基于时钟的（请参阅RFC），则可能无法确定是否存在冲突，因为（a）您无法等待时间足够长，或者（b）你不能在时钟周期内请求足够的Guid来强制冲突。
或者，您可能能够显示Guid中的位之间的统计关系，或Guid之间的位相关性。 这样的关系可能使得该algorithm很有可能是有缺陷的，而不一定能够find实际的碰撞。
当然，如果你只是想certificateGuids可以碰撞，那么mathcertificate而不是程序就是答案。
但是，你必须确保你有一个重复的，或者你只关心，如果可以重复。 为了确保你有两个同一个生日的人，你需要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比特是很多，所以你仍然在谈论大量的项目，仍然给你一个很小的碰撞机会。 对于给定的几率，使用近似值需要以下数量的logging：
- 发生碰撞事故的可能性为1/1000
- 发生碰撞的概率为50％，达21.7亿
- 发生碰撞的几率为90％，达到396亿
每年发送的电子邮件大约有1E14个，所以在这个级别大概要40万年，然后你有90％的机会拥有两个具有相同的GUID，但这与说你需要运行一台计算机有很大的不同。乘以宇宙的年龄，或在发现重复之前太阳会变冷。
我不明白为什么没有人提到升级你的显卡…当然，如果你有一个高端的NVIDIA Quadro FX 4800什么的（192 CUDA核心），这将会更快…
当然，如果你能买得起几块NVIDIA Qadro Plex 2200 S4（每块960个CUDA内核），这个计算结果真的会尖叫起来。 也许NVIDIA愿意借给你一些“技术示范”作为公关特技？
他们肯定希望成为这个历史性计算的一部分
你们不是都错过了一个重点吗？
我认为GUID是用两件事情来产生的，这两件事使得它们在全球范围内独一无二的可能性相当高。 一个是他们与您正在使用的机器的MAC地址播种，两个他们使用生成的时间加上一个随机数字。
因此，除非您在实际机器上运行它，并且在机器用来代表GUID中的时间的最短时间内运行所有猜测，否则无论您使用系统调用进行了多less次猜测，都不会生成相同的编号。
我想如果你知道一个GUID的实际方法实际上会缩短猜测的时间。
托尼
你可以散列GUID。 这样，你应该得到更快的结果。
哦，当然，同时运行多个线程也是一个好主意，这样你将增加竞争条件在不同线程上产生两次相同GUID的机会。
- 去纽约市的低温实验室。
- 冻结自己（大致）1990年。
- 在Planet Express找份工作。
- 买一个全新的CPU。 build立一台计算机，运行程序，并使用伪永动机（如末日机）将其安置在安全的地方。
- 等到时间机器发明了。
- 使用时间机器跳转到未来。 如果您购买了1YHz的128位CPU，请在
3,938,453,320 days 20 hours 15 minutes 38 seconds 463 ms 463 μs 374 ns 607 ps当您开始运行程序后3,938,453,320 days 20 hours 15 minutes 38 seconds 463 ms 463 μs 374 ns 607 ps。 - …？
- 利润！！！
…即使你有1兆赫的CPU是1,000,000,000,000,000 （或1,125,899,906,842,624如果你喜欢使用二进制前缀）时间比1GHz的CPU要快至less10, 10,783,127年。
因此，不要等待计算机完成，最好是喂鸽子，因为其他n只鸽子把它们带回家。 🙁
或者，你可以等到128位量子计算机发明。 那么你可以通过在合理的时间（也许）使用你的程序来certificateGUID不是唯一的。
GUID是124位，因为4位保存版本号。
您是否尝试过begin = begin + new BigInteger((long)1)来代替begin ++？
如果生成的UUID数量遵循摩尔定律，那么在可预见的未来永远不会用完GUID的印象是错误的。
使用2 ^ 128个UUID，只需要18个月* Log2（2 ^ 128）〜= 192年，在我们用完所有的UUID之前。
自从UUID被大量采用以来，我相信在过去的几年里（没有统计证据），我们产生UUID的速度正在以比摩尔定律更快的速度增长。 换句话说，我们可能还不到192年，直到我们不得不面对UUID危机，这要比宇宙的末日早得多。
但是由于我们肯定不会在2012年底之前将它们运行，所以我们会把它留给其他物种来担心这个问题。
GUID生成代码中的一个错误的可能性远高于生成冲突的algorithm的可能性。 代码中testingGUID的错误的可能性更大。 放弃。
不是在这里的篝火p p，但它确实发生了，是的，我明白你给这个家伙开玩笑，但GUID是唯一的原则上，我撞到这个线程，因为有一个错误在WP7模拟器中，这意味着每次启动时都会在第一次调用时发出相同的GUID！ 所以，在理论上你不能有任何冲突，如果有产生上述GUI的问题，那么你可以得到重复
http://forums.create.msdn.com/forums/p/92086/597310.aspx#597310
The program, albeit its errors, shows proof that a GUID is not unique. Those that try to prove the contrary are missing the point. This statement just proves the weak implementation of some of the GUID variations.
A GUID is not necessary unique by definition, it is highly unique by definition. You just refined the meaning of highly. Depending on the version, the implementator (MS or others), use of VM's, etc your definition of highly changes. (see link in earlier post)
You can shorten your 128 bit table to prove your point. The best solution is to use a hash formula to shorten your table with duplicates, and then use the full value once the hash collides and based on that re-generate a GUID. If running from different locations, you would be storing your hash/full key pairs in a central location.
Ps: If the goal is just to generate x number of different values, create a hash table of this width and just check on the hash value.
Since part of Guid generation is based on the current machine's time, my theory to get a duplicate Guid is:
- Perform a clean installation of Windows
- Create a startup script that resets the time to 2010-01-01 12:00:00 just as Windows boots up.
- Just after the startup script, it triggers your application to generate a Guid.
- Clone this Windows installation, so that you rule out any subtle differences that may occur in subsequent boot-ups.
- Re-image the hard drive with this image and boot-up the machine a few times.
For me.. the time it takes for a single core to generate a UUIDv1 guarantees it will be unique. Even in a multi core situation if the UUID generator only allows one UUID to be generated at a time for your specific resource (keep in mind that multiple resources can totally utilize the same UUIDs however unlikely since the resource inherently part of the address) then you will have more than enough UUIDs to last you until the timestamp burns out. At which point I really doubt you would care.
Here's a solution, too:
int main() { QUuid uuid; while ( (uuid = QUuid::createUuid()) != QUuid::createUuid() ) { } std::cout << "Aha! I've found one! " << qPrintable( uuid.toString() ) << std::endl; }
Note: requires Qt, but I guarantee that if you let it run long enough, it might find one.
(Note note: actually, now that I'm looking at it, there may be something about the generation algorithm that prevents two subsequently generated uuids that collide–but I kinda doubt it).
The only solution to prove GUIDs are not unique would be by having a World GUID Pool. Each time a GUID is generated somewhere, it should be registered to the organization. Or heck, we might include a standardization that all GUID generators needs to register it automatically and for that it needs an active internet connection!
