萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> PHP 程式設計

PHP 位圖 實現大數據集合高效存儲與查詢

當需要處理億級整數集合的存在性判斷(如用戶 ID 去重、標籤系統)時,傳統陣列或資料庫索引佔用記憶體極大。位圖 以 bit 為單位存儲,空間效率極高。本文詳細講解位圖原理,並提供一個可直接使用的 PHP BigMap 類。

位圖核心原理

  • 一個 32 位整數可代表 0~31 共 32 個數字的存在狀態。
  • 對於數字 N:
    • 陣列下標:N >> 5(等價 N / 32)
    • 位偏移:N & 0x1F(等價 N % 32)
    • 設置 bit:array[index] |= (1 << offset)
    • 清除 bit:array[index] &= ~(1 << offset)
    • 測試 bit:array[index] & (1 << offset)

以 N=30 為例:下標 0,偏移 30,對應二進制第 30 位置 1。

空間估算

1000 萬個 bit ≈ 1.25 MB,遠小於陣列或資料庫方案。

PHP 類實現

class BigMap {
    private $mask = 0x1F;      // 31,用於取模 32
    private $bitsPerWord = 32;
    private $shift = 5;        // 2^5 = 32
    public $bitArray = array();

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

    // 置 0
    function clearBit($i) {
        @$this->bitArray[$i >> $this->shift] &= ~(1 << ($i & $this->mask));
    }

    // 測試
    function testBit($i) {
        return $this->bitArray[$i >> $this->shift] & (1 << ($i & $this->mask));
    }
}

// 使用示例
$oBig = new BigMap();
$oBig->setBit(30);
var_dump($oBig->testBit(2));  // false
var_dump($oBig->testBit(30)); // true
var_dump($oBig->bitArray);    // 查看底層陣列

應用場景

  • 海量用戶 ID 去重/簽到統計
  • URL 爬蟲去重(Bloom Filter 的基礎)
  • 標籤/權限位掩碼系統
  • 大範圍整數集合的快速交並差運算

擴展建議

  • 使用 SplFixedArray 替代普通陣列提升性能。
  • 結合 gmp 或 bcmath 擴展支援超大整數位運算。
  • 持久化時可序列化 $bitArray 存入 Redis/文件。

位圖是處理大規模稀疏整數集合的利器,BigMap 類以極簡代碼展示了核心邏輯,可作為高性能組件的基石進一步優化。

copyright © 萬盛學電腦網 all rights reserved