Java 常用基础类（六）：随机

1. Java 对随机的支持

• Java 对随机的最基本的支持是 Math 类中的静态方法 random()
• random() 方法生成一个 0 ~ 1 的随机数，类型为 double，包括 0 但不包括 1
• 还有一些基础类，比如 UUID、Math、Objects
  • UUID：用于随机生成需要确保唯一性的标识符
  • Math：用于进行数学运算
  • Objects：包含一些操作对象、检查条件的方法

2. Math.random()方法是怎样实现的

• 源码基于 Java 7

  private static Random randomNumberGenerator;
  
  private static synchronized Random initRNG() {
      Random rnd = randomNumberGenerator;
      return (rnd == null) ? (randomNumberGenerator = new Random()) : rnd;
  }
  
  public static double random() {
      Random rnd = randomNumberGenerator;
      if (rnd == null) rnd = initRNG();
      return rnd.nextDouble();
  }

• random() 方法内部使用了一个 Random 类型的静态变量 randomNumberGenerator，调用 random() 就是调用该变量的 nextDouble() 方法，这个 Random 变量只有在第一次使用的时候才创建

3. 怎样理解 Random 类

• Random 类提供了更为丰富的随机方法，它的方法不是静态方法
  • nextInt() 方法产生一个随机的 int，可能为正数，也可能为负数
  • nextInt(100) 产生一个随机 int，范围是 0 ~ 100，包括 0 不包括 100
  • 除了默认构造方法，Random 类还有一个构造方法，可以接受一个 long 类型的种子参数：public Random(long seed)
• Random 类是线程安全的，即多个线程可以同时使用一个 Random 实例对象；如果并发性很高，会产生竞争，这时可以考虑使用类 ThreadLocalRandom
• Java 类库中还有一个随机类 SecureRandom，可以产生安全性更高、随机性更强的随机数，用于安全加密等领域

4. 为什么要指定种子呢？指定种子还是真正的随机吗

• 指定种子是为了实现可重复的随机
• 比如用于模拟测试程序中，模拟要求随机，但测试要求可重复
• 在北京购车摇号程序中，种子也是指定的

5. 随机的基本原理是怎样的

• Random 产生的随机数并不是真正的随机数。相反，它产生的随机数一般称为伪随机数
• 真正的随机数比较难以产生，计算机程序中的随机数一般都是伪随机数
• 伪随机数都是基于一个种子数的，然后每需要一个随机数，都是对当前种子进行一些数学运算得到一个数，基于这个数得到需要的随机数和新的种子

6. 伪随机数是什么意思

• 数学运算是固定的，所以种子确定后，产生的随机数序列就是确定的，确定的数字序列当然不是真正的随机数。但种子不同，序列就不同，每个序列中数字的分布也都是比较随机和均匀的，所以称之为伪随机数
• 伪随机数并不是真正意义上的完全的随机数，但具有一定的随机特征，所以叫伪随机数（类似于日军和日伪军的概念）

7. Java 中有真正的随机数吗

• 有
• Random 的默认构造方法中没有传递种子，它会自动生成一个种子，这个自动生成的种子数就是一个真正的随机数
• 看 Random 类默认构造方法源码（Java 7）可知，这个真正的种子数是 seedUniquifier() 与 System.nanoTime() 按位异或的结果，具体可查看源码

8. 有了种子数之后，其他数是怎么生成的呢

• nextInt() 方法、nextLong() 方法、nextFloat() 方法、nextBoolean() 方法都调用了 next(int bits) 方法，生成指定位数的随机数
• 查看源码，简单来说，就是使用了如下公式：nextseed = (oldseed * mulitplier + addend) & mask;
  • 随机算法就是：旧的种子（oldseed）乘以一个数（multiplier），加上一个数 addend，然后取低 48 位作为结果（mask）做与运算
  • 这个算法的名称叫线性同余随机数生成器（linear congruential pseudorandom number generator），描述在高德纳老爷子的《计算机程序设计艺术》一书中，随机的理论是一个比较复杂的话题
• 随机的基本原理
  • 随机数基于一个种子数，种子数固定，随机数序列就固定
  • Random 的默认构造方法中，种子是一个真正的随机数

9. 生成一个 6 位数字的随机密码

public static String randomPassword() {
    char[] chars = new char[6];
    Random rnd = new Random();
    for(int i = 0; i < 6; i++) {
        chars[i] = (char) ('0' + rnd.nextInt(10));
    }
    return new String(chars);
}

10. 生成一个简单 8 位的随机密码（要求：密码由大写字母、小写字母、数字和特殊符号组成）

private static final String SPECIAL_CHARS = "!@#$%^&*_+=-/"; // 约定的特殊符号

private static char nextChar(Random rnd) {
    switch(rnd.nextInt(4)) {
        case 0:
            return (char) ('a' + rnd.nextInt(26)); // 小写字母
        case 1:
            return (char) ('A' + rnd.nextInt(26)); // 大写字母
        case 2:
            return (char) ('0' + rnd.nextInt(10)); // 数字
        default:
            return SPECIAL_CHARS.charAt(rnd.nextInt(SPECIAL_CHARS.length())); // 特殊符号
    }
}

public static String randomPassword() {
    char[] chars = new char[8];
    Random rnd = new Random();
    for(int i = 0; i < 8; i++) {
        chars[i] = nextChar(rnd);
    }
    return new String(chars);
}

