node.js - 加密安全随机数生成器生成相同 uuid 的几率是否足够小，以至于您不需要检查唯一性？

Question

我正在使用this uuid 的长度为 20。如果生成的 uuid 用于持久唯一值，则通常的做法是不检查生成的 uuid 是否尚未使用？

或者，如果必须保持唯一性，最好的做法是验证它尚未被应用程序的某些部分使用。

Answer 1

您可以使用 this formula from Wikipedia: 计算碰撞概率:

     

其中 n(p; H) 是为了找到具有一定概率的碰撞而必须选择的最小样本数给定 H 个具有相同概率的可能输出，至少 p。

同一篇文章还提供了可用于计算该值的 Python 源代码:

from math import log1p, sqrt

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

因此，如果您使用 20 字节(160 位)随机数据生成 UUID，您如何确定不会发生任何冲突？假设您希望发生碰撞的概率小于五亿分之一 (10^–18):

>>> birthday(-18,160)
1709679290002018.5

这意味着在生成大约 1.7 万亿个 UUID(每个 UUID 包含 20 字节的随机数据)后，其中两个 UUID 相同的可能性只有五分之一。

基本上，20 字节就足够了。