Java 加權隨機抽獎算法：基於機率區間的高效實現

算法原理

將每個獎品的中獎機率映射到一個連續的整數區間，隨機生成一個數字，落在哪個區間即中該獎品。時間複雜度 O(n)，n 為獎品種類數，適合獎品較少、頻率高的場景。

核心代碼

public class LotteryService {

    private static final int PRECISION = 1_000_000; // 百萬分率精度

    public int draw(List<Prize> prizes) {
        if (prizes == null || prizes.isEmpty()) return 0;

        // 1. 洗牌：打亂順序，避免同機率獎品固定優先
        Collections.shuffle(prizes);

        // 2. 建立區間映射
        Map<Integer, int[]> ranges = new LinkedHashMap<>();
        Map<Integer, Integer> stock = new HashMap<>();
        int cursor = 0;

        for (Prize p : prizes) {
            int prob = p.getProbability().multiply(BigDecimal.valueOf(PRECISION)).intValue();
            if (prob <= 0) continue;
            int start = cursor + 1;
            int end = cursor + prob;
            ranges.put(p.getId(), new int[]{start, end});
            stock.put(p.getId(), p.getQuantity());
            cursor = end;
        }

        // 3. 總機率未覆蓋全範圍視為「未中獎」
        if (cursor == 0) return 0;

        // 4. 隨機抽取
        int lucky = ThreadLocalRandom.current().nextInt(1, cursor + 1);

        // 5. 查找命中區間
        for (Map.Entry<Integer, int[]> e : ranges.entrySet()) {
            int id = e.getKey();
            int[] range = e.getValue();
            if (lucky >= range[0] && lucky <= range[1] && stock.get(id) > 0) {
                stock.put(id, stock.get(id) - 1); // 庫存扣減 (實際需持久化)
                return id;
            }
        }
        return 0; // 未中獎
    }
}

獎品實體

public class Prize {
    private Integer id;
    private BigDecimal probability; // 如 0.05 表 5%
    private Integer quantity;       // 庫存，-1 表無限

    // getter/setter 略
}

測試驗證

@Test
public void testDistribution() {
    List<Prize> list = Arrays.asList(
        new Prize(1, new BigDecimal("0.05"), 100),
        new Prize(2, new BigDecimal("0.10"), 100),
        new Prize(3, new BigDecimal("0.15"), 100),
        new Prize(4, new BigDecimal("0.20"), 100),
        new Prize(5, new BigDecimal("0.50"), 100)
    );

    Map<Integer, Integer> counter = new HashMap<>();
    int times = 1_000_000;
    LotteryService svc = new LotteryService();

    for (int i = 0; i < times; i++) {
        int id = svc.draw(list);
        counter.merge(id, 1, Integer::sum);
    }

    counter.forEach((k, v) -> 
        System.out.printf("獎品 %d: 理論 %.2f%% 實際 %.2f%%%n", 
            k, list.stream().filter(p -> p.getId()==k).findFirst().get().getProbability().doubleValue()*100,
            v * 100.0 / times));
}

輸出範例

獎品 1: 理論 5.00% 實際 4.99%
獎品 2: 理論 10.00% 實際 10.01%
獎品 3: 理論 15.00% 實際 15.02%
獎品 4: 理論 20.00% 實際 19.98%
獎品 5: 理論 50.00% 實際 50.00%

進階優化方向

• 二分查找：獎品超過 50 種時，將區間陣列排序後用 Arrays.binarySearch 將查找降為 O(log n)。
• 前綴和 + 二分：預計算前綴和陣列 prefix[i]，隨機數 r，找首個 prefix[i] >= r。
• 分佈式庫存：引入 Redis Lua 腳本原子扣減，解決高併發超賣。
• 動態機率：支援運營後台熱更新機率，配合版本號機制平滑切換。

結語

區間映射法概念清晰、易於驗證，是中小型抽獎系統的首選。若獎品極多或需極致效能，可升級為前綴和二分或 Alias Method (離散概率分布常數時間採樣)。