首页 > 代码库 > 计算机程序的思维逻辑 (34) - 随机
计算机程序的思维逻辑 (34) - 随机
随机
本节，我们来讨论随机，随机是计算机程序中一个非常常见的需求，比如说：
- 各种游戏中有大量的随机，比如扑克游戏洗牌
- 微信抢红包，抢的红包金额是随机的
- 北京购车摇号，谁能摇到是随机的
- 给用户生成随机密码
我们首先来介绍Java中对随机的支持，同时介绍其实现原理，然后我们针对一些实际场景，包括洗牌、抢红包、摇号、随机高强度密码、带权重的随机选择等，讨论如何应用随机。
先来看如何使用最基本的随机。
Math.random
Java中，对随机最基本的支持是Math类中的静态方法random，它生成一个0到1的随机数，类型为double，包括0但不包括1，比如，随机生成并输出3个数：
for(int i=0;i<3;i++){ System.out.println(Math.random());}
我的电脑上的一次运行，输出为：
0.47848961338232690.030125156283334230.7921024363953197
每次运行，输出都不一样。
Math.random()是如何实现的呢？我们来看相关代码：
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类型的静态变量randomNumberGenerator，调用random()就是调用该变量的nextDouble()方法，这个Random变量只有在第一次使用的时候才创建。
下面我们来看这个Random类，它位于包java.util下。
Random
基本用法
Random类提供了更为丰富的随机方法，它的方法不是静态方法，使用Random，先要创建一个Random实例，看个例子：
Random rnd = new Random();System.out.println(rnd.nextInt());System.out.println(rnd.nextInt(100));
我的电脑上的一次运行，输出为：
-151661260823
nextInt()产生一个随机的int，可能为正数，也可能为负数，nextInt(100)产生一个随机int，范围是0到100，包括0不包括100。
除了nextInt，还有一些别的方法。
随机生成一个long
public long nextLong()
随机生成一个boolean
public boolean nextBoolean()
产生随机字节
public void nextBytes(byte[] bytes)
随机产生的字节放入提供的byte数组bytes，字节个数就是bytes的长度。
产生随机浮点数，从0到1，包括0不包括1
public float nextFloat()public double nextDouble()
设置种子
除了默认构造方法，Random类还有一个构造方法，可以接受一个long类型的种子参数：
public Random(long seed)
种子决定了随机产生的序列，种子相同，产生的随机数序列就是相同的。看个例子：
Random rnd = new Random(20160824);for(int i=0;i<5;i++){ System.out.print(rnd.nextInt(100)+" ");}
种子为20160824，产生5个0到100的随机数，输出为：
69 13 13 94 50
这个程序无论执行多少遍，在哪执行，输出结果都是相同的。
除了在构造方法中指定种子，Random类还有一个setter实例方法：
synchronized public void setSeed(long seed)
其效果与在构造方法中指定种子是一样的。
为什么要指定种子呢？指定种子还是真正的随机吗？
指定种子是为了实现可重复的随机。比如用于模拟测试程序中，模拟要求随机，但测试要求可重复。在北京购车摇号程序中，种子也是指定的，后面我们还会介绍。
种子到底扮演了什么角色呢？随机到底是如何产生的呢？让我们看下随机的基本原理。
随机的基本原理
Random产生的随机数不是真正的随机数，相反，它产生的随机数一般称之为伪随机数，真正的随机数比较难以产生，计算机程序中的随机数一般都是伪随机数。
伪随机数都是基于一个种子数的，然后每需要一个随机数，都是对当前种子进行一些数学运算，得到一个数，基于这个数得到需要的随机数和新的种子。
数学运算是固定的，所以种子确定后，产生的随机数序列就是确定的，确定的数字序列当然不是真正的随机数，但种子不同，序列就不同，每个序列中数字的分布也都是比较随机和均匀的，所以称之为伪随机数。
Random的默认构造方法中没有传递种子，它会自动生成一个种子，这个种子数是一个真正的随机数，代码如下：
private static final AtomicLong seedUniquifier = new AtomicLong(8682522807148012L); public Random() { this(seedUniquifier() ^ System.nanoTime());}private static long seedUniquifier() { for (;;) { long current = seedUniquifier.get(); long next = current * 181783497276652981L; if (seedUniquifier.compareAndSet(current, next)) return next; }}
种子是seedUniquifier() 与System.nanoTime()按位异或的结果，System.nanoTime()返回一个更高精度(纳秒)的当前时间，seedUniquifier()里面的代码涉及一些多线程相关的知识，我们后续章节再介绍，简单的说，就是返回当前seedUniquifier(current)与一个常数181783497276652981L相乘的结果(next)，然后，将seedUniquifier设置为next，使用循环和compareAndSet都是为了确保在多线程的环境下不会有两次调用返回相同的值，保证随机性。
有了种子数之后，其他数是怎么生成的呢？我们来看一些代码：
public int nextInt() { return next(32);}public long nextLong() { return ((long)(next(32)) << 32) + next(32);}public float nextFloat() { return next(24) / ((float)(1 << 24));}public boolean nextBoolean() { return next(1) != 0;}
它们都调用了next(int bits)，生成指定位数的随机数，我们来看下它的代码：
private static final long multiplier = 0x5DEECE66DL;private static final long addend = 0xBL;private static final long mask = (1L << 48) - 1;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));}
简单的说，就是使用了如下公式：
nextseed = (oldseed * multiplier + addend) & mask;
旧的种子(oldseed)乘以一个数(multiplier)，加上一个数addend，然后取低48位作为结果(mask相与)。
为什么采用这个方法？这个方法为什么可以产生随机数？这个方法的名称叫线性同余随机数生成器(linear congruential pseudorandom number generator)，描述在《计算机程序设计艺术》一书中。随机的理论是一个比较复杂的话题，超出了本文的范畴，我们就不讨论了。
我们需要知道的基本原理是，随机数基于一个种子，种子固定，随机数序列就固定，默认构造方法中，种子是一个真正的随机数。
理解了随机的基本概念和原理，我们来看一些应用场景，从产生随机密码开始。
随机密码
在给用户生成账号时，经常需要给用户生成一个默认随机密码，然后通过邮件或短信发给用户，作为初次登录使用。
我们假定密码是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);}
代码很简单，就不解释了。如果要求是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);}
这个代码，对每个字符，先随机选类型，然后在给定类型中随机选字符。在我的电脑上，一次的随机运行结果是：
8Ctp2S4H
这个结果不含特殊字符，很多环境对密码复杂度有要求，比如说，至少要含一个大写字母、一个小写字母、一个特殊符号、一个数字。以上的代码满足不了这个要求，怎么满足呢？一种可能的代码是：
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 nextUpperlLetter(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)] = nextUpperlLetter(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);}
nextIndex随机生成一个未赋值的位置，程序先随机生成四个不同类型的字符，放到随机位置上，然后给未赋值的其他位置随机生成字符。
洗牌
一种常见的随机场景是洗牌，就是将一个数组或序列随机重新排列，我们以一个整数数组为例来看，怎么随机重排呢？我们直接看代码：
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)); }}
shuffle这个方法就能将参数数组arr随机重排，来看使用它的代码：
int[] arr = new int[13];for(int i=0; i<arr.length; i++){ arr[i] = i;}shuffle(arr);System.out.println(Arrays.toString(arr));
调用shuffle前，arr是排好序的，调用后，一次调用的输出为：
[3, 8, 11, 10, 7, 9, 4, 1, 6, 12, 5, 0, 2]
已经随机重新排序了。
shuffle的基本思路是什么呢？从后往前，逐个给每个数组位置重新赋值，值是从剩下的元素中随机挑选的。在如下关键语句中，
swap(arr, i-1, rnd.nextInt(i));
i-1表示当前要赋值的位置，rnd.nextInt(i)表示从剩下的元素中随机挑选。
带权重的随机选择
实际场景中，经常要从多个选项中随机选择一个，不过，不同选项经常有不同的权重。
比如说，给用户随机奖励，三种面额，1元、5元和10元，权重分别为70, 20和10。这个怎么实现呢？
实现的基本思路是，使用概率中的累计概率分布。
以上面的例子来说，计算每个选项的累计概率值，首先计算总的权重，这里正好是100，每个选项的概率是70%，20%和10%，累计概率则分别是70%，90%和100%。
有了累计概率，则随机选择的过程是，使用nextDouble()生成一个0到1的随机数，然后使用二分查找，看其落入那个区间，如果小于等于70%则选择第一个选项，70%和90%之间选第二个，90%以上选第三个，如下图示所示：
下面来看代码，我们使用一个类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; private Random rnd; public WeightRandom(Pair[] options){ this.options = options; this.rnd = new Random(); prepare(); } private void prepare(){ int weights = 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(); cumulativeProbabilities[i] = sum / (double)weights; } } public Object nextItem(){ double randomValue =http://www.mamicode.com/ rnd.nextDouble(); int index = Arrays.binarySearch(cumulativeProbabilities, randomValue); if (index < 0) { index = -index-1; } return options[index].getItem(); }}
其中，prepare方法计算每个选项的累计概率，保存在数组cumulativeProbabilities中，nextItem()根据权重随机选择一个，具体就是，首先生成一个0到1的数，然后使用二分查找，以前介绍过，如果没找到，返回结果是-(插入点)-1，所以-index-1就是插入点，插入点的位置就对应选项的索引。
回到上面的例子，随机选择10次，代码为：
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()+" ");}
在一次运行中，输出正好符合预期，具体为：
1元 1元 1元 2元 1元 10元 1元 2元 1元 1元
不过，需要说明的，由于随机，每次执行结果比例不一定正好相等。
抢红包算法
我们都知道，微信可以抢红包，红包有一个总金额和总数量，领的时候随机分配金额，金额是怎么随机分配的呢？微信具体是怎么做的，我们并不能确切的知道，根据一些公开资料，思路可能如下。
维护一个剩余总金额和总数量，分配时，如果数量等于1，直接返回总金额，如果大于1，则计算平均值，并设定随机最大值为平均值的两倍，然后取一个随机值，如果随机值小于0.01，则为0.01，这个随机值就是下一个的红包金额。
我们来看代码，为计算方便，金额我们用整数表示，以分为单位。
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; }}
代码比较简单，就不解释了。我们来看一个使用的例子，总金额为10元，10个红包，代码如下：
RandomRedPacket redPacket = new RandomRedPacket(1000, 10);for(int i=0; i<10; i++){ System.out.print(redPacket.nextMoney()+" ");}
一次输出为：
136 48 90 151 36 178 92 18 122 129
如果是这个算法，那先抢好，还是后抢好呢？先抢肯定抢不到特别大的，不过，后抢也不一定会，这要看前面抢的金额，剩下的多就有可能抢到大的，剩下的少就不可能有大的。
北京购车摇号算法
我们来看下影响很多人的北京购车摇号，它的算法是怎样的呢？根据公开资料，它的算法大概是这样的。
- 每期摇号前，将每个符合摇号资格的人，分配一个从0到总数的编号，这个编号是公开的，比如总人数为2304567，则编号从0到2304566。
- 摇号第一步是生成一个随机种子数，这个随机种子数在摇号当天通过一定流程生成，整个过程由公证员公证，就是生成一个真正的随机数。
- 种子数生成后，然后就是循环调用类似Random.nextInt(int n)方法，生成中签的编号。
编号是事先确定的，种子数是当场公证随机生成的，公开的，随机算法是公开透明的，任何人都可以根据公开的种子数和编号验证中签的编号。
一些说明
需要说明的是，Random类是线程安全的，也就是说，多个线程可以同时使用一个Random实例对象，不过，如果并发性很高，会产生竞争，这时，可以考虑使用多线程库中的ThreadLocalRandom类。
另外，Java类库中还有一个随机类SecureRandom，以产生安全性更高、随机性更强的随机数，用于安全加密等领域。
这两个类本文就不介绍了。
小结
本节介绍了随机，介绍了Java中对随机的支持Math.random()以及Random类，介绍了其使用和实现原理，同时，我们介绍了随机的一些应用场景，包括随机密码、洗牌、带权重的随机选择、微信抢红包和北京购车摇号。
至此，关于一些基本常用类的介绍，我们就告一段落了，回顾一下，我们深入剖析了各种包装类、String、StringBuilder、Arrays、日期和时间、Joda-Time以及随机，这些都是日常程序中经常用到的功能。
之前章节中，我们经常提到泛型这一概念，是时候具体讨论一下了。
----------------
未完待续，查看最新文章，敬请关注微信公众号“老马说编程”(扫描下方二维码)，从入门到高级，深入浅出，老马和你一起探索Java编程及计算机技术的本质。用心写作，原创文章，保留所有版权。
计算机程序的思维逻辑 (34) - 随机