布隆过滤器为什么能用35MB存下3000万条数据？

先贴一段生产环境里的代码。这是一个活动弹窗通知的配置，新活动上线后要给会员弹窗口，每个用户只弹一次，不能重复弹。

publicstaticclassPopupBloomFilterConfig{// 弹窗持续5天，过滤器过期时间 = 弹窗天数 + 1publicstaticfinallongEXPIRE=60*60*24*6;// 预期数据量，参考会员总数publicstaticfinallongEXPECTED_SIZE=30000000;// 误判率1%publicstaticfinaldoubleFALSE_PROBABILITY=0.01;}

三个参数：预期数据量3000万，误判率1%，过期时间6天。用的是Redisson的布隆过滤器，初始化代码长这样：

RBloomFilter<Object>bloomFilter=redissonClient.getBloomFilter(key);if(!bloomFilter.isExists()){bloomFilter.tryInit(expectedInsertions,falseProbability);bloomFilter.expire(expire,TimeUnit.SECONDS);}

用户在请求进来时，先拿用户ID去布隆过滤器里查一下。返回false说明这个用户还没弹过窗，执行弹窗逻辑，然后把用户ID写进过滤器。返回true说明已经弹过了，跳过。

这就是布隆过滤器在生产环境里最常见的用法：海量数据的存在性判断。

这个问题还能怎么解

看完上面的代码，一个自然的问题是：不用布隆过滤器行不行？

3000万用户，要记住谁看过弹窗，最直接的方案是用HashSet存用户ID。Java里一个Long对象加上HashSet内部的Node结构、对象头、数组开销，3000万条数据大约要占700MB到1GB内存。如果是分布式环境，还得把这个数据放到Redis里，占用更大。

另一个方案是查数据库。每次用户请求时查一次记录表，看这个用户有没有弹窗记录。能跑，但一个活动弹窗要扛住短时间内几千万次查询，数据库压力很大。

还可以用Redis的Bitmap。Bitmap用1个bit表示一个用户，3000万用户大约占3.58MB，空间很省。但Bitmap要求用户ID能直接映射到位数组的下标，如果用户ID是连续的（1、2、3…3000万），Bitmap很合适。可实际业务中的用户ID往往跨度很大，比如ID最大到了10亿，位数组就得按10亿来分配，实际只用了3000万个位，大量空间浪费在没用的ID段上。

布隆过滤器在这些方案之间找到了一个平衡点：用接近Bitmap的空间开销，做到可控误判率的存在性判断。3000万用户、1%误判率的配置下，布隆过滤器大约只占35MB。

布隆过滤器的原理

布隆过滤器的底层结构就两样东西：一个位数组和几个哈希函数。

位数组就是一长串0和1，每个位置只占1个bit。假设位数组长度是m，初始状态全是0。

写入一个元素的时候，用k个哈希函数分别对这个元素做哈希运算，每个哈希函数算出一个位置编号，然后把位数组中对应位置的值设为1。比如用3个哈希函数，元素A算出来的位置是2、7、15，那就把位数组的第2位、第7位、第15位都设成1。

查询一个元素是否存在，同样用这k个哈希函数算出k个位置，检查这些位置是否全是1。全是1，判断为存在；只要有一个是0，判断为不存在。

这个设计有一个好处：判断不存在是100%准确的。因为一个元素如果真的写入过，它的k个位置一定都是1。只要有任何一个位置是0，说明这个元素肯定没写入过。而且布隆过滤器只会把0变成1，从来不会把1重新变回0，所以一个已经写入的元素，不会因为后续插入其他元素而丢失。不存在假阴性。

为什么会有误判

布隆过滤器的误判只有一种方向：一个本来不存在的元素，被判断为存在。这种情况叫假阳性。

原因不难想。位数组的位数是有限的，不同元素经过哈希运算后，可能在某些位置上重叠。比如元素A把第2、7、15位设成了1，元素B把第5、7、20位设成了1。这时候来查元素C，如果C算出来的位置刚好是2、5、7，这三个位置都已经被A和B设为1了，布隆过滤器就会误认为C存在。

前面生产配置里的1%误判率，意思就是：查100个确实不存在的元素，大约有1个会被误判为存在。在弹窗场景里，误判的后果是漏弹：某些还没弹过窗的用户被误判为已弹过，返回true，就不会收到弹窗。对弹窗通知这种场景来说，漏掉一些用户的通知问题不大，所以1%是可接受的。

布隆过滤器的判断有一个不对称性：说不存在，一定准确；说存在，有一定概率是误判。

这个特性决定了它适合那些能容忍少量漏判、不能容忍误放的场景。对应到布隆过滤器的术语：假阳性（误判为存在）就是漏弹，能忍；假阴性（误判为不存在）就是多弹，不能忍。弹窗通知就是典型例子：漏弹几个用户问题不大，但已经弹过的用户再弹一次，用户会觉得系统在出bug。

三个关键参数怎么定

生产代码里那三个参数不是随便填的，每个都有讲究。

位数组的大小不是拍脑袋定的，背后有一个公式：m = -n * ln§ / (ln2)^2。其中n是预期数据量，p是误判率。Redisson内部就是根据预期数据量和误判率，用这个公式自动计算位数组大小。后面速查表里的数字都是这个公式算出来的。

预期数据量（expectedInsertions）。这个数字决定了位数组的长度。定小了，实际存入的元素超过预期，位数组会越来越密，误判率会远超设定值。宁可按偏大的值来估。实际项目中，如果会员数是2500万，定3000万是合理的，留一些余量。

误判率（falseProbability）。误判率越低，需要的位数组越大，空间成本越高。几个常见取值对应的空间开销差异很明显：

• 1%：3000万数据约占35MB
• 0.1%：3000万数据约占52MB
• 0.01%：3000万数据约占70MB

从1%降到0.1%，空间多用了差不多50%。大多数业务场景下1%够用了，对准确性要求更高的场景可以设到0.1%或0.01%。

过期时间（expire）。这个参数跟布隆过滤器本身的原理无关，但在实际项目里很关键。布隆过滤器不支持删除单个元素，但可以给整个过滤器设过期时间让系统自动回收。弹窗展示5天，过期时间设6天。权益改版通知要持续1年，过期时间就设365天。过期后过滤器自动清除，下次请求时重新创建。

下面这张速查表列出了不同参数组合下的位数组大小和哈希函数个数，做技术选型时可以直接查：

哈希函数个数的计算方式是 -(ln(误判率) / ln2)。误判率越低，需要的哈希函数越多，写入时的计算开销也越大。

不能删除的问题

布隆过滤器有一个经常被问到的限制：不支持删除单个元素。

原因在于位数组的位置是共享的。元素A占了第2、7、15位，元素B占了第5、7、20位，第7位是共用的。如果删除元素A，把第2、7、15位清零，第7位变成0，元素B查询时就会发现第7位是0，被误判为不存在。

计数布隆过滤器（Counting Bloom Filter）是解决这个问题的一个变体。它把每个位从1bit的0/1改成一个计数器，写入时计数器加1，删除时计数器减1，查询时检查计数器是否大于0。这样删除一个元素不会影响其他元素的判断。

代价是空间翻了好几倍。原来每个位占1bit，改成计数器后每个位至少占4bit。3000万数据量、1%误判率的配置下，空间从35MB涨到140MB。

实际项目中，大多数场景用不着计数布隆过滤器。给整个过滤器设一个过期时间，到期自动清除重建，比维护单个元素的删除逻辑要省事。一些分布式存储系统在内部使用了支持删除的布隆过滤器变体，但由于空间和维护成本更高，普通业务中用得不算多。

布隆过滤器不能无限写入

布隆过滤器在初始化时，位数组大小就已经固定了。随着不断写入元素，越来越多的位被置为1。当写入量远超预期数据量时，位数组会变得越来越密，误判率也随之飙升。极端情况下，如果位数组几乎全是1，任何元素查进来都会被判为存在，误判率接近100%，布隆过滤器就失去了过滤的意义。

所以布隆过滤器是一种容量固定的数据结构，不是想加多少就加多少。生产环境在创建时就要估算好expectedInsertions，留够余量。如果数据量真的超过了设计容量，需要创建一个新的布隆过滤器来替换旧的。这也是为什么前面配置里的预期数据量会按会员总数的1.2到1.5倍来设定。

实际项目中的两种用法

Java生态里用布隆过滤器，常见的有两个库。

单机场景用Guava的BloomFilter。Guava提供了标准的创建接口，指定预期数据量和误判率就行，内部会自动计算位数组大小和哈希函数个数。单机部署时直接创建使用，代码很简洁。

分布式场景用Redisson的RBloomFilter。多个服务实例需要共享同一个布隆过滤器时，单机版就不够用了，因为每个实例各自维护一份位数组，数据不互通。Redisson把布隆过滤器的数据存在Redis里，所有实例都能读写同一份数据。

前面贴的生产代码就是Redisson的方案。在实际项目里，通常会在Redis层封装一层initBloomFilter和getBloomFilter，处理过滤器不存在时的自动创建、分布式锁防止并发初始化这些细节。

两种方案的选型依据就看部署方式：单实例用Guava，多实例用Redisson。

小结

布隆过滤器的价值在于用很小的空间代价解决海量数据的存在性判断问题。3000万条记录，35MB内存就够了，这个空间效率是HashSet这类数据结构做不到的。

面试的时候把三个关键点讲明白就行：位数组是存储结构，多个哈希函数是写入和查询的机制，假阳性是它区别于精确判断的核心特征。假阳性只有单方向：判断不存在一定准确，判断存在可能误判。

做技术选型时多留意预期数据量这个参数。定小了会导致误判率飙升，定大了浪费空间，尽量提前估算准确。