0%

Java 常用基础类(六):随机

1. Java 对随机的支持

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

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

  • 源码基于 Java 7:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    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 位数字的随机密码

1
2
3
4
5
6
7
8
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 位的随机密码(要求:密码由大写字母、小写字母、数字和特殊符号组成)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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 位的随机密码(要求:至少包含一个大写字母、一个小写字母、一个特殊符号、一个数字)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//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. 随机重排(洗牌)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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()、二分查找)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
//表示选项和权重的类 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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    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) 方法,生成中签的编号
  • 编号是事先确定的,种子数是当场公证随机生成的,是公开的;随机算法是公开透明的,任何人都可以根据公开的种子数和编号验证中签的编号。
-------------------- 本文结束感谢您的阅读 --------------------