本文目录导读：
我来给你详细介绍PHP中布隆过滤器的使用,包括原生实现和Redis实现两种方式。
使用Redis的布隆过滤器（推荐）
安装RedisBloom模块
# Ubuntu/Debian sudo apt-get install redis-server # 然后安装RedisBloom模块 git clone https://github.com/RedisBloom/RedisBloom.git cd RedisBloom make # 在redis.conf中添加 loadmodule /path/to/redisbloom.so
PHP使用示例
<?php
class BloomFilterRedis {
private $redis;
private $key;
public function __construct($host = '127.0.0.1', $port = 6379, $key = 'bloom_filter') {
$this->redis = new Redis();
$this->redis->connect($host, $port);
$this->key = $key;
}
/**
* 创建布隆过滤器
* @param float $errorRate 错误率 (0-1)
* @param int $capacity 预计元素数量
*/
public function create($errorRate = 0.01, $capacity = 100000) {
return $this->redis->rawCommand('BF.RESERVE', $this->key, $errorRate, $capacity);
}
/**
* 添加元素
*/
public function add($item) {
return $this->redis->rawCommand('BF.ADD', $this->key, $item);
}
/**
* 批量添加元素
*/
public function addMultiple(array $items) {
$params = array_merge(['BF.MADD', $this->key], $items);
return $this->redis->rawCommand(...$params);
}
/**
* 检查元素是否存在
* @return bool true=可能存在, false=一定不存在
*/
public function exists($item) {
return $this->redis->rawCommand('BF.EXISTS', $this->key, $item) === 1;
}
/**
* 批量检查元素
*/
public function existsMultiple(array $items) {
$params = array_merge(['BF.MEXISTS', $this->key], $items);
return $this->redis->rawCommand(...$params);
}
/**
* 获取布隆过滤器信息
*/
public function info() {
return $this->redis->rawCommand('BF.INFO', $this->key);
}
}
// 使用示例
$bf = new BloomFilterRedis();
// 创建过滤器
$bf->create(0.01, 100000);
// 添加单个元素
$bf->add('user_12345');
// 批量添加
$bf->addMultiple(['user_123', 'user_456', 'user_789']);
// 检查是否存在
var_dump($bf->exists('user_123')); // bool(true) - 可能存在
var_dump($bf->exists('user_99999')); // bool(false) - 一定不存在
纯PHP实现布隆过滤器
<?php
class BloomFilter {
private $bitArray;
private $size;
private $hashFunctions;
/**
* @param int $size 位数组大小
* @param int $hashFunctions 哈希函数数量
*/
public function __construct($size = 100000, $hashFunctions = 3) {
$this->size = $size;
$this->hashFunctions = $hashFunctions;
$this->bitArray = array_fill(0, $size, 0);
}
/**
* 计算多个哈希值
* @param string $item
* @return array 返回哈希值数组
*/
private function hash($item) {
$hashes = [];
// 使用多个不同的哈希函数
$hashes[] = crc32($item);
$hashes[] = md5($item);
$hashes[] = sha1($item);
// 补充其他哈希
for ($i = 3; $i < $this->hashFunctions; $i++) {
$hashes[] = hexdec(substr(hash('sha256', $item . $i), 0, 8));
}
// 映射到bit数组范围
return array_map(function($hash) {
return $hash % $this->size;
}, $hashes);
}
/**
* 添加元素
*/
public function add($item) {
$hashes = $this->hash($item);
foreach ($hashes as $hash) {
$this->bitArray[$hash] = 1;
}
}
/**
* 批量添加
*/
public function addMultiple(array $items) {
foreach ($items as $item) {
$this->add($item);
}
}
/**
* 检查元素是否存在
* @return bool true=可能存在, false=一定不存在
*/
public function contains($item) {
$hashes = $this->hash($item);
foreach ($hashes as $hash) {
if (!isset($this->bitArray[$hash]) || $this->bitArray[$hash] === 0) {
return false; // 一定不存在
}
}
return true; // 可能存在
}
/**
* 获取当前填充的位数
*/
public function getFilledBits() {
return array_sum($this->bitArray);
}
}
// 使用示例
$bf = new BloomFilter(100000, 3);
// 添加一些用户名
$usernames = ['alice', 'bob', 'charlie', 'david'];
$bf->addMultiple($usernames);
// 检查
var_dump($bf->contains('alice')); // bool(true) 可能存在
var_dump($bf->contains('eve')); // bool(false) 一定不存在
使用第三方库 (phpbloom)
<?php
// 安装: composer require danielstjules/php-bloom-filter
require 'vendor/autoload.php';
use BloomFilter\BloomFilter;
// 创建布隆过滤器实例
$bloom = new BloomFilter(100000, 0.01); // 容量, 误判率
// 添加元素
$bloom->add('user@example.com');
// 检查是否存在
if ($bloom->has('user@example.com')) {
echo "可能存在";
}
// 批量添加
$emails = ['a@example.com', 'b@example.com', 'c@example.com'];
$bloom->addAll($emails);
实际应用场景示例
<?php
class CacheService {
private $bf;
private $cache;
private $db;
public function __construct() {
$this->bf = new BloomFilterRedis();
$this->cache = new Redis();
$this->cache->connect('127.0.0.1', 6379);
// 初始化数据库连接...
}
/**
* 防止缓存穿透的查询方法
*/
public function getUserData($userId) {
$key = "user:{$userId}";
// 1. 先检查布隆过滤器
if (!$this->bf->exists("user:{$userId}")) {
return null; // 一定不存在，直接返回
}
// 2. 检查缓存
$data = $this->cache->get($key);
if ($data !== false) {
return json_decode($data, true);
}
// 3. 查询数据库
$user = $this->db->find($userId);
if ($user) {
// 4. 写入缓存
$this->cache->set($key, json_encode($user), 3600);
return $user;
}
// 5. 数据不存在，缓存空值防止穿透
$this->cache->set($key, null, 60);
return null;
}
/**
* 添加新用户时更新布隆过滤器
*/
public function addUser($userId) {
$this->bf->add("user:{$userId}");
}
}
参数选择建议
<?php
/**
* 计算最佳参数
* @param int $n 预计元素数量
* @param float $p 误判率（0-1）
* @return array [大小, 哈希函数数量]
*/
function calculateOptimalParams($n, $p) {
$size = ceil(-($n * log($p)) / (log(2) * log(2)));
$hashFunctions = ceil(($size / $n) * log(2));
return [$size, $hashFunctions];
}
// 预计10万数据，误判率1%
list($size, $hashNum) = calculateOptimalParams(100000, 0.01);
echo "推荐位数组大小: {$size}\n"; // 约958506位（约117KB）
echo "推荐哈希函数数量: {$hashNum}\n"; // 约7个
注意事项
- 不能删除元素：布隆过滤器不支持删除操作
- 误判率：存在一定的误判率，根据参数调整
- 内存优化：位数组大小直接影响内存使用
- 应用场景：适合"一定不存在"的判断，用于防止缓存穿透、URL去重等场景
选择哪种实现方式取决于你的需求：Redis实现更适合分布式系统，纯PHP实现适合单机应用。
