使用Math.random获取相同值的概率

Question

使用Math.random获取相同值的概率

javascriptrandomprobabilityentropy

11

要求在用户点击提交按钮时向数据库发送唯一ID。因此，我使用了JavaScript的Math.random方法。我只想知道获取相同数字的机会或可能性有多大，并且使用Math.random需要什么位数。

- Jitender

5

不好的主意，不要这样做。点。你的数据库应该能够自动编号字段，所以请使用它。 - Matt Burland

我更喜欢用时间戳和表ID等生成自己的随机数。 - Rahul Winner

是的，我同意你的观点Matt。我们也可以包含一些用户信息。据我了解问题是关于从网页发送唯一数字到数据库的，所以我相信这种方法应该足够了。 - Rahul Winner

3

还有一件事需要考虑：你只考虑了意外碰撞的可能性，那如果是故意碰撞呢？也就是客户端故意发送相同的ID来规避你对API使用的某些限制。因此，生成ID应该留给后端处理。如果客户端未来需要这个ID进行某些操作，它应该在第一个请求中返回给他们，并且他们需要等待返回值。 - Matt Burland

1

为了让随机ID有合理的唯一性，至少需要128位，最好是256位。而且你需要一个加密安全的伪随机数生成器。Javascript的Math.random()在这两个方面都不符合要求。它只有56位，并且不安全。 - Lee Daniel Crocker

显示剩余2条评论

3个回答

3

不要这样做。相信（多个）客户端产生独特值是不可行的。

即使每个客户端都能保证生成唯一值，你仍可能会有两个客户端生成相同的值。由于大多数伪随机数生成器都是基于当前时间种子化的，随着用户数量的增加，这种情况会变得更加普遍。

如果你正在创建数据库记录，你的数据库应该提供类似于此的功能。大多数或所有SQL数据库都有自动增量概念，而许多NoSQL数据库也有相应的概念（例如，Mongo对ID有一个）。允许数据库处理这些数据可以提高性能（它可以设置索引并分配空间来处理这些ID），而且DB可以最终决定数据，因此可以保证ID唯一性。

如果没有这样的功能，那么你可以让服务器端生成一些唯一标识符（例如UUID）并使用它们。让服务器端处理并使用已知的良好算法（例如Type 4 UUID），可以保证足够的随机性，从而避免发生冲突。请注意，与顺序ID相比，使用UUIDs（除非你的数据库为它们提供了类型）将具有非常不同的索引性能。

- ssube

两个GUID的变化不是大约十亿分之一吗？ - Mouser

@Mouser 我认为比那要低得多，参考自http://en.wikipedia.org/wiki/Universally_unique_identifier#Random_UUID_probability_of_duplicates - ssube

不错，被陨石击中的概率实际上比我计算出碰撞的GUID还要高。 - Mouser

@Mouser：除非你的GUID生成算法存在严重缺陷，否则不会出现这种情况。 - Matt Burland

1

我相信使用crypto.getRandomValues可以缓解碰撞问题，支持的浏览器包括IE11+；它保证使用良好的熵源进行种子生成（因此不是当前时间）。但客户端随机值的真正问题在于它们容易被篡改。 - Retsam

我认为信任“任意客户端”比信任容易发生碰撞的随机数更为重要。当然，这取决于实际使用这些数字的情况，但不要忘记安全方面的影响。 - Bergi

0

我更喜欢使用时间戳、客户端或用户相关标识生成自己的随机数。

- Rahul Winner

为什么在数据库支持计数器、我们有UUID等工具的情况下，要使用带盐的随机数呢？ - ssube

这是关于从客户端向数据库发送一些唯一数字的问题。数据库计数器可能没有帮助。 - Rahul Winner

该问题指定了唯一性（客户无法保证），并且要求使用ID（数据库肯定有特殊的支持）。 - ssube

2

@RahulWinner 如果两个客户端在同一时间生成ID，或者单个客户端在计时器步骤（通常为10纳秒左右）内生成两个ID，使用时间戳会发生冲突。这种情况通常很容易发生。 - ssube

这就是为什么我在上面的评论中建议使用用户（客户端）相关信息的原因。请参考我的问题下方的评论。 - Rahul Winner

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Lee Daniel Crocker · Accepted Answer

你将会遇到生日问题：尽管有366种可能的生日，但只要在一个房间里聚集26个人，就有超过50%的概率会有两个人出生日期相同。通常情况下，当你的数量接近样本大小的平方根时（26接近于366的平方根），碰撞是很可能发生的。

Javascript的Math.random()函数大约有52位的随机性。因此，当你的记录数接近2 ** 26（大约为6000万）时，发生碰撞的可能性就会增加，对于数据库来说是一个相当适中的规模。

为了避免碰撞，应该使用至少128位、最好256位的加密安全伪随机数生成器（PRNG）。这方面可能已经有现成的UUID库可用。

对于给定数量的键和键空间，碰撞的近似概率如下：

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

因此，对于100万条记录，N=2 ** 52，如果我算得正确，这大约是1/9000的概率。这还假设Javascript的Math.random()函数真正利用了它可以获得的所有52位随机性......这也是我不会做出的假设。