1. 位图核心思想：把“数据本身”丢掉，只留“存在与否”

很多朋友第一次接触位图（Bitset）时，脑子里冒出来的问题是：这玩意儿不就是个数组吗？无非是把数组里的每个元素从int换成了boolean，有什么好讲的？如果你也这样想，那就错过了位图真正值钱的地方。它不是在“省一个字节”，而是把数据结构的整个存储维度都换了。

1.1 从生活例子理解位图的“位置即数据”逻辑

想象一下你开了一家电影院，一共有 1000 个座位，你想快速知道某个座位有没有人。最笨的办法是拿个本子，每卖出一张票就写一行：“3排7座，张三”。查的时候翻本子，翻半天。聪明一点的办法是拿一张座位图，在 3排7座 那个格子上画个勾，查的时候直接看那个格子就行了。

位图就是这个“座位图”，而且它比“画勾的格子纸”更极端——每个格子只占 1 个 bit，也就是二进制的一位。0 表示“没人”，1 表示“有人”。你不需要记录任何人的名字，你只需要知道“有没有人”。大多数业务场景里，我们想查的恰恰就是这个“有没有”。

这里的核心思维转变是：下标即数据，bit 即状态。传统的数组或集合，存的是“数据本身”，比如HashSet<Integer>里存的是整数 42 这个具体的值。位图反过来，它把整数 42 当成“第 42 个位置”，然后在这个位置上放 0 或 1。你要判断 42 存不存在，不需要遍历，不需要哈希计算，直接看第 42 个 bit 是 0 还是 1。

这个逻辑听起来简单，但实际工程里很多人栽就栽在没转过弯来。有位同事问我：为什么我用HashMap<Integer, Boolean>也能实现同样的功能？完全可以，但你算一笔账就明白了：一个HashMap里的每个键值对，光 Java 对象的头就有十六字节，再加上哈希表的桶、指针、扩容余量，存 1 亿个数差不多要吃掉几个 GB 的内存。而位图存 1 亿个状态，只要 12.5 MB。

1.2 为什么位图能省这么多空间：一次具体计算

我习惯用具体数字来说话。假设你要判断 10 亿个不重复的整数（32 位无符号）中，某个数是否存在。

• 用HashSet<Integer>：每个Integer在 64 位 JVM 上，对象头 16 字节 + 4 字节 int 值 + 对齐填充，至少 24 字节；再加上HashMap节点（约 32 字节）和哈希表负载因子导致的空桶，摊下来每个元素实际占用 50 字节以上。10 亿个，就是 50 亿字节，差不多 5 GB 内存。很多服务器根本扛不住。
• 用位图：我们需要的 bit 总数等于数值范围。如果是 32 位整数全部覆盖，需要 2^32 个 bit，也就是 2^32 / 8 = 512 MB。如果你只需要覆盖 10 亿以内的数，那么 10 亿 bit = 125 MB 左右。

更极端一点，很多业务场景里的 ID 是通过自增主键产生的，一个亿级用户平台，用户 ID 大概在几千万到几亿这个量级。此时用位图管理所有用户的状态，内存开销是：最大 ID 数目除以 8 字节。一亿用户，12.5 MB。这个数字小到可以在服务端随便开好几份。对比一下，任何基于对象的容器在这个量级下都不可能做到这个体积。

这里还有一层“为什么”值得展开：哈希表存数据要同时存“键”和“值”，而且哈希冲突时要额外存储指针维持链表或红黑树结构；堆上的对象还有对齐填充。位图的结构本质上是一个连续内存数组，没有任何元信息开销，它就是“裸”的内存块。所以它不是“比哈希表优化了一点点”，而是把常数因子从几十降到了 1。

1.3 位操作的温度：set、get、clear 背后的位运算

理解了“位置即数据”，下一步就得能动手操作。位图底层通常是个long[]数组（Java 里）或std::bitset（C++ 里），一次操作一个 64 位长的字。

