Java 實作 12306 售票演算法（二）：位元組標記與大數運算

承接上篇架構設計，本文展示核心售票邏輯的 Java 程式碼實作。採用 BigInteger 位元運算表示「車站區間佔用」，結合 Map 管理座位庫存，實現高併發下的無鎖扣減邏輯，並附上效能測試數據。

核心資料結構

• Train：車次、站數、各席別總量（Map<String,Integer>）、發車日期。
• Ticket：單張票實體，含 ticketFlag (BigInteger) 位元標記、座位類型、銷售渠道、GUID。
• Order：下單成功產生的訂單，記錄座位、區間、票號等。

關鍵演算法邏輯

1. 區間位元標記建構

// 第 i 站到第 j 站：將第 i 到 j-1 位設為 1
public static String buildTicket(int i, int stationNum) {
    BigInteger bits = BigInteger.ZERO;
    for (int j = i; j < stationNum; j++) {
        bits = bits.or(buildSingleStation(j)); // 單站位元
    }
    return bits.shiftRight(1).toString(); // 右移對齊
}

2. 可售判斷（核心無鎖邏輯）

// A = ~(~A | B)  →  若 fromTicket 包含 toTicket 則可售
private static boolean canTicket(BigInteger from, BigInteger to) {
    return from.equals(from.not().or(to).not());
}

3. 下單扣減（原子性 CAS 風格）

public static Order createOrder(String ticketStr, List<Ticket> list, Map cond) {
    BigInteger want = new BigInteger(ticketStr);
    for (Ticket t : list) {
        BigInteger have = new BigInteger(t.getTicketFlag());
        if (canTicket(have, want) && t.getTicketType().equals(cond.get("ticketType"))) {
            Order o = new Order();
            o.setTicketFlag(want.toString());
            // 關鍵：原地更新票標記，模擬 CAS
            t.setTicketFlag(have.or(want).toString());
            return o;
        }
    }
    return null;
}

效能測試結果（筆記本級環境）

• 初始化票池：約 2,000 張票（多席別、多區間）
• 逐張下單模擬：全車站區間遍歷
• 總耗時：~200 ms，吞吐 ~10,000 筆/秒

程式碼採用單執行緒模擬，實際生產環境需搭配 AtomicReference 或資料庫樂觀鎖實現真正併發安全。完整類別定義（Train、Ticket、Order、CommonUtil、MainTest）已整理於文章中，可直接下載研究。