布隆过滤器（Bloom Filter）
1. 什么是布隆过滤器？
布隆过滤器是 1970 年由 Burton Howard Bloom 提出的。它用来判断一个元素是否属于某个集合。
1.1 作用
快速拦截"一定不存在"的请求，检查元素是否存在指定集合中，例如：判断一个数字是否存在数字集合中（5亿个数），缓存穿透防护、爬虫 URL 去重、垃圾邮的过滤、黑名单拦截等。
1.2 组成
布隆过滤器由以下两部分组成：
位数组：位数组通常初始化为0
多个哈希函数：哈希函数用于将元素映射到位数组中的位置。
1.3 添加元素的流程
向布隆过滤器中添加一个元素时，执行以下步骤：
使用 多个哈希函数分别对该元素计算哈希值，得到 多个位数组下标。
将位数组中这些下标对应的位全部置为 1。
例如，添加元素 "App" 时，6 个哈希函数分别计算出下标 2、5、7、9、11、13，则将位数组的第 2、5、7 、9、11、13位设为 1。
1.4 查询元素的流程
当查询一个元素是否在集合中时：
- 使用相同的多个哈希函数对该元素计算哈希值，得到多个位数组下标。
- 检查位数组中这些个下标对应的位：
- 如果任意一位为 0，则该元素一定不在集合中。
- 如果所有位都为 1，则该元素可能在集合中（存在误判可能）。
1.5 特点
误判率：布隆过滤器存在误判，即可能将不在集合中的元素误判为在集合中。误判率与位数组长度 、哈希函数个数以及已添加元素数量有关。通过合理选择位数组长度和哈希函数数量，可以将误判率控制在可接受范围内。
不支持删除元素：布隆过滤器无法安全地删除元素。因为多个元素可能映射到同一位，直接将该位清零会导致其他元素被误判为不存在。
2. 布隆过滤器的优点和缺点
2.1 优点
- 空间效率极高：布隆过滤器只需要一个位数组，占用内存非常少，只存布特位，不存原始数据。
- 查询和插入速度快：添加和查询操作都只涉及 k 次哈希计算和位数组访问，时间复杂度为 O(k)，与集合大小无关。
- 安全性好：布隆过滤器不存储元素本身，只存储哈希映射后的位信息，因此无法从位数组中还原原始数据，适合保护敏感数据。
- 易于并行化：多个哈希函数可以并行计算，位数组的读写操作也可以并发执行。
2.2 缺点
- 存在误判率：无法做到 100% 准确，可能将不在集合中的元素误判为存在。误判率无法降为 0，只能通过增加位数组长度来降低。
- 无法删除元素：标准布隆过滤器不支持删除操作。
- 无法获取元素本身：布隆过滤器只能回答"是否存在"，无法像哈希表那样返回元素的值或关联数据。
- 误判率随元素数量增加而上升：当已添加元素数量接近或超过设计容量时，误判率会急剧上升，需要提前规划好容量。
3. 黑名单场景实战：判断手机号码是否在黑名单
3.1 场景描述
发送业务通知短信前，需要判断手机号码是否在 1000 万条黑名单中。布隆过滤器非常适合这种"大量数据、允许少量误判、追求高性能"的场景。
3.2 实现思路
整体方案采用布隆过滤器 + 数据库的双层架构：
- 初始化阶段：从数据库中读取全部 1000 万条黑名单手机号码，逐个添加到布隆过滤器中。布隆过滤器加载到内存中常驻。
- 查询阶段：发送短信前，先用布隆过滤器判断手机号码：
- 如果布隆过滤器返回不存在（某位为 0），则直接放行，无需查询数据库。
- 如果布隆过滤器返回可能存在（所有位为 1），再回源数据库做精确查询，确认是否真的在黑名单中。