Java LoadBalanceUtil 负载均衡、轮询加权 https://www.cnblogs.com/vipsoft/p/19728820
Java - 加权随机算法--Demo: https://www.cnblogs.com/vipsoft/p/19741845

示例

VideoInfo.java

public class VideoInfo {
    private String name;
    private int weight;

    public VideoInfo(String name, int weight) {
        this.name = name;
        this.weight = weight;
    }

    public String getName() { return name; }
    public int getWeight() { return weight; }
}

service.java

private static final Object lock = new Object();

private final Random random = new Random();

public VideoInfo getVideoInfo(List<VideoInfo> videoList) {
    synchronized (lock) {
        // 使用 TreeMap 自动按键排序
        TreeMap<Integer, List<VideoInfo>> weightMap = new TreeMap<>();
        int totalWeight = 0;
        // 构建权重累积和映射
        for (VideoInfo video : videoList) {
            totalWeight += video.getWeight();
            weightMap.computeIfAbsent(totalWeight, k -> new ArrayList<>()).add(video);
        }
        // 生成随机数 [0, totalWeight)
        int randomNum = random.nextInt(totalWeight);
        // 找到第一个大于 randomNum 的键
        Map.Entry<Integer, List<VideoInfo>> entry = weightMap.higherEntry(randomNum);
        if (entry != null) {
            List<VideoInfo> candidates = entry.getValue();
            // 如果该权重区间有多个视频，随机选择一个
            return candidates.get(random.nextInt(candidates.size()));
        }
    }
    return null;
}

Test

@Test
void getVideoInfo() {

    List<VideoInfo> videoList = Arrays.asList(
            getVideoInfo("视频A", 1),
            getVideoInfo("视频B", 2),
            getVideoInfo("视频C", 3),
            getVideoInfo("视频D", 2)
    );

    Map<String, Integer> countMap = new HashMap<>();
    for (int i = 0; i < 100; i++) {
        VideoInfo video = lotteryService.getVideoInfo(videoList);
        countMap.merge(video.getTitle(), 1, Integer::sum);
    }
    System.out.println("测试结果（100次）：");
    countMap.forEach((name, count) ->
            System.out.printf("%s: %d次 (%.1f%%)%n", name, count, count / 10.0));
}

测试结果（100次）：
视频B: 29次 (2.9%)
视频A: 12次 (1.2%)
视频D: 22次 (2.2%)
视频C: 37次 (3.7%)

累积权重 vs 单个权重

