Java 隨機數生成原理與 ThreadLocalRandom 詳解
簡介
在 JDK7 中，java.util.concurrent 包含了一個相當便利的類隨機數生成類 ThreadLocalRandom，當應用程序期望在多個線程或 ForkJoinTasks 中使用隨機數時。對于并發(fā)訪問，使用 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
// 重試直到符合區(qū)間要求
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 循環(huán)語句的目的是防止結果為負數。
這里我們可以看到主要是通過 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 實例。
參考資料
《計算機程序設計藝術》 TACOP
《Java 開發(fā)手冊》阿里巴巴
www.cnblogs.com/shamo89/p/8…
ifeve.com/tag/threadl…
www.cnblogs.com/softidea/p/…
baike.baidu.com/item/%E7%BA…
www.cnblogs.com/binarylei/p…
作者：老鄭_
鏈接：https://juejin.cn/post/7003371579300118535
來源：掘金
著作權歸作者所有。商業(yè)轉載請聯系作者獲得授權，非商業(yè)轉載請注明出處。