如果你接到一个需求在一批少则千万、多则上亿的数据里快速判断一个元素到底存不存在。很多人的第一反应是“搞个HashMap不就行了”可当数据量大起来HashMap的内存开销会先让你绝望接着想到“建一张数据库表查一下count”但几十亿条记录的数据库查询一样扛不住。这其实是一个非常经典的问题不需要取数据只需要一个布尔答案。位图和布隆过滤器就是为此而生的两个方案。它们一个用比特位精确记账一个用概率换空间处理的是同一个“存在性判断”问题却有着完全不同的脾气。这篇文章我会把原理、参数计算、工程选型和那些踩过的坑一次讲清楚适合正在做缓存、爬虫、网盘去重、用户标记等场景的工程师参考。1. 存在性判断为什么简单问题在海量数据下变得棘手1.1 一个朴素场景把问题拉出来假设你在做一个网盘类产品用户上传文件时系统要判断“这个文件是不是已经存过了”。如果把所有已存文件的路径都塞进数据库几十亿条记录每次上传都要走一次索引查询存储成本和写入放大直接卡住瓶颈。如果换成内存里的HashMap一条文件路径平均按64字节算存1亿个路径就需要6.4GB内存光为了回答“存没存过”这个问题就烧掉一大块内存。同样的场景多到数不过来判断一个URL是不是已经抓取过了判断用户是否已经领取过奖励判断一个IP是否在白名单里判断某个缓存key是不是被人恶意构造的“不存在但高频请求”的假key。这些需求有个共同点我不需要拿到这条数据本身只需要一个“有还是没有”的布尔结果。麻烦就在于数据量一旦到了千万、亿这个级别传统精确索引结构的成本就压不住。1.2 为什么HashMap在数据量大了以后就不香了很多人一提到判存第一反应就是HashSet、HashMap。但仔细算一笔账就明白了。HashMap底层是数组加链表或红黑树每个键值对除了要存key本身还要存对象头、哈希值、指向下一个节点的引用。在JVM里一个Integer对象加上引用占用可能超过20字节如果key是字符串光String对象内部就有一个char数组的引用、一个hash字段再加上字符数组本身一条记录轻松上百字节。存1000万个整数理论上int本身只要40MB但放进HashMap之后Integer装箱加上节点对象实际内存可能冲到300MB以上。如果存的是字符串URL内存开销更夸张。更难受的是HashMap还需要预留扩容空间负载因子默认0.75意味着你最多用到75%的容量就要resize。数据量从1000万涨到2000万的那次扩容会有明显的停顿对在线服务来说相当不友好。当需求退化成“只要一个存在性判断”时HashMap等于用大量存储去记录那些最终根本不会被读取的value。在“存在性”这个需求面前HashMap是杀鸡用牛刀。1.3 两类经典的“省内存判存”思路于是工程上就分化出两个流派。第一个是位图。把元素ID直接映射到二进制数组里的某一位这一位是1表示存在是0表示不存在。优点是精确、极省内存缺点是要求你能把元素压成一段连续范围内的整数。第二个是布隆过滤器。用一组哈希函数把一个元素映射到二进制数组里的多个位置所有位置都是1才判定为“可能存在”只要有一个位置是0就判定为“一定不存在”。优点是任意类型的元素都能用空间极省缺点是有误判率。这两个方案不是互斥的很多系统会叠着用。下面我先把各自原理和参数讲清楚再讲怎么选型。2. 位图用1个二进制位标记一件事的存在2.1 位图的核心原理与内存账本位图的思想一句话就能说清准备一个很长的二进制数组数组的每一位代表一个元素编号第i位等于1就表示编号i的元素存在。内存怎么算N个bitN除以8得到字节数再除以1024得到KB再除以1024得到MB。打个比方系统里用户ID是自增int最大1000万那就开一个1000万bit的位图。10000000除以8等于1250000字节约1.19MB。存同样1000万个用户HashMap要几百MB位图只用1.19MB差了近两个数量级。很多初学者听到“位图”以为是什么高端数据结构其实它就是最原始的bit数组。之所以省内存是因为它把连续整数的“存在性”压缩到了极致一个元素只占一个位连一字节都不到。2.2 位图的适用边界整数域与稀疏陷阱位图的最大前提是你得能把待判断元素映射到一段连续整数范围。网上经常说“位图只能对连续整数去重”这话不准确。严格说只要存在从元素到整数的单射映射位图就能用。比如26个小写字母映射成0到25照样可以用位图。真正的坑有两个。第一个坑是元素域太大。比如系统用UUID当主键你没法把UUID直接映射成一段可管理的整数范围。强行用UUID的哈希值当offset哈希值分布到整个32位甚至64位空间位图长度会暴涨。假设你用UUID的自带数值直接映射到128位空间那个位图长度比宇宙里的原子还多内存直接爆掉。所以位图要么用于本身是整型的ID要么你得先维护一张“业务ID到连续序号”的映射表。第二个坑是稀疏。要表示32位int的全部取值范围需要2的32次方个bit也就是512MB。如果实际只有100个元素这512MB里几乎全是0白瞎。位图最怕的就是“域很大真实元素很少”的场景。它擅长的是“域确定、分布相对稠密”的判断。2.3 实战中的位图形态Redis BITMAP与Roaring Bitmap真正写业务时很少有人从头维护裸bit数组。最常见的落地形态是Redis的BITMAP也就是SETBIT和GETBIT命令。Redis的bitmap底层是一个动态字符串偏移量超出当前长度会自动扩容单个key最多能承载2的32次方个bit换算下来512MB。但要注意offset本身不能太大。如果把一个雪花算法生成的19位长整型当offset直接SETBITRedis会自动把字符串扩容到接近offset除以8的字节数。一个19位数字作为offset内存可能瞬间变成几十TB直接炸掉。所以用Redis BITMAP之前先确认用户ID是相对连续的int或者先做一次密集化映射。另一个常见形态是Roaring Bitmap。它把32位整数拆成高16位和低16位两个部分每个高16位分区内部如果数据稠密就用bitmap存储如果稀疏就用有序数组存储数据量变化时会自动切换。这样既能处理稀疏数据又能保留位图的压缩优势。很多列式存储、OLAP引擎、倒排索引里都在用Roaring Bitmap如果业务里要存大量离散整数并频繁做交集并集很值得研究。3. 布隆过滤器用极低误判率换海量判存能力3.1 布隆过滤器的工作流程布隆过滤器的数据结构比位图复杂一层。它有一个长度为m的位数组以及k个相互独立的哈希函数。插入一个元素时用这k个哈希函数分别算出k个位置把这k个bit全部置为1。查询一个元素时同样算出k个位置检查是否全部为1。如果全部为1就认为这个元素“可能存在”只要有一个位置为0就认为“一定不存在”。关键点来了布隆过滤器说“不存在”是100%准确的。因为如果某个元素真的插入过它对应的k个位置必然都是1绝不可能是0。但它说“存在”只是大概率成立。因为多个不同元素的k个位置可能叠加让一个没插入过的元素恰好撞上所有位置都是1这就是假阳性误判。用个土味比喻你在一片空地上对每个“来过的人”钉k根钉子。判断一个人是否来过你只要看他的那k个固定点位是不是都有钉子。如果有人没来过但他的点位都被别人钉过了你也会误以为他来过。你只能确定“点位没钉子的人肯定没来过”但“点位都有钉子”不一定代表是他本人钉的。3.2 位数组长度m、元素数量n、哈希函数k的数学关系用布隆过滤器不能拍脑袋。三个核心参数m、n、k之间有明确的数学关系。当预估元素数为n期望误判率为p时位数组长度m的最优值公式是m - n * ln(p) / (ln2)^2哈希函数个数k的最优值公式是k (m / n) * ln2这里的ln2约等于0.693。拿一个具体场景算一算。如果要存1亿个元素期望误判率控制在1%也就是p等于0.01那么ln(0.01)约等于-4.605(ln2)^2约等于0.480m约等于9.58亿bit换算成内存约114MB。接着算kk等于9.58亿除1亿再乘0.693约等于6.64取整就是7。也就是说用114MB内存和7次哈希运算就能在1亿个元素上实现大约1%的误判率。作为对比精确存1亿个32位整数本身就要400MB换成Java HashSet可能要几个GB。布隆过滤器在“可以容忍一点误判”的场景下优势非常明显。3.3 为什么布隆过滤器不能删元素布隆过滤器有一个让很多人头疼的限制不能删除元素。原因很直接。位数组里的每一个bit都可能被多个元素共享。删除一个元素时如果把它对应的k个bit从1改成0完全可能把另一个元素“存在”的证据也抹掉。下次查询另一个确实存在的元素发现某个bit变回了0就会错误地判定为“不存在”。这种反向误判比假阳性更麻烦业务上通常无法接受。如果业务确实需要删除可以改用Counting Bloom Filter也就是把每一个bit升级成一个小计数器。插入时对应计数器加1删除时对应计数器减1计数器归0才真正清空这个位置。代价是内存涨了好几倍计数器还有溢出风险需要定期检查修正。另一个常见变通是定期重建。比如每天凌晨生成一个新的布隆过滤器把当天需要保留的元素重新塞进去然后把老实例丢弃。简单有效很多爬虫和反作弊系统都是这么干的。3.4 典型战场缓存穿透、URL去重、网盘秒传布隆过滤器最经典的工程场景是防缓存穿透。用户请求一个不存在的数据时如果每次都穿透缓存打到数据库容易被恶意流量打爆。做法是在缓存前面加一个布隆过滤器把所有可能存在的key预先进来。请求来了先问布隆过滤器如果说不存在就直接拦截如果说可能存在才去查缓存和数据库。这样绝大多数“不存在”的请求根本不会打到后端存储。第二个常见场景是爬虫的URL去重。抓过的URL字符串长短不一数量可能上亿。如果全部放进Set内存消耗非常大。布隆过滤器可以在1%误判率下把内存从几个GB压到一百多MB。代价是极少数没抓过的URL会被判成“抓过”造成漏抓。对于合格率要求没那么苛刻的爬虫完全可以接受。第三个场景是网盘类产品的内容去重。用户在秒传文件时平台先通过文件哈希去查是否存在相同文件。这里不会让布隆过滤器做最终判决而是拿它做前置过滤先把“几乎不可能存在”的文件指纹快速排除命中“可能存在”的指纹再去精确哈希索引里查一遍。布隆过滤器过滤掉大批噪音精确结构只处理少量命中整体性能能拉高不少。4. 位图与布隆过滤器怎么选一张表看懂4.1 核心指标横向对比很多新人问都是判存到底选哪个我习惯用四个维度来对比。第一是精确性。位图是精确判断位是1就是存在是0就是不存在没有误判。布隆过滤器有误判率只会把不存在的判成存在绝不会把存在的判成不存在。第二是数据形态。位图本质上要求元素能映射成连续整数。布隆过滤器对字符串、二进制、自定义对象都可以通过哈希函数处理覆盖面广得多。第三是空间。在元素域N确定且密集的情况下位图是固定的N bit你无法再压缩。布隆过滤器的空间是m bitm和预估元素量、目标误判率挂钩。元素量预估越准空间越好控制。第四是删除能力。位图支持删除把对应位直接清零就行。布隆过滤器标准版不支持删除。下面这张表是我项目里常用的快速参考方便直接照着选。维度位图布隆过滤器核心思想用bit位精确标记整数用多个哈希位置做概率标记是否存在误判否是只可能把不存在的判成存在需要的数据形态整数或可映射为整数任意数据经过哈希空间开销N bitN为域大小m bitm与元素量和误判率相关删除能力支持直接置0标准版不支持典型应用用户签到、活跃标记缓存穿透、URL去重、黑名单预判4.2 选型决策路径我总结了一条选型线照着走基本不会出错。第一步看元素本身是不是连续整数。如果是自增ID、序号、编码这类本身就在一个可控范围内的整数而且域范围不大空间能接受那就无脑用位图。它的实现简单没有误判内存极其可控。第二步如果元素是字符串、URL、UUID这些不连续对象或者域范围大到不可控就别硬做映射了直接用布隆过滤器。虽然在哈希到布隆过滤器时依然可能碰撞但至少你不需要维护一张巨大的“业务ID到序号”映射表。第三步如果既要大容量精确判存又不想维护映射表可以用布隆过滤器做前置快速排除命中后再去精确存储里查一次。这个组合能兼顾准确性和内存。这里必须提醒一个容易被忽略的问题位图的存储是固定成本跟你实际塞了多少真实元素没关系。哪怕只有1万个用户只要域是1亿位图就要占1亿bit。布隆过滤器的存储则和预估元素量n强相关。如果你把n估小了实际塞进去的元素比预估多10倍误判率会急剧恶化甚至恶化到你无法容忍的地步。4.3 二者能不能叠着用能而且叠着用的场景很多。有个典型组合是双层结构外层布隆过滤器负责挡住绝对不存在的key内层位图负责精确判断高频连续ID是否存在。比如在防缓存穿透系统里先用布隆过滤器处理字符串类key命中后再到后端的连续ID序列里用位图做精确过滤。这样既不需要为所有字符串key维护一套巨大映射表又能让高频整数判断保持零误判。另一个组合是“快速排除”加“精确确认”。布隆过滤器先过滤掉绝大多数的“不存在”剩下的少量“可能存在”再去精确索引里做最终确认。网盘秒传、图片去重、消息幂等里都能用这个思路。组合的本质是布隆过滤器过滤掉绝大多数噪音精确结构处理剩下的少数。内存和CPU的账算下来往往比单一方案更划算。5. 实操两个可以直接抄作业的例子5.1 案例1000万用户ID判断是否领取过活动奖励用位图先看一个最常见的位图场景。假设系统有1000万用户ID是从1到1000万左右的整数。要判断每个用户是否已经领取过新人礼包领过打标没领过就不能重复领。这个场景用Redis BITMAP非常合适直接把用户ID当作offset用户领奖后把对应位置置1。先用Lua脚本保证判断和置位是原子的防止并发重复领取-- KEYS[1] 为位图key -- KEYS[2] 为用户ID -- 返回值 0 表示本次可以领取1 表示已经领取过 if redis.call(getbit, KEYS[1], KEYS[2]) 1 then return 0 end redis.call(setbit, KEYS[1], KEYS[2], 1) return 1这段脚本的意思是先查用户ID这一位是不是1如果已经是1说明领过了返回0拒绝否则把这一位置为1返回1表示本次领取成功。整个判断和置位在Redis里是原子操作不会出现两个人同时抢到一个可领取名额。如果用Java客户端大概长这样String key activity:newbie:reward; Long userId 10800001L; boolean hasClaimed jedis.getbit(key, userId); if (!hasClaimed) { // 实际项目中建议用上面的Lua脚本 jedis.setbit(key, userId, true); // 发放奖励 }但这个写法有个并发问题先getbit再setbit不是原子操作两个请求同时进来可能都看到0于是都去发奖。所以线上我强烈推荐用Lua。内存账本1000万用户1000万个bit约1.19MB。放Redis里毫无压力。在这个场景里用位图明显优于用Set或者数据库表。Set需要存1000万个用户ID至少几十MB数据库表还要维护索引写放大。还要提醒一个业务细节如果把“置位”和“发奖”分开做置位成功但发奖失败用户会永久失去领取机会。所以要么发奖和置位放在同一个事务里要么置位后异步发奖并且给发奖失败提供补偿机制。5.2 案例1亿个URL去重用布隆过滤器再来看一个布隆过滤器场景。爬虫系统要判断一个URL是不是已经抓取过了。URL是字符串长短不一精确存HashMap内存受不了于是用布隆过滤器做前置去重。预估未来总URL数量为1亿目标误判率控制在1%以内。根据3.2节的计算m约9.58亿bit约114MBk约7。用Guava实现的话代码很短import 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), 100_000_000, 0.01); // 爬取前判断 boolean mightBeCrawled filter.mightContain(url); if (!mightBeCrawled) { // 没爬过去抓取 filter.put(url); }如果你看过Guava源码会发现它在底层不是真的生成7个完全独立的哈希函数而是用双哈希法组合出7个位置这样既保证分布均匀又减少计算量。要注意一点Guava的BloomFilter是进程内的对象。如果系统部署在多个实例每个实例有独立的布隆过滤器会出现“这台机器判定没爬过另一台机器已经在爬”的情况。要全集群共享判存要么用Redis Stack的BF.RESERVE、BF.ADD、BF.EXISTS命令要么自己用一个分布式位数组保存布隆状态。这个在多实例部署时特别容易踩坑。5.3 参数计算为什么这个位数组长度最合适新手最容易跳过参数计算直接调库。我给你手写一遍完整过程。已知n等于1亿p等于0.01。先算mm -100000000 * ln(0.01) / (ln2)^2ln(0.01)约等于 -4.605170ln2约等于0.693147平方约0.480453。代入后m 100000000 * 4.605170 / 0.480453 m ≈ 958505161 bit除以8约119813145字节约114.3MB。再算kk (958505161 / 100000000) * 0.693147 k ≈ 6.64取整数7。回代验证误判率p ≈ (1 - e^(-7 * 100000000 / 958505161))^7 p ≈ (1 - e^(-0.7303))^7 p ≈ (1 - 0.4817)^7 p ≈ 0.5183^7 p ≈ 0.0098约0.98%满足1%的目标。下面这张表是常见配置的速查可以直接抄预估元素数 n目标误判率 p位数组大小 m内存约最优哈希数 k1亿10%4.79亿bit57.1MB41亿1%9.59亿bit114.3MB71亿0.1%14.38亿bit171.6MB1010亿1%95.85亿bit1.12GB7注意k不是越大越好。位数组长度为m插入n个元素后某个bit位上是1的概率约等于 1 - e^(-kn/m)。k太大位数组里的1会越来越多最后所有位置都可能变成1误判率反而反弹。所以一定要围绕最优k值附近取整而不是随手设一个“感觉很大的数”。5.4 如果不想用依赖库自己写一个简版布隆过滤器理解原理最快的方式是自己花几分钟写一个玩具版。Python代码非常短核心就是位数组加哈希函数。import math import mmh3 class BloomFilter: def __init__(self, n, p): self.m int(-n * math.log(p) / (math.log(2) ** 2)) self.k int((self.m / n) * math.log(2)) self.bits bytearray(self.m // 8 1) def _positions(self, item): return [ (mmh3.hash(item, seed) 0xFFFFFFFF) % self.m for seed in range(self.k) ] def put(self, item): for pos in self._positions(item): self.bits[pos // 8] | 1 (pos % 8) def might_contain(self, item): return all( self.bits[pos // 8] (1 (pos % 8)) for pos in self._positions(item) )这个实现有几个细节要说明。第一mmh3.hash返回的是32位有符号整数会出现负值所以要做一次 0xFFFFFFFF保证结果落在0到2的32次方减1之间。第二这里用不同的seed生成k个独立的哈希简单直观但计算量偏高。真正工程实现里常用双哈希法先算出两个基础哈希h1和h2然后通过h1 i * h2的方式派生第i个位置这样性能更好。第三bytearray的长度是m // 8 1多一个字节无伤大雅但要保证取模时不会越界。如果你拿这个玩具代码上生产还是建议换成熟库。6. 工程中的坑与排查实录6.1 位图稀疏导致空间失控第一个大坑是位图看着省内存但遇上稀疏数据就会失控。比如用户ID是雪花算法生成的长整型最大值可能到2的63次方。你直接把ID当Redis的offset用SETBIT一个bitRedis底层字符串就要扩容到offset除以8的字节数。一个10的18次方级别的ID一个bit下去字符串可能扩展到一百多TB直接报内存错误。这不是夸张是真实会发生的事。所以用位图之前先确认你的ID最大值。要么用自增ID要么先做一次“密集化映射”把已存在的用户ID排序后映射成连续序号。Redis BITMAP听话的前提是offset不能太离谱。6.2 布隆过滤器误判引发的业务问题布隆过滤器的误判属于“设计内概率”不是bug但业务通常不会容忍假阳性。我见过一个线上事故团队用布隆过滤器判断“用户是否有过购买行为”返回false就不发优惠券。结果因为误判极少数没买过东西的用户被漏判出现了投诉。排查下来发现这不是代码问题而是选型问题。布隆过滤器只适合“漏掉几个不存在的请求无所谓”的场景。如果漏掉一个真实用户就是事故那必须给误判兜底。以缓存穿透为例正确做法是布隆过滤器返回“可能存在”后如果缓存和数据库里查不到也要正常返回“无数据”给前端不能因为布隆过滤器说有就固执地认为一定有。因为那极小概率是假阳性。一个严谨系统必须在精确查询后接受“布隆过滤器也可能错”的事实。6.3 哈希函数与误判率的关系哈希函数的质量直接影响误判率。如果两个哈希函数之间线性相关相当于你只用了少于k个的独立哈希位数组中的点更容易重叠误判率会上升。工程上推荐用MurmurHash、xxHash这类非加密哈希速度快、分布均匀。MD5、SHA-1虽然更随机但速度慢在布隆过滤器这种需要反复哈希的场景里不划算。另外要注意“双哈希法”的正确姿势。用h1加i乘h2派生第i个位置时如果h2在某个数值上退化成0所有派生位置都等于h1那k就失效了。所以实际项目里要么选用成熟库要么随机验证一下种子的分布。6.4 排查工具与调优经验排查布隆过滤器问题时先看三个指标当前插入数量、位数组长度、实测误判率。如果实测误判率远高于设计值第一怀疑对象是n预估不足。比如按1亿设计的实际插入了3亿误判率会从1%涨到40%以上这种恶化速度非常可怕。所以要给n留出余量高峰期的量也一并算进去。第二怀疑对象是哈希函数的实现是否真的独立。如果多个哈希函数用的是同一个随机种子退化出来的误判率也会不正常。第三是位数组是否被多个过滤器共用。有些团队图省事在一个位数组里塞多个业务的数据结果互相污染。发现之后要立刻拆开。调优时建议做一次实测。用随机样本不断插入再用另一批从未插入过的样本去查询统计被误判的比例。这个实测值比公式更直观也更接近线上真实情况。如果误判率可以接受就继续沿用不能接受就调低p重新算一遍m和k。不要靠感觉调参一定要回到公式上去算。7. 写在最后我的一点工程习惯做了这么多年数据判存相关的事我自己的习惯是每次拿到“判断某个东西存不存在”的需求先问自己三个问题。第一允不允许有误判哪怕是0.1%的概率。第二这个元素是整数还是字符串域大概多大。第三是需要全集群共享判存还是单机够用。第一个问题决定能不能用布隆过滤器。第二个问题决定该用位图还是布隆过滤器。第三个问题决定用Redis还是进程内库。三个问题想清楚选型就顺了。参数方面布隆过滤器永远先按峰值预估算一遍再留出至少20%的余量不要刚刚好卡着容量设计。位图也一样先确认ID最大值和分布密度别让偏移量失控。判存问题看起来简单但真正决定上限的从来不是某个数据结构而是你对“误判”和“内存”这两个词有多敏感。
如果你接到一个需求在一批少则千万、多则上亿的数据里快速判断一个元素到底存不存在。很多人的第一反应是“搞个HashMap不就行了”可当数据量大起来HashMap的内存开销会先让你绝望接着想到“建一张数据库表查一下count”但几十亿条记录的数据库查询一样扛不住。这其实是一个非常经典的问题不需要取数据只需要一个布尔答案。位图和布隆过滤器就是为此而生的两个方案。它们一个用比特位精确记账一个用概率换空间处理的是同一个“存在性判断”问题却有着完全不同的脾气。这篇文章我会把原理、参数计算、工程选型和那些踩过的坑一次讲清楚适合正在做缓存、爬虫、网盘去重、用户标记等场景的工程师参考。1. 存在性判断为什么简单问题在海量数据下变得棘手1.1 一个朴素场景把问题拉出来假设你在做一个网盘类产品用户上传文件时系统要判断“这个文件是不是已经存过了”。如果把所有已存文件的路径都塞进数据库几十亿条记录每次上传都要走一次索引查询存储成本和写入放大直接卡住瓶颈。如果换成内存里的HashMap一条文件路径平均按64字节算存1亿个路径就需要6.4GB内存光为了回答“存没存过”这个问题就烧掉一大块内存。同样的场景多到数不过来判断一个URL是不是已经抓取过了判断用户是否已经领取过奖励判断一个IP是否在白名单里判断某个缓存key是不是被人恶意构造的“不存在但高频请求”的假key。这些需求有个共同点我不需要拿到这条数据本身只需要一个“有还是没有”的布尔结果。麻烦就在于数据量一旦到了千万、亿这个级别传统精确索引结构的成本就压不住。1.2 为什么HashMap在数据量大了以后就不香了很多人一提到判存第一反应就是HashSet、HashMap。但仔细算一笔账就明白了。HashMap底层是数组加链表或红黑树每个键值对除了要存key本身还要存对象头、哈希值、指向下一个节点的引用。在JVM里一个Integer对象加上引用占用可能超过20字节如果key是字符串光String对象内部就有一个char数组的引用、一个hash字段再加上字符数组本身一条记录轻松上百字节。存1000万个整数理论上int本身只要40MB但放进HashMap之后Integer装箱加上节点对象实际内存可能冲到300MB以上。如果存的是字符串URL内存开销更夸张。更难受的是HashMap还需要预留扩容空间负载因子默认0.75意味着你最多用到75%的容量就要resize。数据量从1000万涨到2000万的那次扩容会有明显的停顿对在线服务来说相当不友好。当需求退化成“只要一个存在性判断”时HashMap等于用大量存储去记录那些最终根本不会被读取的value。在“存在性”这个需求面前HashMap是杀鸡用牛刀。1.3 两类经典的“省内存判存”思路于是工程上就分化出两个流派。第一个是位图。把元素ID直接映射到二进制数组里的某一位这一位是1表示存在是0表示不存在。优点是精确、极省内存缺点是要求你能把元素压成一段连续范围内的整数。第二个是布隆过滤器。用一组哈希函数把一个元素映射到二进制数组里的多个位置所有位置都是1才判定为“可能存在”只要有一个位置是0就判定为“一定不存在”。优点是任意类型的元素都能用空间极省缺点是有误判率。这两个方案不是互斥的很多系统会叠着用。下面我先把各自原理和参数讲清楚再讲怎么选型。2. 位图用1个二进制位标记一件事的存在2.1 位图的核心原理与内存账本位图的思想一句话就能说清准备一个很长的二进制数组数组的每一位代表一个元素编号第i位等于1就表示编号i的元素存在。内存怎么算N个bitN除以8得到字节数再除以1024得到KB再除以1024得到MB。打个比方系统里用户ID是自增int最大1000万那就开一个1000万bit的位图。10000000除以8等于1250000字节约1.19MB。存同样1000万个用户HashMap要几百MB位图只用1.19MB差了近两个数量级。很多初学者听到“位图”以为是什么高端数据结构其实它就是最原始的bit数组。之所以省内存是因为它把连续整数的“存在性”压缩到了极致一个元素只占一个位连一字节都不到。2.2 位图的适用边界整数域与稀疏陷阱位图的最大前提是你得能把待判断元素映射到一段连续整数范围。网上经常说“位图只能对连续整数去重”这话不准确。严格说只要存在从元素到整数的单射映射位图就能用。比如26个小写字母映射成0到25照样可以用位图。真正的坑有两个。第一个坑是元素域太大。比如系统用UUID当主键你没法把UUID直接映射成一段可管理的整数范围。强行用UUID的哈希值当offset哈希值分布到整个32位甚至64位空间位图长度会暴涨。假设你用UUID的自带数值直接映射到128位空间那个位图长度比宇宙里的原子还多内存直接爆掉。所以位图要么用于本身是整型的ID要么你得先维护一张“业务ID到连续序号”的映射表。第二个坑是稀疏。要表示32位int的全部取值范围需要2的32次方个bit也就是512MB。如果实际只有100个元素这512MB里几乎全是0白瞎。位图最怕的就是“域很大真实元素很少”的场景。它擅长的是“域确定、分布相对稠密”的判断。2.3 实战中的位图形态Redis BITMAP与Roaring Bitmap真正写业务时很少有人从头维护裸bit数组。最常见的落地形态是Redis的BITMAP也就是SETBIT和GETBIT命令。Redis的bitmap底层是一个动态字符串偏移量超出当前长度会自动扩容单个key最多能承载2的32次方个bit换算下来512MB。但要注意offset本身不能太大。如果把一个雪花算法生成的19位长整型当offset直接SETBITRedis会自动把字符串扩容到接近offset除以8的字节数。一个19位数字作为offset内存可能瞬间变成几十TB直接炸掉。所以用Redis BITMAP之前先确认用户ID是相对连续的int或者先做一次密集化映射。另一个常见形态是Roaring Bitmap。它把32位整数拆成高16位和低16位两个部分每个高16位分区内部如果数据稠密就用bitmap存储如果稀疏就用有序数组存储数据量变化时会自动切换。这样既能处理稀疏数据又能保留位图的压缩优势。很多列式存储、OLAP引擎、倒排索引里都在用Roaring Bitmap如果业务里要存大量离散整数并频繁做交集并集很值得研究。3. 布隆过滤器用极低误判率换海量判存能力3.1 布隆过滤器的工作流程布隆过滤器的数据结构比位图复杂一层。它有一个长度为m的位数组以及k个相互独立的哈希函数。插入一个元素时用这k个哈希函数分别算出k个位置把这k个bit全部置为1。查询一个元素时同样算出k个位置检查是否全部为1。如果全部为1就认为这个元素“可能存在”只要有一个位置为0就认为“一定不存在”。关键点来了布隆过滤器说“不存在”是100%准确的。因为如果某个元素真的插入过它对应的k个位置必然都是1绝不可能是0。但它说“存在”只是大概率成立。因为多个不同元素的k个位置可能叠加让一个没插入过的元素恰好撞上所有位置都是1这就是假阳性误判。用个土味比喻你在一片空地上对每个“来过的人”钉k根钉子。判断一个人是否来过你只要看他的那k个固定点位是不是都有钉子。如果有人没来过但他的点位都被别人钉过了你也会误以为他来过。你只能确定“点位没钉子的人肯定没来过”但“点位都有钉子”不一定代表是他本人钉的。3.2 位数组长度m、元素数量n、哈希函数k的数学关系用布隆过滤器不能拍脑袋。三个核心参数m、n、k之间有明确的数学关系。当预估元素数为n期望误判率为p时位数组长度m的最优值公式是m - n * ln(p) / (ln2)^2哈希函数个数k的最优值公式是k (m / n) * ln2这里的ln2约等于0.693。拿一个具体场景算一算。如果要存1亿个元素期望误判率控制在1%也就是p等于0.01那么ln(0.01)约等于-4.605(ln2)^2约等于0.480m约等于9.58亿bit换算成内存约114MB。接着算kk等于9.58亿除1亿再乘0.693约等于6.64取整就是7。也就是说用114MB内存和7次哈希运算就能在1亿个元素上实现大约1%的误判率。作为对比精确存1亿个32位整数本身就要400MB换成Java HashSet可能要几个GB。布隆过滤器在“可以容忍一点误判”的场景下优势非常明显。3.3 为什么布隆过滤器不能删元素布隆过滤器有一个让很多人头疼的限制不能删除元素。原因很直接。位数组里的每一个bit都可能被多个元素共享。删除一个元素时如果把它对应的k个bit从1改成0完全可能把另一个元素“存在”的证据也抹掉。下次查询另一个确实存在的元素发现某个bit变回了0就会错误地判定为“不存在”。这种反向误判比假阳性更麻烦业务上通常无法接受。如果业务确实需要删除可以改用Counting Bloom Filter也就是把每一个bit升级成一个小计数器。插入时对应计数器加1删除时对应计数器减1计数器归0才真正清空这个位置。代价是内存涨了好几倍计数器还有溢出风险需要定期检查修正。另一个常见变通是定期重建。比如每天凌晨生成一个新的布隆过滤器把当天需要保留的元素重新塞进去然后把老实例丢弃。简单有效很多爬虫和反作弊系统都是这么干的。3.4 典型战场缓存穿透、URL去重、网盘秒传布隆过滤器最经典的工程场景是防缓存穿透。用户请求一个不存在的数据时如果每次都穿透缓存打到数据库容易被恶意流量打爆。做法是在缓存前面加一个布隆过滤器把所有可能存在的key预先进来。请求来了先问布隆过滤器如果说不存在就直接拦截如果说可能存在才去查缓存和数据库。这样绝大多数“不存在”的请求根本不会打到后端存储。第二个常见场景是爬虫的URL去重。抓过的URL字符串长短不一数量可能上亿。如果全部放进Set内存消耗非常大。布隆过滤器可以在1%误判率下把内存从几个GB压到一百多MB。代价是极少数没抓过的URL会被判成“抓过”造成漏抓。对于合格率要求没那么苛刻的爬虫完全可以接受。第三个场景是网盘类产品的内容去重。用户在秒传文件时平台先通过文件哈希去查是否存在相同文件。这里不会让布隆过滤器做最终判决而是拿它做前置过滤先把“几乎不可能存在”的文件指纹快速排除命中“可能存在”的指纹再去精确哈希索引里查一遍。布隆过滤器过滤掉大批噪音精确结构只处理少量命中整体性能能拉高不少。4. 位图与布隆过滤器怎么选一张表看懂4.1 核心指标横向对比很多新人问都是判存到底选哪个我习惯用四个维度来对比。第一是精确性。位图是精确判断位是1就是存在是0就是不存在没有误判。布隆过滤器有误判率只会把不存在的判成存在绝不会把存在的判成不存在。第二是数据形态。位图本质上要求元素能映射成连续整数。布隆过滤器对字符串、二进制、自定义对象都可以通过哈希函数处理覆盖面广得多。第三是空间。在元素域N确定且密集的情况下位图是固定的N bit你无法再压缩。布隆过滤器的空间是m bitm和预估元素量、目标误判率挂钩。元素量预估越准空间越好控制。第四是删除能力。位图支持删除把对应位直接清零就行。布隆过滤器标准版不支持删除。下面这张表是我项目里常用的快速参考方便直接照着选。维度位图布隆过滤器核心思想用bit位精确标记整数用多个哈希位置做概率标记是否存在误判否是只可能把不存在的判成存在需要的数据形态整数或可映射为整数任意数据经过哈希空间开销N bitN为域大小m bitm与元素量和误判率相关删除能力支持直接置0标准版不支持典型应用用户签到、活跃标记缓存穿透、URL去重、黑名单预判4.2 选型决策路径我总结了一条选型线照着走基本不会出错。第一步看元素本身是不是连续整数。如果是自增ID、序号、编码这类本身就在一个可控范围内的整数而且域范围不大空间能接受那就无脑用位图。它的实现简单没有误判内存极其可控。第二步如果元素是字符串、URL、UUID这些不连续对象或者域范围大到不可控就别硬做映射了直接用布隆过滤器。虽然在哈希到布隆过滤器时依然可能碰撞但至少你不需要维护一张巨大的“业务ID到序号”映射表。第三步如果既要大容量精确判存又不想维护映射表可以用布隆过滤器做前置快速排除命中后再去精确存储里查一次。这个组合能兼顾准确性和内存。这里必须提醒一个容易被忽略的问题位图的存储是固定成本跟你实际塞了多少真实元素没关系。哪怕只有1万个用户只要域是1亿位图就要占1亿bit。布隆过滤器的存储则和预估元素量n强相关。如果你把n估小了实际塞进去的元素比预估多10倍误判率会急剧恶化甚至恶化到你无法容忍的地步。4.3 二者能不能叠着用能而且叠着用的场景很多。有个典型组合是双层结构外层布隆过滤器负责挡住绝对不存在的key内层位图负责精确判断高频连续ID是否存在。比如在防缓存穿透系统里先用布隆过滤器处理字符串类key命中后再到后端的连续ID序列里用位图做精确过滤。这样既不需要为所有字符串key维护一套巨大映射表又能让高频整数判断保持零误判。另一个组合是“快速排除”加“精确确认”。布隆过滤器先过滤掉绝大多数的“不存在”剩下的少量“可能存在”再去精确索引里做最终确认。网盘秒传、图片去重、消息幂等里都能用这个思路。组合的本质是布隆过滤器过滤掉绝大多数噪音精确结构处理剩下的少数。内存和CPU的账算下来往往比单一方案更划算。5. 实操两个可以直接抄作业的例子5.1 案例1000万用户ID判断是否领取过活动奖励用位图先看一个最常见的位图场景。假设系统有1000万用户ID是从1到1000万左右的整数。要判断每个用户是否已经领取过新人礼包领过打标没领过就不能重复领。这个场景用Redis BITMAP非常合适直接把用户ID当作offset用户领奖后把对应位置置1。先用Lua脚本保证判断和置位是原子的防止并发重复领取-- KEYS[1] 为位图key -- KEYS[2] 为用户ID -- 返回值 0 表示本次可以领取1 表示已经领取过 if redis.call(getbit, KEYS[1], KEYS[2]) 1 then return 0 end redis.call(setbit, KEYS[1], KEYS[2], 1) return 1这段脚本的意思是先查用户ID这一位是不是1如果已经是1说明领过了返回0拒绝否则把这一位置为1返回1表示本次领取成功。整个判断和置位在Redis里是原子操作不会出现两个人同时抢到一个可领取名额。如果用Java客户端大概长这样String key activity:newbie:reward; Long userId 10800001L; boolean hasClaimed jedis.getbit(key, userId); if (!hasClaimed) { // 实际项目中建议用上面的Lua脚本 jedis.setbit(key, userId, true); // 发放奖励 }但这个写法有个并发问题先getbit再setbit不是原子操作两个请求同时进来可能都看到0于是都去发奖。所以线上我强烈推荐用Lua。内存账本1000万用户1000万个bit约1.19MB。放Redis里毫无压力。在这个场景里用位图明显优于用Set或者数据库表。Set需要存1000万个用户ID至少几十MB数据库表还要维护索引写放大。还要提醒一个业务细节如果把“置位”和“发奖”分开做置位成功但发奖失败用户会永久失去领取机会。所以要么发奖和置位放在同一个事务里要么置位后异步发奖并且给发奖失败提供补偿机制。5.2 案例1亿个URL去重用布隆过滤器再来看一个布隆过滤器场景。爬虫系统要判断一个URL是不是已经抓取过了。URL是字符串长短不一精确存HashMap内存受不了于是用布隆过滤器做前置去重。预估未来总URL数量为1亿目标误判率控制在1%以内。根据3.2节的计算m约9.58亿bit约114MBk约7。用Guava实现的话代码很短import 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), 100_000_000, 0.01); // 爬取前判断 boolean mightBeCrawled filter.mightContain(url); if (!mightBeCrawled) { // 没爬过去抓取 filter.put(url); }如果你看过Guava源码会发现它在底层不是真的生成7个完全独立的哈希函数而是用双哈希法组合出7个位置这样既保证分布均匀又减少计算量。要注意一点Guava的BloomFilter是进程内的对象。如果系统部署在多个实例每个实例有独立的布隆过滤器会出现“这台机器判定没爬过另一台机器已经在爬”的情况。要全集群共享判存要么用Redis Stack的BF.RESERVE、BF.ADD、BF.EXISTS命令要么自己用一个分布式位数组保存布隆状态。这个在多实例部署时特别容易踩坑。5.3 参数计算为什么这个位数组长度最合适新手最容易跳过参数计算直接调库。我给你手写一遍完整过程。已知n等于1亿p等于0.01。先算mm -100000000 * ln(0.01) / (ln2)^2ln(0.01)约等于 -4.605170ln2约等于0.693147平方约0.480453。代入后m 100000000 * 4.605170 / 0.480453 m ≈ 958505161 bit除以8约119813145字节约114.3MB。再算kk (958505161 / 100000000) * 0.693147 k ≈ 6.64取整数7。回代验证误判率p ≈ (1 - e^(-7 * 100000000 / 958505161))^7 p ≈ (1 - e^(-0.7303))^7 p ≈ (1 - 0.4817)^7 p ≈ 0.5183^7 p ≈ 0.0098约0.98%满足1%的目标。下面这张表是常见配置的速查可以直接抄预估元素数 n目标误判率 p位数组大小 m内存约最优哈希数 k1亿10%4.79亿bit57.1MB41亿1%9.59亿bit114.3MB71亿0.1%14.38亿bit171.6MB1010亿1%95.85亿bit1.12GB7注意k不是越大越好。位数组长度为m插入n个元素后某个bit位上是1的概率约等于 1 - e^(-kn/m)。k太大位数组里的1会越来越多最后所有位置都可能变成1误判率反而反弹。所以一定要围绕最优k值附近取整而不是随手设一个“感觉很大的数”。5.4 如果不想用依赖库自己写一个简版布隆过滤器理解原理最快的方式是自己花几分钟写一个玩具版。Python代码非常短核心就是位数组加哈希函数。import math import mmh3 class BloomFilter: def __init__(self, n, p): self.m int(-n * math.log(p) / (math.log(2) ** 2)) self.k int((self.m / n) * math.log(2)) self.bits bytearray(self.m // 8 1) def _positions(self, item): return [ (mmh3.hash(item, seed) 0xFFFFFFFF) % self.m for seed in range(self.k) ] def put(self, item): for pos in self._positions(item): self.bits[pos // 8] | 1 (pos % 8) def might_contain(self, item): return all( self.bits[pos // 8] (1 (pos % 8)) for pos in self._positions(item) )这个实现有几个细节要说明。第一mmh3.hash返回的是32位有符号整数会出现负值所以要做一次 0xFFFFFFFF保证结果落在0到2的32次方减1之间。第二这里用不同的seed生成k个独立的哈希简单直观但计算量偏高。真正工程实现里常用双哈希法先算出两个基础哈希h1和h2然后通过h1 i * h2的方式派生第i个位置这样性能更好。第三bytearray的长度是m // 8 1多一个字节无伤大雅但要保证取模时不会越界。如果你拿这个玩具代码上生产还是建议换成熟库。6. 工程中的坑与排查实录6.1 位图稀疏导致空间失控第一个大坑是位图看着省内存但遇上稀疏数据就会失控。比如用户ID是雪花算法生成的长整型最大值可能到2的63次方。你直接把ID当Redis的offset用SETBIT一个bitRedis底层字符串就要扩容到offset除以8的字节数。一个10的18次方级别的ID一个bit下去字符串可能扩展到一百多TB直接报内存错误。这不是夸张是真实会发生的事。所以用位图之前先确认你的ID最大值。要么用自增ID要么先做一次“密集化映射”把已存在的用户ID排序后映射成连续序号。Redis BITMAP听话的前提是offset不能太离谱。6.2 布隆过滤器误判引发的业务问题布隆过滤器的误判属于“设计内概率”不是bug但业务通常不会容忍假阳性。我见过一个线上事故团队用布隆过滤器判断“用户是否有过购买行为”返回false就不发优惠券。结果因为误判极少数没买过东西的用户被漏判出现了投诉。排查下来发现这不是代码问题而是选型问题。布隆过滤器只适合“漏掉几个不存在的请求无所谓”的场景。如果漏掉一个真实用户就是事故那必须给误判兜底。以缓存穿透为例正确做法是布隆过滤器返回“可能存在”后如果缓存和数据库里查不到也要正常返回“无数据”给前端不能因为布隆过滤器说有就固执地认为一定有。因为那极小概率是假阳性。一个严谨系统必须在精确查询后接受“布隆过滤器也可能错”的事实。6.3 哈希函数与误判率的关系哈希函数的质量直接影响误判率。如果两个哈希函数之间线性相关相当于你只用了少于k个的独立哈希位数组中的点更容易重叠误判率会上升。工程上推荐用MurmurHash、xxHash这类非加密哈希速度快、分布均匀。MD5、SHA-1虽然更随机但速度慢在布隆过滤器这种需要反复哈希的场景里不划算。另外要注意“双哈希法”的正确姿势。用h1加i乘h2派生第i个位置时如果h2在某个数值上退化成0所有派生位置都等于h1那k就失效了。所以实际项目里要么选用成熟库要么随机验证一下种子的分布。6.4 排查工具与调优经验排查布隆过滤器问题时先看三个指标当前插入数量、位数组长度、实测误判率。如果实测误判率远高于设计值第一怀疑对象是n预估不足。比如按1亿设计的实际插入了3亿误判率会从1%涨到40%以上这种恶化速度非常可怕。所以要给n留出余量高峰期的量也一并算进去。第二怀疑对象是哈希函数的实现是否真的独立。如果多个哈希函数用的是同一个随机种子退化出来的误判率也会不正常。第三是位数组是否被多个过滤器共用。有些团队图省事在一个位数组里塞多个业务的数据结果互相污染。发现之后要立刻拆开。调优时建议做一次实测。用随机样本不断插入再用另一批从未插入过的样本去查询统计被误判的比例。这个实测值比公式更直观也更接近线上真实情况。如果误判率可以接受就继续沿用不能接受就调低p重新算一遍m和k。不要靠感觉调参一定要回到公式上去算。7. 写在最后我的一点工程习惯做了这么多年数据判存相关的事我自己的习惯是每次拿到“判断某个东西存不存在”的需求先问自己三个问题。第一允不允许有误判哪怕是0.1%的概率。第二这个元素是整数还是字符串域大概多大。第三是需要全集群共享判存还是单机够用。第一个问题决定能不能用布隆过滤器。第二个问题决定该用位图还是布隆过滤器。第三个问题决定用Redis还是进程内库。三个问题想清楚选型就顺了。参数方面布隆过滤器永远先按峰值预估算一遍再留出至少20%的余量不要刚刚好卡着容量设计。位图也一样先确认ID最大值和分布密度别让偏移量失控。判存问题看起来简单但真正决定上限的从来不是某个数据结构而是你对“误判”和“内存”这两个词有多敏感。
