12306 售票核心算法解析：位運算座位標識與並發搶票的 Java 實現

座位標識設計：位圖

以 G71 次列車 18 個站點為例，單個座位用 18 位二進制字符串表示，每位對應一站。初始全 0 表示全程可售。

// 18 站，初始標識
String ticketFlag = "000000000000000000"; // 0=可售, 1=已售

餘票數 = 標識中 '0' 的個數。始發/終到受限站點可靈活配置，實現區間限售。

查詢餘票

查詢保定東(站3) → 韶關(站15) 的二等座 F 座：

SELECT ... FROM booking_table
WHERE to_number(substring(seat_flag, 3, 13)) = 0  -- 區間全 0
  AND depart_date = '2016-06-11'
  AND train_code = 'G71'
  AND seat_type = '二等座'
  AND seat_position = 'F'
  AND ticket_status = '待售'
  AND substring(origin_limit, 3, 1) = '1'  -- 允許從站3上車
  AND substring(dest_limit, 15, 1) = '1';  -- 允許到站15下車

訂票流程（位運算核心）

1. 檢查區間全 0 → 可售。
2. 鎖定車票（狀態改「鎖定」）。
3. 用戶支付成功 → 或運算 更新標識：newFlag = oldFlag | intervalMask。
   例：100000000000000000 | 000111111111111000 = 100111111111111000
4. 支付超時/取消 → 異或運算 回滾：newFlag = oldFlag ^ intervalMask（前提區間未被其他訂單佔用）。

退票流程

非運算 恢復：newFlag = oldFlag & (~intervalMask)，將對應位重置為 0。

Java 核心實現

public class TicketAlgorithm {
    public static String orderTicket(String flag, int begin, int end) {
        if (canBook(flag, begin, end)) {
            String mask = buildMask(flag.length(), begin, end);
            return applyMask(flag, mask, true); // 或運算
        }
        return flag;
    }

    public static String releaseTicket(String flag, int begin, int end) {
        String mask = buildMask(flag.length(), begin, end);
        return applyMask(flag, mask, false); // 非運算
    }

    private static boolean canBook(String flag, int begin, int end) {
        String sub = flag.substring(begin, end);
        return new BigInteger(sub, 2).equals(BigInteger.ZERO);
    }

    private static String buildMask(int len, int begin, int end) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < len; i++)
            sb.append((i >= begin && i < end) ? '1' : '0');
        return sb.toString();
    }

    private static String applyMask(String flag, String mask, boolean isBook) {
        char[] f = flag.toCharArray();
        char[] m = mask.toCharArray();
        for (int i = 0; i < f.length; i++) {
            if (isBook) {
                if (f[i] == '1' || m[i] == '1') f[i] = '1'; // OR
            } else {
                if (f[i] == '1' && m[i] == '1') f[i] = '0'; // AND NOT (simplified)
            }
        }
        return new String(f);
    }
}

並發考量

• 資料庫層面：行鎖（SELECT ... FOR UPDATE）或樂觀鎖（版本號）。
• 應用層面：Redis 分散式鎖保護「查詢-鎖定-更新」原子性。
• 位運算極快，適合高併發核心邏輯。