具有不同种子的Java Random实例是否真的产生不同的序列，还是它们在相同序列的不同位置开始?

Question

想象实例化两个具有不同种子的random, rA和rB。看看rA生成的第一个整数是什么。然后在rB上调用nextInt()，直到得到相同的整数。

groovy:000> rA = new Random()
===> java.util.Random@463b4ac8
groovy:000> rB = new Random(1)
===> java.util.Random@5644dc81
groovy:000> rA_0 = rA.nextInt()
===> -1458003306
groovy:000> rB_0 = rB.nextInt()
===> -1155869325
groovy:000> for (int rB_n = rB.nextInt(); rB_n != rA_0; rB_n = rB.nextInt());
===> null

是否可能这两个实例现在"同步"，也就是说，它们将无限向前产生相同的整数序列?

groovy:000> rA.nextInt()
===> 1701960179
groovy:000> rB.nextInt()
===> 1760857409
groovy:000> for (int rB_n = rB.nextInt(); rB_n != rA_0; rB_n = rB.nextInt());
===> null
groovy:000> rB.nextInt()
===> 614305687

所示的有限实验没有发现这样的序列碰撞，但很难知道这样的碰撞是否可以被发现。

换句话说，我们是在处理一个很长的序列，而种子决定我们从序列的哪里开始，还是可以依赖具有不同种子的随机实例来实际产生完全不同的数字序列?或者更糟的是，一些种子共享序列吗?(还是取决于Sally在哪个海岸卖贝壳?)

Answer 1

Java Random.next()(它是所有公共nextX()方法的基础)有义务遵循以下LCG方程:

(x * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1)

因此给定当前状态(x)，下一个状态完全确定。

所以假设这是一个"全循环"LCG(即迭代所有可能的值)，那么rB最终达到rA的起始状态一定是这样的。此时，其输出序列将与rA匹配。