PHP项目怎么实现布隆去重？

本文目录导读：

1. 使用 Redis 的布隆过滤器（推荐）
2. 纯 PHP 实现（不依赖外部服务）
3. 使用位图文件实现（适合大量数据）
4. 选择建议
5. 最佳实践

在PHP项目中实现布隆去重,主要有两种方式：

使用 Redis 的布隆过滤器（推荐）

Redis 4.0+ 支持布隆过滤器模块，这是最常用且高效的方式。

安装 RedisBloom 模块

# 下载并编译
git clone https://github.com/RedisBloom/RedisBloom.git
cd RedisBloom
make
# 启动 Redis 时加载
redis-server --loadmodule ./redisbloom.so

PHP 代码实现

<?php
class BloomFilter {
    private $redis;
    private $key;
    public function __construct($redisConfig = []) {
        $this->redis = new Redis();
        $this->redis->connect(
            $redisConfig['host'] ?? '127.0.0.1',
            $redisConfig['port'] ?? 6379
        );
        $this->key = 'bloom_filter';
    }
    /**
     * 添加元素
     */
    public function add($item) {
        return $this->redis->rawCommand('BF.ADD', $this->key, $item);
    }
    /**
     * 检查元素是否存在
     */
    public function exists($item) {
        return $this->redis->rawCommand('BF.EXISTS', $this->key, $item);
    }
    /**
     * 批量添加
     */
    public function mAdd($items) {
        $args = array_merge([$this->key], $items);
        return $this->redis->rawCommand('BF.MADD', ...$args);
    }
    /**
     * 批量检查
     */
    public function mExists($items) {
        $args = array_merge([$this->key], $items);
        return $this->redis->rawCommand('BF.MEXISTS', ...$args);
    }
    /**
     * 创建过滤器（设置参数）
     * @param float $errorRate 错误率（0-1之间）
     * @param int $capacity 预期容量
     */
    public function reserve($errorRate = 0.01, $capacity = 10000) {
        return $this->redis->rawCommand('BF.RESERVE', $this->key, $errorRate, $capacity);
    }
    /**
     * 获取过滤器信息
     */
    public function info() {
        return $this->redis->rawCommand('BF.INFO', $this->key);
    }
}
// 使用示例
$bloom = new BloomFilter();
// 初始化（可选，不设置会自动使用默认参数）
$bloom->reserve(0.001, 100000); // 0.1%错误率，10万容量
// 添加元素
$bloom->add('user_12345');
$bloom->add('url_https://example.com');
// 检查是否存在
if ($bloom->exists('user_12345')) {
    echo "可能存在（可能误判）\n";
} else {
    echo "一定不存在\n";
}
// 批量操作
$users = ['user_1', 'user_2', 'user_3', 'user_4'];
$results = $bloom->mAdd($users); // 返回 [1, 1, 1, 1]
$checkUsers = ['user_1', 'user_999', 'user_3', 'user_888'];
$results = $bloom->mExists($checkUsers); // 返回 [1, 0, 1, 0]

纯 PHP 实现（不依赖外部服务）

适合小型项目或无法安装 Redis 的情况。