这边为什么是 weightMap.computeIfAbsent(totalWeight, 而不是 weightMap.computeIfAbsent(video.getWeight(),

具体例子说明

假设有视频列表：

• 视频A：权重 1
• 视频B：权重 2
• 视频C：权重 2
• 视频D：权重 3

如果使用单个权重（错误）：

weightMap 会变成：
key=1 → [视频A]
key=2 → [视频B, 视频C]  // 视频B和C被错误地放在同一个区间！
key=3 → [视频D]

随机数区间划分：
[0,1) → key=1 → [视频A]
[1,2) → key=2 → [视频B, 视频C]  // 这不对！视频B应该占更大的区间
[2,3) → key=2 → [视频B, 视频C]  // 视频C也应该有自己的区间
[3,6) → key=3 → [视频D]  // 区间大小不对！

使用累积权重（正确）：

计算过程：
totalWeight=1  → key=1 → [视频A]
totalWeight=3  → key=3 → [视频B]  // 1+2=3
totalWeight=5  → key=5 → [视频C]  // 3+2=5  
totalWeight=8  → key=8 → [视频D]  // 5+3=8

weightMap 变成：
key=1 → [视频A]
key=3 → [视频B]
key=5 → [视频C]
key=8 → [视频D]

随机数区间划分：
[0,1)  → key=1 → [视频A]  // A占1个单位
[1,3)  → key=3 → [视频B]  // B占2个单位
[3,5)  → key=5 → [视频C]  // C占2个单位  
[5,8)  → key=8 → [视频D]  // D占3个单位

可视化对比

总权重 = 8

正确方式（累积权重）：
0    1         3         5         8
|----|---------|---------|---------|
  A      B         C         D
 1      2         2         3

错误方式（单个权重）：
0    1    2    3    4    5    6    7    8
|----|----|----|----|----|----|----|----|
  A   B/C  B/C   D    D    D   ???  ???
 1    2    2    3    3    3

问题：
- B和C被压缩在同一个区间 [1,3)
- D的区间 [3,6) 虽然大小正确，但位置错误
- [6,8) 变成空白区间

总结

使用 totalWeight 作为 key 的原因：

1. 区间唯一性：每个累积权重值都是唯一的，确保了每个视频有独立的区间
2. 正确的概率分布：保证了每个视频被选中的概率等于其权重/总权重
3. 随机映射准确：随机数可以直接映射到正确的视频区间

这就是为什么在权重随机算法中，我们通常使用累积权重而不是原始权重作为映射的键。

累积权重的话，要不要对 videoList 先做排序？

不需要排序！ 这是一个很好的问题，让我解释为什么不需要排序：

为什么不需要排序？

累积权重算法天然地保持了原始顺序，而且顺序不影响概率分布。让我通过例子说明：

示例：不排序的情况

假设视频列表原始顺序：

List<VideoInfo> videoList = Arrays.asList(
    new VideoInfo("视频C", 3),  // 权重3
    new VideoInfo("视频A", 1),  // 权重1  
    new VideoInfo("视频B", 2)   // 权重2
);

累积权重计算过程：

// 第1个：视频C (权重3)
totalWeight = 3  → key=3 → [视频C]

// 第2个：视频A (权重1)  
totalWeight = 4  → key=4 → [视频A]

// 第3个：视频B (权重2)
totalWeight = 6  → key=6 → [视频B]

// 最终映射：
// key=3 → [视频C]
// key=4 → [视频A]  
// key=6 → [视频B]

随机数区间划分：

总权重 = 6

0    3         4         6
|----|---------|---------|
  C      A        B
 3      1        2

排序 vs 不排序的对比

不排序的情况（原始顺序：C, A, B）：

区间划分：
[0,3) → 视频C (3个单位)
[3,4) → 视频A (1个单位)
[4,6) → 视频B (2个单位)

概率：C=3/6, A=1/6, B=2/6 ✅ 正确！

如果排序（A, B, C）：

排序后：A(1), B(2), C(3)

区间划分：
[0,1) → 视频A (1个单位)
[1,3) → 视频B (2个单位)
[3,6) → 视频C (3个单位)

概率：A=1/6, B=2/6, C=3/6 ✅ 同样正确！

核心原理

累积权重算法的本质是将总权重区间按顺序分配给每个元素，无论元素顺序如何：

总权重区间 [0, totalWeight)
   ↓
按遍历顺序依次分配子区间：
元素1: [0, w1)
元素2: [w1, w1+w2)
元素3: [w1+w2, w1+w2+w3)
...

顺序只影响哪个元素对应哪个区间段，但不影响每个区间段的大小。

代码验证

public class WeightOrderTest {
    public static void main(String[] args) {
        // 原始顺序：C(3), A(1), B(2)
        List<VideoInfo> originalList = Arrays.asList(
            new VideoInfo("视频C", 3),
            new VideoInfo("视频A", 1),
            new VideoInfo("视频B", 2)
        );
        
        // 排序后：A(1), B(2), C(3)
        List<VideoInfo> sortedList = new ArrayList<>(originalList);
        sortedList.sort(Comparator.comparingInt(VideoInfo::getWeight));
        
        System.out.println("=== 不排序的区间分配 ===");
        printIntervals(originalList);
        
        System.out.println("\n=== 排序后的区间分配 ===");
        printIntervals(sortedList);
        
        // 测试10000次，验证概率分布
        System.out.println("\n=== 概率分布测试（不排序，10000次）===");
        testProbability(originalList);
    }
    
    private static void printIntervals(List<VideoInfo> list) {
        int total = 0;
        int start = 0;
        
        for (VideoInfo video : list) {
            int end = start + video.getWeight();
            System.out.printf("%s(权重%d): [%d, %d)%n", 
                video.getName(), video.getWeight(), start, end);
            start = end;
        }
        System.out.println("总权重: " + start);
    }
    
    private static void testProbability(List<VideoInfo> list) {
        Map<Integer, List<VideoInfo>> weightMap = new HashMap<>();
        int totalWeight = 0;
        
        for (VideoInfo video : list) {
            totalWeight += video.getWeight();
            weightMap.computeIfAbsent(totalWeight, k -> new ArrayList<>()).add(video);
        }
        
        List<Integer> sortedKeys = new ArrayList<>(weightMap.keySet());
        Collections.sort(sortedKeys);
        
        Random random = new Random();
        Map<String, Integer> countMap = new HashMap<>();
        
        for (int i = 0; i < 10000; i++) {
            int randomNum = random.nextInt(totalWeight);
            int key = findKey(sortedKeys, randomNum);
            VideoInfo selected = weightMap.get(key).get(0);
            countMap.merge(selected.getName(), 1, Integer::sum);
        }
        
        countMap.forEach((name, count) -> 
            System.out.printf("%s: %d次 (%.2f%%)%n", 
                name, count, count / 100.0));
    }
    
    private static int findKey(List<Integer> sortedKeys, int randomNum) {
        for (int key : sortedKeys) {
            if (randomNum < key) {
                return key;
            }
        }
        return sortedKeys.get(sortedKeys.size() - 1);
    }
}

输出结果：

=== 不排序的区间分配 ===
视频C(权重3): [0, 3)
视频A(权重1): [3, 4)
视频B(权重2): [4, 6)
总权重: 6

=== 排序后的区间分配 ===
视频A(权重1): [0, 1)
视频B(权重2): [1, 3)
视频C(权重3): [3, 6)
总权重: 6

=== 概率分布测试（不排序，10000次）===
视频C: 5012次 (50.12%)
视频A: 1689次 (16.89%)
视频B: 3299次 (32.99%)

什么时候需要排序？

虽然算法本身不需要排序，但以下情况可能需要：

1. 业务需求：比如权重相同时按某种规则优先

   // 如果权重相同，按创建时间排序
   list.sort((v1, v2) -> {
       if (v1.getWeight() != v2.getWeight()) {
           return Integer.compare(v1.getWeight(), v2.getWeight());
       }
       return v1.getCreateTime().compareTo(v2.getCreateTime());
   });
   

2. 调试方便：排序后更容易理解和调试

   // 排序后，累积权重是递增的，更容易看懂
   // [1, 3, 6]  vs  [3, 4, 6]
   

3. 缓存优化：如果同一个列表会被多次查询，排序后可以利用二分查找

   // 排序后可以用二分查找
   int index = Collections.binarySearch(sortedKeys, randomNum);
   if (index < 0) {
       index = -index - 1;
   }
   

结论

累积权重算法本身不要求输入列表有序，它只是按照你提供的顺序分配区间。顺序不影响概率的正确性，只会改变哪个随机数区间对应哪个元素。

所以你可以：

• ✅ 保持原始顺序直接使用
• ✅ 按任意业务规则排序后使用
• ✅ 随机打乱后使用

概率分布始终正确，只要权重值不变！