使用Math.random获得相同值的可能性 [英] Probability of getting the same value using Math.random

问题描述

要求是当用户单击提交"按钮时向数据库发送唯一的ID.所以我正在使用Javascript Math.random 方法.我只想知道使用 Math.random 的相同数字的位数是多少?

解决方案

您遇到了一个叫做生日的问题:即使有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 = 1百万条记录，N = 2 ** 52，如果我做对的话，大约等于9000分之一.进一步假设Javascript的Math.random()确实在使用52位可用的随机性……这也是我不会做的假设.

The requirement is to send a unique id to database when user click on submit button. So I am using Javascript Math.random method. I just want to know what are the chances or possibility to get same number and what bit size of using Math.random.

解决方案

You're up against something called the birthday problem: even though there are 366 possible birthdays, when you get only 26 people in a room, the chance that some pair will have the same birthday is better than 50-50. In general, collisions are likely when your numbers approach the square root of the sample size (26 is in the neighborhood of the square root of 366).

Javascript's Math.random() has about 52 bits of randomness. Therefore, collisions should be likely as your record count approaches 2**26, which is about 60 million, a quite modest size for a database.

You should use a cryptographically-secure PRNG with at least 128 bits, preferably 256, to avoid collisions. There are probably ready-to-use UUID libraries for this available.

For an given number of keys k, and a keyspace N, the approximate odds of collision are:

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

So for k=1 million records, N=2**52, that comes to about 1 in 9000, if I did the math right. That's further assuming that Javascript's Math.random() is truly using the fill 52 bits of randomness available to it...that too is an assumption I wouldn't make.

这篇关于使用Math.random获得相同值的可能性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！