明明谢谢参与的大小跟特等奖的大小一样，可是为什么我们大部分情况还是只能中谢谢参与

发表于 | 分类于

Hello 大家好，我是鸭血粉丝，不知道你有没有过这样的经历，经常在手机上参与各种抽奖，但是明明眼看着就要中特等奖了，但是最后还是中了个谢谢参与，阿粉我就是一个中奖绝缘体，以前总是觉得是自己的运气不好，但是自从知道了背后的暗箱操作过后，阿粉就见怪不怪了。

img

背景

前段时间阿粉参与了一个活动的项目，这个项目有个功能就是在最后会有一个抽奖的页面，用户只要完成最后一步就能参与抽奖，并且奖品有 IPad 等大奖。但是大奖必定是有限制的，总不能无终止的让用户抽取，原本抽奖都是随机的，但是这种情况下肯定不能完全随机，因为要按照奖品的数量进行伪随机。

让数量多的小奖品更容易被抽中，数量少的大奖品被抽中的概率变小，那么在这种情况下，我们可以很自然的想到，我们需要给奖品增加一个权重来满足这个要求了。

设计

我们假设某次抽奖的奖品列表为”谢谢参与“，”50 元话费“，”200 元京东购物卡“，”Java 极客技术知识星球年卡一张“。然后因为经费有限，我们 50 元话费的名额为 100 个，200 元购物卡的 50 个，知识星球年卡 10 个，当然谢谢参与无限量。按照这种情况，我们就需要给每个奖品设置响应的权重值，假设我们这里这几个奖品对应的权重依次为 99，0.7，0.2，0.1，说明中谢谢参与的权重为 99，中年卡的权重为 0.1，为了方便计算我们这里将权重全部放大十倍，调整为 990，7，2，1。

img

思考

为了实现按照权重随机的效果，我们可以把权重想象成x 坐标轴上的位置，在 x 轴上标出每个奖品的范围，如下图所示：

从上图我们可以看出只要范围在 [0, 990) 的就说明中奖谢谢参与，同理 [990, 997) 表示中奖 50 元话费，[997, 999) 表示中奖 200 元京东购物卡，[999, 1000) 表示中奖知识星球年卡一张。

按照这种思路，我们只要随机生成一个数，然后看这个数在哪个范围里面，就能知道中的是什么奖品，而且这个中奖的比例也是跟权重正相关的。根据这个方案，我们需要记录这么几个数，一个是奖品 key，一个是权重 weight，一个是范围的最低值以及范围的最大值。

定义一个类用来存放上面提到的四个属性，如下

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
		@Data
    @NoArgsConstructor
    @AllArgsConstructor
    public static class WeightNode {
        /**
         * 奖品
         **/
        private String key;
        /**
         * 奖品权重
         **/
        private Integer weight;
        /**
         * 最低范围
         **/
        private Integer minValue;
        /**
         * 最高范围
         **/
        private Integer maxValue;

        @Override
        public String toString() {
            return "key:" + this.key + " weight:" + this.weight + " low:" + this.minValue + " height:" + this.maxValue;
        }
    }

在定义一个使用的类

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
public class WeightRandom {

    /**
     * 存储数据节点
     */
    private List<WeightNode> nodes;

    /**
     * 设置数据与权重
     *
     * @param keys    数据
     * @param weights 权重
     */
    public void addNode(String[] keys, Integer[] weights) {
        if (keys == null || weights == null || keys.length != weights.length) {
            return;
        }
        nodes = new ArrayList<>();
        for (int i = 0; i < keys.length; i++) {
            Integer minValue = 0;
            Integer maxValue = 0;
            if (i == 0) {
                minValue = i;
                maxValue = weights[i];
            } else {
                if (i + 1 <= keys.length) {
                    Integer sum = preSum(weights, i);
                    minValue = sum;
                    maxValue = sum + weights[i];
                }
            }
            nodes.add(new WeightNode(keys[i], weights[i], minValue, maxValue));
        }
    }

