公司最近有一个项目需要使用到随机数，用户通过抽奖的方式获得奖品。
public static int random(int min,int max){
Random r=new Random();
return r.nextInt(max-min)+min;
}
逻辑很简单，就是产生[min,max)范围的随机数。这种实现问题是否会有问题？
业界常用的随机算法，希望从实现原理分析一下一个简单随机算法使用的正确姿势。
- Random
- ThreadLocalRandom
- SecureRandom
Random
首先我们要知道random是一个伪随机算法，并不是一个真正的随机算法。
* If two instances of {@code Random} are created with the same
* seed, and the same sequence of method calls is made for each, they
* will generate and return identical sequences of numbers.
官方文档说明，如果两个Random的实例通过一个相同的seed构建，则会产生相同的数字序列。
public Random() {
this(seedUniquifier() ^ System.nanoTime());
}
private static long seedUniquifier() {
// L'Ecuyer, "Tables of Linear Congruential Generators of
// Different Sizes and Good Lattice Structure", 1999
for (;;) {
long current = seedUniquifier.get();
long next = current * 181783497276652981L;
if (seedUniquifier.compareAndSet(current, next))
return next;
}
}
如果不指定初始化的seed，则会以当前的系统时间(精确到纳秒)来初始化seed。
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的过程。通过代码我们可以知道Random本身是线程安全的(通过CAS保证)
所以我们再回到一开始讲到的业务代码，每次去new Random()会有问题吗？
我们知道随机数算法是通过当前的seed来计算下一次的seed，如果每次去new一个实例，同一个时间点的中奖结果必然是一样的。
另外Random保证的是单实例下的多次调用的概率分布的平衡，通过每次new一个实例是无法保证整个概率分布的合理性。
我们尝试把代码修改为如下：
private static final class RandomNumberGeneratorHolder {
static final Random randomNumberGenerator = new Random();
}
public static int random(int min,int max){
return RandomNumberGeneratorHolder.randomNumberGenerator.nextInt(max-min)+min;
}
保证在多线程环境下使用一个实例进行随机。
然而在高并发环境下会由于需要对seed进行加锁而导致性能下降，因此考虑使用ThreadLocalRandom来解决性能的问题。
ThreadLocalRandom
由于Random类在多线程环境会共享同一个seed的变量，锁会导致随机数生成的性能下降。ThreadLocalRandom就是为了解决这个问题存在的。
解决的思路是为每一个线程单独分配一个seed。
我们先看下Thread的源码，保留了两个属性。
/** The current seed for a ThreadLocalRandom */
@sun.misc.Contended("tlr")
long threadLocalRandomSeed;
/** Probe hash value; nonzero if threadLocalRandomSeed initialized */
@sun.misc.Contended("tlr")
int threadLocalRandomProbe;
-
threadLocalRandomSeed
每个线程单独的种子
-
threadLocalRandomProbe
标志种子是否初始化，非0为初始化，0为未初始化。
接下来看ThreadLocalRandom的current()方法。
/**
* Returns the current thread's {@code ThreadLocalRandom}.
*
* @return the current thread's {@code ThreadLocalRandom}
*/
public static ThreadLocalRandom current() {
if (UNSAFE.getInt(Thread.currentThread(), PROBE) == 0)
localInit();
return instance;
}
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的threadLocalRandomSeed和threadLocalRandomProbe两个属性。在初始化的过程中并不是简单地通过获取线程的属性进行更新，而是通过unsafe(JNI)的方式进行。SEED和PROBE分别是这两个属性的偏移量。
另外初始化的种子为seeder增加一个常量来初始化。seeder为静态变量，但是只有在初始化的时候才会使用到，所以对性能影响不大。
// We must define this, but never use it.
protected int next(int bits) {
return (int)(mix64(nextSeed()) >>> (64 - bits));
}
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类似，通过获取当前的seed按照一定的算法规则进行更新，并返回给调用方。
SecureRandom
在看ThreadLocalRandom源码的时候，我们发现在初始化seed的方法里面有使用到SecureRandom的方法。我们回想一下，如果初始化的种子被破解，那么其实整个随机序列都会被得知，而初始化的种子如果是完全依赖服务器时间的话，用户可以在某个时间点上操作来控制整个随机算法。
SecureRandom来保证初始化的种子更难以被猜测。
private static long initialSeed() {
String pp = java.security.AccessController.doPrivileged(
new sun.security.action.GetPropertyAction(
"java.util.secureRandomSeed"));
if (pp != null && pp.equalsIgnoreCase("true")) {
byte[] seedBytes = java.security.SecureRandom.getSeed(8);
long s = (long)(seedBytes[0]) & 0xffL;
for (int i = 1; i < 8; ++i)
s = (s << 8) | ((long)(seedBytes[i]) & 0xffL);
return s;
}
return (mix64(System.currentTimeMillis()) ^
mix64(System.nanoTime()));
}
参考文献：
