布隆过滤器是一种空间效率高的数据结构，用于判断元素是否属于集合。它使用哈希函数和位数组来高效地查找是否存在该元素，可能会出现假阳性。它适用于需要快速检索大量元素的场景，如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 是否已经被抓取过。
实现：
- 初始化布隆过滤器，设置大小和哈希函数个数。
- 为每个已抓取的 URL 调用
add()方法将其添加到过滤器中。 - 当遇到新的 URL 时，使用
isExists()方法快速检查它是否已经存在于过滤器中。如果存在，则跳过该 URL；否则，将新 URL 添加到过滤器中。
优点：
- 空间高效：布隆过滤器大小与需要检测的元素数量无关。
- 检索速度快：通过使用哈希函数，检索操作无需遍历整个集合。
- 可接受的误差率：布隆过滤器允许一些假阳性，但可以根据需要调整大小和哈希函数个数来优化误差率。
