硬核 - Java 随机数相关 API 的演进与思考（上1）

本系列将 Java 17 之前的随机数 API 以及 Java 17 之后的统一 API 都做了比较详细的说明，并且将随机数的特性以及实现思路也做了一些简单的分析，帮助大家明白为何会有这么多的随机数算法，以及他们的设计思路是什么。本系列会分为两篇，第一篇讲述 Java 随机数算法的演变思路以及底层原理与考量，之后介绍 Java 17 之前的随机算法 API 以及测试性能，第二篇详细分析 Java 17 之后的随机数生成器算法以及 API 和底层实现类以及他们的属性，性能以及使用场景，如何选择随机算法等等，并对 Java 的随机数对于 Java 的一些未来特性的适用进行展望

这是第一篇。

如何生成随机数

我们一般使用随机数生成器的时候，都认为随机数生成器（Pseudo Random Number Generator， PRNG）是一个黑盒：

这个黑盒的产出，一般是一个数字。假设是一个 int 数字。这个结果可以转化成各种我们想要的类型，例如：如果我们想要的的其实是一个 long，那我们可以取两次，其中一次的结果作为高 32 位，另一次结果作为低 32 位，组成一个 long（boolean，byte，short，char 等等同理，取一次，取其中某几位作为结果）。如果我们想要的是一个浮点型数字，那么我们可以根据 IEEE 标准组合多次取随机 int 然后取其中某几位组合成浮点型数字的整数位以及小数位。

如果要限制范围，最简单的方式是将结果取余 + 偏移实现。例如我们想取范围在 1 ~ 100 之间，那么我们就将结果先对 99 取余，然后取绝对值，然后 +1 即可。当然，由于取余操作是一个性能消耗比较高的操作，最简单的优化即检查这个数字 N 与 N-1 取与运算，如果等于 0 即这个书是 2 的 n 次方（2 的 n 次方 2 进制表示一定是 100000 这样的，减去 1 之后 为 011111，取与肯定是 0）；对于 2 的 n 次方取余相当于对 2 的 n 次方减一取与运算。这是一个简单的优化， 实际的优化要比这个复杂多。

初始化这个黑盒的时候，一般采用一个 SEED 进行初始化，这个 SEED 的来源可能多种多样，这个我们先按下不表，先来看一些这个黑盒中的一些算法。

线性同余算法

首先是最常见的随机数算法：线性同余（Linear Congruential Generator）。即根据当前 Seed 乘以一个系数 A，然后加上一个偏移 B，最后按照 C 进行取余（限制整体在一定范围内，这样才能选择出合适的 A 和 B，为什么要这么做后面会说），得出随机数，然后这个随机数作为下次随机的种子，即：

X(n+1) = ( A * X(n) + B ) % C

这种算法的优势在于，实现简单，并且性能算是比较好的。 A，B 取值必须精挑细算，让在 C 范围内的所有数字都是等可能的出现的。例如一个极端的例子就是 A = 2， B = 2， C = 10，那么 1，3，5，7，9 这些奇数在后续都不可能出现。为了能计算出一个合适的 A 和 B，要限制 C 在一个比较可控的范围内。一般为了计算效率，将 C 限制为 2 的 n 次方。这样取余运算就可以优化为取与运算。不过好在，数学大师们已经将这些值（也就是魔法数）找到了，我们直接用就好了。

这种算法生成的随机序列，是确定的，例如 X 下一个是 Y， Y 下一个是 Z，这可以理解成一个确定环（loop）。

这个环的大小，即 Period。由于 Period 足够大，初始 SEED 一般也是每次不一样的，这样近似做到了随机。但是，假设我们需要多个随机数生成器的时候，就比较麻烦了，因为我们虽然能保证每个随机生成器的初始 SEED 不一样，但是在这种算法下，无法保证某个随机数生成器的初始 SEED 就是另一个随机数生成器初始 SEED 的下一个（或者很短步骤内的） SEED。举个例子，假设某个随机数生成器的初始 SEED 是 X，另一个是 Z，虽然 X 和 Z 可能看上去差距很大，但是他们在这个算法的随机序列中仅隔了一个 Y。这样的不同的随机数生成器，效果不好。

那么如何能保证不同的随机数生成器之间间隔比较大呢？也就是，我们能通过简单计算（而不是计算 100w 次从而调到 100w 次之后的随机数）直接使另一个随机数生成器的初始 SEED 与当前这个的初始 SEED，间隔一个比较大的数，这种性质叫做可跳跃性。 基于线性反馈移位寄存器算法的 Xoshiro 算法给我们提供了一种可跳跃的随机数算法。

线性反馈移位寄存器算法

线性反馈移位寄存器（Linear feedback shift register，LFSR）是指给定前一状态的输出，将该输出的线性函数再用作输入的移位寄存器。异或运算是最常见的单比特线性函数：对寄存器的某些位进行异或操作后作为输入，再对寄存器中的每个 bit 进行整体移位。

