當需要處理億級整數集合的存在性判斷(如用戶 ID 去重、標籤系統)時,傳統陣列或資料庫索引佔用記憶體極大。位圖 以 bit 為單位存儲,空間效率極高。本文詳細講解位圖原理,並提供一個可直接使用的 PHP BigMap 類。
N:N >> 5(等價 N / 32)N & 0x1F(等價 N % 32)array[index] |= (1 << offset)array[index] &= ~(1 << offset)array[index] & (1 << offset)以 N=30 為例:下標 0,偏移 30,對應二進制第 30 位置 1。
1000 萬個 bit ≈ 1.25 MB,遠小於陣列或資料庫方案。
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); // 查看底層陣列
SplFixedArray 替代普通陣列提升性能。gmp 或 bcmath 擴展支援超大整數位運算。$bitArray 存入 Redis/文件。位圖是處理大規模稀疏整數集合的利器,BigMap 類以極簡代碼展示了核心邏輯,可作為高性能組件的基石進一步優化。