庆祝1024,从冯诺依曼解析到Java Random类源码

大家好, 这里是 K 字的研究. 我是爱灌水的老 K.

好久没有解析源码了, 今天来给大家解析一个 Java 里的常用工具类: java.util.Random.

先说一点, Random 类其实和我们提过的 Integer 有点像. 整个类里 1 成是主逻辑, 9 成都是 util 代码,工具代码. 我会略过一些工具代码.另外, Random核心的几个参数, 我暂时没考虑好,先不涉及.

1引子

按照惯例, 一般会先自己实现一个残次品版本, 然后再去翻源码.

不过, 鉴于这块我的水平不行,自己实现确实有点困难. 我就直接给大家抄一个经典算法过来实现下吧.

平方取中法

import java.math.BigInteger;

public class RandomNeumann {
    public static void main(String[] args) {
        long r = random(5772156649L, 10);
        System.out.println("r = " + r);
    }

    static public long random(long n, int size) {
        BigInteger bigN = BigInteger.valueOf(n);
        BigInteger mul = bigN.multiply(bigN);
        String num = mul.toString();
        int numSize = num.length();
        int padding = (numSize - size) / 2;
        return Long.parseLong(num.substring(padding, padding + size));
    }
}

这个算法实现的很挫, 不过反正是玩具,凑合看, 应该很好看懂逻辑.用上一个随机数取平方, 从正中间截出想要的位数.

入参有两个:

上次生成的随机数
要生成多少位

这个算法叫: 平方取中法.1946 年一个叫约翰的人发明了这个算法.

虽然看上去很卡哇伊, 但是他在计算机界也算是小有名气, 全名是(John von Neumann),一般被翻译为冯·诺依曼^[1].

算法特点

这算法有几个特点

每一个数都依赖于上一个数,因此需要自己手动提供第一个数.
过了一阵子之后, 数字序列就开始固定不变了,或者进入一个循环.

需要提供的第一个数字,一般被称为种子,这个种子对后面的生成很关键.假若我们提供的种子是 10000000000, 那么后面生成的所有数字都会变成 0.基本上就宣告这算法废了.

种子在随机数生成时候, 很关键.

后续

他这个算法, 很快就被人发现有问题, 不过, 对于我们刚开始看Random类的人来说, 了解下这个算法还是有必要的.

这套每一个数由上一个数生成的架构, 这么多年并没有变化: 种子的选取,以及随机数序列周期的存在,依然还在.

每一个随机数都被上一个数字计算出来, 也带来一个问题. 就是他们看着像随机数, 但是本质上不是真随机的,一般被称为伪随机数.

冯诺依曼本人曾经嘲讽过这么一句话:

翻译成当代文明话就是: 想用算术方法生成随机数的人都是**.

2重点回顾

前摇结束, 知道了这两点:

每一个随机数是由上一个随机数决定的.
第一个随机数叫种子(seed)

我们现在就可以开始看 Random 的源码了.

3Random 类图

属性图

这里明显能看到, 确实有个 seed.

构造器

这里有两个构造器, 第二个构造器的参数就是种子. 第一个无参构造器,里面会自己产生一个种子,然后继续调用第二个构造器.

我们先来试一下, 用两个种子相同的Random,是不是生成的随机数就一样.

Random a = new Random(1);
Random b = new Random(1);
for (int i = 0; i < 10; i++) {
  System.out.println(
    a.nextLong()+","
           +b.nextLong());
}

//输出还真是一样的.

-4964420948893066024,-4964420948893066024
7564655870752979346,7564655870752979346
3831662765844904176,3831662765844904176
6137546356583794141,6137546356583794141
-594798593157429144,-594798593157429144
112842269129291794,112842269129291794
-669528114487223426,-669528114487223426
-1109287713991315740,-1109287713991315740
-974081879987450628,-974081879987450628
-1160629452687687109,-1160629452687687109

4如何生成不一样的种子?

刚刚的实验结果已经看到了, 种子相同会带来奇怪的随机数相同问题. 那么无参构造器里种子, 是怎么生成的?

public Random() {
      this(seedUniquifier() ^ System.nanoTime());
}

代码倒是好理解, 取纳秒级别的当前时间, 然后异或一个函数seedUniquifier. 因为这里是异或, 所以, 两边只要有一个不一样的就可以.

大多数时候, 时间都是不一样的, 所以肯定种子不一样.主要要处理的是相同时间内的问题, 这时候 seedUniquifier,就是用来生成局部唯一数的.是不是感觉到, 其实这部分跟生成分布式唯一 id 雪花算法有点像.

seedUniquifier

继续看函数 seedUniquifier, 这段就是不断做乘法, 跟上一个 Uniquifier 作比较, 来确保短时间内唯一.这里借助了 CAS 的自旋操作.

for (;;) {
    long current = seedUniquifier.get();
    long next = current * 1181783497276652981L;
    if (seedUniquifier.compareAndSet(current, next))
        return next;
}

最为神奇的代码, 应该还是这句.long next = current * 1181783497276652981L; 盲猜又是和三距离定理相关的内容, 关于这部分我们在ThreadLocal的 hashCode 生成部分介绍过一次了.就不提了. 作用就是让碰撞变的没那么频繁, 这里的自旋消耗小点.

5有了种子以后

有了种子以后, 也并不是直接就使用了,后半句针对子类做的优化不提了, 只看构造器前面部分的代码.

这里用到一个this.seed = new AtomicLong(initialScramble(seed));

内部这个initialScramble的实现是这样的

(seed ^ multiplier) & mask;

先取 mask

mask=(1L << 48) - 1;

这个其实很容易理解, 1 << n, 那他就是只有一个 1,1 的最右边只有 n 个 0. 1L<<48就是 1 后面跟着 48 个 0 的一个数字,是 . 这就是一种快速得到一个连续 48 个 1 的小技巧.

我们画过一次这种神奇的数字,像这种只有一个 1 的数字, -1, 就意味着后面的位置会全部变成 1.

然后, 通过 &mask生成了一个只有 48 位的数字做种.

6生成随机数

这样下来之后, Random 已经构造完成. 剩下的就是根据当前数生成下一个数的算法.

Random 方法这么多, 算法的实现在哪里呢?

核心的算法是这部分

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