布隆过滤器原理及其应用

解决成员查询问题的最简单且最知名的数据结构是 布隆过滤器（bloom filter）。1970 年由 Burton Howard Bloom 提出。

布隆过滤器只支持两种操作：

向集合添加一个元素。
测试一个元素是否属于该集合

布隆过滤器不支持删除操作，如果需要删除操作，可以考虑使用改进的方法，例如：计数布隆过滤器

优点

高效性：内存占用小，查询速度快。
可扩展性：通过改进可以适应更多场景。
概率特性：能有效减少误判率。

缺点

假阳性问题：无法完全避免误判。
不支持精确删除：原始布隆过滤器无法删除元素。
依赖散列函数：散列函数的选择直接影响性能。

数据结构

实际应用中，常用 比特数组 来表示布隆过滤器。假定该数组长度为 $m$ ，包含不同的散列函数 $\{h_i\}_{i=1}^{k}$ 。假定 $m$ 正比于期望的元素数量 $n$ ，且 $k \ll m$ 。

数组一开始被初始化为 0
散列函数 $h_i$ 必须相互独立且服从均匀分布
由于散列碰撞，数组中的一些比特可能多次被置为 1

添加元素

插入元素 x 时，则需要对每个散列函数 $h_k$ 计算其值 $j=h_k(x)$ ，并将过滤器中的第 $j$ 位的比特置为 1。

检测元素

如果遍历发现某个散列计算出来的位置对应的比特位不为 1，则为 False。

如果所有对应的比特都已经被置为1，那么元素 x 可能存在于过滤器中 。否则，元素 x 一定不可能在过滤器中。

假阳性的概率分析

布隆过滤器的不足之处就是它可能把不在集合中的元素错判成集合中的元素，这个概率很低。

假定布隆过滤器中有 $m$ 比特，里面有 $n$ 个元素，每个元素对应 $k$ 个信息指纹的散列函数。目前比特数组中有的是 1，有的 0。

向这个布隆过滤器中插入一个元素，它的第一个散列函数会把某个比特置为 1。因此，任何一个比特被置为 1 的概率是 $1/m$ ，该位依然是 0 的概率则是：

$1-\frac{1}{m}$

对于某个特定的位置， $k$ 个散列函数都没有把这个位置设置为 1 的概率：

$(1-\frac{1}{m})^k$

依此类推，插入 $n$ 个元素后，还没有把该位设置为 1（依然为 0），概率是：

$(1-\frac{1}{m})^{kn}$

反过来，某个比特位置，再被插入 $n$ 个元素后，被设置为 1 的概率：

$1-(1-\frac{1}{m})^{kn}$

现在假定 $n$ 个元素都在布隆过滤器中，新增一个不在该集合中的元素。一个不在集合中的元素被误识别为在集合中，需要所有的散列函数对应的比特值均为 1，其概率为：

$P_{fp}=(1-(1-\frac{1}{m})^{kn})^k \approx (1 - e^{-\frac{kn}{m}})^k$

这是下界的概率。在期望元素总数 n 固定的情况下，假阳性率取决于 k 和 m 的选择。很显然，这是在过滤器的大小、散列函数的数量与误报率之间做出权衡。

实际情况中，假阳性率 $P_{fp}$ 以及期望元素数量 n 确定的时候，过滤器长度 m 由公式决定：

$m=-\frac{n\ln{P_{fp}}}{(\ln{2})^2}$

因此为保持误报率不变，过滤器的大小与元素数量呈线性关系。

对于给定比例 m/n，其意义为每个元素所需要分配的平均存储位数，假阳性率可以通过改变散列函数的数量 k 进行调整。最优的 k 值可通过最小化公式 $P_{fp}$ 中的假阳性率来计算的：

$k=\frac{m}{n}\ln{2}$

换句话来说，散列函数的最优数量 k 约为每个元素平均比特数的 0.7 倍。因为 k 必须为一个整数，因此向下取整的 k 的次优值是更为常用的。

基础实现

用 Rust 语言实现一个基础的布隆过滤器：

use std::collections::hash_map::DefaultHasher;
use std::hash::{Hash, Hasher};

pub struct BloomFilter {
    bit_array: Vec<bool>,
    size: usize,
    hash_functions: usize,
}

impl BloomFilter {
    /// 创建一个新的布隆过滤器
    pub fn new(size: usize, hash_functions: usize) -> Self {
        BloomFilter {
            bit_array: vec![false; size],
            size,
            hash_functions,
        }
    }

    /// 将一个元素插入布隆过滤器
    pub fn insert<T: Hash>(&mut self, item: T) {
        for i in 0..self.hash_functions {
            let index = self.hash(&item, i) % self.size;
            self.bit_array[index] = true;
        }
    }

    /// 检查一个元素是否可能在布隆过滤器中
    pub fn contains<T: Hash>(&self, item: T) -> bool {
        for i in 0..self.hash_functions {
            let index = self.hash(&item, i) % self.size;
            if !self.bit_array[index] {
                return false;
            }
        }
        true
    }