11. 生成一个复杂 8 位的随机密码（要求：至少包含一个大写字母、一个小写字母、一个特殊符号、一个数字）

//TODO: 感觉有 bug
private static int nextIndex(char[] chars, Random rnd) {
    int index = rnd.nextInt(chars.length);
    while(chars[index] != 0) {
        index = rnd.nextInt(chars.length);
    }
    return index;
}

private static char nextSpecialChar(Random rnd) {
    return SPECIAL_CHARS.charAt(rnd.nextInt(SPECIAL_CHARS.length()));
}

private static char nextUpperLetter(Random rnd) {
    return (char) ('A' + rnd.nextInt(26));
}

private static char nextLowerLetter(Random rnd) {
    return (char) ('a' + rnd.nextInt(26));
}

private static char nextNumLetter(Random rnd) {
    return (char) ('0' + rnd.nextInt(10));
}

public static String randomPassword() {
    char[] chars = new char[8];
    Random rnd = new Random();
    chars[nextIndex(chars, rnd)] = nextSpecialChar(rnd);
    chars[nextIndex(chars, rnd)] = nextUpperLetter(rnd);
    chars[nextIndex(chars, rnd)] = nextLowerLetter(rnd);
    chars[nextIndex(chars, rnd)] = nextNumLetter(rnd);
    for(int i = 0; i < 8; i++) {
        if(chars[i] == 0) {
            chars[i] = nextChar(rnd);
        }
    }
    return new String(chars);
}

12. 随机重排（洗牌）

private static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

public static void shuffle(int[] arr) {
    Random rnd = new Random();
    for(int i = arr.length; i > 1; i--) {
        swap(arr, i - 1, rnd.nextInt(i));
    }
}

int [] arr = new int[13]; //插播一句：前天晚上看的《狗十三》电影很好看
for(int i = 0; i < arr.length; i++) {
    arr[i] = i;
}
shuffle(arr);
System.out.println(Arrays.toString(arr));

13. 带权重的随机选择（累计概率分布、nextDouble()、二分查找）

//表示选项和权重的类 Pair
class Pair {
    Object item;
    int weight;
    public Pair(Object item, int weight) {
        this.item = item;
        this.weight = weight;
    }
    public Object getItem() {
        return item;
    }
    public int getWeight() {
        return weight;
    }
}

//带权重的选择 WeightRandom
public class WeightRandom {
    private Pair[] options;
    private double[] cumulativeProbabilities; //double 类型的累计概率数组
    private Random rnd;
    public WeightRandom(Pair[] options) {
        this.options = options;
        this.rnd = new Random();
        prepare();
    }
    private void  prepare() {
        int weight = 0;
        for(Pair pair : options) {
            weights += pair.getWeight();
        }
        cumulativeProbabilities = new double[options.length];
        int sum = 0;
        for(int i = 0; i < options.length; i++) {
            sum += options[i].getWeight();
            cumulativeProbabhilities[i] = sum / (double) weights;
        }
    }
    public Object nextItem() {
        double randomValue = rnd.nextDouble(); //nextDouble()
        int index = Arrays.binarySearch(cumulativeProbabilities, randomValue); //二分查找
        if(index < 0) {
            index = -index - 1;
        }
        return options[index].getItem();
    }
}

Pair[] options = new Pair[] {new Pair("1 元", 7), new Pair("2 元", 2), new Pair("10 元", 1);};
WeightRandom rnd = new WeightRandom(options);
for(int i = 0; i < 10; i++) {
    System.out.print(rnd.nextItem() + " ");
}

14. 抢红包算法

• Demo：

  public class RandomRedPacket {
      private int leftMoney;
      private int leftNum;
      private Random rnd;
      public RandomRedPacket(int total, int num) {
          this. leftMoney = total;
          this.leftNum = num;
          this.rnd = new Random();
      }
      public synchronized int nextMoney() {
          if(this.leftNum <= 0) {
              throw new IllegalStateException("红包抢光了");
          }
          if(this.leftNum == 1) {
              return this.leftMoney;
          }
          double max  = this.leftMoney / this.leftNum * 2d; //设定随机最大值为平均值的两倍
          int money = (int) (rnd.nextDouble() * max);
          money = Math.max(1, money);
          this.leftMoney -= money;
          this.leftNum --;
          return money;
      }
  }
  
  RandomRedPackey redPackey = new RandomRedPacket(1000, 10);
  for(int i = 0; i < 10; i++) {
      System.out.println(redPacket.nextMoney() + "   ");
  }

• 大概思路：维护一个剩余总金额和总数量，分配时，如果数量等于 1，直接返回总金额；如果大于 1，则计算平均值，并设定随机最大值为平均值的两倍，然后取一个随机值，如果随机值小于 0.01，则为 0.01，这个随机值就是下一个的红包金额。

15. 北京购车摇号算法的大概思路是

• 每期摇号前，将每个符合摇号资格的人，分配一个从 0 到总数的编号，这个编号是公开的
• 摇号第一步是生成一个随机种子数，这个随机种子数在摇号当天通过一定流程生成，整个过程由公证员公证，就是生成一个真正的随机数
• 种子数生成后，然后就是循环调用类似 Random.nextInt(int n) 方法，生成中签的编号
• 编号是事先确定的，种子数是当场公证随机生成的，是公开的；随机算法是公开透明的，任何人都可以根据公开的种子数和编号验证中签的编号