但是如何选择这些 Bit，是一门学问，目前比较常见的实现是 XorShift 算法以及在此基础上进一步优化的 Xoshiro 的相关算法。Xoshiro 算法是一种比较新的优化随机数算法，计算很简单并且性能优异。同时实现了可跳跃性。

这种算法是可跳跃的。假设我们要生成两个差距比较大的随机数生成器，我们可以使用一个随机初始 SEED 创建一个随机数生成器，然后利用算法的跳跃操作，直接生成一个间隔比较大的 SEED 作为另一个随机数生成器的初始 SEED。

还有一点比较有意思的是，线性同余算法并不可逆，我们只能通过 X(n) 推出 X(n + 1)，而不能根据 X(n + 1) 直接推出 X(n)。这个操作对应的业务例如随机播放歌单，上一首下一首，我们不需要记录整个歌单，而是仅根据当前的随机数就能知道。线性反馈移位寄存器算法能实现可逆。

线性反馈移位寄存器算法在生成不同的随机序列生成器也有局限性，即它们还是来自于同一个环，即使通过跳跃操作让不同的随机数生成器都间隔开了，但是如果压力不够均衡，随着时间的推移，它们还是有可能 SEED，又变成一样的了。那么有没有那种能生成不同随机序列环的随机算法呢？

DotMix 算法

DotMix 算法提供了另一种思路，即给定一个初始 SEED，设置一个固定步长 M，每次随机，将这个 SEED 加上步长 M，经过一个 HASH 函数，将这个值散列映射到一个 HASH 值：

X(n+1) = HASH(X(n) + M)

这个算法对于 HASH 算法的要求比较高，重点要求 HASH 算法针对输入的一点改变则造成输出大幅度改变。基于 DotMix 算法的 SplitMix 算法使用的即 MurMurHash3 算法，这个即 Java 8 引入的 SplittableRandom 的底层原理。

这种算法好在，我们很容易能明确两个不同参数的随机生成器他们的生成序列是不同的，例如一个生成的随机序列是 1，4，3，7，... 另一个生成的是 1，5，3，2。这点正是线性同余算法无法做到的，他的序列无论怎么修改 SEED 也是确定的，而我们有不能随意更改算法中的 A、B、C 的值，因为可能会导致无法遍历到所有数字，这点之前已经说过了。Xoshiro 也是同理。而 SplitMix 算法不用担心，我们指定不同的 SEED 以及不同的步长 M 就可以保证生成的序列是不同的。这种可以生成不同序列的性质，称为可拆分性

这也是 SplittableRandom 比 Random （Random 基于线性同余）更适合多线程的原因：

• 假设多线程使用同一个 Random，保证了序列的随机性，但是有 CompareAndSet 新 seed 的性能损失。
• 假设每个线程使用 SEED 相同的 Random，则每个线程生成的随机序列相同。
• 假设每个线程使用 SEED 不相同的 Random，但是我们不能保证一个 Random 的 SEED 是否是另一个 Random SEED 的下一个结果（或者是很短步长以内的结果），这种情况下如果线程压力不均匀（线程池在比较闲的时候，其实只有一部分线程在工作，这些线程很可能他们私有的 Random 来到和其他线程同一个 SEED 的位置），某些线程也会有相同的随机序列。

使用 SplittableRandom 只要直接使用接口 split 就能给不同线程分配一个参数不同的 SplittableRandom ，并且参数不同基本就可以保证生成不了相同序列。

思考：我们如何生成 Period 大于生成数字容量的随机序列呢？

最简单的做法，我们将两个 Period 等于容量的序列通过轮询合并在一起，这样就得到了 Period = 容量 + 容量 的序列：

我们还可以直接记录两个序列的结果，然后将两个序列的结果用某种运算，例如异或或者散列操作拼到一起。这样，Period = 容量 * 容量。

如果我们想扩展更多，都可以通过以上办法拼接。用一定的操作拼接不同算法的序列，我们可以得到每种算法的随机优势。 Java 17 引入的 LXM 算法就是一个例子。

LXM 算法

这是在 Java 17 中引入的算法 LXM 算法（L 即线性同余，X 即 Xoshiro，M 即 MurMurHash）的实现较为简单，结合线性同余算法和 Xoshiro 算法，之后通过 MurMurHash 散列，例如：

• L34X64M：即使用一个 32 位的数字保存线性同余的结果，两个 32 位的数字保存 Xoshiro 算法的结果，使用 MurMurHash 散列合并这些结果到一个 64 位数字。
• L128X256M：即使用两个 64 位的数字保存线性同余的结果，4 个 64 位的数字保存 Xoshiro 算法的结果，使用 MurMurHash 散列合并这些结果到一个 64 位数字。

LXM 算法通过 MurMurhash 实现了分割性，没有保留 Xoshiro 的跳跃性。