基于 Hutool 的抽奖实现与原理

前言

先大概描述下 hutool 工具是如何根据权重进行抽取后面再结合源码进行讲解。
假设有如下奖品以及对应的权重

奖品名称	权重	奖品数量
谢谢参与	0.7	60
10积分	0.45	50
IPhone 14	0.05	5
Mac Book Air	0.01	1

需要注意 谢谢参与 也算是一种奖品因为它也能被抽中。

hutool 的工具会根据 总权重 * 随机数 得到一个随机的权重然后取第一个大于等于该 随机权重 的奖品作为抽中的结果。

说白了就是将奖品按如下分割出自己的区域然后随机生成一个在范围内的数看这个数落在哪一个区间上面。

代码实现

导入 Maven 依赖或者自行前往 Hutool 官网下载 jar 包

<dependency>
    <groupId>cn.hutool</groupId>
    <artifactId>hutool-all</artifactId>
    <version>5.8.11</version>
</dependency>
<dependency>
    <groupId>org.projectlombok</groupId>
    <artifactId>lombok</artifactId>
    <optional>true</optional>
</dependency>

抽奖代码实现

/**
 * 抽奖实现
 *
 * @author thai
 */
public class LuckyDraw {

    public static void main(String[] args) {
        List<Prize> prizes = List.of(
                new Prize("谢谢参与", 60, 0.7),
                new Prize("IPhone 14", 5, 0.05),
                new Prize("Mac Air M2", 1, 0.01),
                new Prize("10 积分", 50, 0.45)
        );
        List<WeightRandom.WeightObj<Prize>> weightObjs = prizes.stream()
                .map(p -> new WeightRandom.WeightObj<>(p, p.getProbability()))
                .collect(Collectors.toList());

        WeightRandom<Prize> weightRandom = RandomUtil.weightRandom(weightObjs);
        // 连续抽奖 100 次抽中结果如下
        for (int i = 0; i < 100; i++) {
            Prize prize = weightRandom.next();
            // 抽到某个奖品小于等于 0 的直接打印谢谢参与
            if (prize.getQuantity() <= 0) {
                System.out.println("谢谢参与");
                continue;
            }
            prize.setQuantity(prize.getQuantity() - 1);
            System.out.println("恭喜您抽到了" + prize.getName());
        }
    }

    @Data
    @AllArgsConstructor
    static class Prize {
        /**
         * 奖品名称
         */
        private String name;

        /**
         * 奖品数量
         */
        private int quantity;

        /**
         * 中奖概率
         */
        private double probability;
    }

}

执行上面的代码打印出的结果如下

恭喜您抽到了10 积分
恭喜您抽到了10 积分
恭喜您抽到了谢谢参与
恭喜您抽到了谢谢参与
...
恭喜您抽到了10 积分
恭喜您抽到了IPhone 14
恭喜您抽到了谢谢参与

Hutool 根据权重抽取的原理分析

在构造 WeightRandom 对象时实际会将它们添加到一个 TreeMap 中

public WeightRandom(Iterable<WeightObj<T>> weightObjs) {
	// 初始化 TreeMap
	this();
	if(CollUtil.isNotEmpty(weightObjs)) {
		for (WeightObj<T> weightObj : weightObjs) {
			add(weightObj);
		}
	}
}
/**
 * 增加对象权重
 *
 * @param weightObj 权重对象
 * @return this
 */
public WeightRandom<T> add(WeightObj<T> weightObj) {
	if(null != weightObj) {
		final double weight = weightObj.getWeight();
		if(weightObj.getWeight() > 0) {
			/* 
			 由于 key 为权重这一步做的工作其实就是将所有的权重累加起来
			 lastWeight 其实就是在这之前所有权重之和那么后面获取总权重
			 只需要拿 Map 最后一个 key 就可以了
			*/
			double lastWeight = (this.weightMap.size() == 0) ? 0 : this.weightMap.lastKey();
			this.weightMap.put(weight + lastWeight, weightObj.getObj());
		}
	}
	return this;
}

让我们再看看核心的 weightRandom.next() 方法

/**
 * 下一个随机对象
 *
 * @return 随机对象
 */
public T next() {
	if(MapUtil.isEmpty(this.weightMap)) {
		return null;
	}
	final Random random = RandomUtil.getRandom();
	// 总权重 * 随机数这里的随机数范围在 [0.0, 1.0) 之间
	final double randomWeight = this.weightMap.lastKey() * random.nextDouble();
	// tailMap 表示从 Map 中截取大于等于 randomWeight 的 key 数据
	final SortedMap<Double, T> tailMap = this.weightMap.tailMap(randomWeight, false);
	// 取第一个 key
	return this.weightMap.get(tailMap.firstKey());
}

补充说明

对上述 tailMap 的一个补充说明

    public static void main(String[] args) {
        TreeMap<Integer, Integer> treeMap = new TreeMap<>();
        treeMap.put(1, 1);
        treeMap.put(2, 2);
        treeMap.put(3, 3);
        treeMap.put(4, 4);

        SortedMap<Integer, Integer> sortedMap = treeMap.tailMap(2);
        // 输出{2=2, 3=3, 4=4}
        System.out.println(sortedMap);
    }