前言

在现代互联网系统中，性能与资源的平衡尤为重要。**Bloom Filter（布隆过滤器）**作为一种极致空间效率的数据结构，常用于“快速判断某元素是否存在于一个集合中”，广泛应用于缓存、搜索引擎、防止重复提交等场景。

定义

Wiki 定义如下：

A Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set.

简而言之：布隆过滤器是一种基于位数组和哈希函数的概率性数据结构，用于集合“可能包含”与“一定不包含”元素的快速判断。

工作原理

一句话：通过将元素用多个哈希函数映射到位数组上的若干位置，实现高效存在性判断。

简要步骤如下：

  1. 初始化一个长度为 m 的位数组，初始全为 0；
  2. 插入元素时，计算 k 个哈希函数，置对应位为 1；
  3. 查询时，检查这 k 位是否都为 1，若存在一位为 0，则该元素一定不存在；若全为 1，则“可能存在”。

属性与指标

布隆过滤器关注的关键属性如下：

  1. False Positive Rate（误判率）：布隆过滤器会有“可能存在”的误判，但不会漏判（即不会错判存在为不存在）。
  2. Bit Array Size（位数组大小）：越大越准确，但也占内存。
  3. Hash Functions 数量（k）：哈希函数越多，误判率越低，但插入/查询成本更高。
  4. Insert and Query Complexity：通常为 O(k)，常为常数时间。
  5. 不可删除性（标准布隆过滤器）：无法从集合中删除元素。
  6. 压缩性与可扩展性：基本布隆过滤器固定大小，不能动态扩容。
  7. 空间效率：极高，远优于传统 Set/List。

类型

标准 Bloom Filter

最基础的实现，适合静态集合，不支持删除操作，空间效率高。

可扩展 Bloom Filter（Scalable Bloom Filter）

通过创建多个布隆过滤器级联，支持集合动态增长，同时控制误判率。

计数型 Bloom Filter（Counting Bloom Filter）

将位数组替换为计数数组，支持元素删除；常用于缓存淘汰场景。

压缩 Bloom Filter（Compressed Bloom Filter）

为传输优化，将 Bloom Filter 压缩后发送至其他节点，牺牲部分误判率换取网络传输效率。

分布式 Bloom Filter

适用于分布式系统，将哈希映射值均匀分配到多台机器中。

常见应用场景

  1. 缓存系统中的预过滤器：减少缓存穿透（如 Redis + Bloom Filter）。
  2. 黑名单过滤：快速判断请求是否来自非法用户。
  3. 搜索引擎爬虫去重：判断 URL 是否已访问。
  4. 邮箱/垃圾邮件检测：判定是否为黑名单发件人。
  5. 防止重复提交/注册：判断用户名、请求是否已存在。
  6. 数据库索引加速：提前判断 key 是否存在，减少 I/O。

常用实现与库

常见布隆过滤器实现如下：

  1. Guava BloomFilter（Java）：Google 出品，配置灵活，性能优异。
  2. Redis Module: RedisBloom：支持布隆过滤器、计数型布隆等高级功能。
  3. Apache HBase：使用 Bloom Filter 加速存储访问。
  4. Apache Kafka Streams：用于流处理中的去重判断。
  5. bloom-filter-cpp / bloomd：高性能 C/C++ 实现，适合系统底层集成。
  6. Python: pybloom, bloom-filter3：简洁易用，适合脚本和实验场景。