数据结构 Bitmap（位图）完整详解

数据结构 Bitmap位图完整详解一、什么是 BitmapBitmap位图是一种基于位的数组结构使用每一个 bit 位来存储一个二元状态0/1true/false存在/不存在。它将一个范围如整数 ID、枚举值直接映射到内存中的某个 bit 位置从而实现极高的空间效率和快速的位置访问。核心思想用 1 个 bit 代替原本需要 1 个 byte甚至更多才能存储的布尔信息。二、核心原理假设我们要记录0到n-1共 n 个元素的存在性。传统做法是用一个boolean[]每个布尔值在大多数语言中占用 1 字节Java甚至 4 字节C# bool。而 Bitmap 将 n 个 bit 连续存储这些 bit 被组织成若干个字节或字。映射关系第k个 bit 对应数字k的状态。内存中第i个字节的第j位通常 j 从 0 到 7从低位到高位或相反字节索引byteIndex k / 8位偏移bitOffset k % 8访问公式读取(bytes[byteIndex] bitOffset) 1设置 1bytes[byteIndex] | (1 bitOffset)设置 0bytes[byteIndex] ~(1 bitOffset)翻转bytes[byteIndex] ^ (1 bitOffset)三、基本操作操作描述时间复杂度set(k)将第 k 位设为 1O(1)clear(k)将第 k 位设为 0O(1)test(k)返回第 k 位的值O(1)count()统计所有 1 的个数O(n) 或硬件加速bitwise AND/OR/XOR/NOT两个 bitmap 之间的集合运算O(n)nextSetBit(from)从某个位置向后找第一个 1O(n) 或通过分段优化位运算操作是 bitmap 相对于其他集合如 HashSet的独特优势可以极快地完成并集、交集、差集非常适合批处理和索引合并。四、空间占用与计算理论最小内存size_in_bits max_element 1时内存占用 ceil(size_in_bits / 8)字节。实例记录 0~99 共 100 个数 → 100 bits ≈ 13 字节记录 0~10 亿10^9 → 10^9 bits ≈ 119 MB记录 0~2^32-1约 43 亿 → 512 MB对比数据结构存储 1 亿个布尔值内存boolean[](Java)100M × 1 字节100 MBBitSet(Java)100M bits12.5 MBHashSetInteger(存储存在的那些值)若存在 5000 万个数每个 Integer 对象指针≈ 1.2 GB但注意bitmap 的空间开销与值域范围成正比与实际元素个数无关。如果值域稀疏如只有 10 个元素但它们的值在 0~10^9 之间单纯 bitmap 会非常浪费。此时需用稀疏优化方案Roaring Bitmap。五、实现细节以 Java 和 Python 为例Javajava.util.BitSet的内部实现内部使用long[] words每个 long 存储 64 个 bit。动态扩容当需要的索引超出当前大小时自动创建更大的数组。提供了丰富的集合运算and,or,xor,andNot。BitSetbsnewBitSet();bs.set(100);// 设置第100位为1bs.set(200,300);// 设置区间 [200,300) 为1booleanexistbs.get(100);// truebs.clear(100);// 清除intnextbs.nextSetBit(0);// 找到第一个1的位置Python 使用bytearray实现简易 bitmapclassBitmap:def__init__(self,size):self.sizesize self.bytesbytearray((size7)//8)defset(self,k):ifkself.size:raiseIndexError self.bytes[k3]|1(k7)defclear(self,k):self.bytes[k3]~(1(k7))deftest(self,k):return(self.bytes[k3](k7))1defcount(self):# bin(x).count(1) 效率低可查表或使用 int.bit_count() (Python 3.8)returnsum(b.bit_count()forbinself.bytes)六、优点与局限性✅ 优点极致空间效率比基于字节的布尔数组节省 8~32 倍内存。CPU 缓存友好连续内存布局批量操作时高速缓存命中率高。并行/向量化一次 64 位运算可同时处理 64 个元素SIMD 友好。集合运算极快交集、并集只需逐字进行位运算时间复杂度 O(N/word_size)。❌ 局限性固定值域需要预先知道最大元素范围范围过大而元素稀疏时浪费严重。只能存储二元状态不能直接存储关联数据如权重、附加属性。非动态稀疏若最大 ID 上亿但只有几千个元素512 MB 内存远高于红黑树或哈希表。计数与遍历统计 1 的个数count需要扫描整个位图O(内存大小)除非用硬件popcount指令加速但扫描依然需要遍历所有 bits。七、高级变体解决稀疏问题为解决“值域大而元素少”时的内存浪费学术界和工业界提出了多种压缩 bitmap 结构其中最著名的是Roaring Bitmap。Roaring Bitmap 核心思想将 32 位整数范围按高 16 位分成 2^16 个桶chunk每个桶最多包含 65536 个可能的低 16 位值。桶内根据元素密度选择不同容器Array Container稀疏时元素数 4096存储有序 16 位整数数组内存约 2 字节/元素。Bitmap Container稠密时元素数 ≥ 4096使用 8KB 的位图65536 bits 8KB内存固定。Run Container可选对连续区间如 [100,200]使用 RLE 编码空间更优。效果对随机分布的元素Roaring 比普通 bitmap 节省 90% 以上内存且交集、并集性能仍然极高。已被广泛应用于Spark、Druid、ClickHouse、Lucene 等。其他变体EWAH (Compressed Word-Aligned Bitmap)使用运行长度编码适合数据库。Concise对连续 0/1 压缩查询略慢。JavaBitSet的简单扩展不支持压缩仅固定长度。八、典型应用场景深度剖析应用领域具体说明为何用 Bitmap海量整数判存布隆过滤器底层如网页 URL 去重、垃圾邮件过滤。布隆过滤器使用多个 bitmap 和多个哈希函数。极低内存 可容忍小概率误判。用户签到/活跃统计每个用户一条记录每天一个 bit 表示是否签到。1 亿用户 × 365 天 365 亿 bits ≈ 4.3 GB比传统方式小几十倍。按天按位运算快速统计连续签到天数等。数据库位图索引对低基数列性别、地区、产品类别建立位图索引每个值对应一个 bitmap标记哪些行具有该值。适合 OLAP 多维分析。支持快速 AND/OR 多条件过滤空间远小于 B-Tree。权限系统使用 32 位整数作为权限掩码每个 bit 代表一种权限读、写、删除、审核…。位运算组合权限操作简单存储仅 4 字节/用户。磁盘块/内存页管理操作系统的空闲块位图每个 bit 表示磁盘块或内存页是否空闲。内存小查询和修改极快。图着色/状态标记BFS/DFS 中记录节点是否访问过当节点数达百万级以上时bitmap 比 bool 数组节省内存。节省内存避免 OOM。倒排索引压缩搜索引擎中 docID 列表可用 bitmap 或 Roaring 存储用于快速求交集多关键词搜索。位图压缩 高性能集合运算。实时风控/反作弊记录用户在最近 N 小时内是否触发某个事件如 24 小时滑动窗口每个时间片用一位。滑动窗口可通过移位和位运算实现高效无锁。九、性能考量与优化技巧计数优化使用 CPU 提供的POPCNT指令通过Long.bitCount、int.bit_count硬件加速比逐位检查快 10 倍以上。循环遍历所有 1不要逐位扫描使用nextSetBit跳跃到下一个 1内部实现通常按字查找。批量操作尽可能使用and、or等矢量操作而不是对每个 bit 单独循环。选择合适的变体稠密、值域固定 → 普通 bitmap值域很大 2^31但分布未知 → Roaring Bitmap需要持久化到磁盘 → 考虑 EWAH 或 Roaring 的序列化格式字节对齐在 C/C 中访问时使用uint64_t对齐避免跨字访问开销。十、总结特性描述本质以 bit 为基本单位的数组映射整数到状态内存N bits 存储 N 个二元值约 N/8 字节速度单点 O(1)批量运算 O(N/字长)最佳适用值域紧凑、元素稠密或需要高速集合运算的场景稀疏优化Roaring Bitmap 等压缩结构Bitmap 是计算机科学中“用空间换时间”的反面——用极致的空间压缩换取大量内存节省同时在批量集合运算上甚至超过传统结构。理解 bitmap不仅是掌握一个数据结构更是学会如何用位这一最底层的单元去表示海量信息这是高级系统设计和大数据处理的基石之一。