🤗 Random源码解析

/**
     * Returns a pseudorandom, uniformly distributed {@code int} value
     * between 0 (inclusive) and the specified value (exclusive), drawn from
     * this random number generator's sequence.  The general contract of
     * {@code nextInt} is that one {@code int} value in the specified range
     * is pseudorandomly generated and returned.  All {@code bound} possible
     * {@code int} values are produced with (approximately) equal
     * probability.
     *
     * @implSpec The method {@code nextInt(int bound)} is implemented by
     * class {@code Random} as if by:
     * <pre>{@code
     * public int nextInt(int bound) {
     *   if (bound <= 0)
     *     throw new IllegalArgumentException("bound must be positive");
     *
     *   if ((bound & -bound) == bound)  // i.e., bound is a power of 2
     *     return (int)((bound * (long)next(31)) >> 31);
     *
     *   int bits, val;
     *   do {
     *       bits = next(31);
     *       val = bits % bound;
     *   } while (bits - val + (bound-1) < 0);
     *   return val;
     * }}</pre>
     *
     * <p>The hedge "approximately" is used in the foregoing description only
     * because the next method is only approximately an unbiased source of
     * independently chosen bits.  If it were a perfect source of randomly
     * chosen bits, then the algorithm shown would choose {@code int}
     * values from the stated range with perfect uniformity.
     * <p>
     * The algorithm is slightly tricky.  It rejects values that would result
     * in an uneven distribution (due to the fact that 2^31 is not divisible
     * by n). The probability of a value being rejected depends on n.  The
     * worst case is n=2^30+1, for which the probability of a reject is 1/2,
     * and the expected number of iterations before the loop terminates is 2.
     * <p>
     * The algorithm treats the case where n is a power of two specially: it
     * returns the correct number of high-order bits from the underlying
     * pseudo-random number generator.  In the absence of special treatment,
     * the correct number of <i>low-order</i> bits would be returned.  Linear
     * congruential pseudo-random number generators such as the one
     * implemented by this class are known to have short periods in the
     * sequence of values of their low-order bits.  Thus, this special case
     * greatly increases the length of the sequence of values returned by
     * successive calls to this method if n is a small power of two.
     *
     * @param bound the upper bound (exclusive).  Must be positive.
     * @return the next pseudorandom, uniformly distributed {@code int}
     *         value between zero (inclusive) and {@code bound} (exclusive)
     *         from this random number generator's sequence
     * @throws IllegalArgumentException if bound is not positive
     * @since 1.2
     */
			public int nextInt(int bound) {
			    // 验证边界的合法性
			    if (bound <= 0)
			        throw new IllegalArgumentException(BadBound);
				// 根据老种子生成新种子
			    int r = next(31);
			    // 计算最大值
			    int m = bound - 1;
			    // 根据新种子计算随机数
			    if ((bound & m) == 0)  // i.e., bound is a power of 2
			        r = (int)((bound * (long)r) >> 31);
			    else {
			        for (int u = r;
			                u - (r = u % bound) + m < 0;
			                u = next(31));
			    }
			    return r;
			}

从以上源码我们可以看出，整个源码最核心的部分有两块：

根据老种子生成新种子；
根据新种子计算出随机数。

根据新种子计算出随机数的代码已经很明确了，我们需要确认一下 next() 方法是如何实现的，继续看源码：

 /**
     * Generates the next pseudorandom number. This method returns an
     * {@code int} value such that, if the argument {@code bits} is between
     * {@code 1} and {@code 32} (inclusive), then that many low-order
     * bits of the returned value will be (approximately) independently
     * chosen bit values, each of which is (approximately) equally
     * likely to be {@code 0} or {@code 1}.
     *
     * @apiNote
     * The other random-producing methods in this class are implemented
     * in terms of this method, so subclasses can override just this
     * method to provide a different source of pseudorandom numbers for
     * the entire class.
     *
     * @implSpec
     * The implementation in this class atomically updates the seed to
     *  <pre>{@code (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1)}</pre>
     * and returns
     *  <pre>{@code (int)(seed >>> (48 - bits))}.</pre>
     *
     * <p>This is a linear congruential pseudorandom number generator, as
     * defined by D. H. Lehmer and described by Donald E. Knuth in
     * <cite>The Art of Computer Programming, Volume 2, Third edition:
     * Seminumerical Algorithms</cite>, section 3.2.1.
     *
     * @param  bits random bits
     * @return the next pseudorandom value from this random number
     *         generator's sequence
     * @since  1.1
     */
    protected int next(int bits) {
        long oldseed, nextseed;
        AtomicLong seed = this.seed;
        do {
            oldseed = seed.get();
            nextseed = (oldseed * multiplier + addend) & mask;
        } while (!seed.compareAndSet(oldseed, nextseed));
        return (int)(nextseed >>> (48 - bits));
    }

