Java 權重隨機算法：二分查找法 vs 數組展開法，百萬級性能對比

業務場景：加權抽獎、流量分發、負載均衡

給定 Map weightMap，權重值代表相對概率。例如 {A:10, B:30, C:60}，期望 C 被選中概率 60%。

方案一：數組展開法（簡單、O(1) 取樣、記憶體爆炸）

// 權重總和 100，展開數組長度 100
List expanded = new ArrayList<>(totalWeight);
weightMap.forEach((k, v) -> {
    for (int i = 0; i < v; i++) expanded.add(k);
});
// 取樣
T result = expanded.get(ThreadLocalRandom.current().nextInt(totalWeight));

缺陷：權重值大（如 1000000）或項目多時，記憶體佔用 O(Σw)，不可接受。

方案二：前綴和 + 二分查找（標準、O(log N) 取樣、O(N) 空間）

public final class WeightRandom {
    private final T[] items;
    private final int[] prefixSums; // 遞增數組
    private final int totalWeight;
    private final ThreadLocalRandom random = ThreadLocalRandom.current();

    @SafeVarargs
    public WeightRandom(Map weightMap) {
        int n = weightMap.size();
        this.items = (T[]) new Object[n];
        this.prefixSums = new int[n];
        
        int idx = 0, sum = 0;
        // 建議按權重降序排列，熱門項目前置，二分查找更快命中
        List> entries = new ArrayList<>(weightMap.entrySet());
        entries.sort(Map.Entry.comparingByValue().reversed());
        
        for (Map.Entry e : entries) {
            items[idx] = e.getKey();
            sum += e.getValue();
            prefixSums[idx] = sum;
            idx++;
        }
        this.totalWeight = sum;
    }

    /** 核心取樣：O(log N) */
    public T next() {
        int r = random.nextInt(totalWeight) + 1; // [1, totalWeight]
        int idx = Arrays.binarySearch(prefixSums, r);
        if (idx < 0) idx = -idx - 1; // binarySearch 返回插入點
        return items[idx];
    }

    /** 支持指定隨機數（測試/復現） */
    public T next(int randomInt) {
        int r = Math.clamp(randomInt, 1, totalWeight);
        int idx = Arrays.binarySearch(prefixSums, r);
        return items[idx < 0 ? -idx - 1 : idx];
    }
}

關鍵細節：binarySearch 返回值處理

• 找到精確匹配 → 返回索引 ≥ 0；
• 未找到 → 返回 -(插入點) - 1，插入點即為第一個 >= r 的位置；
• 統一轉換：idx = idx >= 0 ? idx : -idx - 1。

性能基準（JMH，1000 萬次調用）

結論：絕大多數場景首選二分法；只有「項目極少（<10）、權重極小（<100）、極高頻（億級 QPS）」才考慮展開法換空間換時間。

進階：動態權重更新（熱加載）

public class DynamicWeightRandom {
    private final AtomicReference> holder = new AtomicReference<>();

    public void updateWeights(Map newMap) {
        holder.set(new WeightRandom<>(newMap)); // 原子替換，無鎖讀取
    }
    public T next() { return holder.get().next(); }
}

利用 AtomicReference 實現「寫時複製」，讀線程零阻塞，適合配置中心動態下發權重場景。

總結

1. 權重隨機核心：前綴和數組 + 二分查找，時間 O(log N)、空間 O(N)；
2. 構建時按權重降序排列，熱門項目前置，提升緩存命中與分支預測；
3. 使用 ThreadLocalRandom 避免 Random 併發爭用；
4. 動態更新用 AtomicReference 無鎖熱換；
5. 生產環境可直接用 Guava WeightedRandom 或 Apache Commons Math RandomDataGenerator。