一文讲透布隆过滤器实现原理及应用场景总结

布隆过滤器的工作原理

布隆过滤器的工作原理基于三个核心要素：

1. 一个大的位数组（Bit Array）

这是布隆过滤器的存储主体。它是一个长度为m的数组，每个位置只存储一个比特（0或1）。初始时，所有位都是0

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]（一个长度为12的位数组示例）

2. 一组哈希函数（Hash Functions）

你需要准备k个不同的、相互独立的哈希函数（比如h1(x),h2(x),h3(x)）。这些函数的作用是：将任意输入的字符串（或其他数据）映射到位数组的某个下标位置上

关键点：好的哈希函数应该尽可能均匀地把输入散列到整个位数组上

3. 两种基本操作：添加（Add）和查询（Exists）

3.1.A. 添加元素（例如，把客人“张三”加入名单）

1. 将“张三”分别通过k个哈希函数进行计算

• h1("张三")-> 返回位置 2
• h2("张三("张三")-> 返回位置 5
• h3("张三")-> 返回位置 10

2. 将位数组中这 k 个位置个位置（2, 5, 10）的值都设置为1

操作后的位数组变为：[0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0]

接着，你再添加“李四”：

• h1("李四")-> 位置 2 (巧合，与张三相同)
• h2("李四")-> 位置 7
• h3("李四")-> 位置 位置 11

再次将位置2, 7, 11设为1。注意，位置2原本就是1了，保持不变。 操作后的位数组变为：[0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1]

3.2.B. 查询元素（例如，查询“王五”是否来过）

1. 将“王五”同样通过那k个哈希函数进行计算。

• h1("王五")-> 返回位置 3
• h2("王五")-> 返回位置 5
• h3("王五")-> 返回位置 11

2. 去检查位数组中这k个位置（3, 5, 11）的值。

• 如果其中有任何一个位置的值为0：那么可以肯定地说，“王五”绝对没有被加入过过滤器（因为如果他来过，这些位置肯定都被设为1了）
• 如果所有位置的值都是1：那么布隆过滤器会告诉你，“王五”可能存在（可能会存在误判）

在上面的例子中，位置3是0，所以我们可以确信地回答：“王五没来过”

现在，我们来查一个不存在的“赵六”：

• h1("赵六")-> 位置 2
• h2("赵六")-> 位置 5
• h3("赵六")-> 位置 10

我们发现位置2、5、10全都是1！这时布隆过滤器会错误地告诉我们：“赵六可能存在”，这就是所谓的误判（False Positive）

3.3. 为什么会产生误判？

误判的根本原因是：哈希碰撞

• 不同的元素（如“张三”和“李四”）可能会被哈希到同一个位置（比如位置2）
• 当我们查询一个从未加入过的元素“赵六”时，它被哈希到的所有位置 (2, 5, 10) 恰好都被之前加入的其他元素（“张三”把2,5,10都占了）给设置成了1
• 布隆过滤器看到这些位都是1，就“想当然”地认为这个元素之前已经被添加过了

3.4. 如何减少误判率？

误判是无法完全消除的，但可以通过调整参数将其控制在一个很低的水平，主要参数有三个：

1. 位数组长度（m）：m越大，可供标记的位置越多，发生哈希碰撞的概率就越低；但需要的空间也越大。
2. 哈希函数的数量（k）：k太少，会导致对每个元素的标识不够独特；k太多，又会很快把位数组填满，增加碰撞概率。需要一个最优值
3. 已插入元素的数量（n）：随着插入的元素越来越多，位数组里1的比例越来越高，误判率也会随之上升

有一个著名的公式可以用来估算最优的k值和预期的误判率p：

从公式可以看出，要想获得较低的误判率，位数组大小m需要与插入元素数量n成正比例关系。通常在实践中，我们会预设一个期望的误判率和最大数据量，然后反推出需要多大的m

3.5 优缺点总结

优点：

1. 空间效率极高：相比于存储原始数据（如哈希表），它只使用比特位，非常省内存
2. 查询时间复杂度为O(k)：仅需进行k次哈希计算和位查找，速度极快，k是常数

缺点：

1. 存在误判率：这是最主要的缺点，只能回答“必然不存在”和“可能存在”
2. 不能删除元素：因为将一个位置由1置0可能会影响到其他也被映射到该位置的元素；
   不过有一种变体叫计数布隆过滤器（Counting Bloom Filter），它使用计数器而不是单个比特，可以支持删除操作，但会占用更多空间

布隆过滤器常见应用场景

01-缓存穿透问题

这是布隆过滤器最常用的场景，在查询数据库前，先用布隆过滤器判断数据是否存在。如果布隆过滤器说不存在，就直接返回，避免了对数据库的无意义查询。解决缓存穿透问题常用（老生常谈）

02-网络与安全方面

1.网页爬虫的 URL 去重

• 背景:网络爬虫需要避免重复抓取相同的 URL，既浪费资源，又可能给对方服务器造成压力。
• 问题: 互联网上的 URL 数量极其庞大，使用传统的哈希表存储在内存中会占用巨大空间。
• 解决方案:使用一个布隆过滤器来记录所有已经爬取过的 URL
• 工作流程:
  1.每当爬虫解析出一个新的待爬取 URL。
  2.先查询布隆过滤器：“这个 URL 我可能爬过吗？”
  3.如果返回“肯定没爬过”，那么就放心地去爬取，并将该 URL 加入过滤器。
  4.如果返回“可能爬过”，则可以直接丢弃或放入一个优先级很低的队列中进行二次确认（例如再用一个小型的精确集合检查一次）
• 效果:用极小的内存代价实现了海量 URL 的去重。虽然可能有极少数的 URL 因误判而被遗漏，但对于大多数搜索引擎来说，这是完全可以接受的代价

2.恶意网站/垃圾邮件检测

• 背景: 浏览器、防火墙或邮件服务器需要快速判断一个网址/发件人是否是恶意的
• 解决方案: 维护一个已知的恶意网址/邮箱黑名单 的布隆过滤器
• 工作流程:
  1.用户点击一个链接或收到一封邮件。
  2.客户端迅速用布隆过滤器检查该网址/邮箱地址。
  3.如果布隆过滤器说“肯定是安全的”（即不在黑名单中），则立即放行，用户体验无延迟。
  4.如果布隆过滤器说“可能是恶意的”，此时再启动更复杂、更耗时的精确查询（例如到云端的安全数据库进行核实）。
• 效果:为绝大多数安全的访问提供了“零延迟”的体验，只在少数可疑情况下才付出较高的验证成本

03-推荐系统与内容治理

1.已读内容去重 (如新闻推送、社交媒体)

• 背景：在今日头条、微博等信息流产品中，需要避免给用户重复推荐他们已经看过的内容
• 解决方案：为每个用户维护一个布隆过滤器，里面存放他们近期已浏览内容的ID
• 效果：当从内容池中选择内容推送给用户时，可以先通过布隆过滤器过滤掉那些用户“很可能”已经看过的内容，提升用户体验。即使偶尔误判了一个用户没看过的内容，也只是少推荐一条而已，影响可控

2.防止缓存击穿 (一种特殊的缓存穿透)

• 背景: 缓存击穿是指某个热点key过期，此时有大量请求并发涌向数据库，导致数据库瞬间压力过大
• 解决方案: 使用布隆过滤器 + 互斥锁
• 工作流程:
  1. 将所有可能成为热点的 key 预先加入到布隆过滤器中。
  2. 当一个请求查询缓存未命中时，先去布隆过滤器检查。
  3. 如果布隆过滤器说“肯定不存在”（意味着这不是一个合法的热点key），直接返回空
  4. 如果说“可能存在”，才允许他去争夺一个互斥锁，然后只有一个请求可以去数据库加载数据并回填缓存。
• 效果：布隆过滤器在这里起到了第一道屏障的作用，将大量的非法请求和一部分非热点数据的请求直接挡在数据库之外，让竞争锁的请求数大大减少

04-密码校验

有些系统会维护一个“弱密码”列表，禁止用户设置。
在注册或修改密码时，可以用布隆过滤器快速判断用户设置的密码是否“绝对不是”弱密码。如果是，则直接通过；如果“可能是”，再进行精确匹配。这样可以避免每次都在庞大的弱密码库里做字符串比对