先分享一个我自己的经历。之前做用户行为风控系统每天要处理上亿条日志里面有个需求很朴素判断某个用户ID今天是不是第一次出现。我一开始直接上了HashSetString结果线上实例内存肉眼可见地往上涨没撑过两轮压测就OOM了。后来把存储结构换成位图Bitmap内存一下降了两个数量级再遇到URL去重这种没法直接用整数索引的场景又引入了布隆过滤器Bloom Filter。这两个工具放到一起其实就是海量数据下做“存在性判断”的标配思路也是面试里高频出现的考点。这篇文章我会把位图和布隆过滤器的原理、选型逻辑、代码实现、生产参数算法一次讲透最后送上几个我自己反复踩坑后总结出来的工程经验。想省心的直接照着用问题不大。另外提醒一句如果你搜“位图”搜出来一堆PCB点位图、电路板点位图之类的说明你搜到另一个领域了——这里说的是数据结构里的Bitmap是用“一个比特位”表示“一个状态”的存储结构和图片处理中的位图完全两码事。1. 先搞清楚你在找哪一种“位图”1.1 一个让内存从GB降到MB的面试题很多后端同学对“海量数据存在性判断”这个概念都是从一道经典面试题开始的给你10亿个整数范围在0到20亿之间内存限制1GB如何判断某个数是否出现过这题第一反应基本都是哈希表。但你可以算一笔账10亿个int就算去掉对象头光裸数据就是40亿字节约4GB这还没算HashMap的Node节点、扩容冗余和指针开销真要用HashSetInteger存内存奔着几十GB去了明显不行。那用位图是什么结果呢20亿个可能的取值用20亿个bit去标记也就是20亿 / 8 2.5亿字节约250MB。就算再留一倍余量500MB也放进1GB限制了。查询的时候算一次下标取一个bit时间复杂度O(1)快得离谱。这就是位图的核心逻辑用一块连续的内存空间把“值”映射成“位置”位置上的0/1代表“不存在/存在”。1.2 存在性判断的本质允许误差吗不过现实业务不像面试题那么干净数据常常不是整数而是URL、手机号、订单ID这种字符串。位图没有办法直接索引一个字符串这时候就需要把字符串通过哈希函数“折叠”成整数位置用一个位数组去标记它。这里会出现一个关键分岔哈希折叠是有概率冲突的。两个不同的字符串可能落进同一个bit位于是“判断A存在但其实是B的标记”——这就是布隆过滤器里著名的误判false positive。换句话说布隆过滤器告诉你的答案是“可能存在”和“一定不存在”不是100%的“存在”。所以选型的一开始先想清楚业务允不允许误判。允许就用布隆过滤器省内存省到极致不允许老老实实上精确结构比如位图如果数据是整数或者精确的哈希表。这个决策点比后面所有细节都重要。2. 位图整数集合判断的“一张点名表”2.1 一个bit位回答一个“是否存在”位图的实现思路简单到有点朴素。想象你有一张巨大的点名表表上有N个格子每个格子只可能被涂成“已到”或“未到”两种状态。数据里的数字是什么你就去第几个格子上涂一笔。查询时看对应格子有没有被涂过。在计算机里“两种状态”天然对应一个bit也就是二进制的0和1。因为一个字节有8个bit所以如果取值范围是0到7一个字节就够了0到100万125KB就够。这里要注意的是位图占用的内存不取决于你往里面塞了多少个元素而是取决于值域范围有多大。即使你只存3个数但它们的取值范围是0到20亿位图仍然要占用250MB。理解了这一点位图的优缺点其实已经写在脸上了省内存查询、写入都是O(1)速度极快只适合“非负整数”或者能转成非负整数的场景值域很稀疏时反而浪费内存2.2 内存账本为什么能省这么多我用一个表格直接对比一下不同存储方式存1000万个整数假设值域在0到1亿之间的内存占用存储方式理论内存实际估算备注HashSetInteger约40MB裸数据300MB以上算上对象头、指针、扩容冗余int[]40MB40MB但判断“是否存在”得遍历二分查找排序数组40MB40MB排序后可以二分但插入成本高位图12.5MB12.5MB1亿bit除以8你可以看到位图在空间上的优势是数量级的。尤其是“值域密集、数据量大”的场景位图几乎是无脑最优解。它唯一的短板是没法处理负数和字符串但这可以通过“加偏移量”和“哈希二次映射”来补救后面会讲。2.3 极简Java实现与Redis实操自己实现一个位图并不难核心就是用一个long[]数组每个long是64位然后通过位运算定位到具体某一个bit。public class BitMap { private final long[] words; private final int bitCount; public BitMap(int bitCount) { this.bitCount bitCount; this.words new long[(bitCount 63) / 64]; } public void set(int index) { checkRange(index); words[index / 64] | (1L (index % 64)); } public boolean get(int index) { checkRange(index); return (words[index / 64] (1L (index % 64))) ! 0; } public void clear(int index) { checkRange(index); words[index / 64] ~(1L (index % 64)); } private void checkRange(int index) { if (index 0 || index bitCount) { throw new IndexOutOfBoundsException(index: index); } } }这里有个小细节index / 64定位到第几个longindex % 64定位到long里的第几位。位运算里的1L (index % 64)注意一定要用1L而不是1否则当移位超过31位时int会被自动包装结果完全不对。更省心的是用现成的类。Java里有java.util.BitSet已经封装好了set、get、clear、nextSetBit这些方法内部就是long数组改改直接用非常方便。但BitSet的set方法是线程不安全的分布式场景别忘加锁或者用AtomicLongArray。如果不想写Java代码Redis也内置了位图操作日常开发做个日活、签到简直不要太顺手# 记录用户100086在2024-01-01登录过 SETBIT login:2024-01-01 100086 1 # 查询用户100086那天是否登录 GETBIT login:2024-01-01 100086 # 统计当天登录人数 BITCOUNT login:2024-01-01 # 连续3天都登录过的用户把3天的位图做AND运算 BITOP AND login:3days login:2024-01-01 login:2024-01-02 login:2024-01-03注意Redis的SETBIT的value只能是0或1offset就是你的业务ID。如果用户ID很大比如9位数的手机号也没关系offset直接用它就行。但offset太大会导致单个key的底层字符串变长记得评估一下内存一台实例别塞太多大offset的key。2.4 位图的三个边界条件第一个坑是负数。位图的下标天然是非负整数遇到负数怎么办常见的做法是加一个偏移量比如区间是[-1000, 1000]存的时候用index value 1000。如果范围很大又不想提前知道边界那就把它转换成long再处理或者干脆走布隆过滤器路线。第二个坑是值域太稀疏。比如你有1000万个随机整数但它们的取值范围是0到100亿那用位图意味着你要申请100亿bit 1.25GB的内存为了存1000万个元素花1.25GB这就很不值了。这种场景反而应该用哈希表或者布隆过滤器。第三个坑是你必须提前知道值域上限。位图在初始化时就要分配好空间后面没法轻松扩容。如果业务上线后数值不断变大位图很容易“撑爆”。稳妥的做法是预留足够的余量或者在业务上做好分段比如按年拆分位图每个key对应一年的数据跨年滚动使用。3. 布隆过滤器把“哈希表”折叠成一张位图3.1 从哈希函数组合说起布隆过滤器的思想可以这样理解字符串没法直接当位图下标那我就用哈希函数把它算成一个整数再把这个整数取模到位数组的长度范围内把对应bit置1。但单个哈希函数冲突概率太高两个不同字符串可能哈希到同一个位置。布隆过滤器的设计巧妙之处在于它用了K个相互独立的哈希函数。插入时用K个哈希函数算出K个位置全部置1。查询时也用K个哈希函数算出K个位置检查这K个位置是否全部为1。类比一下特别好懂你开始在K个不同窗口都登记过名字后来有人来核对只要有一个窗口说“没见过”那基本可以肯定你确实没登记过但如果所有窗口都说“见过”那也可能是几个窗口一起记岔了。所以布隆过滤器的判定结果是某个位置为0一定不存在所有位置都为1可能存在这个“可能存在”就是误判的根源。好消息是误判率是可以通过参数控制的而且布隆过滤器永远不出现“漏判”也就是如果数据真的在集合里查询结果一定为true。这个特性在缓存穿透、URL去重里非常有价值。3.2 误判率公式与参数估算布隆过滤器有三个核心参数n预期插入的元素个数m位数组长度单位是bitk哈希函数个数误判率的理论公式是最优哈希函数个数k (m / n) * ln2位数组长度估算m - (n * ln(p)) / (ln2)^2其中p是你期望的误判率ln2约等于0.693。这俩公式是工程上最常用的。举一个具体例子。假设我们要对1000万个URL去重希望误判率控制在1%也就是p0.01m - (10^7 * ln(0.01)) / (0.693)^2 ≈ 9.58 * 10^7 bit换算成字节约11.4MBk (m / n) * ln2 ≈ 9.58 * 0.693 ≈ 6.64取整为7也就是说一个11.4MB的位数组配合7个独立的哈希函数就能支撑1000万数据、1%误判率的需求。这个体量放在生产环境里完全不算事。实际开发中留心一点公式算出来只是理想值因为真实数据分布、哈希函数质量都会影响最终表现。我一般会在算出来的m上再乘1.5到2的冗余系数宁可多占一点内存也要给以后数据增长留空间毕竟布隆过滤器满了再扩容是非常痛苦的。3.3 代码落地Guava一行搞定手写版理解原理生产环境我强烈建议直接用经过充分测试的库Java生态里最常用的是Guava的BloomFilterimport com.google.common.hash.BloomFilter; import com.google.common.hash.Funnels; import java.nio.charset.StandardCharsets; BloomFilterString filter BloomFilter.create( Funnels.stringFunnel(StandardCharsets.UTF_8), 10_000_000L, 0.01 ); filter.put(news:12345); boolean exists filter.mightContain(news:12345); // true boolean notExists filter.mightContain(news:99999); // 可能为true也可能为falsecreate的第三个参数就是预期的误判率Guava内部会自动计算最佳位数组长度和哈希函数个数。注意BloomFilter不是线程安全的多线程写入时需要外部加锁或者用ConcurrentHashMap加布隆过滤器的组合方案。如果想搞清楚原理我写了一个简化版核心逻辑也就几十行import java.util.BitSet; public class SimpleBloomFilter { private final BitSet bits; private final int bitSize; private final int hashCount; public SimpleBloomFilter(int bitSize, int hashCount) { this.bits new BitSet(bitSize); this.bitSize bitSize; this.hashCount hashCount; } public void add(String value) { for (int i 0; i hashCount; i) { bits.set(hash(value, i)); } } public boolean mightContain(String value) { for (int i 0; i hashCount; i) { if (!bits.get(hash(value, i))) { return false; } } return true; } private int hash(String value, int i) { int h1 value.hashCode(); int h2 (h1 16) * 31 0x9E3779B9 i * 0x9E3779B9; return ((h1 i * h2) 0x7FFFFFFF) % bitSize; } }注意这里为了演示简单我用了String.hashCode()和一个衍生hash来模拟K个独立哈希实际工程要追求分布均匀通常会用MurmurHash等高质量哈希函数。Guava内部就是这么干的。3.4 为什么标准布隆过滤器不能删除这是新手最容易踩的坑想从布隆过滤器里删除一个元素把它对应的K个bit置0不行因为这K个bit可能还承载了其他元素的信息一旦你清零其他元素的查询结果就被破坏了。也因此标准布隆过滤器只支持插入和查询不支持删除。如果业务上有“删除”需求比如推荐系统里用户把某条内容划走了不想再看到直接把它的bit置0会污染整个过滤器正确做法是用“计数布隆过滤器”Counting Bloom Filter也就是每个bit位换成计数器删除时对应位置的计数减1减到0才真正释放。但代价是内存暴涨几倍工程上用得不算多。更朴素也更常见的做法是“定期重建”数据量超过预估后新建一个过滤器把老数据重新灌进去然后切换读和写。Redis里甚至直接有BF.RESERVE、BF.ADD、BF.EXISTS这类命令底层就是计数布隆过滤器功能上对应用层友好很多。4. 哈希表、位图、布隆过滤器三张表做选型4.1 三个维度横向对比很多同学面试时被问到“哈希表和布隆过滤器怎么选”其实把三者放在一张表里看就清楚了对比项哈希表位图布隆过滤器查询结果精确精确有误判不会漏判内存占用高和元素个数成正比极低和值域大小成正比低和预期元素个数相关查询耗时O(1)但哈希碰撞可能退化O(1)纯位运算O(k)k通常很小接近O(1)支持的数据类型任意对象非负整数任意对象经哈希映射删除操作支持支持标准版不支持典型场景数据库索引、Map结构日活统计、签到、在线状态URL去重、缓存穿透防护从这张表能清晰看到位图和布隆过滤器并非竞争关系而是互补的。位图是“精确但限整数”布隆过滤器是“省内存但有概率误判”哈希表则是“功能全面但费内存”。4.2 工业选型经验什么时候无脑上位图我自己的选型习惯是这样的你可以直接抄数据是整数或可以转成整数值域已知且相对密集业务要求精确判断优先位图。比如用户ID、手机号、活动ID去重。数据是字符串、值域未知、业务对“偶尔误判”不敏感优先布隆过滤器。比如URL爬虫去重、缓存穿透保护。数据量小几千到几十万级别别折腾这些结构直接用哈希表省心。位图和布隆过滤器的优势在大数据量下才体现得出来。如果既要精确又要省内存位图哈希表的混合方案也常见外层位图过滤掉大部分明显不存在的数据命中后再用哈希表兜底确认既能挡住无效请求又能保证最终结果准确。还有一点别忽视不要为了炫技硬上。规模没到百万元素级别你用HashSet照样跑得很欢没必要引入额外的复杂度和维护成本。4.3 Redis里的现成答案生产环境不是所有场景都能自己写库很多时候你只需要在Redis层把方案落下去。Redis本身支持位图命令也提供了RedisBloom模块支持布隆过滤器。位图已经提过这里说下RedisBloom的用法。安装模块后你可以这样初始化一个布隆过滤器# 预分配期望插入100万个元素误判率1% BF.RESERVE my_bf 0.01 1000000 # 插入 BF.ADD my_bf order:12345 # 查询 BF.EXISTS my_bf order:12345用Redis做布隆过滤器有个好处它就是天然的分布式共享状态多个服务实例同时读写不需要自己做同步。坏处是Redis本身可能成为瓶颈插入量和查询量很大的时候网络开销不可忽略所以有些场景会用本地Guava布隆过滤器做一级过滤Redis布隆过滤器做二级过滤把流量分层扛住。5. 三个生产案例还原5.1 用户签到与连续性统计位图最顺手的场景做签到功能时如果每个用户都存一条签到记录运营一年下来光签到表数据量就很吓人。用位图的话一个用户可以对应一个keykey的每一位代表某一天是否签到。比如用户ID为1000862024年1月1日签到SETBIT sign:2024:01 100086 0这里把offset设为100086bit位为0就表示那天签到。如果要算某天签到人数直接BITCOUNT。如果要算连续7天签到用户用BITOP AND把7天的位图求交结果位图里为1的位置就是连续签到的用户ID。这个方案最舒服的点在于空间一个用户一年的签到记录只要365个bit约46字节。1亿用户一年也不过4.6GB左右分散到不同月份的key里单key内存完全可控。注意Redis单key的字符串上限是512MB所以别把全量用户塞进同一个key建议按天或者按月拆key这样无论是统计还是运维清理都比较方便。5.2 新闻/商品推荐去重布隆过滤器的标准用法推荐系统里经常要判断“这条新闻用户看过了没”如果用户已经看过的item放在Set里精确存储内存压力很大。我之前处理过一个千万级用户、亿级内容量的推荐项目最后就是给每个用户建了一个布隆过滤器。写入时用户每看一条内容就filter.put(contentId)推荐时先mightContain返回false就直接过滤掉返回true再做一次精确比较避免误删。这里有个很实用的优化布隆过滤器的误判率只在“已经完全放满”时才明显失控所以我在设计时给每个用户的过滤器预估容量是实际内容的1.5倍。用户一天最多看200条内容就给过滤器预留300的容量这样就能保证过滤器不会很快就满误判率也一直保持在低位。有个缺点也得承认用户量大的时候每个用户一个过滤器内存也不小。1000万用户每个过滤器按1000bit算就是10Gbit约1.25GB加上对象开销单个实例可能扛不住。这种情况一般会做两层本机用Guava缓存热点用户的过滤器冷数据落到Redis里查不到时再回源。5.3 缓存穿透保护先问布隆再问Redis缓存穿透是后端老生常谈的问题大量请求查询一个不存在的keyRedis里没有请求全部打到数据库数据库直接被压垮。常规做法是缓存空值但空值缓存时间短、效果有限而且会被恶意key刷穿。用布隆过滤器做前置拦截是更优雅的方案。核心思路是数据库里每条存在的记录写入时都把它存在主键ID放进布隆过滤器查询时先过布隆过滤器如果返回false说明这个ID大概率不存在直接返回空根本不用进Redis和数据库。public Article getArticle(Long id) { String key article: id; // 第一层布隆过滤器判断是否存在 if (!articleBloom.mightContain(key)) { return null; } // 第二层查Redis缓存 Article article redis.get(key); if (article ! null) { return article; } // 第三层查数据库并把结果写回缓存 article dao.findById(id); if (article ! null) { redis.set(key, article); } return article; }注意一个细节布隆过滤器的数据是在“写入DB”时同步灌进去的不是插入Redis时。而且如果系统有删除数据的操作被删掉的数据ID还会留在过滤器里查询时依然会放行到Redis和DB不过因为是“可能存在”最后还是会落库查一次。所以这类方案更适合“数据只增不删”或者“删除不频繁”的场景如果删除操作太频繁过滤器里的残留数据会让防护效果大打折扣。6. 工程避坑速查这些问题我踩过6.1 误判带来的脏数据如何兜底布隆过滤器最大的隐患就是误判哪怕误判率只有1%在海量请求下也会累积成大量无效查询所以“完全信任BF结果”是不能接受的。我在生产环境的标准做法永远是“BF是过滤器不是最终结论”它放行后后续流程一定要有精确存储做兜底。比如上面的缓存穿透例子BF放行后还是会走Redis和DBRedis和DB会给最终答案。这样就保证了系统性能被BF优化但数据正确性不受误判影响。6.2 容量估算错了怎么调整预估n只估了1000万结果业务爆发增长到5000万布隆过滤器会出现什么情况位数组里1的比例快速上升误判率急剧升高最坏情况整个数组全1用什么key都返回true等于过滤器失效了。这类问题没有灵丹妙药最直接的方案是“换更大的过滤器全量重建”。数据不大时重建成本可接受数据量大时可以用双缓冲先新建一个容量更大的过滤器把老数据异步灌进去数据迁移完成后再切换读写流量。整个过程对业务方透明但代码实现得多一个开关控制。更稳妥的办法是上线前就按业务峰值的3到5倍来做容量规划宁可多占内存也别年中做一次全量重建那个运维成本真是谁做谁知道。6.3 负数、大整数、字符串怎么办位图处理负数用偏移量处理超大整数要么分段要么转字符串后走布隆过滤器。这里说一个常见误区不要把整数直接toString()后丢进HashSet交给位图处理字符串哈希之后冲突概率会变大而且位图的意义就没了。字符串场景应该直接用布隆过滤器。还有要注意哈希函数必须返回非负整数。Java里String.hashCode()可能返回负数所以手写布隆过滤器时一定要做 0x7FFFFFFF这类处理保证下标落在合法范围。这个问题看似小但排查起来很隐蔽经常表现为布隆过滤器“间歇性失灵”。6.4 短期窗口判断滚动布隆过滤器最后分享一个性价比极高的实战技巧滚动布隆过滤器。适用于“最近N分钟内是否出现过”“5分钟是否发过验证码”这类短时间窗口的判断需求。实现思路是用一个固定大小的数组保存多个布隆过滤器每个过滤器负责一个时间窗口比如1分钟一个。新数据写入当前分钟的过滤器查询时遍历最近N个过滤器只要有一个返回true就命中了。窗口过期后直接丢弃对应过滤器或者复用对象清空内部bit数组。public class SlidingBloomFilter { private final BloomFilterString[] windows; private final int windowCount; private int currentIndex; public SlidingBloomFilter(int windowCount, long expectedInsertions, double fpp) { this.windowCount windowCount; this.windows new BloomFilter[windowCount]; for (int i 0; i windowCount; i) { windows[i] BloomFilter.create( Funnels.stringFunnel(StandardCharsets.UTF_8), expectedInsertions, fpp ); } } public void add(String value) { windows[currentIndex].put(value); } public boolean mightContain(String value) { for (BloomFilterString window : windows) { if (window.mightContain(value)) { return true; } } return false; } public void rollWindow() { currentIndex (currentIndex 1) % windowCount; windows[currentIndex] BloomFilter.create( Funnels.stringFunnel(StandardCharsets.UTF_8), 10_000_000L, 0.01 ); } }这样设计的好处是旧数据会随着窗口滚动自然失效不用手动清数据非常适合“5分钟内不能重复发送验证码”“1小时内防重复提交”这类场景。我个人做短时窗口需求时已经离不了这个套路了你直接把上面的代码拿过去改改参数就能用。