位圖 (Bitmap)#

位圖是一種使用二進位位來標記元素存在性的資料結構，在海量資料處理中極為高效。

核心思想#

用一個 bit 表示一個元素的存在與否：

• 1：存在
• 0：不存在

1 億個整數用位圖只需 12.5 MB（1 億 bit = 12.5 MB），而用整數陣列需要 400 MB。

基本操作#

設置第 k 位為 1#

byte[k / 8] |= (1 << (k % 8));

查詢第 k 位#

return (byte[k / 8] & (1 << (k % 8))) != 0;

public class BitMap {
    private byte[] bytes;
    private int nbits;

    public BitMap(int nbits) {
        this.nbits = nbits;
        this.bytes = new byte[nbits / 8 + 1];
    }

    public void set(int k) {
        if (k > nbits) return;
        int byteIndex = k / 8;
        int bitIndex = k % 8;
        bytes[byteIndex] |= (1 << bitIndex);
    }

    public boolean get(int k) {
        if (k > nbits) return false;
        int byteIndex = k / 8;
        int bitIndex = k % 8;
        return (bytes[byteIndex] & (1 << bitIndex)) != 0;
    }
}

應用場景#

1. 爬蟲 URL 去重#

問題：10 億個網頁 URL，如何快速判斷是否已爬取？

散列表方案：

• 平均 URL 64 位元組 → 60GB+ 記憶體

位圖 + 布隆過濾器方案：

• 100 億位元 ≈ 1.2 GB
• 允許小概率誤判（漏爬幾個網頁可接受）

2. 海量整數排序#

問題：1 億個整數，範圍 1~10 億，快速排序

解法：

1. 建立 10 億位元的位圖（125 MB）
2. 走訪整數，設置對應位元為 1
3. 順序掃描位圖，輸出為 1 的索引

時間複雜度：O(N + M)，其中 M 為資料範圍

3. 用戶活躍統計#

每日用戶訪問記錄：

• 1 億用戶 → 12.5 MB 位圖
• 第 i 位為 1 表示用戶 i 今日活躍
• 多日位圖做 AND 運算可求連續活躍用戶

位圖 vs 布隆過濾器#

當資料範圍遠大於資料量時（如範圍 1~10 億，但只有 1 千萬個數），位圖空間浪費嚴重，應使用布隆過濾器。

常用實作#

• Java: BitSet 類
• Redis: SETBIT、GETBIT 命令
• Google Guava: BloomFilter