布隆过滤器

GGBOND2025/10/19大约 3 分钟

一、什么是布隆过滤器

布隆过滤器（Bloom Filter）是一种 高效的概率型数据结构，用于判断一个元素是否存在于集合中。
它的核心特点是：

判断“一定不存在”是准确的；
判断“可能存在”是有一定误差的（即存在误判率）。

因此，布隆过滤器非常适合用于 快速判断元素是否存在 的场景，而不需要真正存储所有元素。

二、布隆过滤器的工作原理

布隆过滤器底层由两部分组成：

一个位数组（bit array）：长度为 m，初始时所有位都为 0。
多个哈希函数（k 个）：每个函数将输入映射到位数组中的一个索引位置。

插入过程：

将元素通过 k 个哈希函数计算出 k 个位置；
把这些位置的 bit 位设置为 1。

查询过程：

再次用相同的 k 个哈希函数计算位置；
若所有对应的 bit 位都是 1，则认为“可能存在”；
若其中任意一位为 0，则“肯定不存在”。

三、布隆过滤器的优势

节省内存空间：布隆过滤器使用位数组存储数据，比存储整个集合占用的空间小得多。
查询速度快：时间复杂度为 O(k)，k 为哈希函数个数，通常很小。
适合大数据场景：能在内存有限的情况下完成大规模集合判重操作。

四、布隆过滤器的缺点

存在误判：可能会把不存在的元素判断为存在（假阳性）。
无法删除元素：标准布隆过滤器不支持删除操作（删除会导致误判率上升）。
误判率随数据量增加而上升：当存入的数据量接近设计容量时，准确性降低。

五、为什么要使用布隆过滤器

布隆过滤器的设计初衷是 在有限内存中实现高效的集合存在性判断。
在传统方式下，若使用哈希表或集合存储大量数据，会消耗大量内存，而布隆过滤器能以极低成本完成快速判断。

它之所以能解决并发系统中的性能问题，是因为：

避免了无意义的数据库或缓存查询。
能在高 QPS 场景下快速判断请求是否有效。

六、应用场景

缓存穿透防护
在 Redis 缓存中，如果用户频繁请求不存在的 key，会导致请求直接打到数据库。
使用布隆过滤器可以在请求前判断 key 是否存在，不存在的直接拦截，从而保护数据库。
网页爬虫 URL 判重
爬虫系统中用于判断某个 URL 是否已经爬取过，防止重复抓取。
垃圾邮件过滤
判断邮件地址或内容是否出现在黑名单中。
推荐系统或广告系统
判断用户是否已浏览过某个内容或广告。

七、在 Redis 中的实现

Redis 官方提供了 RedisBloom 模块 支持布隆过滤器，常用命令如下：

# 创建布隆过滤器并设置误判率与预期数量
BF.RESERVE myBloom 0.01 1000000

# 添加元素
BF.ADD myBloom user:1001

# 判断元素是否存在
BF.EXISTS myBloom user:1001
BF.EXISTS myBloom user:2002

0.01 表示允许的误判率（1%）
1000000 表示预计存储 100 万个元素

Redis 会自动根据参数分配 bit 数组大小和哈希函数数量，以达到目标误判率。

八、总结

布隆过滤器是一种基于哈希思想的 高效空间换时间 数据结构：

优点：节省内存、查询快、适合大数据场景；
缺点：存在误判、无法删除；
典型用途：缓存穿透防护、URL 判重、垃圾邮件检测等。

它通过简单的位操作和多哈希函数映射，成为高并发系统中快速判断数据存在性的利器。