Java 隨機(jī)數(shù)生成原理與 ThreadLocalRandom 詳解
簡介
在 JDK7 中，java.util.concurrent 包含了一個(gè)相當(dāng)便利的類隨機(jī)數(shù)生成類 ThreadLocalRandom，當(dāng)應(yīng)用程序期望在多個(gè)線程或 ForkJoinTasks 中使用隨機(jī)數(shù)時(shí)。對(duì)于并發(fā)訪問，使用 TheadLocalRandom 代替 Math.random() 可以減少競爭，從而獲得更好的性能。使用中只需調(diào)用 ThreadLocalRandom.current()， 然后調(diào)用它的其中一個(gè)方法去獲取一個(gè)隨機(jī)數(shù)即可。下面是一個(gè)例子：
int randomNum = ThreadLocalRandom.current().nextInt(max);
復(fù)制代碼源碼分析
線性同余法
線性同余法( linear congruential method) 亦稱“線性同余隨機(jī)數(shù)生成器”。產(chǎn)生[0，1]均勻分布隨機(jī)數(shù)的方法之一。包括混合同余法和乘同余法。由美國萊默爾在1951年提出。Java 中的 Random 生成隨機(jī)數(shù)的算法就是通過它實(shí)現(xiàn)的。
X[n + 1] = (a * X[n] + c) mod m
其中，
m > 0，模數(shù)據(jù)
0 <= a <= m， 乘數(shù)
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;
// 構(gòu)造方法初始化 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));
}
// 獲取隨機(jī)數(shù)
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;
}
復(fù)制代碼從源碼中我們可以看到核心計(jì)算為
nextseed = (oldseed * multiplier + addend) & mask;
然后替換掉固定值可以得到如下的公式
nextseed = (oldseed * 25214903917L + 11L) & 281474976710655L;
seed 其實(shí)我們也可以成為 隨機(jī)種子再次拷貝公式方便閱讀
X[n + 1] = (a * X[n] + c) mod m
其中 multiplier 和 addend 分別代表公式中的 a 和 c，但mask代表什么呢？其實(shí)，x & [(1L << 48)–1]與 x（mod 2^48）等價(jià)。解釋一下：x 對(duì)于 2 的 N 次冪取余，由于除數(shù)是2的N次冪，如：0001，0010，0100，1000 相當(dāng)于把x的二進(jìn)制形式向右移N位，此時(shí)移到小數(shù)點(diǎn)右側(cè)的就是余數(shù)，如：13 = 1101 8 = 1000 13 / 8 = 1.101，所以小數(shù)點(diǎn)右側(cè)的101就是余數(shù)，化成十進(jìn)制就是 5
注意：**AtomicLong seed**** 說明 Random 是一個(gè)線程安全的隨機(jī)數(shù)工具類 **
ThreadLocalRandom 源碼分析
我們可以通過 ThreadLocalRandom.current() 獲取實(shí)例。
public static ThreadLocalRandom current() {
if (UNSAFE.getInt(Thread.currentThread(), PROBE) == 0)
localInit();
return instance;
}
復(fù)制代碼如果沒有初始化會(huì)調(diào)用 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);
}
復(fù)制代碼通過代碼我們可以看到，使用 Thread.currentThread() 獲取當(dāng)前線程。說明生成隨機(jī)數(shù)的過程不在依賴 CAS 獲取共享對(duì)象。我們最后再來看 nextInt 方法：
public int nextInt(int bound) {
if (bound <= 0)
throw new IllegalArgumentException(BadBound);
// 生成隨機(jī)數(shù)
int r = mix32(nextSeed());
int m = bound - 1;
// 隨機(jī)數(shù)判斷
if ((bound & m) == 0) // power of two
// 取余數(shù)
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;
}
復(fù)制代碼nextInt(int bound) 和 nextInt 的思路是一樣的，先調(diào)用 mix32(nextSeed()) 方法生成隨機(jī)數(shù)（int類型的范圍），再對(duì)參數(shù) n 進(jìn)行判斷，如果 n 恰好為 2 的方冪，那么直接移位就可以得到想要的結(jié)果；如果不是 2 的方冪，那么就關(guān)于 n 取余，最終使結(jié)果在[0,n)范圍內(nèi)。另外，for 循環(huán)語句的目的是防止結(jié)果為負(fù)數(shù)。
這里我們可以看到主要是通過 mix32(nextSeed())
// 根據(jù)新種子生成隨機(jī)數(shù)，隨機(jī)數(shù)算法和 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;
}
復(fù)制代碼使用案例
Random
下面是 Random 類生成隨機(jī)數(shù)的使用方法
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();
}
}
}
復(fù)制代碼ThreadLocalRandom
下面是是一個(gè)簡單的 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();
}
}
}
// 輸出結(jié)果
randomNum: 648582
randomNum: 76984
randomNum: 561085
randomNum: 120131
randomNum: 210919
randomNum: 546645
randomNum: 194225
randomNum: 930034
randomNum: 203882
復(fù)制代碼使用總結(jié)
避免 Random 實(shí)例被多線程使用，雖然共享該實(shí)例是線程安全的，但會(huì)因競爭同一 seed 導(dǎo)致的性能下降。說明：Random 實(shí)例包括 java.util.Random 的實(shí)例或者 Math.random()的方式。正例：在 JDK7 之后，可以直接使用 API ThreadLocalRandom，而在 JDK7 之前，需要編碼保證每個(gè)線 程持有一個(gè)單獨(dú)的 Random 實(shí)例。
參考資料
《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》 TACOP
《Java 開發(fā)手冊(cè)》阿里巴巴
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
來源：掘金
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。