高并发抢红包系统红包随机金额生成算法

本文介绍高并发抢红包系统中，必不可少的红包随机金额生成算法。

假定我们采用预生成方式（相对的还有实时生成，如微信红包），算法的输入和输出如下：

• 给定总金额M和总人数N，采用某种算法生成红包随机金额列表

算法要求：

• 随机金额列表的金额之和，不能超也不能少，恰好等于总金额M
• 每个人至少抢到1分钱
• 所有人抢到金额的几率是相等的，不能有些人抢到金额的几率大，而有些人抢不到红包的几率大

红包随机金额生成算法通常采用二倍均值法，如下是该算法的简介：

• 剩余总金额M/剩余总人数N，将结果*2得到边界值E，然后在(0,E)之间得到一个随机数R，R就是要求的随机金额
• 将剩余金额进去此时生成的随机金额R，将剩余人数减1
• 循环执行上述操作，直到剩余人数为0
• 这里要确保生成的所有随机金额之和，要等于一开始的总金额

如果还想将生成的随机金额列表再随机一点，可以再进行打散：

• 因为二倍均值法的算法本质，通常生成的第一个金额会偏大，生成的最后一个金额会偏小。举个例子，100分钱，5个人分，第一个随机金额在[1分,40)区间生成，极端情况下可以获取39分钱。如果前面的人正好瓜分了99分钱，那么最后一个人只能得到1分钱。因此对这种情况有避讳的话可以再打散
• 如何打散？可以针对每个随机金额生成一个排序值，然后按排序值从小到大或从大到小排序都可以，排序后的随机金额列表就更具有随机性了

我们将金额单位设为分，这样的话发红包的总金额和每个人抢到的红包金额都可以精确到1分钱；金额变量整数形式（用元做单位就要用小数了，小数在做计算时容易丢失精度），且确保抢到红包的人至少抢到一分钱。

下面是算法实现。

package com.bobo.springbootredpacket.util;

import com.bobo.springbootredpacket.exception.RedpacketException;
import java.util.List;
import java.util.Random;
import java.util.TreeMap;
import java.util.stream.Collectors;

public class RedpacketUtil {
    /**
     * 分红包算法：二倍均值法
     * @param amount 红包总金额，单位为分
     * @param total 总人数
     * @return 随机金额数组
     */
    public static List<Integer> splitRedpacket(int amount,int total){
        // 总金额不能小于总人数（即每人至少一分钱），总人数不能少于1人
        if(amount < total || total < 1){
            throw new RedpacketException("总金额不能小于总人数（即每人至少一分钱），总人数不能少于1人");
        }
        // 随机金额数组
        int[] amountArr = new int[total];
        // 随机数生成器
        Random random = new Random();
        // 剩余金额和剩余人数
        int residualAmount = amount;
        int residualTotal = total;
        // 总共生成total-1个随机金额
        for (int i = 0;i < total-1;i++){
            // 金额除以总人数
            int max = (residualAmount/residualTotal)*2;
            // 本次生成的随机金额，区间：[1,max)，不能包含max
            int randomAmount = random.nextInt(max-1)+1;
            amountArr[i] = randomAmount;
            // 剩余金额减少，剩余人数减1
            residualAmount -= randomAmount;
            residualTotal --;
        }
        // 为确保红包正好分完，最后一个人的随机金额就是剩余金额
        amountArr[amountArr.length-1] = residualAmount;

        // 再将生成的随机金额打散：对每个随机金额 对应 生成一个随机数字，然后将这些随机数字排序
        TreeMap<Integer, Integer> map = new TreeMap<>();
        // 表示第i个随机金额
        int i = 0;
        while (map.size() < total){
            int maxSortNum = random.nextInt(total * 2)+1;
            if(map.containsKey(maxSortNum)){
                continue;
            }
            map.put(maxSortNum,i);
            i++;
        }
        // 校验
        if(map.size() != total){
            throw new RedpacketException("生成的排序号个数不等于总人数");
        }
        // 替换
        List<Integer> amountList = map.values().stream().map(e -> amountArr[e]).collect(Collectors.toList());
        return amountList;
    }
}
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

单测：

@Test
public void test(){
    // 100元，10个人分
    List<Integer> amounts = RedpacketUtil.splitRedpacket(10000, 10);
    int sum = 0;
    for (int amount : amounts) {
        sum += amount;
        System.out.println((double) amount/100+"元");
    }
    System.out.println("抢到的红包金额之和："+(double)sum/100+"元");
}
1
2
3
4
5
6
7
8
9
10
11

单测结果：

12.77元
16.9元
3.08元
11.43元
14.96元
3.85元
6.15元
4.51元
20.07元
6.28元
抢到的红包金额之和：100.0元
1
2
3
4
5
6
7
8
9
10
11