红包算法优化：高效随机分配算法实现

本文介绍了一种优化后的红包算法，旨在提高随机分配红包的效率和安全性。

原始算法:

public static List<Integer> splitRedPacket(int amount, int total) {
    // 总金额不能小于总人数（即每人至少一分钱），总人数不能少于1人
    if (amount < total || total < 1) {
        throw new RuntimeException('总金额不能小于总人数');
    }

    // 随机金额数组
    int[] amountArr = new int[total];
    // 剩余金额
    int surplusAmount = amount;
    // 剩余个数
    int surplusTotal = total;
    for (int i = 0; i < total - 1; i++) {
        // 金额除以总个数
        int max = (surplusAmount / surplusTotal) * 2;
        // 本次生成的随机金额，区间：[1，max)
        int randomAmount = random.nextInt(max - 1) + 1;
        amountArr[i] = randomAmount;
        // 剩余金额减少，剩余人数-1
        surplusAmount -= randomAmount;
        surplusTotal--;
    }
    // 为保证红包正好分完，最后一个人的随机金额=剩余金额
    amountArr[amountArr.length - 1] = surplusAmount;

    // 再将生成的随机金额打散：对每个随机金额对应生成一个随机数，然后将这些随机数排序
    TreeMap<Integer, Integer> map = getRandomSortAmount(total);
    return map.values().stream().map(e -> amountArr[e]).collect(Collectors.toList());
}

优化后的算法:

使用ThreadLocalRandom替换Random，避免多线程竞争问题。
使用ThreadLocalRandom#nextInt(int bound)方法生成随机金额，避免重复创建Random实例和多次调用nextInt方法。
使用公式(surplusAmount - (surplusTotal - 1) * minAmount) / surplusTotal * 2生成随机金额，避免使用除法和取模操作，提高效率。
去掉TreeMap的使用，直接在生成随机金额时将随机数和下标存入List中，然后使用Collections#shuffle(List<?> list)方法打乱顺序。

public static List<Integer> splitRedPacket(int amount, int total) {
    if (amount < total || total < 1) {
        throw new RuntimeException('总金额不能小于总人数');
    }

    int[] amountArr = new int[total];
    int surplusAmount = amount;
    int surplusTotal = total;
    ThreadLocalRandom random = ThreadLocalRandom.current();
    List<Integer> indices = new ArrayList<>(total);
    for (int i = 0; i < total - 1; i++) {
        int max = (surplusAmount - (surplusTotal - 1)) / surplusTotal * 2;
        int randomAmount = random.nextInt(1, max + 1);
        amountArr[i] = randomAmount;
        indices.add(i);
        surplusAmount -= randomAmount;
        surplusTotal--;
    }
    amountArr[total - 1] = surplusAmount;

    Collections.shuffle(indices);
    List<Integer> result = new ArrayList<>(total);
    for (int i = 0; i < total; i++) {
        result.add(amountArr[indices.get(i)]);
    }
    return result;
}

总结:

优化后的红包算法在以下方面有所提升：

效率更高，避免了重复创建Random实例和使用除法、取模操作。
安全性更高，使用ThreadLocalRandom避免了多线程竞争问题。
代码更简洁，去掉了TreeMap的使用，简化了代码逻辑。

通过这些优化，可以有效提高红包算法的效率和安全性，为用户提供更优质的体验。