Java 随机数生成原理与 ThreadLocalRandom 详解

站长

2023年08月11日 09:35 · 阅读数 12

简介

在 JDK7 中，java.util.concurrent 包含了一个相当便利的类随机数生成类 ThreadLocalRandom，当应用程序期望在多个线程或 ForkJoinTasks 中使用随机数时。对于并发访问，使用 TheadLocalRandom 代替 Math.random() 可以减少竞争，从而获得更好的性能。使用中只需调用 ThreadLocalRandom.current()，然后调用它的其中一个方法去获取一个随机数即可。下面是一个例子：

int randomNum = ThreadLocalRandom.current().nextInt(max);

源码分析

线性同余法

线性同余法( linear congruential method) 亦称“线性同余随机数生成器”。产生[0，1]均匀分布随机数的方法之一。包括混合同余法和乘同余法。由美国莱默尔在1951年提出。 Java 中的 Random 生成随机数的算法就是通过它实现的。

X[n + 1] = (a * X[n] + c) mod m

其中，

m > 0，模数据
0 <= a <= m，乘数
0 <= c <= m，增量
0 <= X0 < m， X0 开始值

Random 源码分析

下面是 Random 的核心源码部分

private static final long multiplier = 0x5DEECE66DL;
private static final long addend = 0xBL;
private static final long mask = (1L << 48) - 1;

// 构造方法初始化 this.seed
public Random(long seed) {
    if (getClass() == Random.class)
        this.seed = new AtomicLong(initialScramble(seed));
    else {
        // subclass might have overriden setSeed
        this.seed = new AtomicLong();
        setSeed(seed);
    }
}

protected int next(int bits) {
    long oldseed, nextseed;
    AtomicLong seed = this.seed;
    do {
        oldseed = seed.get();
        nextseed = (oldseed * multiplier + addend) & mask;
    // CAS 方式保证线程安全，但是多线程情况下可能存在性能问题    
    } while (!seed.compareAndSet(oldseed, nextseed));
    return (int)(nextseed >>> (48 - bits));
}


// 获取随机数
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;
}

从源码中我们可以看到核心计算为

nextseed = (oldseed * multiplier + addend) & mask;

然后替换掉固定值可以得到如下的公式

nextseed = (oldseed * 25214903917L + 11L) & 281474976710655L;

seed 其实我们也可以成为 随机种子 再次拷贝公式方便阅读

X[n + 1] = (a * X[n] + c) mod m

其中 multiplier 和 addend 分别代表公式中的 a 和 c，但mask代表什么呢？其实，x & [(1L << 48)–1]与 x（mod 2^48）等价。解释一下： x 对于 2 的 N 次幂取余，由于除数是2的N次幂，如： 0001，0010，0100，1000 相当于把x的二进制形式向右移N位，此时移到小数点右侧的就是余数，如： 13 = 1101 8 = 1000 13 / 8 = 1.101，所以小数点右侧的101就是余数，化成十进制就是 5

注意：**AtomicLong seed**** 说明 Random 是一个线程安全的随机数工具类 **

ThreadLocalRandom 源码分析

我们可以通过 ThreadLocalRandom.current() 获取实例。

public static ThreadLocalRandom current() {
        if (UNSAFE.getInt(Thread.currentThread(), PROBE) == 0)
            localInit();
        return instance;
}

如果没有初始化会调用 localInit() 初始化:

static final void localInit() {
    int p = probeGenerator.addAndGet(PROBE_INCREMENT);
    int probe = (p == 0) ? 1 : p; // skip 0
    long seed = mix64(seeder.getAndAdd(SEEDER_INCREMENT));
    Thread t = Thread.currentThread();
    UNSAFE.putLong(t, SEED, seed);
    UNSAFE.putInt(t, PROBE, probe);
}

通过代码我们可以看到，使用 Thread.currentThread() 获取当前线程。说明生成随机数的过程不在依赖 CAS 获取共享对象。我们最后再来看 nextInt 方法：

public int nextInt(int bound) {
    if (bound <= 0)
        throw new IllegalArgumentException(BadBound);
    // 生成随机数
    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;
}

nextInt(int bound) 和 nextInt 的思路是一样的，先调用 mix32(nextSeed()) 方法生成随机数（int类型的范围），再对参数 n 进行判断，如果 n 恰好为 2 的方幂，那么直接移位就可以得到想要的结果；如果不是 2 的方幂，那么就关于 n 取余，最终使结果在[0,n)范围内。另外，for 循环语句的目的是防止结果为负数。

这里我们可以看到主要是通过 mix32(nextSeed())

// 根据新种子生成随机数，随机数算法和 Random 一样
private static int mix32(long z) {
    z = (z ^ (z >>> 33)) * 0xff51afd7ed558ccdL;
    return (int)(((z ^ (z >>> 33)) * 0xc4ceb9fe1a85ec53L) >>> 32);
}


// 生成新的种子，保存在 Thread.threadLocalRandomSeed 中。 GAMMA=0x9e3779b97f4a7c15L
final long nextSeed() {
    Thread t; long r; // read and update per-thread seed
    UNSAFE.putLong(t = Thread.currentThread(), SEED,
                   r = UNSAFE.getLong(t, SEED) + GAMMA);
    return r;
}

使用案例

Random

下面是 Random 类生成随机数的使用方法

public class RandomTest {
    static Random RANDOM = new Random();

    public static void main(String[] args) {
        final int max = 1000000;
        for (int i = 0; i < 1000; i++) {
            new Thread(() -> {
                int randomNum = RANDOM.nextInt(max);
                System.out.println("randomNum: " + randomNum);
            }).start();
        }
    }
}

ThreadLocalRandom

下面是是一个简单的 ThreadLocalRandom 如下所示：

public class ThreadLocalRandomTest {

    public static void main(String[] args) {
        final int max = 1000000;
        for (int i = 0; i < 1000; i++) {
            new Thread(()-> {
                int randomNum = ThreadLocalRandom.current().nextInt(max);
                System.out.println("randomNum: " + randomNum);
            }).start();
        }
    }
}

// 输出结果
randomNum: 648582
randomNum: 76984
randomNum: 561085
randomNum: 120131
randomNum: 210919
randomNum: 546645
randomNum: 194225
randomNum: 930034
randomNum: 203882

使用总结

避免 Random 实例被多线程使用，虽然共享该实例是线程安全的，但会因竞争同一 seed 导致的性能下降。 说明：Random 实例包括 java.util.Random 的实例或者 Math.random()的方式。正例：在 JDK7 之后，可以直接使用 API ThreadLocalRandom，而在 JDK7 之前，需要编码保证每个线程持有一个单独的 Random 实例。