一文搞懂Java随机数生成

你是如何生成随机数据的?

是这样?

new Random().nextInt();
复制代码

是这样?

org.apache.commons.lang3.RandomUtils.nextInt(startInclusive, endExclusive);
复制代码

还是这样?

ThreadLocalRandom.current().nextInt();
复制代码

先说结论

  • 并发场景 下随机数生成优先请用**ThreadLocalRandom**
  • 少并发场景 可用org.apache.commons.lang3.RandomUtils
  • 安全随机数场景 请使用java.security.**SecureRandom**,推荐算法**SHA1PRNG**(PRNG->pseudo-random numer generator )
  • 不建议 直接使用new Random().nextInt()

Random生成的随机数真的“随机”吗?

我们可以在java.util.Random类注释中找到答案:

An instance of this class is used to generate a stream of pseudorandom numbers. The class uses a 48-bit seed, which is modified using a linear congruential formula. (See Donald Knuth, , Section 3.2.1.)

If two instances of 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.

译文:

该类的实例用于生成 伪随机数 。该类使用48位种子,使用线性同余公式进行修改。 (参见Donald Knuth,<计算机程序设计的艺术,第2卷>,第3.2.1节。)

如果使用相同的种子创建两个Random实例,并且对每个实例都进行相同的方法调用,则它们将生成相同的随机数字。

所以可以看到其实Random生成的随机数都是伪随机数,只要种子一样,那么生成的随机数是完全一样的,可以看到seed对随机数生成至关重要。

Random原理浅析

直接上码, Random构造函数

private static final AtomicLong seedUniquifier  = new AtomicLong(8682522807148012L);

    public Random() {
        //获取一个seed和当前nanoTime异或后,调用有参构造函数构建实例
        this(seedUniquifier() ^ System.nanoTime());
    }

    private static long seedUniquifier() {
        // L'Ecuyer, "Tables of Linear Congruential Generators of
        // Different Sizes and Good Lattice Structure", 1999

        for (;;) {
            //获取当前seed的初始值,这个值是Random类的静态变量,用来保证每次构造Random实例的初始seed是不一样的,增强seed的差异
            long current = seedUniquifier.get();

            //为什么要乘以这数值,应该要看看线性同余公式了
            long next = current * 181783497276652981L;

            //把最新的值CAS更新到seedUniquifier
            if (seedUniquifier.compareAndSet(current, next))
                return next;
        }
    }

    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);
        }
    }
复制代码

可以看到Random的构造函数,就做了一件事情,就是为Random实例构建了一个初始的seed。

再看nextInt方法

public int nextInt(int bound) {
        if (bound <= 0)
            throw new IllegalArgumentException(BadBound);
        //根据上一个seed生成一个新的seed
        int r = next(31);
        int m = bound - 1;
        //下面是算法,根据新的seed计算最终的随机数
        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;
    }

    protected int next(int bits) {
        long oldseed, nextseed;
        AtomicLong seed = this.seed;
        do {
            oldseed = seed.get();
            //根据当前seed值计算新的seed
            nextseed = (oldseed * multiplier + addend) & mask;
            //使用nextSeed通过CAS+自旋的方式更新seed的值
        } while (!seed.compareAndSet(oldseed, nextseed));
        return (int)(nextseed >>> (48 - bits));
    }

复制代码

通过上面的代码可知随机数的生成主要是两个核心步骤:

  • 首先需要根据oldSeed计算生成nextSeed。
  • 然后根据nextSeed和bound变量通过一定的算法来计算生成新的随机数。

Random的局限

在并发场景下使用单个Random实例生成随机数时候,多个线程同时调用next(int bits)计算nextSeed时候,多个线程会竞争同一个seed的更新操作,但是由于seed的更新是CAS+自旋的方式,同一时间只有一个线程会成功,所以 Random实例是线程安全 的。但是CAS操作在大并发场景下会有大量线程更新失败,然后进行自旋重试,直至成功,而大量线程的自旋重试是会降低并发性能和消耗CPU资源的,为了解决这个问题,ThreadLocalRandom类应运而生。

ThreadLocalRandom原理浅析

ThreadLocalRandom是怎么解决并发场景下因自旋重试导致的性能下降呢?

