javascript - 使用 Math.random 获得相同值的概率

Question

要求是当用户点击提交按钮时向数据库发送一个唯一的 id。所以我正在使用 Javascript Math.random 方法。我只想知道获得相同数字的机会或可能性是多少，以及使用 Math.random 的位数是多少。

Answer 1

你遇到了一个叫做生日问题的问题:即使有 366 种可能的生日，当你在一个房间里只有 26 个人时，一些人生日相同的可能性要高于 50-50。一般来说，当您的数字接近样本量的平方根时(26 在 366 的平方根附近)，很可能会发生冲突。

Javascript 的 Math.random() 具有大约 52 位的随机性。因此，当您的记录数接近 2**26(大约 6000 万条)时，应该很可能发生冲突，这对于数据库来说是一个相当适中的大小。

您应该使用至少 128 位(最好是 256 位)的加密安全 PRNG，以避免冲突。可能有现成可用的 UUID 库。

对于给定数量的键 k 和键空间 N，碰撞的近似几率为:

1 - exp((-k * (k-1))/(2 * N))

所以对于 k=100 万条记录，N=2**52，如果我算对的话，这大约是 9000 分之一。这进一步假设 Javascript 的 Math.random() 确实使用了可用的填充 52 位随机性……这也是我不会做出的假设。