布隆过滤器（Bloom Filter）

1. 什么是布隆过滤器？

布隆过滤器是 1970 年由 Burton Howard Bloom 提出的。它用来判断一个元素是否属于某个集合。

1.1 作用

快速拦截"一定不存在"的请求，检查元素是否存在指定集合中，例如：判断一个数字是否存在数字集合中（5亿个数），缓存穿透防护、爬虫 URL 去重、垃圾邮的过滤、黑名单拦截等。

1.2 组成

布隆过滤器由以下两部分组成：

位数组：位数组通常初始化为0

多个哈希函数：哈希函数用于将元素映射到位数组中的位置。

1.3 添加元素的流程

向布隆过滤器中添加一个元素时，执行以下步骤：

1. 使用 多个哈希函数分别对该元素计算哈希值，得到 多个位数组下标。

2. 将位数组中这些下标对应的位全部置为 1。

例如，添加元素 "App" 时，6 个哈希函数分别计算出下标 2、5、7、9、11、13，则将位数组的第 2、5、7 、9、11、13位设为 1。

1.4 查询元素的流程

当查询一个元素是否在集合中时：

1. 使用相同的多个哈希函数对该元素计算哈希值，得到多个位数组下标。
2. 检查位数组中这些个下标对应的位：
   • 如果任意一位为 0，则该元素一定不在集合中。
   • 如果所有位都为 1，则该元素可能在集合中（存在误判可能）。

1.5 特点

• 误判率：布隆过滤器存在误判，即可能将不在集合中的元素误判为在集合中。误判率与位数组长度 、哈希函数个数以及已添加元素数量有关。通过合理选择位数组长度和哈希函数数量，可以将误判率控制在可接受范围内。

• 不支持删除元素：布隆过滤器无法安全地删除元素。因为多个元素可能映射到同一位，直接将该位清零会导致其他元素被误判为不存在。

2. 布隆过滤器的优点和缺点

2.1 优点

• 空间效率极高：布隆过滤器只需要一个位数组，占用内存非常少，只存布特位，不存原始数据。
• 查询和插入速度快：添加和查询操作都只涉及 k 次哈希计算和位数组访问，时间复杂度为 O(k)，与集合大小无关。
• 安全性好：布隆过滤器不存储元素本身，只存储哈希映射后的位信息，因此无法从位数组中还原原始数据，适合保护敏感数据。
• 易于并行化：多个哈希函数可以并行计算，位数组的读写操作也可以并发执行。

2.2 缺点

• 存在误判率：无法做到 100% 准确，可能将不在集合中的元素误判为存在。误判率无法降为 0，只能通过增加位数组长度来降低。
• 无法删除元素：标准布隆过滤器不支持删除操作。
• 无法获取元素本身：布隆过滤器只能回答"是否存在"，无法像哈希表那样返回元素的值或关联数据。
• 误判率随元素数量增加而上升：当已添加元素数量接近或超过设计容量时，误判率会急剧上升，需要提前规划好容量。

3. 黑名单场景实战：判断手机号码是否在黑名单

3.1 场景描述

发送业务通知短信前，需要判断手机号码是否在 1000 万条黑名单中。布隆过滤器非常适合这种"大量数据、允许少量误判、追求高性能"的场景。

3.2 实现思路

整体方案采用布隆过滤器 + 数据库的双层架构：

1. 初始化阶段：从数据库中读取全部 1000 万条黑名单手机号码，逐个添加到布隆过滤器中。布隆过滤器加载到内存中常驻。
2. 查询阶段：发送短信前，先用布隆过滤器判断手机号码：
   • 如果布隆过滤器返回不存在（某位为 0），则直接放行，无需查询数据库。
   • 如果布隆过滤器返回可能存在（所有位为 1），再回源数据库做精确查询，确认是否真的在黑名单中。