Java 權重演算法實作：廣告加權隨機展示策略

演算法核心邏輯

適用於「按權重比例隨機選取」的場景，如廣告輪播、負載均衡、抽獎系統：

1. 每個項目賦予權重值
2. 計算總權重 sum
3. 生成 [1, sum] 區間隨機數 rd
4. 遍歷項目累加權重 curWt，首個 curWt >= rd 的項目即為選中結果

完整代碼實作

import java.util.*;

public class WeightRandomSelector {
    static class Node {
        int weight;
        String keyword;
        Node(int w, String k) { weight = w; keyword = k; }
    }

    public static void main(String[] args) {
        List<Node> nodes = Arrays.asList(
            new Node(10, "廣告A"),
            new Node(20, "廣告B"),
            new Node(30, "廣告C"),
            new Node(40, "廣告D")
        );
        
        int sum = nodes.stream().mapToInt(n -> n.weight).sum();
        Map<String, Integer> stats = new LinkedHashMap<>();
        
        // 模擬 100 次選取，驗證分佈
        for (int i = 0; i < 100; i++) {
            int rd = (int) (Math.random() * sum) + 1;
            Node selected = select(nodes, rd);
            stats.merge(selected.keyword, 1, Integer::sum);
        }
        
        stats.forEach((k, v) -> System.out.println(k + ": " + v + "%"));
        // 預期輸出接近：廣告A:10%, 廣告B:20%, 廣告C:30%, 廣告D:40%
    }

    static Node select(List<Node> nodes, int rd) {
        int curWt = 0;
        for (Node n : nodes) {
            curWt += n.weight;
            if (curWt >= rd) return n;
        }
        return nodes.get(nodes.size() - 1); // 理論上不會到達
    }
}

關鍵特性分析

效能優化：前綴和 + 二分查找 (O(log n))

當項目數量大 (如 > 1000) 時，預計算前綴和陣列，用二分查找定位：

class OptimizedSelector {
    private int[] prefixSum;
    private List<Node> nodes;
    private int totalWeight;
    
    public OptimizedSelector(List<Node> nodes) {
        this.nodes = nodes;
        prefixSum = new int[nodes.size()];
        int sum = 0;
        for (int i = 0; i < nodes.size(); i++) {
            sum += nodes.get(i).weight;
            prefixSum[i] = sum;
        }
        totalWeight = sum;
    }
    
    public Node select() {
        int rd = (int) (Math.random() * totalWeight) + 1;
        int idx = Arrays.binarySearch(prefixSum, rd);
        if (idx < 0) idx = -idx - 1; // 插入點即為目標索引
        return nodes.get(idx);
    }
}

應用場景擴展

• 廣告系統：按出價/點擊率加權展示
• 負載均衡：按伺服器效能權重分發請求
• 遊戲掉寶：稀有度權重控制掉落機率
• A/B 測試：流量按比例分流至不同版本

注意事項

1. 權重值建議用整數，避免浮點精度問題
2. 總權重超過 Integer.MAX_VALUE 需用 long
3. 高併發場景下，Random 非線程安全，改用 ThreadLocalRandom
4. 需「平滑加權」 (如 Nginx 平滑加權輪詢) 時，此演算法不適用

權重隨機演算法簡單高效，是分散式系統、廣告引擎、遊戲邏輯中的基石組件，掌握其原理與優化方向至關重要。

1. 上一篇文章： Java Swing 開發多功能日曆日記應用完整實戰
2. 下一篇文章： Java 物件陣列排序完全指南：Comparable 與 Comparator 實戰

Java 相關知識

深入解析 Java HashMap 核心原理與源碼實現

HashMap 整體結構概覽 HashMap 是 Java

J2ME 雙緩衝技術實現屏幕內容捕獲為 Image：原理與實戰

J2ME (MIDP) 中 Canvas 無直接獲取像素數據

Axis2 系列教程（二）：複合類型數據傳遞與序列化技巧

複合類型概述 Axis2 原生支援陣列與自訂類別（介面）作為

JUnit 框架實現 Java 單元測試深度解析

背景動機 隨專案規模增長，缺乏有效測試流程會導致問題積累、版