基于java.lang.Math.Random()的近似均匀分布特性实现的抽奖算法

在电商促销或一些直播小游戏中，抽奖是一种比较常见的玩法。很多时候，展现给用户的可能是一个大转盘，如下：

通常我们会给出一堆奖品，每个奖品有各自的中奖概率，而且每个奖品可能还有库存的概念，就是说已经被抽完了的奖品是不再参与抽奖的。就拿陌陌里的这个大转盘来举例，奖品列表有爱心火箭、私人飞机、旋转木马、梦幻香水、口红、暖心奶茶、糖果、未中奖（未中奖可以看着是特殊的奖品）等8个奖品，每个奖品会根据其价值有不同的中奖概率，比如中糖果和暖心奶茶的概率高些，但中火箭的概率可能低很多。如果让你用java实现一个抽奖，你会怎么实现它呢？这正是我们今天要探讨的内容。

抽奖算法

在Java中，java.lang.Math.Random()方法本身基本可以保证大量测试的情况下避免高重复，且概率分布比较平均。所以我们根据奖品的概率列表基于java.lang.Math.Random()方法实现一个抽奖的工具类：

1. 根据奖品的中奖概率列表probabilityList计算总概率sumRate；
2. 根据总概率和各个奖品的概率对概率进行分块，得到分块列表blockList，比如传过来的概率列表是｛0.25,0.15,0.6｝,那么分块区间就是0-0.25，0.25-0.4,0.4-1.0，blockList的集合就是{0.25,0.4,1.0}；
3. 根据java.lang.Math.Random()平均概率返回0到1之间数字的特性得到nextDouble;
4. 把nextDouble的值按大小顺序插入到blockList中；
5. 返回nextDouble插入的位置

package cn.lovecto.util;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 抽奖工具类
 *
 */
public class LotteryDrawUtil {

    /**
     * 根据中奖概率列表进行抽奖，返回被抽中的概率的index
     * 
     * @param probabilityList
     * @return
     */
    public static int lottery(List<Double> probabilityList) {
        if (probabilityList == null || probabilityList.isEmpty()) {
            return -1;
        }
        int lotteryBlockSize = probabilityList.size();
        // 计算总概率，这样可以保证不一定总概率是1
        double sumRate = 0d;
        for (double rate : probabilityList) {
            sumRate += rate;
        }
        // 对应奖品概率分块
        List<Double> blockList = new ArrayList<Double>(lotteryBlockSize);
        Double tempSumRate = 0d;
        // 比如传过来的list是｛0.25,0.15,0.6｝,那么分块区间就是0-0.25，0.25-0.4,0.4-1
        for (double rate : probabilityList) {
            tempSumRate += rate;
            blockList.add(tempSumRate / sumRate);
        }
        // 根据java的random平均概率返回0到1之间数字的特性
        double nextDouble = Math.random();
        blockList.add(nextDouble);
        // 把数字放到上面的分块区间中,比如nextDouble是0.3，那么就是在第二个分块区间中，则中第二个概率对应的奖品
        Collections.sort(blockList);
        return blockList.indexOf(nextDouble);
    }
}

抽奖逻辑

有了上面的抽奖算法，接下来我们分析下抽奖的逻辑是怎么实现的。为了更贴近使用场景，除了每个奖品有中奖概率外，增加一个库存的概念。因为有时候大奖并不是无限的，可能只有一个。在促销活动进行过程中，运营人员不一定一开始就把大奖的库存放出来，毕竟留在后面才更有悬念，如果大奖一放出来就被抽走了，用户的参与热情估计就没了，因为大家都是冲着大奖来的，就跟买彩票只想中500万一个道理。

定义一个奖品类Award，属性包含奖品名称、中奖概率、库存等。

package cn.lovecto.model;

public class Award {
    /**奖品名称*/
    private String name;
    /**概率*/
    private Double probability;
    /**库存,为null表示库存无限*/
    private Integer inventory = null;

