1

假设我通过使用 new Random() 实例化静态最终 Random 对象来使用相同的种子，是否可以通过在同一实例中调用 nextBytes 来获得相同的数字两次？

我知道对于任何给定的种子，可以确定所有可能的“随机”数字，它实际上更像是一个序列：

  synchronized protected int next(int bits) {
     seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
     return (int)(seed >>> (48 - bits));
}

所以基本上如果我有这个代码：

private static final Random random = new Random();

 public void doSomething() {
   for (int i=0; i < 1000000000; i++) {
      byte byteArray[] = new byte[8];
      random.nextBytes(byteArray)
   }
 }

nextBytes 在遍历所有可能生成的数字之前生成相同字节的可能性有多大？

在返回给定位的所有可能组合之前，这会返回相同的值吗？我猜是的，但这种情况多久发生一次？

4

3 回答 3

5

类Random使用具有非常大周期的线性同余生成器。它不会在很长时间内重复一个 int 值。对 8 字节数组的调用会nextBytes生成两个 int 值，并将每个值分成四个 8 位值以填充数组。

我相信连续调用nextBytes生成相同的值是不可能的。这意味着随机数生成器的周期为 2。文档指定了一个特定的行为，next这使得这不可能。（Random当然， 的子类可以有任何你喜欢的病态行为，但是 的实例java.util.Random会表现得很好。）

于 2011-06-24T02:43:13.080 回答
0

nextBytes 返回与其在前一次迭代中返回的值相同的值的概率与 nextBytes 返回任何特定随机 8 个字节的概率完全相同。

一个好的随机数生成器不会对将返回的位做出任何保证，除非这些位是随机的。有时希望生成器以随机顺序返回所有可能的值，但这通常不是随机生成器的目标。

于 2011-06-24T02:29:33.380 回答
0

上面表明不会出现重复相同值的答案似乎忘记了 Java.Random 的周期长度为 2^48。因此，nextInt() 完全有可能在遍历 RNG 周期内的所有值之前生成完全相同的整数。实际上是 2^16 次。

此外，由于整数被分成四部分，即使我们必须遍历所有整数，也可能（将）出现相同的字节。实际上，如果是这样的话，在我们遍历所有整数值之前，每个字节值都会出现 2^24 次。但是，我知道最初的问题涉及一个由八个字节组成的字节数组。对于这种情况，我们将在对 nextByte 调用 2^31（Java 的 Random 为 2^47）后得到相同的数组（因为我们需要两个整数）。

正如我之前所说，我们不需要遍历所有整数。

话虽如此，如果我们假设 nextInt() 返回的值是均匀分布的，那么在一系列 n 个样本中获得完全相同整数的概率大约为 1-((2^32 -1) / 2^32 ) ^(n(n-1)/2)。见http://en.wikipedia.org/wiki/Birthday_problem

我们需要抽取的样本数量有大于 50% 的概率有两个匹配的整数仅比 77000 多一点。如果我们现在假设我们改为统一抽取一个 2^64 的数字，或者两个 2^32 的整数 (对于 8 个字节），那么我们在 5*10^9 个样本后得到相同的概率，大约是 2^32。请注意，即使到那时，我们可以看到所有整数，这仍然比 Random 的周期短得多。真相可能介于两者之间。无论如何，概率非常低，但并非完全为零，正如上面的帖子所建议的那样。

我错过了什么吗？

于 2011-08-10T09:53:55.107 回答