10亿条URL的黑名单，如何快速判断一个新请求的URL是否在黑名单内？
在日常开发中，你是否遇到过这样的场景：
有一个包含10亿条URL的黑名单，如何快速判断一个新请求的URL是否在黑名单内，同时避免占用几十GB的内存？
在我们学习缓存三剑客时，关于缓存穿透，我们常用的解决方案之一是什么？
这些问题的核心，都是对海量数据的存在性判断，我们不需要获取数据本身，只需要知道“在”或“不在”，而布隆过滤器（Bloom Filter），就能很好地解决这个问题。
一、布隆过滤器是什么？
是一种空间高效的概率型数据结构，核心作用是快速判断一个元素是否存在于一个集合中。
布隆过滤器主要由两部分组成，
一部分是初始值都为 0 的位图数组，
一部分是N 个哈希函数。
布隆过滤器不存储数据本身，只存储数据的哈希标记。当我们往数据库中写数据时，顺便在布隆过滤器中做个标记，这样下次查数据时，只要查布隆过滤器，查的数据没有标记的话，那说明数据库里也没有。
那既然这么说了，查布隆过滤器一定很快吧？确实很快。查询布隆过滤器的时间复杂度O(k)，k是哈希函数个数，通常是个位数，效率很高。
二、布隆过滤器是怎么工作的？
布隆过滤器的底层结构很简单，只有两个核心组件：
一个固定长度的位图数组(初始值都为0)，
一组独立的哈希函数，
所有逻辑都围绕这两个组件展开。
接下来举个例子：
假设我有一个布隆过滤器，数组初始长度为8，哈希函数个数为3
当我们插入元素“bloom”时，步骤如下：
将“bloom”传入3个哈希函数，得到3个不同的哈希值；
然后再把这 3 个哈希值对 8 取模
将得到的结果在数组中的相应位置置1，比如取模得到1，3，5 那就1，3，5位置1 （总共0-7）
这样一通操作之后，以后当我们要查询"bloom"是否在数据库中时，只需要通过布隆过滤器查第1，3，5位置是否全为1，必须全为1才可能行，只要有一个0都说明“bloom”不在数据库中。
那为什么是可能行呢？
因为不同的数经计算得到的哈希值对8取模结果可能是一样的，可能存在哈希冲突。那这样明明数据库中没有这个数，我却算出了它1,3,5位也是1，这就判断错误了。
三、使用布隆过滤器解决缓存穿透
这里就回到了开头的缓存三剑客中的缓存穿透了。
发生缓存穿透原因是因为用户请求一个不存在的数据，此数据在缓存和数据库中都不存在。
这是我们可以用布隆过滤器存储所有已存在的key，请求过来时，先查布隆过滤器，如果返回“绝对不存在”，那就直接返回空结果，不访问缓存和数据库。如果返回“可能存在”，再查缓存和数据库。这样就能拦截99%以上的无效请求，保护数据库。
四、布隆过滤器的其它应用
1. 海量数据去重
比如爬虫去重：爬取网页时，需要记录已爬取的URL，避免重复抓取。如果用哈希表存储，1亿条URL会占用几十GB内存，而用布隆过滤器，仅需几十MB内存就能搞定，完美解决空间瓶颈。
类似场景还有：邮件黑名单去重、用户ID去重、日志去重等。
2. 数据库索引优化
HBase、LevelDB、RocksDB等数据库引擎，会用布隆过滤器判断目标键是否存在于某个SSTable文件中，避免不必要的磁盘IO操作，提升查询性能——如果布隆过滤器判断键不存在，就无需读取磁盘文件，直接返回空结果。
3. 分布式系统中的数据校验
比如分布式缓存中，判断一个key是否在其他节点的缓存中；区块链轻节点中，判断某个交易是否可能包含在区块中，减少数据同步的开销。
五、总结
布隆过滤器的本质，是“用极小的空间成本，换取极高的查询效率，同时接受轻微的误判”。它不适合所有场景，但在海量数据的存在性判断中，是无可替代的工具。
如果觉得这篇博客对你有帮助，欢迎点赞~收藏~评论~