PHP資料結構：布隆過濾器的巧用，實現高效的集合檢索

布隆濾波器是一種空間效率高的資料結構，用來判斷元素是否屬於集合。它使用雜湊函數和位數組來有效地查找是否存在該元素，可能會出現假陽性。它適用於需要快速檢索大量元素的場景，如URL重複檢測。

PHP 資料結構：巧用布隆過濾器，實作高效集合檢索

##簡介

布隆過濾器是一種高度空間高效的資料結構，用來判斷元素是否屬於一個集合。它使用雜湊函數和位數組來有效地查找是否存在該元素。

原理

布林過濾器初始化一個位元組，每個位置初始為 0。然後，分別使用多個雜湊函數對元素進行哈希，並用哈希值索引位數組，並將該位置的值置為 1。

如果某個元素屬於集合，則其雜湊值將找出位數組中至少一個為 1 的位置。然而，對於不屬於該集合的元素，它也有可能找到為 1 的位置，稱為假陽性。

實作

class BloomFilter {

    // 过滤器大小 (位数)
    private $size;

    // 哈希函数个数
    private $numHashes;

    // 哈希函数
    private $hashFunctions;

    // 过滤器位数组
    private $filter;

    // 初始化布隆过滤器
    public function __construct($size, $numHashes) {
        $this->size = $size;
        $this->numHashes = $numHashes;
        $this->initHashFunctions();
        $this->filter = array_fill(0, $this->size, 0);
    }

    // 初始化哈希函数
    private function initHashFunctions() {
        $this->hashFunctions = [];
        for ($i = 0; $i < $this->numHashes; $i++) {
            $this->hashFunctions[] = function ($key) use ($i) {
                return abs(crc32($key . $i));
            };
        }
    }

    // 向过滤器中添加元素
    public function add($element) {
        foreach ($this->hashFunctions as $hashFunction) {
            $index = $hashFunction($element) % $this->size;
            $this->filter[$index] = 1;
        }
    }

    // 检查元素是否存在过滤器中
    public function isExists($element) {
        foreach ($this->hashFunctions as $hashFunction) {
            $index = $hashFunction($element) % $this->size;
            if ($this->filter[$index] == 0) {
                return false;
            }
        }
        // 找到了元素的所有哈希值对应的位，但可能是假阳性
        return true;
    }
}

#實戰案例：偵測URL 重複

目標：使用布隆過濾器快速偵測大量URL 是否已經被抓取過。

實作：

初始化布隆過濾器，設定大小和雜湊函數個數。
1. 為每個已抓取的 URL 呼叫
2. add() 方法將其新增至篩選器。
當遇到新的 URL 時，使用
3. isExists() 方法快速檢查它是否已經存在於篩選器中。如果存在，則跳過該 URL；否則，將新 URL 新增至篩選器。

優點：

空間高效率：布隆篩選器大小與需要偵測的元素數量無關。
• 檢索速度快：透過使用雜湊函數，檢索操作無需遍歷整個集合。
• 可接受的誤差率：布隆濾波器允許一些假陽性，但可以根據需要調整大小和雜湊函數個數來優化誤差率。

以上是PHP資料結構：布隆過濾器的巧用，實現高效的集合檢索的詳細內容。更多資訊請關注PHP中文網其他相關文章！