<?php
class PureBloomFilter {
    private $bitArray;
    private $size;
    private $hashCount;
    /**
     * @param int $size 位数组大小
     * @param int $hashCount 哈希函数数量
     */
    public function __construct($size = 1000000, $hashCount = 3) {
        $this->size = $size;
        $this->hashCount = $hashCount;
        $this->bitArray = new SplFixedArray($size / PHP_INT_SIZE + 1);
        // 初始化位数组
        for ($i = 0; $i < count($this->bitArray); $i++) {
            $this->bitArray[$i] = 0;
        }
    }
    /**
     * 哈希函数
     */
    private function hash($item, $seed) {
        $hash = crc32($item . $seed);
        return abs($hash) % $this->size;
    }
    /**
     * 设置位
     */
    private function setBit($index) {
        $arrIndex = intdiv($index, PHP_INT_SIZE);
        $bitIndex = $index % PHP_INT_SIZE;
        $this->bitArray[$arrIndex] |= (1 << $bitIndex);
    }
    /**
     * 获取位
     */
    private function getBit($index) {
        $arrIndex = intdiv($index, PHP_INT_SIZE);
        $bitIndex = $index % PHP_INT_SIZE;
        return ($this->bitArray[$arrIndex] >> $bitIndex) & 1;
    }
    /**
     * 添加元素
     */
    public function add($item) {
        for ($i = 0; $i < $this->hashCount; $i++) {
            $index = $this->hash($item, $i);
            $this->setBit($index);
        }
    }
    /**
     * 检查元素是否存在
     */
    public function exists($item) {
        for ($i = 0; $i < $this->hashCount; $i++) {
            $index = $this->hash($item, $i);
            if (!$this->getBit($index)) {
                return false;
            }
        }
        return true;
    }
    /**
     * 保存到文件
     */
    public function save($filename) {
        $data = serialize($this->bitArray);
        file_put_contents($filename, $data);
    }
    /**
     * 从文件加载
     */
    public function load($filename) {
        $data = file_get_contents($filename);
        $this->bitArray = unserialize($data);
    }
    /**
     * 获取当前元素数量（近似值）
     * n ≈ -m * ln(1 - x/m) / k
     */
    public function count() {
        $countOnes = 0;
        $count = count($this->bitArray);
        for ($i = 0; $i < $count; $i++) {
            $countOnes += PHP_INT_SIZE - $this->bitCount(~$this->bitArray[$i]);
        }
        return -$this->size * log(1 - $countOnes / $this->size) / $this->hashCount;
    }
    private function bitCount($n) {
        $count = 0;
        while ($n) {
            $count++;
            $n &= ($n - 1);
        }
        return $count;
    }
}
// 使用示例
$filter = new PureBloomFilter(10000000, 5); // 1000万位，5个哈希函数
// 添加数据
$filter->add('item_1');
$filter->add('item_2');
// 检查
var_dump($filter->exists('item_1'));    // true
var_dump($filter->exists('item_999'));   // false
// 持久化
$filter->save('/tmp/bloom_filter.dat');
// 重新加载
$newFilter = new PureBloomFilter();
$newFilter->load('/tmp/bloom_filter.dat');
var_dump($newFilter->exists('item_1')); // true

使用位图文件实现（适合大量数据）

<?php
class FileBloomFilter {
    private $filename;
    private $size;
    private $hashCount;
    private $file;
    public function __construct($filename, $size = 100000000, $hashCount = 7) {
        $this->filename = $filename;
        $this->size = $size;
        $this->hashCount = $hashCount;
        // 创建或打开位图文件
        if (!file_exists($filename)) {
            $bytes = ceil($size / 8);
            $this->file = fopen($filename, 'wb+');
            ftruncate($this->file, $bytes);
        } else {
            $this->file = fopen($filename, 'rb+');
        }
    }
    private function getPositions($item) {
        $positions = [];
        $hash1 = crc32($item);
        $hash2 = crc32(strrev($item));
        for ($i = 0; $i < $this->hashCount; $i++) {
            $position = abs($hash1 + $i * $hash2) % $this->size;
            $positions[] = $position;
        }
        return $positions;
    }
    public function add($item) {
        $positions = $this->getPositions($item);
        foreach ($positions as $pos) {
            $byteOffset = intdiv($pos, 8);
            $bitOffset = $pos % 8;
            fseek($this->file, $byteOffset);
            $byte = ord(fgetc($this->file));
            fseek($this->file, $byteOffset);
            fwrite($this->file, chr($byte | (1 << $bitOffset)));
        }
    }
    public function exists($item) {
        $positions = $this->getPositions($item);
        foreach ($positions as $pos) {
            $byteOffset = intdiv($pos, 8);
            $bitOffset = $pos % 8;
            fseek($this->file, $byteOffset);
            $byte = ord(fgetc($this->file));
            if (!($byte & (1 << $bitOffset))) {
                return false;
            }
        }
        return true;
    }
    public function __destruct() {
        if ($this->file) {
            fclose($this->file);
        }
    }
}

选择建议

最佳实践

// 结合数据库的完整示例
class URLDeduplicator {
    private $bloom;
    private $db;
    public function __construct() {
        // 使用 Redis Bloom
        $this->bloom = new BloomFilter();
        // 数据库作为后备存储
        $this->db = new PDO('mysql:host=localhost;dbname=test', 'user', 'pass');
        // 初始化布隆过滤器
        $this->bloom->reserve(0.0001, 10000000);
    }
    public function isDuplicate($url) {
        // 先在布隆过滤器中检查
        if (!$this->bloom->exists($url)) {
            return false;
        }
        // 布隆过滤器返回可能存在，再到数据库确认
        $stmt = $this->db->prepare('SELECT id FROM urls WHERE url = ?');
        $stmt->execute([$url]);
        return (bool)$stmt->fetch();
    }
    public function add($url) {
        // 先添加到布隆过滤器
        $this->bloom->add($url);
        // 再存入数据库
        $stmt = $this->db->prepare('INSERT INTO urls (url) VALUES (?)');
        $stmt->execute([$url]);
    }
}

这样结合布隆过滤器和数据库,既能保证速度，又能确保准确性。