在 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
其中,
下面是 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.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 类生成随机数的使用方法
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
如下所示:
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 实例。