SpringBoot2实现转盘抽奖接口--使用TreeMap实现权重随机算法

「爱情、让人受尽委屈。」 2021-11-11 06:06 365阅读 0赞

# 背景： #

公司每次节日都会有各种活动，其中转盘抽奖肯定是必不可少的。以前这些都是找其他公司做的小程序小游戏，现在招了个前端专门搞小程序了，那么之后肯定我们后端就得提供接口给他们用了。转盘抽奖，最常见的就是使用权重随机算法，其实很多地方会使用到这算法，例如路由的负载均衡、dubbo的服务调用等等。

# 需求与实现： #

/**
     * 转盘抽奖需求：一共有三个奖项，一等奖中奖率10%、二等奖中奖率20%、三等奖中奖率70%
     * 奖品一共有十份，三等奖五份、二等奖三份、一等奖两份。十份抽完就没了。
     * 奖品也有抽中概率：三等奖的分别是30%、30%、20%、10%、10%。二等奖的分别是40%、30%、30%。一等奖的分别是70、30%
     *
     *
     * 需求实现：三个奖项还是使用权重随机算法：[0,10)是一等奖，[10,30)是二等奖，[30,100)是三等奖
     *         三等奖使用权重随机算法：[0-10)是奖品一，[10-20)是奖品二，[30-50)是奖品三，[50-70)是奖品四，[70-100)是奖品五
     *         二等奖使用权重随机算法：[0-30)是奖品一，[30-60)是奖品二，[60-100)是奖品三
     *         一等奖使用权重随机算法：[0-30)是奖品一，[70-100)是奖品二
     *
     */

我们可以发现，我们使用if判断就可以搞定这个需求，但是呢，还有一个数据结构更适合这个需求，而且不用多余的if判断代码，性能还非常的不错，那就是TreeMap了，我们最主要是利用它的红黑树特性，在代码实现后会简单介绍TreeMap，特别是put方法。

# 实现： #

首先准备数据库：三个表，奖项表，奖品表，中奖记录表

CREATE TABLE `turntable_draw` (
      `id` bigint(20) unsigned NOT NULL AUTO_INCREMENT COMMENT 'ID',
      `draw_name` varchar(30) NOT NULL COMMENT '姓名',
      `weight` double(5,2) NOT NULL COMMENT '权重',
      `prize_num` int(11) DEFAULT NULL COMMENT '奖品数量',
      PRIMARY KEY (`id`)
    ) ENGINE=InnoDB AUTO_INCREMENT=4 DEFAULT CHARSET=utf8mb4 COMMENT='转盘抽奖-奖项表';
    
    CREATE TABLE `turntable_prize` (
      `id` bigint(20) unsigned NOT NULL AUTO_INCREMENT COMMENT '主键',
    	`draw_id` BIGINT(20) UNSIGNED not null comment '奖项ID',
      `prize_name` varchar(30) NOT NULL COMMENT '姓名',
      `weight` DOUBLE(5,2)	NOT NULL COMMENT '权重',
      PRIMARY KEY (`id`)
    ) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8mb4 COMMENT='转盘抽奖-奖品表';
    
    CREATE TABLE `turntable_record` (
      `id` bigint(20) unsigned NOT NULL AUTO_INCREMENT COMMENT '主键',
    	`prize_id` BIGINT(20) UNSIGNED not null comment '奖项ID',
      `prize_name` varchar(30) NOT NULL COMMENT '奖品名称',
      `phone` varchar(11)	NOT NULL COMMENT '中奖人手机号码',
      PRIMARY KEY (`id`)
    ) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8mb4 COMMENT='转盘抽奖-中奖纪录表';

最核心的抽奖工具类：TurntableDrawUtils。首先是单例的，然后有一个TreeMap类型的成员变量，在初始化方法中查询数据库中的奖项和对应的奖品，然后将数据存入成员变量中。最后有一个抽奖的方法，为了防止并发问题，对里面的抽奖代码块进行锁，锁对象为TreeMap类型的成员变量。下面看一下代码：

