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

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

一、什么是 Bitmap？

Bitmap（位图）是一种基于位的数组结构，使用每一个 bit 位来存储一个二元状态（0/1，true/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
• 设置 1：bytes[byteIndex] |= (1 << bitOffset)
• 设置 0：bytes[byteIndex] &= ~(1 << bitOffset)
• 翻转：bytes[byteIndex] ^= (1 << bitOffset)

三、基本操作

位运算操作是 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 MB
  BitSet(Java)	100M bits	12.5 MB
  HashSet<Integer>(存储存在的那些值)	若存在 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。

BitSetbs=newBitSet();bs.set(100);// 设置第100位为1bs.set(200,300);// 设置区间 [200,300) 为1booleanexist=bs.get(100);// truebs.clear(100);// 清除intnext=bs.nextSetBit(0);// 找到第一个1的位置

Python 使用bytearray实现简易 bitmap

classBitmap:def__init__(self,size):self.size=size self.bytes=bytearray((size+7)//8)defset(self,k):ifk>=self.size:raiseIndexError self.bytes[k>>3]|=1<<(k&7)defclear(self,k):self.bytes[k>>3]&=~(1<<(k&7))deftest(self,k):return(self.bytes[k>>3]>>(k&7))&1defcount(self):# bin(x).count('1') 效率低，可查表或使用 int.bit_count() (Python 3.8+)returnsum(b.bit_count()forbinself.bytes)

六、优点与局限性

✅ 优点

1. 极致空间效率：比基于字节的布尔数组节省 8~32 倍内存。
2. CPU 缓存友好：连续内存布局，批量操作时高速缓存命中率高。
3. 并行/向量化：一次 64 位运算可同时处理 64 个元素（SIMD 友好）。
4. 集合运算极快：交集、并集只需逐字进行位运算，时间复杂度 O(N/word_size)。

❌ 局限性

1. 固定值域：需要预先知道最大元素范围，范围过大而元素稀疏时浪费严重。
2. 只能存储二元状态：不能直接存储关联数据（如权重、附加属性）。
3. 非动态稀疏：若最大 ID 上亿但只有几千个元素，512 MB 内存远高于红黑树或哈希表。
4. 计数与遍历：统计 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的简单扩展：不支持压缩，仅固定长度。

八、典型应用场景深度剖析

九、性能考量与优化技巧

1. 计数优化：使用 CPU 提供的POPCNT指令（通过Long.bitCount、int.bit_count）硬件加速，比逐位检查快 10 倍以上。
2. 循环遍历所有 1：不要逐位扫描，使用nextSetBit跳跃到下一个 1，内部实现通常按字查找。
3. 批量操作：尽可能使用and、or等矢量操作，而不是对每个 bit 单独循环。
4. 选择合适的变体：
   • 稠密、值域固定 → 普通 bitmap
   • 值域很大（> 2^31）但分布未知 → Roaring Bitmap
   • 需要持久化到磁盘 → 考虑 EWAH 或 Roaring 的序列化格式
5. 字节对齐：在 C/C++ 中访问时使用uint64_t对齐，避免跨字访问开销。

十、总结

Bitmap 是计算机科学中“用空间换时间”的反面——用极致的空间压缩换取大量内存节省，同时在批量集合运算上甚至超过传统结构。理解 bitmap，不仅是掌握一个数据结构，更是学会如何用位这一最底层的单元去表示海量信息，这是高级系统设计和大数据处理的基石之一。