布隆过滤器

布隆过滤器是什么

在处理海量数据去重或判断“是否存在”时，如果使用 Map 或 Set，内存开销会随数据量线性增长。

布隆过滤器是一种概率型数据结构。它的核心权衡是：用极小的内存消耗，换取一定的“误判率”。

它的回答只有两种可能：

1. 绝对不在集合中（100% 准确）。
2. 可能在集合中（存在误判概率）。

原理与结构

布隆过滤器的底层是一个位数组和一组无偏哈希函数。

工作流程：

1. 初始化：所有位（Bit）置为 0。
2. 添加元素：
   • 将元素通过 k 个哈希函数计算，得到 k 个位置。
   • 将位数组中对应的这些位置全部置为 1。
3. 查询元素：
   • 将待查询元素通过同样的 k 个哈希函数计算。
   • 如果所有位置都是 1：认为元素“可能存在”。
   • 如果任一位置是 0：认为元素“绝对不存在”。

应用场景

1. 防止缓存穿透： 在访问数据库前，先通过布隆过滤器判断 Key 是否存在。 如果不存在直接返回，避免无效请求击穿缓存直达数据库。
2. 爬虫 URL 去重： 存入数亿级 URL，快速判断某个网页是否已经爬取过，节省内存。
3. 垃圾邮件过滤： 从数十亿个垃圾邮件地址中快速匹配。
4. 黑名单系统： 如恶意 IP 过滤、敏感词检查。

进阶版：布隆过滤器的变体

1. Counting Bloom Filter (可计数布隆过滤器)

   • 解决问题：不支持删除。
   • 原理：将位数组的每个 Bit 换成一个 Counter (计数器)。
   • 操作：添加时 +1，删除时 -1。虽然增加了空间占用，但支持了动态删除。

2. Cuckoo Filter (布谷鸟过滤器)

   • 优势：支持动态删除，且在误判率较低时，查询性能优于布隆过滤器，空间利用率更高。
   • 原理：基于布谷鸟哈希算法，通过指纹（Fingerprint）存储元素特征。