package com.hyf.algorithm.抽奖概率.config;
    
    import com.hyf.algorithm.抽奖概率.entity.TurntableDraw;
    import com.hyf.algorithm.抽奖概率.entity.TurntablePrize;
    import com.hyf.algorithm.抽奖概率.entity.TurntableRecord;
    import com.hyf.algorithm.抽奖概率.mapper.TurntableMapper;
    import org.springframework.beans.factory.annotation.Autowired;
    import org.springframework.context.annotation.Scope;
    import org.springframework.stereotype.Component;
    
    import javax.annotation.PostConstruct;
    import java.util.List;
    import java.util.SortedMap;
    import java.util.TreeMap;
    
    import static org.springframework.beans.factory.config.ConfigurableBeanFactory.SCOPE_SINGLETON;
    
    /**
     * @author Howinfun
     * @desc 抽奖工具，单例
     * @date 2019/8/5
     */
    @Component
    @Scope(SCOPE_SINGLETON)
    public class TurntableDrawUtils {
    
        @Autowired
        private TurntableMapper turntableMapper;
        /** 转盘抽奖TreeMap，因为TurntableDrawInit是单例的，所以treeMap全局只有一份 */
        private final TreeMap<Double,TreeMap<Double,TurntablePrize>> treeMap = new TreeMap<>();
        /** 私有化构造函数 */
        private TurntableDrawUtils(){}
    
        /**
         * 初始化
         */
        @PostConstruct
        public void init(){
            List<TurntableDraw> drawList = turntableMapper.getDraw();
            if (drawList != null && drawList.size() > 0){
                // 遍历奖项
                for (TurntableDraw draw : drawList) {
                    TreeMap<Double,TurntablePrize> drawTreeMap = new TreeMap<>();
                    List<TurntablePrize> prizeList = turntableMapper.getPrizeByDraw(draw.getId());
                    // 遍历奖品
                    for (TurntablePrize prize : prizeList) {
                        System.out.print(prize);
                        drawTreeMap.put(prize.getWeight(),prize);
                    }
                    treeMap.put(draw.getWeight(),drawTreeMap);
                }
            }
        }
    
        public TurntablePrize turntableDraw(String phone){
            TurntablePrize prize;
            // 加锁，防止并发问题
            synchronized (this.treeMap){
                // 如果还有奖项则进行抽奖
                if (treeMap.size() > 0){
                    // 奖项随机数
                    Double random = treeMap.lastKey()*Math.random();
                    SortedMap<Double, TreeMap<Double,TurntablePrize>> prizeMap = treeMap.tailMap(random,false);
                    // 抽中的奖项
                    Double drawKey = prizeMap.firstKey();
                    TreeMap<Double,TurntablePrize> draw = prizeMap.get(drawKey);
                    // 奖品随机数
                    Double prizeRandom = draw.lastKey()*Math.random();
                    SortedMap<Double,TurntablePrize> resultMap = draw.tailMap(prizeRandom,false);
                    // 抽中的奖品
                    Double prizeKey = resultMap.firstKey();
                    prize = resultMap.get(prizeKey);
                    // 插入抽象记录
                    TurntableRecord record = new TurntableRecord();
                    record.setPrizeId(prize.getId());
                    record.setPrizeName(prize.getPrizeName());
                    record.setPhone(phone);
                    turntableMapper.insertRecord(record);
                    // 奖项的奖品数减一
                    turntableMapper.delPrizeNumByDraw(prize.getDrawId());
                    // 移除抽中的奖品
                    treeMap.get(drawKey).remove(prizeKey);
                    // 判断奖项是否还有奖品，如果没有则将奖项也移除
                    if (treeMap.get(drawKey).size() <=0 ){
                        treeMap.remove(drawKey);
                    }
                }else{
                    prize = null;
                }
            }
            return prize;
        }
    }

Service层直接调用turntableDraw方法返回即可，Controler再稍作判断组合信息返回给前端，就这么简单。

package com.hyf.algorithm.抽奖概率.service.impl;
    
    import com.hyf.algorithm.抽奖概率.config.TurntableDrawUtils;
    import com.hyf.algorithm.抽奖概率.entity.TurntablePrize;
    import com.hyf.algorithm.抽奖概率.service.TurntableService;
    import org.springframework.beans.factory.annotation.Autowired;
    import org.springframework.stereotype.Service;
    
    /**
     * @author Howinfun
     * @desc
     * @date 2019/8/5
     */
    @Service
    public class TurntableServiceImpl implements TurntableService {
    
        @Autowired
        private TurntableDrawUtils drawUtils;
    
        @Override
        public TurntablePrize turntableDraw(String phone) {
            return drawUtils.turntableDraw(phone);
        }
    }

