密码安全的随机数生成器生成相同的uuid的几率是否足够小，您无需检查唯一性？ [英] Are the odds of a cryptographically secure random number generator generating the same uuid small enough that you do not need to check for uniqueness?

问题描述

我正在使用长度为20的

其中 n （ p ; H ）是您必须选择的最少样本数，以便找到概率至少为 p ，给定的 H 可能的输出具有相等的概率。

同一篇文章还提供了可以使用的Python源代码计算此值：

  from math import log1p，sqrt 
 
 def生日（probability_exponent，位）：
概率=10。**概率_指数
输出=2。**位
返回sqrt（2。 *输出* -log1p（-概率））
  

因此，如果您要生成20个字节的UUID（ 160位）的随机数据，您如何确定不会发生冲突？假设您希望发生碰撞的概率小于五分之一（10 ^–18 ）：

 >>生日（-18,160）
 1709679290002018.5 
  

这意味着在生成约1.7万亿个UUID和20个每个字节的随机数据中，两个UUID相同的概率只有五分之一，即五分之一。

基本上，20个字节就足够了。 / p>

I'm using this with a length of 20 for uuid. Is it common practice to not check if the uuid generated has not been used already if it's used for a persistent unique value?

Or is it best practice to verify it's not already being used by some part of your application if it's essential to retain uniqueness.

解决方案

You can calculate the probability of a collision using this formula from Wikipedia::

     

where n(p; H) is the smallest number of samples you have to choose in order to find a collision with a probability of at least p, given H possible outputs with equal probability.

The same article also provides Python source code that you can use to calculate this value:

from math import log1p, sqrt

def birthday(probability_exponent, bits):
    probability = 10. ** probability_exponent
    outputs     =  2. ** bits
    return sqrt(2. * outputs * -log1p(-probability))

So if you're generating UUIDs with 20 bytes (160 bits) of random data, how sure can you be that there won't be any collisions? Let's suppose you want there to be a probability of less than one in a quintillion (10^–18) that a collision will occur:

>>> birthday(-18,160)
1709679290002018.5

This means that after generating about 1.7 quadrillion UUIDs with 20 bytes of random data each, there is only a one in 1 a quintillion chance that two of these UUIDs will be the same.

Basically, 20 bytes is perfectly adequate.

这篇关于密码安全的随机数生成器生成相同的uuid的几率是否足够小，您无需检查唯一性？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！