位圖 (Bitmap)#

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

核心思想#

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

• 1：存在
• 0：不存在

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

基本操作#

設置第 k 位為 1#

words[k ushr 6] = words[k ushr 6] or (1L shl (k and 63))  // k ushr 6 = k / 64；k and 63 = k % 64

查詢第 k 位#

return (words[k ushr 6] and (1L shl (k and 63))) != 0L

這裡用 LongArray 當底層儲存：每個 Long 剛好塞 64 個 bit。k ushr 6 取得所在的 word 索引（等同 k / 64），k and 63 取得該 bit 在 word 內的位置（等同 k % 64）。用位移與遮罩取代除法／取模，既快又不失精度。

class BitMap(private val nbits: Int) {
    // 每個 Long 存 64 個 bit
    private val words = LongArray(nbits / 64 + 1)

    fun set(k: Int) {
        if (k > nbits) return
        val wordIndex = k ushr 6          // k / 64
        words[wordIndex] = words[wordIndex] or (1L shl (k and 63))  // 設第 k % 64 位
    }

    fun get(k: Int): Boolean {
        if (k > nbits) return false
        return (words[k ushr 6] and (1L shl (k and 63))) != 0L
    }
}

應用場景#

爬蟲 URL 去重#

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

雜湊表方案：

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

位圖 + 布隆過濾器方案：

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

海量整數排序#

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

解法：

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

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

使用者活躍統計#

每日使用者訪問記錄：

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

位圖即集合：位元運算就是集合運算#

把一個位圖看成一個集合——第 i 個 bit 為 1，就代表元素 i 在集合裡——之後集合的各種運算，恰好就對應到底層的位元運算：

// 用整數當小型位圖：Kotlin 的 Int 是 32 位、Long 是 64 位，可裝下對應數量的元素
val setA = 0b1010   // 集合 {1, 3}
val setB = 0b0110   // 集合 {1, 2}

val union     = setA or setB    // {1, 2, 3}
val intersect = setA and setB   // {1}
val symDiff   = setA xor setB   // {2, 3}

不同於 Python 的任意精度整數，Kotlin 的 Int/Long 是定長的；要表示超過 64 個元素的集合時，就得改用 LongArray 這類位圖陣列（如上面的 BitMap），對每個 word 分別做位元運算。

真正的威力在於：現代 CPU 一條指令就能對 32 或 64 個 bit 同時做布林運算。所以用位圖表示集合時，整個集合的交聯運算往往一兩個指令就完成——又快又省空間。

這也解釋了兩個重量級應用為什麼能快：

• 資料庫的點陣圖索引 (bitmap index)：把每個欄位值編成一張位圖（例如「性別 = 男」一張、「縣市 = 台北」一張），查詢 性別 = 男 AND 縣市 = 台北 就是兩張位圖做 AND，瞬間得到符合的列。
• 搜尋引擎對倒排索引做布林查詢：每個關鍵詞對應一張「含有此詞的文件」位圖，查 貓 AND 狗 就是兩張位圖 AND、貓 OR 狗 就是 OR，整批文件一次算完。

關於 AND/OR/XOR/NOT 等底層運算的細節，見位操作基礎。

從問題約束長出解法：電話號碼排序#

上面的「海量整數排序」其實是一個更廣的經典題：給一堆互不重複、且落在有限範圍內的整數（典型例子是一批電話號碼），要同時做到去重與排序。

解法只有一句話：開一個 bit 陣列，讀到整數 i 就把第 i 個 bit 設成 1；全部讀完後，從頭掃一遍，把所有為 1 的位置依序輸出即可。

fun sortAndDedup(nums: IntArray, maxVal: Int) {
    val bitmap = BitMap(maxVal)
    for (n in nums) {
        bitmap.set(n)                       // 重複的數設兩次也只是 1，自動去重
    }
    for (i in 0..maxVal) {
        if (bitmap.get(i)) {
            print("$i ")                    // 由小到大輸出，自動排序
        }
    }
}

掃描天然由小到大，所以排序免費；同一個 bit 設幾次都是 1，所以去重也免費。空間只要 O(最大值 / 8) bytes。

值得體會的是：一般排序的下界是 O(n log n)，但這裡只用 O(n + 最大值) 就同時拿到排序與去重。差別不在技巧，而在我們精確利用了問題的約束——「不重複」與「有限範圍整數」這兩個條件，直接打開了一條普通排序看不到的路。約束愈精確，解法的空間愈大。

位圖 vs 布隆過濾器#

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

常用實作#

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