目录
什么是布隆过滤器？
布隆过滤器（Bloom Filter）是1970年由伯顿·霍华德·布隆（Burton Howard Bloom）提出的一种空间高效的概率型数据结构。它本身是一个很长的二进制向量（可以想象成一个很长的数组，里面只有0和1）和一系列随机映射函数。
它的特点是：
- 高效：插入和查询操作都非常快，时间复杂度是 O(k)，k 是哈希函数的个数。
- 省空间：不需要存储元素本身，只用一个个比特位，极大地节省了存储空间。
- 概率性：它告诉你一个元素“可能存在”或“一定不存在”。
注意这个“可能”和“一定”，这是理解布隆过滤器的关键。
布隆过滤器的工作原理
布隆过滤器的运作基于以下三个核心步骤：
1. 初始化
首先，我们需要初始化一个长度为 m 的位数组（Bit Array），所有位的初始值都设为 0。
位数组: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] (m=10)2. 添加元素（add）
当我们要向过滤器中添加一个元素（比如字符串 "geek"）时：
- 使用
k个不同的哈希函数（Hash Function）对这个元素进行计算，得到k个哈希值：h1, h2, ..., hk。 - 将这些哈希值对位数组的长度
m取模，得到k个位置索引：index1, index2, ..., indexk。 - 将位数组中这几个对应的位置都置为
1。
假设 k=3，3个哈希函数对 "geek" 计算后取模得到位置 [1, 4, 9]
位数组变为: [0, 1, 0, 0, 1, 0, 0, 0, 0, 1]我们再添加一个元素 "time"，假设计算出的位置是 [4, 5, 9]。
- 位置4和9已经是1了，保持不变。
- 把位置5置为1。
位数组变为: [0, 1, 0, 0, 1, 1, 0, 0, 0, 1]3. 查询元素（exists）
当我们要判断一个元素（比如字符串 "news"）是否在过滤器中时：
- 同样使用那
k个哈希函数计算该元素的k个哈希值，并取模得到k个位置索引。 - 检查位数组中这些对应的位置是否都为
1：- 如果其中有任何一个位置为
0，那么这个元素“一定不存在”于过滤器中。 - 如果所有位置都是
1，那么这个元素“可能存在”于过滤器中。
- 如果其中有任何一个位置为
为什么是“可能”存在？
因为其他元素的操作可能会巧合地将这些位全部置1。这种现象称为哈希冲突导致的误判（False Positive）。
如上图所示，查询 "W" 时，因为它计算出的两个位其中一个为0，所以它肯定不存在。查询 "Y" 时，它计算出的两个位都是1，但我们并不知道这是 "X" 和 "Y" 共同作用的结果，还是 "Y" 真的存在，所以只能回答“可能存在”。
优势和劣势
优势（为什么用它？）
- 空间效率极高：不存储数据本身，只占用比特位。存储1亿个数据的存在性，可能只需要百兆左右内存，而HashSet可能需要几个G。
- 查询时间极快：查询时间与元素数量无关，永远是O(k)次计算和位操作。
劣势（要注意什么？）
- 误判率（False Positive）：这是它最大的缺点。它可能会误判一个不存在的元素为存在。
- 不能删除元素：这是一个单向的、添加式的数据结构。因为将一个位置由1置0可能会影响其他元素（比如上图中的
"X"和"Y"）。（注：有支持删除的变体计数布隆过滤器（Counting Bloom Filter），它用计数器而不是单个比特位，但会占用更多空间）。 - 不支持获取元素本身：它只关心存在性，不存储数据。
实际应用场景
布隆过滤器的核心思想是：先用极低的成本快速排除绝对不存在的请求，对“可能存在”的请求再进行后续更精确（也更昂贵）的检查。
- 缓存穿透防护：
- 问题：恶意请求频繁查询一个缓存和数据库中根本不存在的数据，导致请求直接穿透缓存，每次都击穿数据库。
- 方案：将缓存中所有已有的key都同步到布隆过滤器。收到查询请求时，先过布隆过滤器。如果返回“不存在”，则直接返回空，不再查询缓存和数据库。这完美解决了缓存穿透问题。
如何在Redis中使用布隆过滤器？
在原生Redis 4.0之前，你需要自己基于位数组（SETBIT, GETBIT）和哈希函数实现布隆过滤器。但从Redis 4.0开始，官方提供了布隆过滤器的模块（module），可以通过BF.ADD和BF.EXISTS等命令直接使用。
示例：
# 添加元素
> BF.ADD myfilter "user123"
(integer) 1
# 判断元素是否存在
> BF.EXISTS myfilter "user123"
(integer) 1 # 表示存在（实际是“可能存在”）
> BF.EXISTS myfilter "user456"
(integer) 0 # 表示一定不存在甚至可以自定义误差率和初始大小的过滤器：
> BF.RESERVE mycustomfilter 0.01 1000000这条命令创建了一个名为 mycustomfilter 的过滤器，我们预计存入100万个元素，并设置误判率为1%。
总结
布隆过滤器是一个“有点粗糙”但极其有用的前置过滤器。它就像一位尽职尽责的门卫：
- 如果它说：“这人我没见过，肯定不能进”（
false）—— 那你100%可以相信他。 - 如果它说：“这人好像在里面，您进去再问问吧”（
true）—— 那你需要进去用更精确的方法（查数据库、查缓存）进行二次确认。
在当今大数据处理和高并发系统中，合理运用布隆过滤器往往是优化性能、保护后端资源的关键一招。下次当你遇到需要判断大规模数据存在性又担心资源消耗的问题时，不妨考虑一下这位“空间魔法师”。