    /// 内部散列函数
    fn hash<T: Hash>(&self, item: &T, seed: usize) -> usize {
        let mut hasher = DefaultHasher::new();
        item.hash(&mut hasher);
        seed.hash(&mut hasher);
        hasher.finish() as usize
    }
}

fn main() {
    // 创建大小为 100，散列函数数量为 3 的布隆过滤器
    let mut bloom = BloomFilter::new(100, 3);

    bloom.insert("hello");
    bloom.insert("world");

    println!("Contains 'hello': {}", bloom.contains("hello")); // true
    println!("Contains 'world': {}", bloom.contains("world")); // true
    println!("Contains 'rust': {}", bloom.contains("rust"));   // false
}

DefaultHasher 是 Rust 标准库中一个基于 SipHash 算法实现的默认哈希器，用于生成散列值。

基础单元测试


#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_insert_and_contains() {
        let mut bloom = BloomFilter::new(100, 3);
        bloom.insert("hello");
        bloom.insert("world");

        // 正确包含的元素
        assert!(bloom.contains("hello"));
        assert!(bloom.contains("world"));

        // 不包含的元素
        assert!(!bloom.contains("rust"));
        assert!(!bloom.contains("bloom"));
    }

    #[test]
    fn test_false_positive_rate() {
        let mut bloom = BloomFilter::new(100, 3);
        let items = vec!["item1", "item2", "item3"];
        for item in &items {
            bloom.insert(item);
        }

        // 确保插入的元素都存在
        for item in &items {
            assert!(bloom.contains(item));
        }

        // 测试一些未插入的元素，可能存在假阳性
        let false_items = vec!["not_in_set1", "not_in_set2"];
        let mut false_positives = 0;
        for item in &false_items {
            if bloom.contains(item) {
                false_positives += 1;
            }
        }

        // 允许少量假阳性
        assert!(false_positives <= 1);
    }

    #[test]
    fn test_empty_bloom_filter() {
        let bloom = BloomFilter::new(100, 3);

        // 检查空的布隆过滤器
        assert!(!bloom.contains("anything"));
    }

    #[test]
    fn test_large_dataset() {
        let mut bloom = BloomFilter::new(10000, 5); // 如果数值小了，会有假阳性，导致失败
        let mut inserted_items = Vec::new();

        // 插入大量数据
        for i in 0..500 {
            let item = format!("item{}", i);
            bloom.insert(&item);
            inserted_items.push(item);
        }

        // 确保插入的数据都可以被查询
        for item in &inserted_items {
            assert!(bloom.contains(item));
        }

        // 测试一些未插入的随机数据
        for i in 500..600 {
            let item = format!("random{}", i);
            assert!(!bloom.contains(&item)); // 理论上不应该存在
        }
    }
}

test_large_dataset 中如果 10000 改成 1000，可以发现测试会失败，代入公式：

$(1 - (1 - 1/1000)^{5\cdot 500})^5$

可以计算出，假阳性概率达到了 0.65。

改进方法

计数布隆过滤器

计数布隆过滤器（Counting Bloom Filter）在原始布隆过滤器的基础上，用计数数组代替比特数组。每个位置存储一个计数值而不是单一的 0 或 1，从而支持删除操作。

工作原理：

插入元素时，对应的计数值加 1。
删除元素时，对应的计数值减 1。

注意：计数值不能为负。

分层布隆过滤器

分层布隆过滤器（Layered Bloom Filter）通过增加多个布隆过滤器的层级来支持动态扩展，适用于需要不断增加新数据的场景。

工作原理：

每个层级对应一个布隆过滤器，层级越高，其大小越大。
当某一层级的布隆过滤器超载时，新建一个更大的布隆过滤器作为下一层。

可扩展布隆过滤器

可扩展布隆过滤器（Scalable Bloom Filter）通过动态调整大小，避免原始布隆过滤器中容量固定的问题。

特点：

新建过滤器以适应数据增长。
支持多种策略来控制增长速度。

应用

防止密码泄露

在用户注册时，检查密码是否属于常用密码集合。将已知弱密码存储在布隆过滤器中，可以快速判断用户密码的强度。

爬虫优化

布隆过滤器可用于检测 URL 是否已经被访问过，从而减少重复爬取。

缓存穿透

在缓存层引入布隆过滤器，减少对数据库的无效查询请求。

网络路由

在分布式系统中，布隆过滤器可用于快速判断某个元素是否属于某个节点。

区块链

布隆过滤器可以用于轻量级节点快速查询交易是否属于某个区块。

参考资料

[乌克兰] 安德烈·加霍夫著,王平辉,贾鹏,李润东译.概率数据结构与算法：面向大数据应用.机械工业出版社有限公司.2022
吴军著.数学之美（第三版）.人民邮电出版社.2020