搜过“位图”这个关键词的人多半是被两件事逼来的要么是程序内存告急想找个极致节省的方案要么是笔试面试遇到一道“手写位图”的题。我属于前者。当时要在一批几十亿规模的用户ID里做去重和存在性判断SetInteger的内存估算出来让人头皮发麻这才认真把模拟实现位图这件事从头到尾做了一遍。位图的原理一句话能讲完用1个bit记录一个对象的状态bit为1表示成立、为0表示不成立。但动手实现时光“定位到第几个long的第几位”就能埋下一堆坑更别说容量对齐、类型移位、多余位掩码这些细节。这篇文章把完整过程写出来先从一笔内存账讲起再落到选址位运算给一个可以直接用的Java实现然后聊可视化调试、页分配器里的“位图安装”最后总结手写过程中最容易翻车的三个细节。适合两类人一类是正在啃“java中的位图”相关源码的开发者另一类是想给海量数据做状态标记但内存吃紧的工程师。1. 位图到底解决什么问题先算一笔内存账1.1 一个能让你直观感受到差距的场景10亿数字去重假设有这样一个需求有一批ID取值范围在0到10亿之间可能有重复需要快速判断某个ID是否出现过还要对这批ID做去重。最朴素的做法是HashSetInteger。问题是Java里一个Integer对象本身就要占16字节默认压缩指针下再加上HashMap.Entry的引用、哈希桶数组、扩容预留空间摊下来一个元素差不多要30~40字节。10亿个不重复的ID内存轻松超过30GB大多数服务器直接撑不住。换成数组呢boolean[]在HotSpot里一个元素占1字节10亿个也要1GB还要再加上数组对象头。好一点但依然不理想。位图方案怎么算前提是数据本身是紧凑的整数比如范围明确是0到10亿。我开一个long[]每个long有64个bit每64个ID共用1个long需要的数组长度是10亿除以64总内存约125MB。125MB对30GB差了几百倍。而且位图的访问复杂度是O(1)——定位到一个bit只需要两次位运算不需要哈希、不需要比较、不需要解决冲突。这里可以打一个生活化的比方。HashSet相当于给每个要找的车牌都建一个独立登记柜柜子越多越占地方位图相当于一张巨长的车位表一张表上的每个格子代表一个车位有车就涂黑没车就留白。所有状态都压缩在表格本身里几乎没有额外开销。1.2 位图能做什么不能做什么位图不是万能的它只适合回答“是或否”这一类问题。我把它能做到和不能做到的事情列清楚。能做到的大规模整数/ID的“是否存在”判定这是性价比最高的用法。状态标记在线/离线、已读/未读、空闲/占用。操作系统页分配器、资源块分配与回收状态管理。作为布隆过滤器的底层存储结构。不能做到的不能计数。想知道某个ID出现过几次、某个页被引用过多少次1个bit的信息量不够。不能存储关联值。除了0/1之外还想带个名字、时间戳位图一概存不下。对稀疏的大范围不友好。假如只在0和10亿两个位置各set一次位图照样会占满10亿/8字节等于浪费。空间无法随数据量自动回收。你只能把某个bit清0但数组长度是固定的不能因为数据变少而压缩。很多人把位图当通用存储结构用结果发现存不了复杂信息就开始吐槽。其实只要明确“它只负责状态”选型就很简单状态问题是位图的天下计数和复杂对象交给别的结构。2. 选址与落位手工位图背后的两段位运算2.1 两次定位先找long再找bit实现位图的第一个核心问题是整数N对应底层数组的什么位置。我用long[] words作为存储。一个long有64个bit定位过程分两步。第一步N除以64得到数组下标wordsIdx N / 64第二步N对64取余得到long内部的bit位置bitOffset N % 64比如N0到63落在words[0]N64到127落在words[1]。因为64是2的6次方除法和取余可以改写为位运算前提是N不是负数wordsIdx N 6; bitOffset N 63;N 6等价于N / 64N 63等价于N % 64。这一步不完全是为了炫技在千万级以上的循环里少几次除法指令还是有可见收益的。定位完成后剩下就是三个基础操作这是整套实现的三把钥匙操作表达式置1words[N 6]清0words[N 6] ~(1L (N 63))判断(words[N 6] (1L (N 63))) ! 0这里有个极容易踩的坑表达式里的1L。很多人写成1 bitOffset当bitOffset取到63时1是int类型只有32位Java对int移位只取低5位作为移动距离于是1 63实际变成1 31符号位直接错乱。必须写成1L让移位发生在64位的long上63才不会被截断。2.2 为什么用long[]而不是byte[]或int[]从逻辑上讲byte[]也能实现位图8个bit一个元素定位公式变成N/8、N%8看起来更简单。但实际工程里我强烈建议用long[]原因有三个。第一是访问粒度。位图的高频操作是批量遍历和随机读写long[]每次可以处理64bitbyte[]每次只能处理8bit。同样一个循环long[]命中的数组元素更少CPU缓存的局部性更好吞吐量明显更高。第二是无符号处理。Java的byte是带符号的取值范围-128到127单个字节的最高位是符号位。想无符号地操作某一位总要做 0xFF之类的转换非常烦。long虽然也是带符号类型但位运算完全不看符号位只要不把long当数值去比较大小就没有任何问题。第三是统计方便。Java标准库提供Long.bitCount(long)直接用CPU或SWAR算法统计一个long里1的个数。如果底层是byte[]统计时要逐字节转换再做popcount慢且麻烦。结论就是能用64位容器就别用8位这不是个人偏好是效率和心智负担的双重考虑。3. 一个可以直接用的BitMap类完整代码与设计取舍3.1 核心API设计与实现细节我把完整实现贴出来代码不长但每行都要说清楚为什么这么写。import java.util.Arrays; public class BitMap { private final long[] words; private final int capacity; public BitMap(int capacity) { if (capacity 0) { throw new IllegalArgumentException(capacity must be 0); } this.capacity capacity; int wordCount (int) (((long) capacity 63) / 64); this.words new long[wordCount]; } public void set(int n) { checkRange(n); words[n 6] | 1L (n 63); } public void clear(int n) { checkRange(n); words[n 6] ~(1L (n 63)); } public boolean get(int n) { checkRange(n); return (words[n 6] (1L (n 63))) ! 0; } public long size() { long count 0; for (long w : words) { count Long.bitCount(w); } return count; } public void clearAll() { Arrays.fill(words, 0L); } public String toString() { StringBuilder sb new StringBuilder(capacity); for (int i 0; i capacity; i) { sb.append(get(i) ? 1 : 0); } return sb.toString(); } private void checkRange(int n) { if (n 0 || n capacity) { throw new IndexOutOfBoundsException(bit index out of range: n); } } }几个关键设计点。构造函数里wordCount的计算为什么写成((long) capacity 63) / 64因为capacity接近Integer.MAX_VALUE时直接用capacity 63会让int加法溢出成负数导致new long[负数]抛异常。先转long计算再转回int安全得多。为什么要加checkRange而不是让越界自然抛错位图的语义是“必须是预先定好的范围”一旦越界说明调用方逻辑有问题早暴露比晚暴露好。n 6对负数不是好事负数经过无符号右移会得到一个巨大的下标可能直接越界所以n 0必须单独拦截。set、clear、get三个方法的代码都很短本质就是两件事定位n 6和偏移n 63。如果面试被问到位图实现能背出这三行位运算并说清楚1L的意义基本就过了。这个类要不要做成自动扩容我建议不要。位图扩容的成本不只是复制数组还涉及新容量和旧数据边界的语义对齐容易导致误判“哪些位有效”。真实场景里页分配器、布隆过滤器都能提前确定最大规模一次分配到位最合适。如果你确实需要动态增长直接用Java标准库的BitSet不要自己造。3.2 统计已置位个数Long.bitCount的妙用size()方法最容易被写坏。有人会自己写循环数1的个数int cnt 0; while (w ! 0) { cnt w 1; w 1; }这个写法功能上没问题但效率低。JDK提供了Long.bitCount(long)底层是硬件popcnt指令或SWAR并行计数比逐位循环快一个量级。正确姿势就是遍历words数组对每个long调用Long.bitCount后累加。使用Long.bitCount时要注意一个隐含问题它统计的是整个long中所有1的个数如果最后一块long里含有超过capacity高位范围的1统计结果会偏大。在我这个实现里所有set都经过checkRange超范围的位永远不会被置1所以size()是准确的。但如果以后你改成批量填充或直接操作底层数组就必须考虑掩码问题这个第6章会专门讲。4. 把内部状态“画”出来调试可视化与基本验证4.1 从“电位图怎么画”说起位图同样需要画有人会搜“电位图怎么画”这个概念我不展开但它的核心思路和位图可视化完全一致把抽象的状态变成肉眼可见的东西。调试位图时直接看long的十进制数值是没用的你需要把每个long铺成64位二进制串来看。我给BitMap加一个toVisual()方法专门用来看内部状态public String toVisual() { StringBuilder sb new StringBuilder(); for (long w : words) { String bits Long.toBinaryString(w); while (bits.length() 64) { bits 0 bits; } sb.append([); for (int i 0; i 64; i 8) { if (i 0) { sb.append( ); } sb.append(bits, i, i 8); } sb.append(]); } return sb.toString(); }Long.toBinaryString(w)会把负数也输出成64位二进制串但如果是正数前面可能没有补零所以要先补足64位。输出效果类似[00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001]我写了一个简单验证BitMap bm new BitMap(200); bm.set(0); bm.set(63); bm.set(64); System.out.println(bm.toVisual());跑出来的结果里第0个long的最低位是1第0个long的最高位也是1第1个long的最低位是1。第一次看可能觉得奇怪明明set(0)和set(63)都是1为什么两个1隔那么远这就是bit位置在8位分组后的真实样子第0位在最右侧第63位在最左侧的分组里。用toVisual()排查问题时可以一眼看出是不是把1L写成了1。这里顺带说一下字节序。我按二进制串从左到右展示高位到低位所以第0位在右、第63位在左。如果你的需求正相反把输出顺序反转即可这不影响数据本身的正确性。4.2 验证与性能真实跑一次set和get继续用上面的对象做断言System.out.println(bm.get(0)); // true System.out.println(bm.get(1)); // false System.out.println(bm.get(63)); // true System.out.println(bm.get(64)); // true System.out.println(bm.size()); // 3capacity200需要4个long最后一块只有8个有效bit200减192。这个非64倍数的容量正好用来做边界测试后面第6章会继续展开。再做一个简单的性能测试不严谨但能说明量级long start System.nanoTime(); BitMap bm2 new BitMap(1 26); Random random new Random(42); for (int i 0; i 10_000_000; i) { bm2.set(random.nextInt(1 26)); } long end System.nanoTime(); System.out.println((end - start) / 1_000_000 ms);我本地环境跑下来大约60~100毫秒其中大部分还是Random.nextInt的开销。相比之下用HashSet插入一千万个Integer往往要2秒以上。位图在批量写场景里之所以快一是数组访问O(1)无哈希冲突二是大量随机set最终会集中在部分long上CPU cache命中率高。这个结果说明位图不只是省内存在固定范围内的海量状态标记任务里速度同样有优势。5. 位图在真实系统里的样子页分配器、BitSet与最终取舍5.1 页分配器里的“位图安装”是怎么操作的“页分配器与位图安装”这组词听起来很底层但其实正好是位图最经典的应用。操作系统把物理内存切成等大的页框比如4KB一个。要快速知道哪些页空闲、哪些页被占用直接给每个页框准备1个bit0表示空闲1表示已分配。所谓“安装位图”就是三步根据物理页总数P计算需要的long数量w (P 63) / 64。分配这段连续内存并全部清零所有页都标记为空闲。把已经被内核、启动代码占用的页对应的bit置1防止被别人分配走。之后分配页框时找第一个值为0的bit并置1释放页时把对应bit清0。如果每次分配都从0开始线性扫描效率太低。实际系统会配合“下一次搜索位置”的游标、空闲链表、伙伴系统等机制位图只负责“谁占用谁空闲”的状态存储真正的分配策略在位图之上。我用前面的BitMap写了一个极简页分配器public class SimplePageAllocator { private final BitMap used; private final int pageCount; private int hint; public SimplePageAllocator(int pageCount) { this.pageCount pageCount; this.used new BitMap(pageCount); } public int alloc() { for (int i hint; i pageCount; i) { if (!used.get(i)) { used.set(i); hint i 1; return i; } } for (int i 0; i hint; i) { if (!used.get(i)) { used.set(i); hint i 1; return i; } } return -1; } public void free(int page) { used.clear(page); } }注意hint这个字段。它记录上次分配到的位置下次分配优先从这里继续向后找找完一圈再回到0开头。在“顺序分配、顺序释放”的典型模式下分配一个页的平均时间复杂度接近O(1)。不要小看这个“游标环形扫描”的思路它就是从位图数据结构到实际分配器设计之间最重要的一层。以后你去看Linux内核的页分配器代码会发现里面不只是位图还叠加了更复杂的order分区和伙伴算法但当你看到类似 per-page state bitmap 的结构时就能自然联想到这里的逻辑了。5.2 Java内置BitSet和手写BitMap怎么选标题虽然是“模拟实现位图”还是要面对一个现实问题Java自带java.util.BitSet为什么还要手写我把两者的差异列成表格维度手写BitMapjava.util.BitSet动态扩容不支持固定容量自动扩容查找空闲位自己写循环内置nextClearBit(int)统计置位数自己遍历Long.bitCount内置cardinality()流式处理无内置stream()可遍历所有置位下标边界校验额外实现checkRange越界时自动扩容BitSet的底层也是long[]核心位运算和手写版完全一致。真实Java项目里如果只是需要一个可变的位集合直接用BitSet别重复造轮子。尤其nextClearBit这个API找第一个空闲bit的效率比手写循环要高做页分配器时非常顺手。那手写版本的价值在哪里我认为有两点。第一是学习价值。理解了选址位运算读源码、看底层结构都会轻松很多面试遇到手写题也不会慌因为你交付的就是一份80行的类加上一段“为什么要用1L而不是1”的解释。第二是定制价值。BitSet会自动扩容这在你明确希望“越界就是bug”的场景里反而不合适。手写版可以加capacity约束、加动作钩子、加“只统计合法范围”的语义这些封装是BitSet不会给你的。选型建议也很直接业务数据量只有几百万且内存充足用HashSet最省事数据量巨大且范围已知位图是正确选择数据量巨大但范围不确定考虑布隆过滤器它底层也是位图。这条决策链基本覆盖了日常大部分场景。6. 手写位图最容易翻车的三个细节6.1 移位与类型最典型的bug是这一行words[n 6] | 1 (n 63); // 错误写法n 63的范围是0到63但1是int类型Java对int移位只取低5位作为移动距离。所以当偏移是32到63时实际移位会被绕回0到31偏移63时1 63实际等于1 31变成一个符号位为1的负数int再和long做|运算结果完全错乱。清0操作同样会踩words[n 6] ~(1 (n 63)); // 错误写法如果有人跟我说“我明明set了但get一直返回false”我第一个会去看的就是代码里有没有漏掉L。这个坑排查起来最迷惑因为低32位的数据表现完全正常只有高位区间才出错。6.2 容量溢出构造函数里直接写(capacity 63) / 64当capacity接近Integer.MAX_VALUE时会溢出成负数。我这份代码用((long) capacity 63) / 64来规避。另一个边界是负数入参。n 6虽然是无符号右移但负数n经过右移后会得到一个很大的整数下标落到数组后面甚至越界。checkRange里必须单独判断n 0不能只判断上限。还有一个隐藏的溢出风险new long[wordCount]时如果wordCount太大数组本身也创建不出来。这属于物理内存限制不是代码逻辑问题但面试时主动提一句“这里还要考虑最大数组长度限制”会比闷头写代码好很多。6.3 最后一块long的多余bit当capacity不是64的倍数时最后一块long里只有capacity % 64个有效bit其余高位属于“无效区”。正常情况下set经过checkRange不会碰到这些无效位但在两类场景下会出现异常。第一类是优化写法。如果为了提高性能直接操作底层数组例如一次性写入多个连续bit时很容易把无效位置1。第二类是某些从别处迁移过来的位图数据原实现里高位本来就是脏的。这些脏bit会导致size()统计偏大遍历时多出一些“幽灵状态”。稳妥做法是在构造时记录最后一块的掩码int tailWords capacity 63; long tailMask; if (tailWords 0) { tailMask ~0L; } else { tailMask ~0L (64 - tailWords); }在做size()统计或遍历最后一块long时先 tailMask再操作。这个掩码处理是位图从玩具实现走向工程实现的分水岭。写完位图一定要用非64倍数容量跑一次边界测试比如capacity200set(199)后看统计结果是否正确再手动往最后一个数组元素的高位写入一个1看size()有没有异常变大。最后再唠叨一句实操建议把这份BitMap代码敲下来以后给它加上toVisual()在本地跑一跑。从0开始一直set到capacity-1看看最后一块long的展示效果再用200这种非64倍数验证一遍边界。网络上讲位图的帖子很多但“讲明白了”和“自己会长在脑子里”是两回事亲手敲过一遍以后遇到内存相关的性能问题你自然会先想到它。
Java手写位图：从内存账到完整实现与踩坑细节
搜过“位图”这个关键词的人多半是被两件事逼来的要么是程序内存告急想找个极致节省的方案要么是笔试面试遇到一道“手写位图”的题。我属于前者。当时要在一批几十亿规模的用户ID里做去重和存在性判断SetInteger的内存估算出来让人头皮发麻这才认真把模拟实现位图这件事从头到尾做了一遍。位图的原理一句话能讲完用1个bit记录一个对象的状态bit为1表示成立、为0表示不成立。但动手实现时光“定位到第几个long的第几位”就能埋下一堆坑更别说容量对齐、类型移位、多余位掩码这些细节。这篇文章把完整过程写出来先从一笔内存账讲起再落到选址位运算给一个可以直接用的Java实现然后聊可视化调试、页分配器里的“位图安装”最后总结手写过程中最容易翻车的三个细节。适合两类人一类是正在啃“java中的位图”相关源码的开发者另一类是想给海量数据做状态标记但内存吃紧的工程师。1. 位图到底解决什么问题先算一笔内存账1.1 一个能让你直观感受到差距的场景10亿数字去重假设有这样一个需求有一批ID取值范围在0到10亿之间可能有重复需要快速判断某个ID是否出现过还要对这批ID做去重。最朴素的做法是HashSetInteger。问题是Java里一个Integer对象本身就要占16字节默认压缩指针下再加上HashMap.Entry的引用、哈希桶数组、扩容预留空间摊下来一个元素差不多要30~40字节。10亿个不重复的ID内存轻松超过30GB大多数服务器直接撑不住。换成数组呢boolean[]在HotSpot里一个元素占1字节10亿个也要1GB还要再加上数组对象头。好一点但依然不理想。位图方案怎么算前提是数据本身是紧凑的整数比如范围明确是0到10亿。我开一个long[]每个long有64个bit每64个ID共用1个long需要的数组长度是10亿除以64总内存约125MB。125MB对30GB差了几百倍。而且位图的访问复杂度是O(1)——定位到一个bit只需要两次位运算不需要哈希、不需要比较、不需要解决冲突。这里可以打一个生活化的比方。HashSet相当于给每个要找的车牌都建一个独立登记柜柜子越多越占地方位图相当于一张巨长的车位表一张表上的每个格子代表一个车位有车就涂黑没车就留白。所有状态都压缩在表格本身里几乎没有额外开销。1.2 位图能做什么不能做什么位图不是万能的它只适合回答“是或否”这一类问题。我把它能做到和不能做到的事情列清楚。能做到的大规模整数/ID的“是否存在”判定这是性价比最高的用法。状态标记在线/离线、已读/未读、空闲/占用。操作系统页分配器、资源块分配与回收状态管理。作为布隆过滤器的底层存储结构。不能做到的不能计数。想知道某个ID出现过几次、某个页被引用过多少次1个bit的信息量不够。不能存储关联值。除了0/1之外还想带个名字、时间戳位图一概存不下。对稀疏的大范围不友好。假如只在0和10亿两个位置各set一次位图照样会占满10亿/8字节等于浪费。空间无法随数据量自动回收。你只能把某个bit清0但数组长度是固定的不能因为数据变少而压缩。很多人把位图当通用存储结构用结果发现存不了复杂信息就开始吐槽。其实只要明确“它只负责状态”选型就很简单状态问题是位图的天下计数和复杂对象交给别的结构。2. 选址与落位手工位图背后的两段位运算2.1 两次定位先找long再找bit实现位图的第一个核心问题是整数N对应底层数组的什么位置。我用long[] words作为存储。一个long有64个bit定位过程分两步。第一步N除以64得到数组下标wordsIdx N / 64第二步N对64取余得到long内部的bit位置bitOffset N % 64比如N0到63落在words[0]N64到127落在words[1]。因为64是2的6次方除法和取余可以改写为位运算前提是N不是负数wordsIdx N 6; bitOffset N 63;N 6等价于N / 64N 63等价于N % 64。这一步不完全是为了炫技在千万级以上的循环里少几次除法指令还是有可见收益的。定位完成后剩下就是三个基础操作这是整套实现的三把钥匙操作表达式置1words[N 6]清0words[N 6] ~(1L (N 63))判断(words[N 6] (1L (N 63))) ! 0这里有个极容易踩的坑表达式里的1L。很多人写成1 bitOffset当bitOffset取到63时1是int类型只有32位Java对int移位只取低5位作为移动距离于是1 63实际变成1 31符号位直接错乱。必须写成1L让移位发生在64位的long上63才不会被截断。2.2 为什么用long[]而不是byte[]或int[]从逻辑上讲byte[]也能实现位图8个bit一个元素定位公式变成N/8、N%8看起来更简单。但实际工程里我强烈建议用long[]原因有三个。第一是访问粒度。位图的高频操作是批量遍历和随机读写long[]每次可以处理64bitbyte[]每次只能处理8bit。同样一个循环long[]命中的数组元素更少CPU缓存的局部性更好吞吐量明显更高。第二是无符号处理。Java的byte是带符号的取值范围-128到127单个字节的最高位是符号位。想无符号地操作某一位总要做 0xFF之类的转换非常烦。long虽然也是带符号类型但位运算完全不看符号位只要不把long当数值去比较大小就没有任何问题。第三是统计方便。Java标准库提供Long.bitCount(long)直接用CPU或SWAR算法统计一个long里1的个数。如果底层是byte[]统计时要逐字节转换再做popcount慢且麻烦。结论就是能用64位容器就别用8位这不是个人偏好是效率和心智负担的双重考虑。3. 一个可以直接用的BitMap类完整代码与设计取舍3.1 核心API设计与实现细节我把完整实现贴出来代码不长但每行都要说清楚为什么这么写。import java.util.Arrays; public class BitMap { private final long[] words; private final int capacity; public BitMap(int capacity) { if (capacity 0) { throw new IllegalArgumentException(capacity must be 0); } this.capacity capacity; int wordCount (int) (((long) capacity 63) / 64); this.words new long[wordCount]; } public void set(int n) { checkRange(n); words[n 6] | 1L (n 63); } public void clear(int n) { checkRange(n); words[n 6] ~(1L (n 63)); } public boolean get(int n) { checkRange(n); return (words[n 6] (1L (n 63))) ! 0; } public long size() { long count 0; for (long w : words) { count Long.bitCount(w); } return count; } public void clearAll() { Arrays.fill(words, 0L); } public String toString() { StringBuilder sb new StringBuilder(capacity); for (int i 0; i capacity; i) { sb.append(get(i) ? 1 : 0); } return sb.toString(); } private void checkRange(int n) { if (n 0 || n capacity) { throw new IndexOutOfBoundsException(bit index out of range: n); } } }几个关键设计点。构造函数里wordCount的计算为什么写成((long) capacity 63) / 64因为capacity接近Integer.MAX_VALUE时直接用capacity 63会让int加法溢出成负数导致new long[负数]抛异常。先转long计算再转回int安全得多。为什么要加checkRange而不是让越界自然抛错位图的语义是“必须是预先定好的范围”一旦越界说明调用方逻辑有问题早暴露比晚暴露好。n 6对负数不是好事负数经过无符号右移会得到一个巨大的下标可能直接越界所以n 0必须单独拦截。set、clear、get三个方法的代码都很短本质就是两件事定位n 6和偏移n 63。如果面试被问到位图实现能背出这三行位运算并说清楚1L的意义基本就过了。这个类要不要做成自动扩容我建议不要。位图扩容的成本不只是复制数组还涉及新容量和旧数据边界的语义对齐容易导致误判“哪些位有效”。真实场景里页分配器、布隆过滤器都能提前确定最大规模一次分配到位最合适。如果你确实需要动态增长直接用Java标准库的BitSet不要自己造。3.2 统计已置位个数Long.bitCount的妙用size()方法最容易被写坏。有人会自己写循环数1的个数int cnt 0; while (w ! 0) { cnt w 1; w 1; }这个写法功能上没问题但效率低。JDK提供了Long.bitCount(long)底层是硬件popcnt指令或SWAR并行计数比逐位循环快一个量级。正确姿势就是遍历words数组对每个long调用Long.bitCount后累加。使用Long.bitCount时要注意一个隐含问题它统计的是整个long中所有1的个数如果最后一块long里含有超过capacity高位范围的1统计结果会偏大。在我这个实现里所有set都经过checkRange超范围的位永远不会被置1所以size()是准确的。但如果以后你改成批量填充或直接操作底层数组就必须考虑掩码问题这个第6章会专门讲。4. 把内部状态“画”出来调试可视化与基本验证4.1 从“电位图怎么画”说起位图同样需要画有人会搜“电位图怎么画”这个概念我不展开但它的核心思路和位图可视化完全一致把抽象的状态变成肉眼可见的东西。调试位图时直接看long的十进制数值是没用的你需要把每个long铺成64位二进制串来看。我给BitMap加一个toVisual()方法专门用来看内部状态public String toVisual() { StringBuilder sb new StringBuilder(); for (long w : words) { String bits Long.toBinaryString(w); while (bits.length() 64) { bits 0 bits; } sb.append([); for (int i 0; i 64; i 8) { if (i 0) { sb.append( ); } sb.append(bits, i, i 8); } sb.append(]); } return sb.toString(); }Long.toBinaryString(w)会把负数也输出成64位二进制串但如果是正数前面可能没有补零所以要先补足64位。输出效果类似[00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001]我写了一个简单验证BitMap bm new BitMap(200); bm.set(0); bm.set(63); bm.set(64); System.out.println(bm.toVisual());跑出来的结果里第0个long的最低位是1第0个long的最高位也是1第1个long的最低位是1。第一次看可能觉得奇怪明明set(0)和set(63)都是1为什么两个1隔那么远这就是bit位置在8位分组后的真实样子第0位在最右侧第63位在最左侧的分组里。用toVisual()排查问题时可以一眼看出是不是把1L写成了1。这里顺带说一下字节序。我按二进制串从左到右展示高位到低位所以第0位在右、第63位在左。如果你的需求正相反把输出顺序反转即可这不影响数据本身的正确性。4.2 验证与性能真实跑一次set和get继续用上面的对象做断言System.out.println(bm.get(0)); // true System.out.println(bm.get(1)); // false System.out.println(bm.get(63)); // true System.out.println(bm.get(64)); // true System.out.println(bm.size()); // 3capacity200需要4个long最后一块只有8个有效bit200减192。这个非64倍数的容量正好用来做边界测试后面第6章会继续展开。再做一个简单的性能测试不严谨但能说明量级long start System.nanoTime(); BitMap bm2 new BitMap(1 26); Random random new Random(42); for (int i 0; i 10_000_000; i) { bm2.set(random.nextInt(1 26)); } long end System.nanoTime(); System.out.println((end - start) / 1_000_000 ms);我本地环境跑下来大约60~100毫秒其中大部分还是Random.nextInt的开销。相比之下用HashSet插入一千万个Integer往往要2秒以上。位图在批量写场景里之所以快一是数组访问O(1)无哈希冲突二是大量随机set最终会集中在部分long上CPU cache命中率高。这个结果说明位图不只是省内存在固定范围内的海量状态标记任务里速度同样有优势。5. 位图在真实系统里的样子页分配器、BitSet与最终取舍5.1 页分配器里的“位图安装”是怎么操作的“页分配器与位图安装”这组词听起来很底层但其实正好是位图最经典的应用。操作系统把物理内存切成等大的页框比如4KB一个。要快速知道哪些页空闲、哪些页被占用直接给每个页框准备1个bit0表示空闲1表示已分配。所谓“安装位图”就是三步根据物理页总数P计算需要的long数量w (P 63) / 64。分配这段连续内存并全部清零所有页都标记为空闲。把已经被内核、启动代码占用的页对应的bit置1防止被别人分配走。之后分配页框时找第一个值为0的bit并置1释放页时把对应bit清0。如果每次分配都从0开始线性扫描效率太低。实际系统会配合“下一次搜索位置”的游标、空闲链表、伙伴系统等机制位图只负责“谁占用谁空闲”的状态存储真正的分配策略在位图之上。我用前面的BitMap写了一个极简页分配器public class SimplePageAllocator { private final BitMap used; private final int pageCount; private int hint; public SimplePageAllocator(int pageCount) { this.pageCount pageCount; this.used new BitMap(pageCount); } public int alloc() { for (int i hint; i pageCount; i) { if (!used.get(i)) { used.set(i); hint i 1; return i; } } for (int i 0; i hint; i) { if (!used.get(i)) { used.set(i); hint i 1; return i; } } return -1; } public void free(int page) { used.clear(page); } }注意hint这个字段。它记录上次分配到的位置下次分配优先从这里继续向后找找完一圈再回到0开头。在“顺序分配、顺序释放”的典型模式下分配一个页的平均时间复杂度接近O(1)。不要小看这个“游标环形扫描”的思路它就是从位图数据结构到实际分配器设计之间最重要的一层。以后你去看Linux内核的页分配器代码会发现里面不只是位图还叠加了更复杂的order分区和伙伴算法但当你看到类似 per-page state bitmap 的结构时就能自然联想到这里的逻辑了。5.2 Java内置BitSet和手写BitMap怎么选标题虽然是“模拟实现位图”还是要面对一个现实问题Java自带java.util.BitSet为什么还要手写我把两者的差异列成表格维度手写BitMapjava.util.BitSet动态扩容不支持固定容量自动扩容查找空闲位自己写循环内置nextClearBit(int)统计置位数自己遍历Long.bitCount内置cardinality()流式处理无内置stream()可遍历所有置位下标边界校验额外实现checkRange越界时自动扩容BitSet的底层也是long[]核心位运算和手写版完全一致。真实Java项目里如果只是需要一个可变的位集合直接用BitSet别重复造轮子。尤其nextClearBit这个API找第一个空闲bit的效率比手写循环要高做页分配器时非常顺手。那手写版本的价值在哪里我认为有两点。第一是学习价值。理解了选址位运算读源码、看底层结构都会轻松很多面试遇到手写题也不会慌因为你交付的就是一份80行的类加上一段“为什么要用1L而不是1”的解释。第二是定制价值。BitSet会自动扩容这在你明确希望“越界就是bug”的场景里反而不合适。手写版可以加capacity约束、加动作钩子、加“只统计合法范围”的语义这些封装是BitSet不会给你的。选型建议也很直接业务数据量只有几百万且内存充足用HashSet最省事数据量巨大且范围已知位图是正确选择数据量巨大但范围不确定考虑布隆过滤器它底层也是位图。这条决策链基本覆盖了日常大部分场景。6. 手写位图最容易翻车的三个细节6.1 移位与类型最典型的bug是这一行words[n 6] | 1 (n 63); // 错误写法n 63的范围是0到63但1是int类型Java对int移位只取低5位作为移动距离。所以当偏移是32到63时实际移位会被绕回0到31偏移63时1 63实际等于1 31变成一个符号位为1的负数int再和long做|运算结果完全错乱。清0操作同样会踩words[n 6] ~(1 (n 63)); // 错误写法如果有人跟我说“我明明set了但get一直返回false”我第一个会去看的就是代码里有没有漏掉L。这个坑排查起来最迷惑因为低32位的数据表现完全正常只有高位区间才出错。6.2 容量溢出构造函数里直接写(capacity 63) / 64当capacity接近Integer.MAX_VALUE时会溢出成负数。我这份代码用((long) capacity 63) / 64来规避。另一个边界是负数入参。n 6虽然是无符号右移但负数n经过右移后会得到一个很大的整数下标落到数组后面甚至越界。checkRange里必须单独判断n 0不能只判断上限。还有一个隐藏的溢出风险new long[wordCount]时如果wordCount太大数组本身也创建不出来。这属于物理内存限制不是代码逻辑问题但面试时主动提一句“这里还要考虑最大数组长度限制”会比闷头写代码好很多。6.3 最后一块long的多余bit当capacity不是64的倍数时最后一块long里只有capacity % 64个有效bit其余高位属于“无效区”。正常情况下set经过checkRange不会碰到这些无效位但在两类场景下会出现异常。第一类是优化写法。如果为了提高性能直接操作底层数组例如一次性写入多个连续bit时很容易把无效位置1。第二类是某些从别处迁移过来的位图数据原实现里高位本来就是脏的。这些脏bit会导致size()统计偏大遍历时多出一些“幽灵状态”。稳妥做法是在构造时记录最后一块的掩码int tailWords capacity 63; long tailMask; if (tailWords 0) { tailMask ~0L; } else { tailMask ~0L (64 - tailWords); }在做size()统计或遍历最后一块long时先 tailMask再操作。这个掩码处理是位图从玩具实现走向工程实现的分水岭。写完位图一定要用非64倍数容量跑一次边界测试比如capacity200set(199)后看统计结果是否正确再手动往最后一个数组元素的高位写入一个1看size()有没有异常变大。最后再唠叨一句实操建议把这份BitMap代码敲下来以后给它加上toVisual()在本地跑一跑。从0开始一直set到capacity-1看看最后一块long的展示效果再用200这种非64倍数验证一遍边界。网络上讲位图的帖子很多但“讲明白了”和“自己会长在脑子里”是两回事亲手敲过一遍以后遇到内存相关的性能问题你自然会先想到它。
