PHP中使用位圖優化大數據存儲與查找實戰

PHP位圖算法原理與BigMap類實現詳解

在處理大規模數據去重、排序或存在性判斷時，傳統數組或哈希表往往面臨內存佔用過大的問題。位圖作為一種極其節省空間的數據結構，利用單個bit位標記元素是否存在，能以極低的內存成本解決千萬級甚至億級數據的快速查找與統計問題。本文將深入剖析位圖的核心原理，並提供一個可直接用於生產環境的PHP BigMap類實現。

位圖核心原理：以空間換時間的極致體現

位圖的基本思想是：申請一塊連續內存空間，每個bit位對應一個非負整數。若某數字存在，則將對應bit位置1；反之置0。由於1個字節包含8個bit位，理論上1MB內存即可容納800萬個數字的標記信息，遠小於數組或哈希表的開銷。

具體映射規則包含三步運算：

1. 定位數組下標：index = n >> 5（等價於 n / 32），因每個32位整數可存32個bit
2. 計算bit偏移量：offset = n & 0x1F（等價於 n % 32），定位在32位整數內的具體位置
3. 設置/檢測bit位：通過 1 << offset 生成掩碼，配合位運算實現置1、清0、測試操作

以數字30為例：30 >> 5 = 0 定位到 a[0]，30 & 31 = 30 偏移30位，最終 a[0] 的二進制表示為 01000000 00000000 00000000 00000000（十進制1073741824）。

BigMap類完整實現代碼

<?php
class BigMap {
    // 掩碼：0x1F = 31，用於快速取模32
    private $mask = 0x1F;
    // 每個字存儲32位
    private $bitsPerWord = 32;
    // 移位數：2^5 = 32
    private $shift = 5;
    // 存儲數據的數組
    public $bitArray = array();

    /** 將指定位置清零 */
    public function clearBit($i) {
        @$this->bitArray[$i >> $this->shift] &= ~(1 << ($i & $this->mask));
    }

    /** 將指定位置置1 */
    public function setBit($i) {
        @$this->bitArray[$i >> $this->shift] |= (1 << ($i & $this->mask));
    }

    /** 測試指定位置是否為1 */
    public function testBit($i) {
        return $this->bitArray[$i >> $this->shift] & (1 << ($i & $this->mask));
    }
}

// 測試用例
$oBig = new BigMap();
$oBig->setBit(30);
var_dump($oBig->testBit(2));  // 輸出 bool(false)
var_dump($oBig->bitArray);    // 輸出 array(0 => 1073741824)
echo decbin($oBig->bitArray[0]), "<br>"; // 輸出二進制字符串

性能優勢與適用場景

對比傳統方案：存儲1000萬個整數，數組需約40MB（int類型4字節×1000萬），哈希表更大；而位圖僅需 10000000 / 8 / 1024 / 1024 ≈ 1.2MB。適用於：

• 大規模用戶ID去重（如日活統計）
• URL爬蟲去重過濾
• 權限標記系統（用戶角色、功能開關）
• 布隆過濾器的底層存儲結構

擴展建議

生產環境中可結合Redis的Bitmap命令（SETBIT/GETBIT/BITCOUNT）實現分佈式位圖，突破單機內存限制，並利用Redis持久化保證數據安全。