对一个整数n，你想把它所在的位置置为 1，核心代码其实就是三行：

int wordIndex = n >> 6; // n / 64，找到落在哪个 long 字里 int bitIndex = n & 63; // n % 64，找到在这个字里的第几位 words[wordIndex] |= (1L << bitIndex); // 把这一位置 1

判断是否存在更简单：

return (words[n >> 6] & (1L << (n & 63))) != 0;

很多初学者会对n >> 6和n & 63感到别扭，其实它们就是整除和取模的位运算写法，因为 64 是 2 的幂，编译器会把除以 64 优化成右移 6 位，把模 64 优化成与 63。这个套路在你手工实现位图时会反复出现，务必背下来。

说到这我想起一个真实的线上事故。某个服务用位图存用户的“已读状态”，结果测试环境一切正常，一上生产就数组越界。查了半天发现，测试数据里的用户 ID 都是从 1 开始连续递增，而生产环境接入了某个老系统的 ID，直接从 5 亿开始。位图的数组长度取决于你创建时给定的 range，一旦访问超出 range 的位置就会越界。这不是位图本身的问题，是你设计时没考虑清楚范围上界的问题。

2. 三个最能体现位图价值的高频场景

位图不是什么万金油，它是“存在性判断 + 大数据集合操作”这个窄赛道里的王者。我整理了一下，下面三个场景是我在真实项目和面试题里见的最多的，也是你学了立刻能用的。

2.1 场景一：亿级数据的存在性查询与去重

先看一个经典面试题：给 40 亿个不重复的无符号整数，没排过序。现在给你一个数，如何快速判断它是否在这 40 亿个数中。限制条件很苛刻，内存只有 1 GB 左右。

很多人第一反应是排序 + 二分，但 40 亿个 int 排序后的数组也占 16 GB，内存直接爆掉。换成位图：2^32 个 bit 就是 512 MB，完全装得下。把 40 亿个数全部写入位图，然后对目标数做一次 O(1) 的查询。整个流程的时间复杂度：建图 O(n)，查询 O(1)。

这是我个人非常喜欢的一道题，因为它直白地展示了位图“用空间换时间”的另一种形态——这里的“空间”反而是被压缩的。哈希表在同样场景下连数据都装不下，位图却轻松搞定。你把这道题吃透了，以后遇到任何“海量数据 + 快速判断是否存在”的需求，第一反应就应该是位图。

实际业务中，这个场景最常见的形态是“白名单/黑名单”。比如你要判断 IP 是否命中某个恶意库，或者判断某个手机号是否是注册用户。这类判断请求量很大，用数据库查询扛不住，用哈希集合内存又太大，位图就是那个“既能扛住高并发、又不会把服务器内存打爆”的方案。

2.2 场景二：统计活跃度与集合运算

位图还有一个很容易被忽略的强项：集合运算。因为它本质上就是一堆 bit，所以“交集”“并集”“差集”直接对应位运算AND、OR、AND NOT。一台 64 位的 CPU 一次就能处理 64 个元素的集合运算，1 亿个元素的集合求交集，循环一百多万次而已，耗时在毫秒级。

举个例子，运营要查“过去 7 天里，既看过 A 视频、又点过 B 视频的活跃用户有哪些”。如果每个用户的活跃记录都放在数据库里，这个查询要 JOIN 两张巨大的表，跑一次可能要几十秒。但如果每天维护一个“当日活跃用户位图”，那这个需求就是一个AND操作：把 7 张位图按日期 AND 一下，扫一遍就出结果。

你可能会问：这难道不是把数据库的活搬到内存里做？对，就是因为数据库的 JOIN 代价太高，位图才值得被拿出来做这样的事。Redis 里的SETBIT/BITOP命令可以干完全相同的事，很多大数据平台也内置了位图索引来加速多维组合查询。只要你把“日期”和“用户 ID”这两个维度对齐，位图的集合运算就是开挂级的表现。

