本文介绍高并发抢红包系统中，必不可少的红包随机金额生成算法。
假定我们采用预生成方式（相对的还有实时生成，如微信红包），算法的输入和输出如下：
- 给定总金额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;
}
}
单测：
@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+"元");
}
单测结果：
12.77元
16.9元
3.08元
11.43元
14.96元
3.85元
6.15元
4.51元
20.07元
6.28元
抢到的红包金额之和：100.0元