2024-05-15

PHP数据结构:布隆过滤器的巧用,实现高效的集合检索

布隆过滤器是一种空间效率高的数据结构,用于判断元素是否属于集合。它使用哈希函数和位数组来高效地查找是否存在该元素,可能会出现假阳性。它适用于需要快速检索大量元素的场景,如url重复检测。

PHP数据结构:布隆过滤器的巧用,实现高效的集合检索

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. 初始化布隆过滤器,设置大小和哈希函数个数。
  2. 为每个已抓取的 URL 调用 add() 方法将其添加到过滤器中。
  3. 当遇到新的 URL 时,使用 isExists() 方法快速检查它是否已经存在于过滤器中。如果存在,则跳过该 URL;否则,将新 URL 添加到过滤器中。

优点:

  • 空间高效:布隆过滤器大小与需要检测的元素数量无关。
  • 检索速度快:通过使用哈希函数,检索操作无需遍历整个集合。
  • 可接受的误差率:布隆过滤器允许一些假阳性,但可以根据需要调整大小和哈希函数个数来优化误差率。

以上就是PHP数据结构:布隆过滤器的巧用,实现高效的集合检索的详细内容,更多请关注php中文网其它相关文章!

https://www.php.cn/faq/791800.html

发表回复

Your email address will not be published. Required fields are marked *