Random源码解析

发表于   |   分类于 ，   |   阅读次数   |   2,714 字   |   11 min

Random类的实例用于生成伪随机数流。此类使用 48 位的种子，使用线性同余公式 (linear congruential form) 对其进行了修改（请参阅 Donald Knuth的The Art of Computer Programming, Volume 3，第 3.2.1 节）。

Random类中实现的随机算法是伪随机，也就是有规则的随机。在进行随机时，随机算法的起源数字称为种子数(seed)，在种子数的基础上进行一定的变换，从而产生需要的随机数字。

相同种子数的Random对象，相同次数生成的随机数字是完全相同的。也就是说，两个种子数相同的Random对象，第一次生成的随机数字完全相同。

线性同余介绍

线性同余发生器(Linear congruential generator)是如下形式的伪随机序列发生器：

$X_{n+1}=(a*X_{n}+c) \quad mod \quad m, \quad n\geqslant 1$

其中 $X_n$ 是序列的第n个数， $X_{n+1}$ 是序列的第n+1个数，变量 $a$ ， $c$ ， $m$ 是常数， $a$ 是乘数， $c$ 是增量， $m$ 是模，密匙即种子初始值是 $X_0$ 。

这种发生器的周期不会超过 $m$ 。如果 $a$ ， $c$ 和 $m$ 都是可选的，那么发生器将会是一个最大周期发生器（maximal period generator，有时也叫最大长度），并且周期为 $m$ 。 $m$ 一般都设置的很大，在选择常数时需要仔细，以保证能找到最大的周期。

根据Hull-Dobell定理，当且仅当：

  1. $c$ 和 $m$ 互素;

  2. 对于整除 $m$ 的每个素数 $p$ ， $b = a-1$ 是 $p$ 的倍数;

  3. 如果 $m$ 是4的整数倍，则 $b$ 也是4的整数倍。

线性同余发生器的优点是：速度快，内存消耗少。

Random类中的线性同余算法

本文基于JDK 1.8的代码来分析，看下Random源码中的注释：

此类的实例用于生成伪随机数流。此类使用 48 位的种子，使用线性同余公式 (linear congruential form) 对其进行了修改（请参阅 Donald Knuth 的The Art of Computer Programming, Volume 3，第 3.2.1 节）。

如果用相同的种子创建两个 Random 实例，则对每个实例进行相同的方法调用序列，它们将生成并返回相同的数字序列。为了保证此属性的实现，为类 Random 指定了特定的算法。为了 Java 代码的完全可移植性，Java 实现必须让类 Random 使用此处所示的所有算法。但是允许 Random 类的子类使用其他算法，只要其符合所有方法的常规协定即可。

Random 类实现的算法使用一个 protected 实用工具方法int next(int bits)，每次调用它最多可提供 32 个伪随机生成的位。

许多应用程序会发现Math.random的使用方法更简单。

java.util.Random的实例是线程安全的。 但是，跨线程同时使用相同的java.util.Random实例可能会遇到争用，从而导致性能下降。 在多线程设计中考虑使用java.util.concurrent.ThreadLocalRandom。

java.util.Random的实例不是加密安全的。 考虑使用java.security.SecureRandom获得一个加密安全的伪随机数生成器，供安全敏感应用程序使用。

Random类中的变量

下面看下Random类中的一些重要的变量：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private final AtomicLong seed;
// 线性同余公式中的乘数a
private static final long multiplier = 0x5DEECE66DL;
// 线性同余公式中的加数c
private static final long addend = 0xBL;
// 线性同余公式中的模数m
private static final long mask = (1L << 48) - 1;
// double类型的计算单位，相当于是1.0 / (1L << 53)，在nextDouble方法中会用到
private static final double DOUBLE_UNIT = 0x1.0p-53; // 1.0 / (1L << 53)
// 用来计算种子
private static final AtomicLong seedUniquifier
        = new AtomicLong(8682522807148012L);

seed变量定义为AtomicLong 原子操作的Long型，并且final修饰的，所以它有如下特征：

  1. seed是final修饰的，也就是说必须要在random的构造方法中进行初始化。为了保证线程安全以后都不能被修改，每次使用必须复制它的一份拷贝，进行变更操作；
  2. Random类的线程安全是由于AtomicLong是线程安全的，基于其compareAndSet（CAS）方法实现；
  3. AtomicLong的最大范围是Long，也就是说可以产生随机的Int和随机的long。

Random类中的构造方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Creates a new random number generator. This constructor sets
 * the seed of the random number generator to a value very likely
 * to be distinct from any other invocation of this constructor.
 */
public Random() {
    this(seedUniquifier() ^ System.nanoTime());
}
private static long seedUniquifier() {
    // CAS自旋设置值
    for (;;) {
        long current = seedUniquifier.get();
        // 计算下一个值
        long next = current * 181783497276652981L;
        // 失败则重试
        if (seedUniquifier.compareAndSet(current, next))
            return next;
    }
}
private static final AtomicLong seedUniquifier
    = new AtomicLong(8682522807148012L);
public Random(long seed) {
    // 判断当前的实例是否是Random的子类类型
    if (getClass() == Random.class)
        // 计算种子的值
        this.seed = new AtomicLong(initialScramble(seed));
    else {
        // 子类可能重写了setSeed方法，调用子类的实现
        this.seed = new AtomicLong();
        setSeed(seed);
    }
}
private static long initialScramble(long seed) {
    return (seed ^ multiplier) & mask;
}

该构造方法，通过seedUniquifier()方法获取一个long型值，再与System.nanoTime()返回的long类型的值进行异或操作得到一个long值，再调用Random类的第二个构造方法 指定种子的构造方法。

简单的说就是：默认构造方法先通过一系列的计算，计算出一个种子，再调用第二构造方法为成员变量seed赋值。

可以看到，seedUniquifier方法使用CAS来进行赋值，在高并发情况下会比较消耗性能。

在public Random(long seed)构造方法中，首先判断当前的实例是否是Random的子类类型，如果不是Random类的子类类型，则调用initialScramble方法计算种子的值，(seed ^ multiplier) & mask，先异或multiplier，再与mask做与操作，也就是取模。

next方法

看下next方法的定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
protected int next(int bits) {
    long oldseed, nextseed;
    AtomicLong seed = this.seed;
    do {
        // 旧的种子
        oldseed = seed.get();
        // 线性同余计算新的48位种子
        nextseed = (oldseed * multiplier + addend) & mask;
        // CAS失败则重试
    } while (!seed.compareAndSet(oldseed, nextseed));
    // 返回值是int类型，保证位数在32位及以内
    return (int)(nextseed >>> (48 - bits));
}

该方法传入的bits参数是位数，返回指定位数范围内的随机数，因为mask是48位，所以最后需要移位。

nextInt方法

nextInt方法使用了next方法来计算随机数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int nextInt() {
    return next(32);
}
public int nextInt(int bound) {
    if (bound <= 0)
        throw new IllegalArgumentException(BadBound);
    // 获取31位的随机数
    int r = next(31);
    int m = bound - 1;
    // 判断是否是2的整数次幂
    if ((bound & m) == 0)  // i.e., bound is a power of 2
        // 如果是2的整数次幂，则直接移位就可以得到想要的结果
        r = (int)((bound * (long)r) >> 31);
    else {
        // 如果不是2的整数次幂，则需要对概率不均匀的范围进行特殊处理
        for (int u = r;
             u - (r = u % bound) + m < 0;
             u = next(31))
            ;
    }
    return r;
}

nextInt的工作是把31位的原始随机范围next(31)的结果映射到[0,n)范围之内。但是，如果不经过特殊处理会出现概率不均匀。

假设原有均匀的随机数范围是[0,100)，当我要产生新的随机数范围为[0,30)时候，因为100不被30整除，所以可以分为以下四组：[0,30)，[30, 60)，[60, 90)， [90,100)。所以实际产生的结果中，产生[0,10)的随机数概率会比[10,30)的要高。

代码中对这种情况的做法是：如果对31bit的随机数映射到[0,n)的时候，如果next(31)产生的数字是最后那部分，则丢弃重试。所以该方法中的循环部分就是对概率分布不均匀的情况进行处理。

当n是2的整数次幂时，n铁定能被2^31整除，这时候可以直接映射，进行一次next(31)运算即可。

当n不是2的整数次幂是，那就会出现刚才例子中的不均匀情况。所以就要特殊处理：当u - (r = u % bound) + m < 0 时，判断为不均匀部分，继续循环重试。那这句判断是什么意思呢？

根据上面的假设来分析一下，假设开始的时候r=95，那么这时就会出现概率不均匀的情况，因为产生[0,10)范围内的随机数的概率4/7，而产生[10,30)范围内的随机数的概率是3/7。u - (r = u % bound)的结果表示临界点的值，如果是在最后一个区间[90,100)中，那么临界值就是90；m = bound - 1，如果这时临界值加上m如果小于0，说明发生了溢出，那么可以通过是否溢出来判断生成的随机数是否在最后一个区间中，如果是则再进行一次next(31)重试。

可以想一下，最坏的情况就是bound传入2^30+1，这时拒绝的概率几乎就是1/2，循环终止前的预期迭代次数为2。

nextDouble方法

下面看一下另一个常用的nextDouble方法：

1
2
3
public double nextDouble() {
    return (((long)(next(26)) << 27) + next(27)) * DOUBLE_UNIT;
}

这里获取的是53位随机数，对于这个方法，源码的实现者很谨慎，也是尽量力求完美。在Java 的早期版本中，实现为(((long)next(27) << 27) + next(27)) / (double)(1L << 54)。这好像看似等效，但实际上根据IEE754标准双精度浮点数的有效位数是52位，最高有效位默认为1相当于可以保存53位，所以浮点数的舍入会存在偏差，因此54位会引入较大的不均匀性：有效数的低位出现 0 的可能性是 1 的三倍！(原来的值是舍入值的中间值时，会采取向偶数舍入，在二进制中，偶数我们认为是末尾为0的数)。同样的nextFloat获取的是24位随机数。

有关double类型在内存中的表示方式和向偶舍入，请参考计算机中浮点数的二进制表示。

通过这个方法可以看到，源码的实现者真的是做到力求完美，哪怕是double类型最后一位的不均匀都有考虑到，实在是佩服！

附录

为什么Random使用的是48位种子？

  1. 因为LCG的性质使得状态的低阶位根本不是非常随机的，所以需要比输出位更多的位状态， 所以如果你想要32位输出，你需要超过32位的状态。
  2. 为什么使用48而不是64？因为48位足够了，在设计这个算法时是很久以前了，而且没有必要如此严格，从而可以避免使用任何更多的资源。

为什么初始种子是8682522807148012L？

请参考：What’s with 181783497276652981 and 8682522807148012 in Random (Java 7)?