位图 vs 布隆过滤器：海量数据存在性判断的工程选型指南

如果你接到一个需求：在一批少则千万、多则上亿的数据里，快速判断一个元素到底存不存在。很多人的第一反应是“搞个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个bit，N除以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直接SETBIT，Redis会自动把字符串扩容到接近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.480，m约等于9.58亿bit，换算成内存约114MB。接着算k，k等于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 bit，m和预估元素量、目标误判率挂钩。元素量预估越准，空间越好控制。

第四是删除能力。位图支持删除，把对应位直接清零就行。布隆过滤器标准版不支持删除。

下面这张表是我项目里常用的快速参考，方便直接照着选。

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，约114MB，k约7。

用Guava实现的话，代码很短：

import com.google.common.hash.BloomFilter; import com.google.common.hash.Funnels; import java.nio.charset.StandardCharsets; BloomFilter<String> 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。

先算m：

m = -100000000 * ln(0.01) / (ln2)^2

ln(0.01)约等于 -4.605170，ln2约等于0.693147，平方约0.480453。代入后：

m = 100000000 * 4.605170 / 0.480453 m ≈ 958505161 bit

除以8约119813145字节，约114.3MB。

再算k：

k = (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%的目标。

下面这张表是常见配置的速查，可以直接抄：

注意，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一个bit，Redis底层字符串就要扩容到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最大值和分布密度，别让偏移量失控。

判存问题看起来简单，但真正决定上限的从来不是某个数据结构，而是你对“误判”和“内存”这两个词有多敏感。