    public Award(String name, Double probability, Integer inventory) {
        super();
        this.name = name;
        this.probability = probability;
        this.inventory = inventory;
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public Double getProbability() {
        return probability;
    }
    public void setProbability(Double probability) {
        this.probability = probability;
    }
    public Integer getInventory() {
        return inventory;
    }
    public void setInventory(Integer inventory) {
        this.inventory = inventory;
    }
    /***
     * 库存是否空了
     * @return
     */
    public boolean isInventoryEmpty(){
        if(this.inventory != null && this.inventory <= 0){
            return true;
        }
        return false;
    }
}

接下来，我们模拟一下抽奖逻辑：

package cn.lovecto.util;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

import org.junit.Test;

import cn.lovecto.model.Award;

public class LotteryDrawUtilTest {

    @Test
    public void lottery() {
        // 奖品
        List<Award> awards = queryAeardsSortByProbability();
        // 中奖的奖品序号
        int index = -1;
        // 中奖奖品
        Award award = null;
        // 进行10次抽奖
        for (int i = 1; i <= 10; i++) {
            // 移除掉库存为空的奖品
            removeEmptyInventoryAwards(awards);
            // System.out.println(awards.size());
            // 抽奖
            index = LotteryDrawUtil.lottery(valuesAwardProbability(awards));
            award = awards.get(index);
            // 扣减库存，此处只是单线程测试，实际环境中还要考虑分布式事务多线程等问题
            if (award.getInventory() != null) {
                award.setInventory(award.getInventory() - 1);
            }
            System.out.println(String.format("第%d次抽奖抽中奖品为：%s", i,
                    award.getName()));
        }
    }

    /**
     * 移除掉库存为空的奖品
     * 
     * @param awards
     */
    private void removeEmptyInventoryAwards(List<Award> awards) {
        Iterator<Award> it = awards.iterator();
        while (it.hasNext()) {
            Award a = it.next();
            if (a.isInventoryEmpty()) {
                it.remove();
            }
        }
    }

    /**
     * 获取奖品概率列表
     * 
     * @param awards
     * @return
     */
    private List<Double> valuesAwardProbability(List<Award> awards) {
        List<Double> values = new ArrayList<Double>();
        for (Award a : awards) {
            values.add(a.getProbability());
        }
        return values;
    }

    /**
     * 获取参与抽奖的奖品,返回结果按照中奖概率排序,奖品概率之和尽量等于1
     * 
     * @return
     */
    private List<Award> queryAeardsSortByProbability() {
        List<Award> awards = new ArrayList<Award>();
        // 爱心火箭、私人飞机、旋转木马、梦幻香水、口红、暖心奶茶、糖果、未中奖
        awards.add(new Award("爱心火箭", 0.01d, 1));
        awards.add(new Award("私人飞机", 0.02d, 1));
        awards.add(new Award("旋转木马", 0.03d, 1));
        awards.add(new Award("梦幻香水", 0.04d, 1));
        awards.add(new Award("口红", 0.10d, 1));
        awards.add(new Award("暖心奶茶", 0.10d, 1));
        awards.add(new Award("糖果", 0.30d, 1));
        // 未中奖库存永远充足
        awards.add(new Award("未中奖", 0.40d, null));
        return awards;
    }

}

运行结果类似：

第1次抽奖抽中奖品为：糖果
第2次抽奖抽中奖品为：口红
第3次抽奖抽中奖品为：爱心火箭
第4次抽奖抽中奖品为：未中奖
第5次抽奖抽中奖品为：未中奖
第6次抽奖抽中奖品为：未中奖
第7次抽奖抽中奖品为：暖心奶茶
第8次抽奖抽中奖品为：未中奖
第9次抽奖抽中奖品为：未中奖
第10次抽奖抽中奖品为：未中奖

抽奖逻辑注意事项

上面的抽奖逻辑只是简单的单线程模拟抽奖算法的有效性，在生产环境中，还需要注意线程安全性、分布式事务等问题，抽奖都是高并发场景下，所以要处理好库存扣减以及库存扣减失败重抽等细节。