萬盛學電腦網

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

PHP 實現 Bloom Filter(布隆過濾器)算法

Bloom Filter 是一種空間極其高效的概率型資料結構,用於判斷元素是否存在於大數據集合中,允許極低的誤判率(False Positive),但絕無漏判。本文從原理到 PHP 完整實現,詳細剖析其核心機制與工程權衡。

核心原理

  1. 申請一個長度為 m 位的位陣列,初始全 0。
  2. 選取 k 個相互獨立的哈希函數,每個函數將元素映射到 [0, m-1] 範圍。
  3. 添加元素:計算 k 個哈希值,將對應位置 1。
  4. 查詢元素:計算 k 個哈希值,若所有位均為 1 則「可能存在」,若有任一位為 0 則「一定不存在」。

誤判率公式:(1 - e^(-kn/m))^k。通過調整 m(位陣列大小)與 k(哈希函數數量)平衡空間、速度與誤判率。

典型應用場景

  • 垃圾郵件過濾(記錄億級黑名單郵箱)
  • 網頁爬蟲 URL 去重(判斷 URL 是否已抓取)
  • 緩存穿透防護(快速判斷 key 是否可能存在)
  • 大數據集合的快速存在性檢查

PHP 簡化版演示

$set = array(1,2,3,4,5,6);
$bloomFilter = array_fill(0, 10, 0);

// 簡單映射:直接用值作為下標(僅示意)
foreach ($set as $key) {
    $bloomFilter[$key] = 1;
}

// 查詢
echo isset($bloomFilter[9]) && $bloomFilter[9] ? '在集合中' : '不在集合中';

生產級類實現

class Bloom_Filter {
    private $hashFuncNum;      // 哈希函數個數
    private $spaceGroupNum;    // 空間組數(分片)
    private $hashSpaceAssoc;   // 位陣列存儲
    private $oneNum = 8;       // 每字節 8 位

    public function __construct($hash_func_num = 3, $space_group_num = 1) {
        $maxLength = pow(2, 25); // 32MB per group
        $binary = pack('C', 0);
        $this->hashFuncNum = $hash_func_num;
        $this->spaceGroupNum = $space_group_num;
        for ($i = 0; $i < $space_group_num; $i++) {
            $this->hashSpaceAssoc[$i] = str_repeat($binary, $maxLength);
        }
        // 預計算 2^n 用於哈希
        $this->powArray = array();
        for ($i = 0; $i < 32; $i++) $this->powArray[$i] = 1 << $i;
    }

    // 多哈希函數(簡易示例,實際建議用 murmurhash、fnv 等)
    private function _hash($str, $seed) {
        $hash = 0;
        for ($i = 0; $i < strlen($str); $i++) {
            $hash = $hash * $seed + ord($str[$i]);
        }
        return $hash;
    }

    // 添加元素
    public function add($str) {
        for ($i = 0; $i < $this->hashFuncNum; $i++) {
            $hash = $this->_hash($str, $this->powArray[$i]);
            $group = $hash % $this->spaceGroupNum;
            $pos = $hash % (strlen($this->hashSpaceAssoc[$group]) * 8);
            $byteIndex = $pos >> 3;
            $bitIndex = $pos & 7;
            $this->hashSpaceAssoc[$group][$byteIndex] |= (1 << $bitIndex);
        }
    }

    // 檢查元素
    public function check($str) {
        for ($i = 0; $i < $this->hashFuncNum; $i++) {
            $hash = $this->_hash($str, $this->powArray[$i]);
            $group = $hash % $this->spaceGroupNum;
            $pos = $hash % (strlen($this->hashSpaceAssoc[$group]) * 8);
            $byteIndex = $pos >> 3;
            $bitIndex = $pos & 7;
            if (!($this->hashSpaceAssoc[$group][$byteIndex] & (1 << $bitIndex))) {
                return false; // 確定不存在
            }
        }
        return true; // 可能存在
    }
}

工程優化要點

  • 哈希函數選擇:採用高性能、低衝突的非加密哈希,如 MurmurHash3、FNV-1a、xxHash。
  • 位陣列存儲:使用 Redis 的 SETBIT/GETBIT 或 PHP gmp 擴展,支援分佈式、持久化。
  • 參數計算:根據預估元素數量 n 與目標誤判率 p 計算最優 m、k:
    m = - (n * ln p) / (ln 2)^2
    k = (m / n) * ln 2
  • 序列化/反序列化:支援將位陣列導出/導入,便於進程重啟恢復。

補救誤判

對於極少數誤判為「存在」的關鍵業務(如白名單),可建立小型白名單資料庫二次驗證。

Bloom Filter 以微小的空間換取極快的查詢速度,是大規模系統中不可或缺的「守門員」。PHP 實現雖受限於單進程記憶體,但結合 Redis 等中間件即可構建高性能分佈式過濾服務。

copyright © 萬盛學電腦網 all rights reserved