核心思路是 把seed的值从Random的成员变量转移到了Thread里面的成员变量 ,从而达到在并发场景下 的目的,进而实现了并发性能的大幅提升。

使用方式:

ThreadLocalRandom.current().nextInt();
复制代码

先看ThreadLocalRandom.current()

/** The common ThreadLocalRandom */
    static final ThreadLocalRandom instance = new ThreadLocalRandom();

    /** Constructor used only for static singleton */
    private ThreadLocalRandom() {
        initialized = true; // false during super() call
    }
    //=======================分割线=======================
    public static ThreadLocalRandom current() {
        //当当前线程的probe等于0时,初始化线程的seed字段
        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
        //获取一个seed
        long seed = mix64(seeder.getAndAdd(SEEDER_INCREMENT));
        Thread t = Thread.currentThread();
        //通过UNSAFE把seed设置到thread里面
        UNSAFE.putLong(t, SEED, seed);
        //通过UNSAFE把probe设置为非0,这样下一次就不需要重新初始化了
        UNSAFE.putInt(t, PROBE, probe);
    }
    //=======================分割线=======================
    // Unsafe mechanics
    private static final sun.misc.Unsafe UNSAFE;
    private static final long SEED;//Thread类的threadLocalRandomSeed字段的偏移量
    private static final long PROBE;//Thread类的threadLocalRandomProbe字段的偏移量
    private static final long SECONDARY;
    static {
        try {
            UNSAFE = sun.misc.Unsafe.getUnsafe();
            Class<?> tk = Thread.class;
            SEED = UNSAFE.objectFieldOffset
                (tk.getDeclaredField("threadLocalRandomSeed"));
            PROBE = UNSAFE.objectFieldOffset
                (tk.getDeclaredField("threadLocalRandomProbe"));
            SECONDARY = UNSAFE.objectFieldOffset
                (tk.getDeclaredField("threadLocalRandomSecondarySeed"));
        } catch (Exception e) {
            throw new Error(e);
        }
    }
复制代码

再看 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
            for (int u = r >>> 1;
                 u + m - (r = u % bound) < 0;
                 u = mix32(nextSeed()) >>> 1)
                ;
        }
        return r;
    }
    //获取当前线程的下一个seed值
    final long nextSeed() {
        Thread t; long r; // read and update per-thread seed
        //先把当前线程的seed获取出来,然后+GAMMA(相当于一个步长)再塞回去
        UNSAFE.putLong(t = Thread.currentThread(), SEED,
                       r = UNSAFE.getLong(t, SEED) + GAMMA);
        return r;
    }

复制代码

再来一张图来帮助下理解:

一文搞懂Java随机数生成

SecureRandom为什么是安全的

SecureRandom和Random都是,也是如果种子一样,产生的随机数也一样: 因为种子确定,随机数算法也确定,因此输出是确定的。

只是说,SecureRandom类收集了一些 随机事件 ,比如从IO中断,网卡传输包等等这些外部入侵者 不可预测 的随机源中获取熵,SecureRandom 使用这些随机事件作为种子。这意味着,种子是不可预测的,而不像Random默认使用系统当前时间的毫秒数作为种子,有规律可寻。

至于为什么选用 SHA1PRNG 的性能更优,详见:《SecureRandom的江湖偏方与真实效果》 calvin1978.blogcn.com/articles/se…

性能比较

使用JMH测试

# JMH version: 1.21
# VM version: JDK 1.8.0_151, Java HotSpot(TM) 64-Bit Server VM, 25.151-b12
# Warmup: 3 iterations, 10 s each
# Measurement: 3 iterations, 5 s each
# Timeout: 10 min per iteration
# Threads: 5 threads, will synchronize iterations
# Benchmark mode: Throughput, ops/time
Benchmark                  Mode  Cnt          Score           Error  Units
new Random().nextInt      thrpt    3   19614207.388 ±   1164741.166  ops/s
RandomUtils.nextInt       thrpt    3   18046679.473 ±   3182634.593  ops/s
ThreadLocalRandom.nextInt thrpt    3  845131847.300 ± 185973223.877  ops/s
SecureRandom.nextInt      thrpt    3   28169402.475 ±   2356713.939  ops/s
复制代码

原文 

https://juejin.im/post/5c510433e51d4547254c7b44

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » 一文搞懂Java随机数生成

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址