前言
生成偽隨機(jī)數(shù)是用Java編程時(shí)的常見(jiàn)需求，本文簡(jiǎn)單討論一下最常用的Random和ThreadLocalRandom這兩個(gè)隨機(jī)數(shù)類，順便介紹線性同余法赊窥。
Random
話休絮煩，直接上源碼。
private final AtomicLong seed;
private static final long multiplier = 0x5DEECE66DL;
private static final long addend = 0xBL;
private static final long mask = (1L << 48) - 1;
public Random() {
this(seedUniquifier() ^ System.nanoTime());
}
private static long seedUniquifier() {
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) {
if (getClass() == Random.class)
this.seed = new AtomicLong(initialScramble(seed));
else {
this.seed = new AtomicLong();
setSeed(seed);
}
}
private static long initialScramble(long seed) {
return (seed ^ multiplier) & mask;
}
如果我們構(gòu)造Random實(shí)例時(shí)乞而，調(diào)用的是有參構(gòu)造方法（即傳入了自定義的隨機(jī)數(shù)種子seed），那么通過(guò)initialScramble()方法產(chǎn)生的實(shí)際使用的種子為：
(seed XOR 0x5DEECE66DL) AND ((1L << 48) - 1)
可見(jiàn)慢显，種子的長(zhǎng)度是48比特爪模。
如果調(diào)用的是無(wú)參構(gòu)造方法，那么會(huì)將seedUniquifier()方法返回的值與當(dāng)前JVM運(yùn)行的納秒時(shí)間戳做異或運(yùn)算荚藻，并作為seed值呻右，再經(jīng)過(guò)上式的運(yùn)算得出實(shí)際使用的種子。而seedUniquifier()是個(gè)自旋的方法鞋喇，它以8682522807148012L作為初始值声滥，不斷與181783497276652981L相乘，直到某次相乘前后的結(jié)果在long范圍內(nèi)相同時(shí)才返回侦香。這兩個(gè)大數(shù)的來(lái)歷請(qǐng)參見(jiàn)StackOverflow上的這個(gè)問(wèn)答落塑。
下面看看生成偽隨機(jī)數(shù)的核心方法next()，其參數(shù)bits是隨機(jī)數(shù)的字長(zhǎng)罐韩，比如nextInt()方法調(diào)用next()方法時(shí)憾赁，bits就是32。
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));
}
產(chǎn)生隨機(jī)數(shù)時(shí)散吵，會(huì)首先根據(jù)當(dāng)前種子seed更新種子的值為：
(seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1)
然后將新的種子值右移(48 - bits)位龙考，得到隨機(jī)數(shù)的真值蟆肆。上式就是所謂線性同余法的實(shí)現(xiàn)，下面簡(jiǎn)單分析一下晦款。
線性同余法
線性同余法（linear congruential generator, LCG）是非常古老的偽隨機(jī)數(shù)生成方法炎功，在1958年提出，但時(shí)至如今缓溅，它仍然是使用最廣泛的方法之一蛇损。它的思想很簡(jiǎn)單，用一個(gè)遞推式即可概括：
X[n+1] = (a·X[n] + c) mod m
其中：
- m > 0坛怪，稱為模（modulus）淤齐；
- 0 < a < m，稱為乘數(shù)（multiplier）袜匿；
- 0 <= c < m更啄，稱為增量（increment）；
- X[0]居灯，即遞推序列的初始值锈死，稱為種子（seed）。X就是生成的隨機(jī)數(shù)序列穆壕。
LCG有如下的重要性質(zhì)（Hull-Dobell定理）：
當(dāng)且僅當(dāng)
(1) c與m互素
(2) a - 1可以被所有m的質(zhì)因數(shù)整除
(3) 如果m能被4整除待牵，那么a - 1也能被4整除
以上三個(gè)條件同時(shí)滿足時(shí)，X是一個(gè)周期為m的序列喇勋。
既然LCG產(chǎn)生的是周期性的偽隨機(jī)數(shù)序列缨该，為了使它難以預(yù)測(cè)，m的值一般都會(huì)選得非常大川背。Random類中a贰拿、c、m這三個(gè)參數(shù)的取值分別為：
a = 0x5DEECE66DL = 25214903917 // multiplier
c = 0xBL = 11 //addend
m = 1L << 48 = 281474976710656 // mask
可見(jiàn)熄云，這三個(gè)值是滿足Hull-Dobell定理的膨更，故Random的周期為248，足夠大了缴允。
為了方便理解荚守，下圖示出不同參數(shù)取值下的LCG周期×钒悖可見(jiàn)矗漾，當(dāng)不滿足上述定理時(shí)（第一行和第二行），X的周期是一定比m短的薄料。
特別地敞贡，c=0的特殊情況叫做Lehmer生成器（Lehmer RNG），又叫乘同余法（multiplicative congruential generator, MCG）摄职。它的出現(xiàn)比LCG更早（1951年）誊役，并且參數(shù)的取值有更多的限制获列。本文不再展開(kāi)講細(xì)節(jié)，看官可以參見(jiàn)LCG與MCG的英文維基相關(guān)頁(yè)面蛔垢。
上面所敘述的過(guò)程產(chǎn)生的是整數(shù)击孩，如果要產(chǎn)生(0, 1)區(qū)間內(nèi)的小數(shù)怎么辦呢？很簡(jiǎn)單啦桌，結(jié)果再除以m就行了，因?yàn)閄中的原始值肯定比m小及皂。
ThreadLocalRandom
阿里Java開(kāi)發(fā)手冊(cè)中如是說(shuō)：
【推薦】避免Random實(shí)例被多線程使用甫男，雖然共享該實(shí)例是線程安全的，但會(huì)因競(jìng)爭(zhēng)同一seed導(dǎo)致性能下降验烧。
說(shuō)明：Random實(shí)例包括java.util.Random的實(shí)例或者M(jìn)ath.random()的方式板驳。
正例：在JDK7之后，可以直接使用API ThreadLocalRandom碍拆，而在JDK7之前若治，需要編碼保證每個(gè)線程持有一個(gè)實(shí)例。
從代碼可知感混，由于Random類中的種子是AtomicLong類型端幼，在多線程進(jìn)入next()方法時(shí)，只有一個(gè)線程能CAS成功更新種子弧满，其他線程都在不斷自旋婆跑，性能降低。為了解決這個(gè)問(wèn)題庭呜，產(chǎn)生了ThreadLocalRandom滑进。
ThreadLocalRandom是Random的子類，但在JDK7與JDK8中的實(shí)現(xiàn)方法頗有不同募谎。下面是JDK7版本的主要源碼扶关。
private static final long multiplier = 0x5DEECE66DL;
private static final long addend = 0xBL;
private static final long mask = (1L << 48) - 1;
private long rnd;
boolean initialized;
// 填充字節(jié)，避免不同線程的ThreadLocalRandom競(jìng)爭(zhēng)CPU緩存行造成虛共享
private long pad0, pad1, pad2, pad3, pad4, pad5, pad6, pad7;
ThreadLocalRandom() {
super();
initialized = true;
}
private static final ThreadLocal<ThreadLocalRandom> localRandom =
new ThreadLocal<ThreadLocalRandom>() {
protected ThreadLocalRandom initialValue() {
return new ThreadLocalRandom();
}
};
public static ThreadLocalRandom current() {
return localRandom.get();
}
public void setSeed(long seed) {
if (initialized)
throw new UnsupportedOperationException();
rnd = (seed ^ multiplier) & mask;
}
protected int next(int bits) {
rnd = (rnd * multiplier + addend) & mask;
return (int) (rnd >>> (48-bits));
}
可見(jiàn)数冬，ThreadLocalRandom產(chǎn)生隨機(jī)數(shù)的思路與Random完全相同节槐，不過(guò)是利用ThreadLocal為每個(gè)線程維護(hù)了不同的ThreadLocalRandom實(shí)例。在ThreadLocalRandom初始化時(shí)拐纱，會(huì)調(diào)用Random的無(wú)參構(gòu)造方法疯淫，并通過(guò)重寫過(guò)的setSeed()方法將計(jì)算出的種子存入rnd變量，故每個(gè)線程都擁有了不同的種子戳玫，通過(guò)current()方法即可取得自己的那一份熙掺，不會(huì)再產(chǎn)生沖突。
下面是JDK8版本的主要源碼咕宿。
private static final AtomicInteger probeGenerator =
new AtomicInteger();
private static final AtomicLong seeder = new AtomicLong(initialSeed());
boolean initialized;
private ThreadLocalRandom() {
initialized = true;
}
static final ThreadLocalRandom instance = new ThreadLocalRandom();
static final void localInit() {
int p = probeGenerator.addAndGet(PROBE_INCREMENT);
int probe = (p == 0) ? 1 : p;
long seed = mix64(seeder.getAndAdd(SEEDER_INCREMENT));
Thread t = Thread.currentThread();
UNSAFE.putLong(t, SEED, seed);
UNSAFE.putInt(t, PROBE, probe);
}
public static ThreadLocalRandom current() {
if (UNSAFE.getInt(Thread.currentThread(), PROBE) == 0)
localInit();
return instance;
}
public void setSeed(long seed) {
if (initialized)
throw new UnsupportedOperationException();
}
final long nextSeed() {
Thread t; long r;
UNSAFE.putLong(t = Thread.currentThread(), SEED,
r = UNSAFE.getLong(t, SEED) + GAMMA);
return r;
}
protected int next(int bits) {
return (int)(mix64(nextSeed()) >>> (64 - bits));
}
這些源碼中并沒(méi)有出現(xiàn)ThreadLocal币绩，那么每個(gè)線程的種子去哪里了蜡秽？答案是加進(jìn)了Thread類里，作為獨(dú)立的字段存在缆镣。
// sun.misc.Contended注解用于填充緩存行
@sun.misc.Contended("tlr")
long threadLocalRandomSeed;
@sun.misc.Contended("tlr")
int threadLocalRandomProbe;
threadLocalRandomSeed就是隨機(jī)數(shù)種子芽突，threadLocalRandomProbe是指示種子是否被初始化的探針變量《埃可見(jiàn)寞蚌，JDK8雖然沒(méi)有顯式使用ThreadLocal，但是基本的思想是相通的——即每個(gè)線程都持有獨(dú)享的種子值钠糊。ThreadLocalRandom代碼中的SEED和PROBE兩個(gè)量挟秤，實(shí)際上是通過(guò)Unsafe API取得的字段偏移地址。
private static final sun.misc.Unsafe UNSAFE;
private static final long SEED;
private static final long PROBE;
static {
try {
UNSAFE = sun.misc.Unsafe.getUnsafe();
Class<?> tk = Thread.class;
SEED = UNSAFE.objectFieldOffset
(tk.getDeclaredField("threadLocalRandomSeed"));
PROBE = UNSAFE.objectFieldOffset
(tk.getDeclaredField("threadLocalRandomProbe"));
} catch (Exception e) {
throw new Error(e);
}
}
JDK8版ThreadLocalRandom只有一個(gè)全局的實(shí)例抄伍，通過(guò)current()方法取得艘刚。當(dāng)某個(gè)Thread實(shí)例的探針threadLocalRandomProbe為0時(shí)，表示是首次執(zhí)行current()方法截珍，進(jìn)而會(huì)調(diào)用localInit()方法初始化種子和探針的值攀甚，并將它們寫入對(duì)應(yīng)的Thread實(shí)例中。通過(guò)nextSeed()方法就可以分別更新對(duì)應(yīng)線程的種子了岗喉。
可見(jiàn)秋度，與JDK7版本相比，JDK8版本的ThreadLocalRandom不再依賴于父類Random的構(gòu)造方法產(chǎn)生種子钱床，也就徹底消除了CAS自旋帶來(lái)的開(kāi)銷静陈。關(guān)于這個(gè)改進(jìn)的細(xì)節(jié)，還可以參考StackOverflow上的這個(gè)問(wèn)題诞丽。
最后一丟丟
上面講的LCG鲸拥、MCG是偽隨機(jī)數(shù)發(fā)生器，也就是說(shuō)如果知道了a僧免、c刑赶、m參數(shù)的值，隨機(jī)數(shù)就被破解了懂衩，無(wú)法做到安全撞叨。要保證安全，可以采用SecureRandom類浊洞。它利用了Linux的特殊設(shè)備/dev/random和/dev/urandom牵敷，基于系統(tǒng)的熵（進(jìn)程數(shù)、內(nèi)存用量法希、設(shè)備輸入等無(wú)法預(yù)測(cè)的指標(biāo)）產(chǎn)生隨機(jī)數(shù)枷餐，這樣也就沒(méi)辦法預(yù)測(cè)隨機(jī)序列的值了。
晚安晚安苫亦。
