PHP データ構造: 効率的なコレクション取得を実現するためのブルームフィルターの賢明な使用-PHPチュートリアル-php.cn

PHP データ構造: 効率的なコレクション取得を実現するためのブルームフィルターの賢明な使用

WBOY

リリース： 2024-06-01 16:04:05

オリジナル

915 人が閲覧しました

ブルームフィルターは、要素がセットに属しているかどうかを判断するために使用されるスペース効率の高いデータ構造です。ハッシュ関数とビット配列を使用して、要素が存在するかどうかを効率的に検索します (誤検知も発生する可能性があります)。 URL 重複検出など、多数の要素を迅速に取得する必要があるシナリオに適しています。

PHP データ構造: 効率的なコレクション取得を実現するためのブルームフィルターの賢明な使用

PHP データ構造: ブルームフィルターを賢く使用して、効率的なコレクションの取得を実現します

はじめに

ブルームフィルターは、要素がギャザリングに属するかどうかを決定するために使用される、スペース効率の高いデータ構造です。ハッシュ関数とビット配列を使用して、要素が存在するかどうかを効率的に検索します。

原理

ブルームフィルターはビット配列を初期化し、各位置は最初は0です。次に、複数のハッシュ関数を使用して要素がハッシュされ、ビット配列にハッシュ値のインデックスが付けられ、その位置の値が 1 に設定されます。

要素がセットに属している場合、そのハッシュ値はビット配列内で 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がクロールされたかどうかを迅速に検出します。

実装: