什么是布隆过滤器？
布隆过滤器（Bloom Filter）是一种空间效率极高的概率型数据结构，由 Burton Howard Bloom 在 1970 年提出。
“概率型数据结构”（Probabilistic Data Structure）是指一类在处理数据时，为了换取极高的空间效率或计算速度，允许在结果中存在一定误差（通常是概率性的）的数据结构。
它主要用于判断一个元素是否在一个集合中。
核心结论
- 如果布隆过滤器判断元素不在集合中：那么该元素一定不在集合中（100% 准确）。
- 如果布隆过滤器判断元素在集合中：那么该元素可能在集合中，也可能不在（存在一定的误判率）。
工作原理
布隆过滤器的底层是一个位数组（Bit Array）和一组哈希函数（Hash Functions）。
1. 初始化
创建一个长度为 m 的位数组，所有位初始化为 0。
2. 添加元素
当一个元素被加入集合时：
- 通过
k个不同的哈希函数计算出k个哈希值。 - 将位数组中对应的
k个下标的值设为1。
3. 查询元素
当查询一个元素是否存在时：
- 同样通过那
k个哈希函数计算出k个下标。 - 检查位数组中这
k个位置的值：- 如果有任何一个位是 0，则该元素一定不存在。
- 如果所有位都是 1，则认为该元素可能存在。
优缺点
优点
- 空间效率极高：它不需要存储原始数据，只存储位的状态。
- 查询速度极快：哈希计算和位查找的时间复杂度都是 ，与集合中的元素数量无关。
缺点
- 存在误判（False Positives）：不同的元素可能哈希到相同的位。
- 难以删除：由于一个位可能被多个元素共享，直接将某位改为
0会影响其他元素的判断。- 注：计数布隆过滤器（Counting Bloom Filter）可以解决删除问题，但会消耗更多空间。
应用场景
1. 解决缓存穿透
在访问数据库之前，先通过布隆过滤器过滤掉那些数据库中肯定不存在的 ID，从而保护数据库。
2. 垃圾邮件过滤
判断一个邮件地址是否在黑名单中。
3. 爬虫去重
在爬取海量 URL 时，判断某个 URL 是否已经抓取过。
4. 数据库索引
Google Bigtable、Apache HBase 和 Cassandra 使用布隆过滤器来减少对不存在的行或列的磁盘寻址。