package com.hyf.algorithm.抽奖概率.controller;
    
    import com.hyf.algorithm.抽奖概率.common.Result;
    import com.hyf.algorithm.抽奖概率.entity.TurntablePrize;
    import com.hyf.algorithm.抽奖概率.service.TurntableService;
    import org.springframework.beans.factory.annotation.Autowired;
    import org.springframework.web.bind.annotation.GetMapping;
    import org.springframework.web.bind.annotation.RequestMapping;
    import org.springframework.web.bind.annotation.RequestParam;
    import org.springframework.web.bind.annotation.RestController;
    
    /**
     * @author Howinfun
     * @desc 抽奖Controller
     * @date 2019/8/5
     */
    @RestController
    @RequestMapping("/turntable")
    public class TurntableController {
    
        @Autowired
        private TurntableService turntableService;
    
        @GetMapping("/draw")
        public Result<TurntablePrize> turntableDraw(@RequestParam("phone") String phone){
            Result result = new Result();
            TurntablePrize prize =  turntableService.turntableDraw(phone);
            result.setData(prize);
            if (prize == null){
                result.setMsg("奖品已抽完");
            }else {
                result.setMsg("恭喜获得"+prize.getPrizeName());
            }
            return result;
        }
    }

如果大家多此小demo有兴趣的话，可以到GitHub上看看：[转盘抽奖][Link 1]

# TreeMap&红黑树介绍： #

TreeMap在JDK的官方介绍是：

* A Red-Black tree based {@link NavigableMap} implementation.
     * The map is sorted according to the {@linkplain Comparable natural
     * ordering} of its keys, or by a {@link Comparator} provided at map
     * creation time, depending on which constructor is used.

大概意思是：TreeMap是基于红黑树实现的，根据默认比较器会对其键进行排序，当然了，你也可以根据自己的需求自定义排序器（个人理解：如果key是数值使用默认的即可，由小到大排序。如果key是自定义对象，那么自定义比较器是必须的，不能少，而且自定义对象可以实现Comparable接口重写compareTo方法）。

因为接下来分析TreeMap的put方法需要先了解红黑树的特性，我们这里就简单介绍一下红黑树的五个特性：

1.  根节点是黑色的
2.  每个节点是红色或者黑色的。
3.  如果一个节点是红色的，那么它的子节点必须是黑色的。
4.  每个叶子节点(NIL)是黑色的。
5.  从任务一个节点到每个叶子节点的所有路径都包含相同数目的黑色节点。

下面附上经典红黑树例子：

![aHR0cHM6Ly9nc3MxLmJkc3RhdGljLmNvbS8tdm8zZFNhZ194STRraEdrcG9XSzFIRjZoaHkvYmFpa2UvYzAlM0RiYWlrZTkyJTJDNSUyQzUlMkM5MiUyQzMwL3NpZ249Y2RkMWRhZTE3YTBlMGNmM2I0ZmE0NmE5NmIyZjk5N2EvOTM1OGQxMDliM2RlOWM4MjhjZGI4ZTdjNjQ4MTgwMGExOGQ4NDM4Mi5qcGc][]

# 源码分析：  #

之所以我们使用TreeMap不再需要多个if判断，是因为TreeMap的put()方法会使用Comparetor比较器来对每个新增的key进行排序，而我们使用的key是Double，使用默认的比较器即可，排序是从小到大排。然后可以使用tailMap()方法会根据指定key来找出比这个key大的所有key。

put方法源码分析：