另一个常见用法是“用户留存率”。某天新增用户做一张位图，第二天的活跃用户做一张位图，两者AND之后再统计 1 的个数，就是次日留存。统计 1 的个数在 Java 里就是cardinality()，在 C++ 里可以用std::bitset::count()，底层通常都用了 CPU 指令级优化，速度极快。

2.3 场景三：位图与布隆过滤器的关系与边界

提到位图，几乎一定会有人提到布隆过滤器（Bloom Filter）。这里要理清一个关系：布隆过滤器是一个“基于位图”的扩展结构，它解决的是位图的一个天然软肋——当数据范围很大但实际元素很少时，位图空间浪费严重；以及当元素本身不是可用作下标的整数时（比如字符串 URL），没法直接映射。

布隆过滤器的做法是：用 k 个哈希函数把同一个元素映射到位图的 k 个不同位置，全部置 1。查询时再看这 k 个位置是否全部为 1，如果是，判断“可能存在”；只要有一个为 0，就判断“一定不存在”。代价是它有一定的误判率（false positive），但绝不会漏判。

这里的关键选型建议是：如果数据本身就是紧凑的整数 ID，直接用位图，精确、无误差；如果数据是字符串、URL、任意字节串，或者数值范围巨大但元素稀疏，那就用布隆过滤器。很多新手搞反了，拿布隆过滤器去处理整数 ID，纯属多绕了一圈还引入误判。记住这句话：布隆过滤器解决的是“不可索引”和“稀疏大范围”的问题，它不是位图的替代品，而是位图思想的延伸。

3. 落地实操：Java BitSet 内存 API 演示与内存对比

前面讲了一堆理念，这章我直接带你跑一遍代码。我以 Java 为例，因为它的BitSet类使用最广泛，而且很多读者学这个是为了应对后端开发或算法面试。C++ 的std::bitset以及 Python 的int位运算和bitarray库，后面会单独提一下行为差异。

3.1 Java BitSet 核心 API 速览

Java 的java.util.BitSet用起来非常直观。我最常用的方法有这么几个：

• set(int index)：把第 index 位置 1；
• set(int fromIndex, int toIndex)：把 [fromIndex, toIndex) 区间全部置 1，适合批量处理连续段；
• get(int index)：查询第 index 位是否为 1；
• clear(int index)：把第 index 位置 0；
• cardinality()：返回置 1 的位数，也就是集合大小；
• nextSetBit(int fromIndex)：从 fromIndex 开始找下一个 1，返回下标，找不到返回 -1；
• and(BitSet set)、or(BitSet set)、xor(BitSet set)：集合运算。

有一个细节容易踩坑：BitSet的size()返回的是底层long[]数组的长度乘以 64，表示“底层空间能容纳多少位”；而length()返回的是最高置 1 位的下标加 1。比如你new BitSet(1000)，但只 set 了第 10 位，那size()可能是 1024（因为内部会按 64 对齐分配字），而length()是 11。查“位图占了多少内存”时，应该看size()而不是length()。

另外，遍历位图时千万别写for (int i = 0; i < bitSet.size(); i++) { if (bitSet.get(i)) ... }这种循环。如果位图覆盖范围是几十亿位，你的查询又只分布在几个点上，这种遍历会白白跑几十亿次get()。正确做法是用nextSetBit：

