前言

生成偽隨機數是用Java編程時的常見需求，本文簡單討論一下最常用的Random和ThreadLocalRandom這兩個隨機數類，順便介紹線性同余法。

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;}

如果我們構造Random實例時，調用的是有參構造方法（即傳入了自定義的隨機數種子seed），那么通過initialScramble()方法產生的實際使用的種子為：
(seed XOR 0x5DEECE66DL) AND ((1L << 48) - 1)

可見，種子的長度是48比特。

如果調用的是無參構造方法，那么會將seedUniquifier()方法返回的值與當前JVM運行的納秒時間戳做異或運算，并作為seed值，再經過上式的運算得出實際使用的種子。而seedUniquifier()是個自旋的方法，它以8682522807148012L作為初始值，不斷與181783497276652981L相乘，直到某次相乘前后的結果在long范圍內相同時才返回。這兩個大數的來歷請參見StackOverflow上的這個問答。

下面看看生成偽隨機數的核心方法next()，其參數bits是隨機數的字長，比如nextInt()方法調用next()方法時，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));}

產生隨機數時，會首先根據當前種子seed更新種子的值為：
(seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1)

然后將新的種子值右移(48 - bits)位，得到隨機數的真值。上式就是所謂線性同余法的實現，下面簡單分析一下。

線性同余法

線性同余法（linear congruential generator, LCG）是非常古老的偽隨機數生成方法，在1958年提出，但時至如今，它仍然是使用最廣泛的方法之一。它的思想很簡單，用一個遞推式即可概括：

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

其中：

• m > 0，稱為模（modulus）；
• 0 < a < m，稱為乘數（multiplier）；
• 0 <= c < m，稱為增量（increment）；
• X[0]，即遞推序列的初始值，稱為種子（seed）。X就是生成的隨機數序列。

LCG有如下的重要性質（Hull-Dobell定理）：

當且僅當
(1) c與m互素
(2) a - 1可以被所有m的質因數整除
(3) 如果m能被4整除，那么a - 1也能被4整除
以上三個條件同時滿足時，X是一個周期為m的序列。

既然LCG產生的是周期性的偽隨機數序列，為了使它難以預測，m的值一般都會選得非常大。Random類中a、c、m這三個參數的取值分別為：

a = 0x5DEECE66DL = 25214903917 // multiplier c = 0xBL = 11 //addend m = 1L << 48 = 281474976710656 // mask

可見，這三個值是滿足Hull-Dobell定理的，故Random的周期為2⁴⁸，足夠大了。

為了方便理解，下圖示出不同參數取值下的LCG周期。可見，當不滿足上述定理時（第一行和第二行），X的周期是一定比m短的。

特別地，c=0的特殊情況叫做Lehmer生成器（Lehmer RNG），又叫乘同余法（multiplicative congruential generator, MCG）。它的出現比LCG更早（1951年），并且參數的取值有更多的限制。本文不再展開講細節，看官可以參見LCG與MCG的英文維基相關頁面。

上面所敘述的過程產生的是整數，如果要產生(0, 1)區間內的小數怎么辦呢？很簡單，結果再除以m就行了，因為X中的原始值肯定比m小。

ThreadLocalRandom

阿里Java開發手冊中如是說：

【推薦】避免Random實例被多線程使用，雖然共享該實例是線程安全的，但會因競爭同一seed導致性能下降。
說明：Random實例包括java.util.Random的實例或者Math.random()的方式。
正例：在JDK7之后，可以直接使用API ThreadLocalRandom，而在JDK7之前，需要編碼保證每個線程持有一個實例。

從代碼可知，由于Random類中的種子是AtomicLong類型，在多線程進入next()方法時，只有一個線程能CAS成功更新種子，其他線程都在不斷自旋，性能降低。為了解決這個問題，產生了ThreadLocalRandom。

ThreadLocalRandom是Random的子類，但在JDK7與JDK8中的實現方法頗有不同。下面是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;// 填充字節，避免不同線程的ThreadLocalRandom競爭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));}

可見，ThreadLocalRandom產生隨機數的思路與Random完全相同，不過是利用ThreadLocal為每個線程維護了不同的ThreadLocalRandom實例。在ThreadLocalRandom初始化時，會調用Random的無參構造方法，并通過重寫過的setSeed()方法將計算出的種子存入rnd變量，故每個線程都擁有了不同的種子，通過current()方法即可取得自己的那一份，不會再產生沖突。

下面是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));}

這些源碼中并沒有出現ThreadLocal，那么每個線程的種子去哪里了？答案是加進了Thread類里，作為獨立的字段存在。

// sun.misc.Contended注解用于填充緩存行 @sun.misc.Contended("tlr") long threadLocalRandomSeed; @sun.misc.Contended("tlr") int threadLocalRandomProbe;

threadLocalRandomSeed就是隨機數種子，threadLocalRandomProbe是指示種子是否被初始化的探針變量。可見，JDK8雖然沒有顯式使用ThreadLocal，但是基本的思想是相通的——即每個線程都持有獨享的種子值。ThreadLocalRandom代碼中的SEED和PROBE兩個量，實際上是通過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只有一個全局的實例，通過current()方法取得。當某個Thread實例的探針threadLocalRandomProbe為0時，表示是首次執行current()方法，進而會調用localInit()方法初始化種子和探針的值，并將它們寫入對應的Thread實例中。通過nextSeed()方法就可以分別更新對應線程的種子了。

可見，與JDK7版本相比，JDK8版本的ThreadLocalRandom不再依賴于父類Random的構造方法產生種子，也就徹底消除了CAS自旋帶來的開銷。關于這個改進的細節，還可以參考StackOverflow上的這個問題。

最后一丟丟

上面講的LCG、MCG是偽隨機數發生器，也就是說如果知道了a、c、m參數的值，隨機數就被破解了，無法做到安全。要保證安全，可以采用SecureRandom類。它利用了Linux的特殊設備/dev/random和/dev/urandom，基于系統的熵（進程數、內存用量、設備輸入等無法預測的指標）產生隨機數，這樣也就沒辦法預測隨機序列的值了。

晚安晚安。

總結

以上是生活随笔為你收集整理的浅谈Java的伪随机数发生器和线性同余法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。