public V put(K key, V value) {
        // 获取当前红黑树的根节点
        Entry<K,V> t = root;
        // 判断根节点是否为空，如果为空的话直接将新增节点作为根节点。
        if (t == null) {
            compare(key, key); // type (and possibly null) check
            // new Entry-> 节点的color默认为black
            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        // 如果根节点不为空，则使用Comparator进行比较
        int cmp;
        Entry<K,V> parent;
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;
        // 是否有自定义Comparator
        if (cpr != null) {
            do {
                // 父节点一开始为根节点
                parent = t;
                cmp = cpr.compare(key, t.key);
                // 如果插入节点比当前父节点的值要小，往红黑树的左边继续遍历，t的左节点作为下个父节点
                if (cmp < 0)
                    t = t.left;
                // 如果插入节点比当前父节点的值要大，往红黑树的右边继续遍历，t的右节点作为下个父节点
                else if (cmp > 0)
                    t = t.right;
                // 如果值相等，则不进行插入操作，直接返回值
                else
                    return t.setValue(value);
            // 下一个父节点不为空，则继续循环
            } while (t != null);
        }
        // 如果没有自定义Comparator，则使用默认的Comparator
        else {
            if (key == null)
                throw new NullPointerException();
            @SuppressWarnings("unchecked")
                Comparable<? super K> k = (Comparable<? super K>) key;
            // 和上面的遍历一样
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        // 创建节点
        Entry<K,V> e = new Entry<>(key, value, parent);
        // 如果是小于的，则放在父节点的左边
        if (cmp < 0)
            parent.left = e;
        // 如果是大于的，放在父节点的右边
        else
            parent.right = e;
        // 根据红黑树规则进行调节【注意：会将插入节点的颜色设置为红色再进行调节】
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }

红黑树调节方法源码分析：

private void fixAfterInsertion(Entry<K,V> x) {
        // 将插入节点的颜色设置为红色
        x.color = RED;
        // 只要x不为空，不是根节点，x的父节点的颜色等于red就一直循环
        while (x != null && x != root && x.parent.color == RED) {
            // 如果父节点是左节点
            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
                // 取父节点的兄弟节点(即祖父的右子节点)
                Entry<K,V> y = rightOf(parentOf(parentOf(x)));
                // 如果父节点的兄弟节点不为空且是空色
                if (colorOf(y) == RED) {
                    // 父节点设置为黑色
                    setColor(parentOf(x), BLACK);
                    // 父节点的兄弟节点设置为黑色
                    setColor(y, BLACK);
                    // 设置祖父节点为红色
                    setColor(parentOf(parentOf(x)), RED);
                    // 将当前节点重新设置为祖父节点
                    x = parentOf(parentOf(x));
                // 如果父节点的兄弟节点为空或者为黑色
                } else {
                    // 当前节点是否为右节点
                    if (x == rightOf(parentOf(x))) {
                        // 将当前节点重新设置为父节点
                        x = parentOf(x);
                        // 当前节点进行左旋操作
                        rotateLeft(x);
                    }
                    // 设置父节点为黑色
                    setColor(parentOf(x), BLACK);
                    // 设置祖父节点为红色
                    setColor(parentOf(parentOf(x)), RED);
                    // 祖父节点进行右旋操作
                    rotateRight(parentOf(parentOf(x)));
                }
            // 如果父节点是右节点
            } else {
            // 取父节点的兄弟节点(即祖父的左子节点)
                Entry<K,V> y = leftOf(parentOf(parentOf(x)));
                // 如果父节点的兄弟节点不为空且是空色
                if (colorOf(y) == RED) {
                    // 设置父节点为黑色
                    setColor(parentOf(x), BLACK);
                    // 设置父亲的兄弟节点为黑色
                    setColor(y, BLACK);
                    // 设置祖父节点为红色
                    setColor(parentOf(parentOf(x)), RED);
                    // 将当前节点重新设置为祖父节点
                    x = parentOf(parentOf(x));
                // 如果父节点的兄弟节点为空或者为黑色
                } else {
                    // 当前节点是否为左节点
                    if (x == leftOf(parentOf(x))) {
                        // 将当前节点重新设置为父节点
                        x = parentOf(x);
                        // 当前节点进行右旋操作
                        rotateRight(x);
                    }
                    // 设置父节点为黑色
                    setColor(parentOf(x), BLACK);
                    // 设置祖父节点为红色
                    setColor(parentOf(parentOf(x)), RED);
                    // 祖父节点进行左旋操作
                    rotateLeft(parentOf(parentOf(x)));
                }
            }
        }
        // 根节点设置为黑色
        root.color = BLACK;
    }

最后是tailMap方法，我们只需要留意是返回升序的Map即可：

public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
            return new AscendingSubMap<>(this,
                                         false, fromKey, inclusive,
                                         true,  null,    true);
        }

[Link 1]: https://github.com/Howinfun/test-algorithm.git
[aHR0cHM6Ly9nc3MxLmJkc3RhdGljLmNvbS8tdm8zZFNhZ194STRraEdrcG9XSzFIRjZoaHkvYmFpa2UvYzAlM0RiYWlrZTkyJTJDNSUyQzUlMkM5MiUyQzMwL3NpZ249Y2RkMWRhZTE3YTBlMGNmM2I0ZmE0NmE5NmIyZjk5N2EvOTM1OGQxMDliM2RlOWM4MjhjZGI4ZTdjNjQ4MTgwMGExOGQ4NDM4Mi5qcGc]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9nc3MxLmJkc3RhdGljLmNvbS8tdm8zZFNhZ194STRraEdrcG9XSzFIRjZoaHkvYmFpa2UvYzAlM0RiYWlrZTkyJTJDNSUyQzUlMkM5MiUyQzMwL3NpZ249Y2RkMWRhZTE3YTBlMGNmM2I0ZmE0NmE5NmIyZjk5N2EvOTM1OGQxMDliM2RlOWM4MjhjZGI4ZTdjNjQ4MTgwMGExOGQ4NDM4Mi5qcGc