    /**
     * 累加权重
     *
     * @param array 数组
     * @param index 索引
     * @return 和
     */
    private Integer preSum(Integer[] array, Integer index) {
        Integer sum = 0;
        for (int i = 0; i < array.length; i++) {
            if (i < index) {
                sum += array[i];
            }
        }
        return sum;
    }

    /**
     * 根据生成的随机数遍历所有元素，查找到随机数的范围
     *
     * @param randomValue 生成的随机数
     * @return 范围节点
     */
    public WeightNode getElementByRandomValue(Integer randomValue) {
        //左闭右开
        for (WeightNode e : nodes) {
            if (randomValue >= e.getMinValue() && randomValue < e.getMaxValue()) {
                return e;
            }
        }
        return null;
    }

    /**
     * 在权重是顺序的情况下，可以采用二分法加速查询
     *
     * @param randomValue 生成的随机数
     * @return 范围节点
     */
    public WeightNode getElementByRandomValueBinary(Integer randomValue) {
        if (randomValue < 0 || randomValue > getMaxRandomValue() - 1) {
            return null;
        }
        int start = 0, end = nodes.size() - 1;
        int middle = nodes.size() >> 1;
        while (true) {
            if (randomValue <= nodes.get(middle).getMinValue()) {
                end = middle - 1;
            } else if (randomValue > nodes.get(middle).getMaxValue()) {
                start = middle + 1;
            } else {
                return nodes.get(middle);
            }
            middle = (start + end) >> 1;
        }
    }

    /**
     * 权重总和，用于设置生成随机数的最大上限
     *
     * @return 权重总和
     */
    public Integer getMaxRandomValue() {
        if (CollectionUtils.isEmpty(nodes)) {
            return null;
        }
        return nodes.get(nodes.size() - 1).getMaxValue();
    }

    public static void main(String[] args) {
        WeightRandom wr = new WeightRandom();
//        wr.initWeight(new String[]{"谢谢参与", "50 元话费", "200 元京东购物卡", "星球年卡一张"}, new Integer[]{10, 10, 10, 70});
        wr.addNode(new String[]{"谢谢参与", "50 元话费", "200 元京东购物卡", "星球年卡一张"}, new Integer[]{990, 7, 2, 1});
        Random random = new Random();
        HashMap<String, Integer> keyCount = new HashMap<>(16);
        keyCount.put("谢谢参与", 0);
        keyCount.put("50 元话费", 0);
        keyCount.put("200 元京东购物卡", 0);
        keyCount.put("星球年卡一张", 0);
        for (int i = 0; i < 100000; i++) {
            Integer randomValue = random.nextInt(wr.getMaxRandomValue());
            String key = wr.getElementByRandomValue(randomValue).getKey();
            keyCount.put(key, keyCount.get(key) + 1);
        }
        keyCount.forEach((key, value) -> {
            System.out.println(key + ": " + value);
        });
    }
}

输出的结果：

1
2
3
4
5
6
7
谢谢参与: 99016
Java极客技术知识星球年卡一张: 94
50 元话费: 696
200 元京东购物卡: 194

Process finished with exit code 0

通过输出的结果我们看到，基本是按照我们设置的权重进行随机的。通过上面的示例阿粉带大家设计了一个带权重的随机实现方案，除了在抽奖的场景会使用的，在其他类似的场景也可以使用。

参考

https://yq.aliyun.com/articles/269456

写在最后

最后邀请你加入我们的知识星球，这里有 1700+ 优秀的人与你一起进步，如果你是小白那你是稳赚了，很多业内经验和干活分享给你；如果你是大佬，那可以进来我们一起交流分享你的经验，说不定日后我们还可以有合作，给你的人生多一个可能。

image-20200205235453492

Java Geek Tech wechat
欢迎订阅 Java 极客技术，这里分享关于 Java 的一切。