根据以上源码可以看出，在使用老种子去获取新种子的时候，如果是多线程操作，则同一时刻只会有一个线程 CAS (Conmpare And Swap，比较并交换) 成功，其他失败的线程会通过自旋等待获取新种子，因此会有一定的性能消耗。

这也是为什么 JDK 1.7 会引入 ThreadLocalRandom 的答案了，它的出现主要为了提升多线程情况下 Random 的执行效率。那它是如何来提升的？接下来一起来看。

🥳 ThreadLocalRandom使用

我们先来看 ThreadLocalRandom 的类关系图：

可以看出 ThreadLocalRandom 继承于 Random 类，先来看它的使用：

ThreadLocalRandom threadLocalRandom = ThreadLocalRandom.current();
for (int i = 0; i < 3; i++) {
    // 生成 0-9 的随机数
    System.out.println(threadLocalRandom.nextInt(10));
}

🤔 ThreadLocalRandom源码解析

/**
 * 源码版本：JDK 11 JDK17和JDK8是直接使用的父类的
 */
public int nextInt(int bound) {
    if (bound <= 0)
        throw new IllegalArgumentException(BAD_BOUND);
    // 根据老种子生成新种子
    int r = mix32(nextSeed());
    int m = bound - 1;
    // 根据新种子计算算出随机数
    if ((bound & m) == 0) // power of two
        r &= m;
    else { // reject over-represented candidates
        for (int u = r >>> 1;
             u + m - (r = u % bound) < 0;
             u = mix32(nextSeed()) >>> 1)
            ;
    }
    return r;
}

/**
 * 源码版本：JDK 11
 */
final long nextSeed() {
    Thread t; long r; // read and update per-thread seed
    // 把当前线程作为参数生成一个新种子
    U.putLong(t = Thread.currentThread(), SEED,
              r = U.getLong(t, SEED) + GAMMA);
    return r;
}
@HotSpotIntrinsicCandidate
public native void putLong(Object o, long offset, long x);

从以上源码可以看出，ThreadLocalRandom 并不是像 Thread 那样使用 CAS 和自旋来获取新种子，而是在每个线程中使用每个线程中保存自己的老种子来生成新种子，因此就可以避免多线程竞争和自旋等待的时间，所以在多线程环境下性能更高。

🤥 ThreadLocalRandom 注意事项

在使用 ThreadLocalRandom 时需要注意一下，在多线程不能共享一个 ThreadLocalRandom 对象，否则会造成生成的随机数都相同，如下代码所示：

// 声明多线程
ExecutorService service = Executors.newCachedThreadPool();
// 共享 ThreadLocalRandom
ThreadLocalRandom threadLocalRandom = ThreadLocalRandom.current();
for (int i = 0; i < 10; i++) {
    // 多线程执行随机数并打印结果
    service.submit(() -> {
        System.out.println(Thread.currentThread().getName() + ":" + threadLocalRandom.nextInt(10));
        ;
    });
}

😶‍🌫️ 性能对比

接下来我们使用 Oracle 官方提供的性能测试工具 JMH (Java Microbenchmark Harness，JAVA 微基准测试套件)，来测试一下 Random 和 ThreadLocalRandom 的吞吐量（单位时间内成功执行程序的数量）:

import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.RunnerException;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;
import java.util.Random;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.TimeUnit;

/**
 * JDK：11
 * Windows 10 I5-4460/16G
 */
@BenchmarkMode(Mode.Throughput) // 测试类型：吞吐量
//@Threads(16)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
public class RandomExample {
    public static void main(String[] args) throws RunnerException {
        // 启动基准测试
        Options opt = new OptionsBuilder()
                .include(RandomExample.class.getSimpleName()) // 要导入的测试类
                .warmupIterations(5) // 预热 5 轮
                .measurementIterations(10) // 度量10轮
                .forks(1)
                .build();
        new Runner(opt).run(); // 执行测试
    }

    /**
     * Random 性能测试
     */
    @Benchmark
    public void randomTest() {
        Random random = new Random();
        for (int i = 0; i < 10; i++) {
            // 生成 0-9 的随机数
            random.nextInt(10);
        }
    }
    /**
     * ThreadLocalRandom 性能测试
     */
    @Benchmark
    public void threadLocalRandomTest() {
        ThreadLocalRandom threadLocalRandom = ThreadLocalRandom.current();
        for (int i = 0; i < 10; i++) {
            threadLocalRandom.nextInt(10);
        }
    }
}

测试结果如下：

其中，Cnt 表示运行了多少次，Score 表示执行的成绩，Units 表示每秒的吞吐量。

从 JMH 测试的结果可以看出，ThreadLocalRandom 在并发情况下的吞吐量约是 Random 的 5 倍。

📎 参考文章

Java Random 随机算法解释

《Java 并发编程之美》翟陆续
ThreadLocalRandom类原理剖析

Random和ThreadLocalRandom区别