for (int i = bitSet.nextSetBit(0); i >= 0; i = bitSet.nextSetBit(i + 1)) { // 只处理置 1 的位置 }

这个差别在小数据量下看不出来，到亿级数据就是毫秒和秒级的差距。我在压测里实测过：同样遍历 1 亿个 bit，get()循环大约耗时 400 毫秒，nextSetBit如果只有几万个 1，耗时不到 1 毫秒。差距三百倍以上。

3.2 完整示例：用位图管理一亿用户的注册状态

这里我写一个完整的小案例。假设我们有个电商平台，用户 ID 最多到 99999999（1 亿以内），需要快速判断任意用户是否已注册。

public class UserRegistry { // 最大用户 ID + 1，创建位图时明确给定范围，避免扩容开销 private static final int MAX_USER_ID = 100_000_000; private final BitSet registered = new BitSet(MAX_USER_ID); public void register(int userId) { checkRange(userId); registered.set(userId); } public boolean isRegistered(int userId) { checkRange(userId); return registered.get(userId); } public int totalRegistered() { return registered.cardinality(); } private void checkRange(int userId) { if (userId < 0 || userId >= MAX_USER_ID) { throw new IllegalArgumentException("userId out of range: " + userId); } } public static void main(String[] args) { UserRegistry registry = new UserRegistry(); registry.register(42); registry.register(88888888); System.out.println(registry.isRegistered(42)); // true System.out.println(registry.isRegistered(43)); // false System.out.println(registry.totalRegistered()); // 2 } }

注意我在创建BitSet时就指定了容量，因为BitSet默认初始大小是 64 位，每次set()超过当前容量会自动扩容，扩容涉及整个底层数组的复制。如果你明确知道上界，一次性给足容量，后面的set()就不会有扩容的复制开销。这一点在数据量大时特别明显，我测过连续插入 5000 万条时，提前指定容量能省掉大约 20% 到 30% 的时间。

运行这个程序后，内存占用大可以简单估算：1 亿个 bit 约 12.5 MB。作为对比，用HashSet<Integer>存 5000 万注册用户，实测大概要吃 2 GB 以上。我把两种方案放在一起对比：

这张表每次讲给团队听，大家都会重新思考一下“用户状态到底存哪里”。不是说什么都用位图，而是这类“存在性判断”的业务，位图往往是最优解，你就别再扛着HashSet硬上了。

3.3 手写一个最简位图：看底层那几行代码

读源码不如自己写一遍。我用long[]手写一个极简版位图，去掉所有花哨的 API，只保留核心逻辑，帮你看清楚位图到底是怎么运转的：

public class SimpleBitSet { private final long[] words; public SimpleBitSet(int capacity) { // 每个 long 有 64 位，向上取整的除法 this.words = new long[(capacity + 63) >> 6]; } public void set(int index) { words[index >> 6] |= (1L << (index & 63)); } public boolean get(int index) { return (words[index >> 6] & (1L << (index & 63))) != 0; } public void clear(int index) { words[index >> 6] &= ~(1L << (index & 63)); } public int cardinality() { int count = 0; for (long word : words) { count += Long.bitCount(word); } return count; } }

Long.bitCount()底层会用到 CPU 的POPCNT指令，一次能数完 64 位里有几个 1，比一位一位遍历快太多了。手写这个类的最大意义是你能真切感受到，位图不是魔法，它就是数组加位运算。理解了这三行，以后看任何语言的 bitset 实现，你都不会发怵。

4. 位图上生产后容易踩的坑，以及改良方向

前面说的都是位图怎么用、怎么省内存，但这东西真要上生产环境，坑也不少。我踩过的或是在代码评审里见过的，挑几个最有代表性的说说。

4.1 稀疏数据：位图最大的敌人

位图的致命弱点是：空间由“值域范围”决定，而不是由“元素个数”决定。如果你要标记的数字是从 0 到 10 亿的范围内随机分布的 100 个点，位图照样需要 125 MB。而如果换成HashSet，存 100 个整数只要几 KB。这种场景下，位图就是灾难。

我在一个推荐系统项目里见过真实案例：团队用位图存“用户已读的 feed 消息 ID”，结果消息 ID 是全局递增的雪花号，量级到 2^63。为了覆盖所有可能的 ID，他们创建了一个超大位图，内存直接打爆。后来换成了采用分段处理（低 32 位 + 高 32 位分桶）的改进方案才解决。

如果你遇到类似的复杂场景，业界有成熟方案：Roaring Bitmap。它的核心思路是把 32 位整数拆成高 16 位和低 16 位，按高 16 位分桶，每个桶内根据元素密度选择容器类型：稀疏时用short数组，稠密时用位图。它有一个内部策略，通常是桶内元素数超过 4096 就切换成位图，否则保留数组。这样无论数据是密集还是稀疏，都能控制在相对较小的内存里。Java 里可以直接用org.roaringbitmap.RoaringBitmap，性能比java.util.BitSet在某些场景下还要好，因为它做了剪枝和压缩。

4.2 并发安全与扩容问题

java.util.BitSet不是线程安全的，底层long[]的读写和修改操作没有加锁。多线程同时set()同一个位图，轻则覆盖丢数据，重则数组越界（扩容过程中另一个线程读）。我建议的解法有两种：

• 读取为主、写入集中的场景，用一个synchronized包一层，或者用ReentrantReadWriteLock，因为位图的读操作不会修改结构，可并发读；
• 写多读少的高压场景，优先考虑用无锁实现或直接让每个线程持有一份独立位图，最后再or()合并。最后合并的操作天然就是并行的，这种设计反而更干净。

还有一个很多人不知道的问题：位图的序列化。如果你要把位图存到 Redis 或传给下游服务，注意不要直接 JDK 序列化BitSet对象，那会带上类描述信息，白白多占几倍体积。正确做法是toLongArray()拿到long[]，对long[]做压缩或者直接按字节流传输；读出时再用valueOf(long[])还原。我见过因为序列化方式不对，12 MB 的位图存到 Redis 里变成 50 MB 的案例。

4.3 生产环境改良：Roaring Bitmap 与其他选择

上面提到了 Roaring Bitmap，我再说几个值得关注的使用经验。

首先，Roaring Bitmap 最适合的领域是“索引”和“标签体系”。比如你在做用户画像，每个用户身上挂了若干个标签，每个标签单独一张 RoaringBitmap 存用户 ID，标签之间的组合筛选就是多个 bitmap 的and/or运算。这个模式在很多公司的大数据架构里都有落地，比传统的倒排索引省内存且更快。

其次，不同语言里的 bitset 行为差异很大。C++ 的std::bitset<N>必须在编译期确定大小，运行时动态大小的可以用boost::dynamic_bitset或std::vector<bool>。但std::vector<bool>是个出了名的坑货，因为它内部做了位压缩，导致bool&引用返回的不是真正的引用而是代理对象，模板泛型代码里很容易踩雷。Java 的BitSet没有boolean数组这种问题，API 也更顺手。Python 里如果你不想装第三方库，直接用整数类型做位运算也能模拟位图——Python 的 int 是无限位宽的，左移一位等于 set 一个位置，但也意味着单次操作的常数因子很大，数据量大了不划算。

如果你是做 Go 的，标准库没有内置位图，一般用github.com/willf/bitset或者github.com/RoaringBitmap/roaring。Go 的uint64切片实现位图思路和 Java 完全一样，只是 API 风格不同，核心思想完全通用。

我想强调一个选型原则：如果你的数据是紧凑的整数 ID，且值域范围已知、密集程度够高，直接用最朴素的 bitset；如果值域巨大且数据稀疏，用 RoaringBitmap；如果数据是非整数类型，再考虑布隆过滤器。千万别一上来就上最复杂的方案，很多时候简单位图 + 一个long[]就够用了。

说到底，位图是个“思路”而非“库”。我见过一个老项目，没有引入任何位图工具库，就在业务代码里用byte[]加几行位运算，照样把亿级用户状态的判断优化到了极致。位图的美妙之处就在于，一旦你接受了“下标即数据”这个视角，你在任何语言、任何场景下都会自然地想到它。希望大家读完这篇，不只是记住 API，而是把这种“用空间形态换查询速度”的思维带进日常的架构设计里。下次再遇到大数据集合判断的需求，先别急着上数据库或 Redis，花五分钟算一下位图的内存和耗时，说不定你会得到远超预期的结果。