位图 Bitmap

calendar Mar 13, 2025 · 2 min read · 数据结构

1. 基本概念

位图（Bitmap），又称位数组（Bit Array）或位集合（Bitset），是一种通过二进制位（0或1）高效存储和操作数据的数据结构。每个二进制位表示某种状态（如存在/不存在、开启/关闭），常用于处理大规模布尔值集合。

2. 核心特性

  • 空间高效：每个元素仅占1位，相比布尔数组（每个元素占1字节）节省8倍空间。
    • 示例：存储1亿个元素的状态仅需约12MB（(10^8 , \text{bit} \approx 12 , \text{MB})）。
  • 快速位运算：支持按位与（AND）、或（OR）、异或（XOR）等操作，高效实现集合的交、并、差运算。
  • 随机访问：可在常数时间（O(1)）内查询或修改某一位的状态。

3. 实现原理

内存分配
  • 位图的大小由最大元素值决定。例如，存储元素范围 [0, n-1] 需要 n 位，分配的内存大小为 (\lceil \frac{n}{8} \rceil) 字节。
  • 示例：存储0~999的数字是否存在，需1000位（125字节）。
位操作
  • 定位位：元素 k 对应的存储位置为：
    • 字节索引：( \text{byteIndex} = \left\lfloor \frac{k}{8} \right\rfloor ) （或 k >> 3）
    • 位偏移：( \text{bitOffset} = k % 8 ) （或 k & 0x07）
  • 设置位：将第 k 位设为1： 
    1bytes[byteIndex] |= (1 << bitOffset);
  • 清除位：将第 k 位设为0： 
    1bytes[byteIndex] &= ~(1 << bitOffset);
  • 查询位：检查第 k 位是否为1： 
    1(bytes[byteIndex] & (1 << bitOffset)) != 0;

4. 应用场景

  1. 集合去重与存在性检查
    • 示例：快速判断用户ID是否已注册。
  2. 布隆过滤器（Bloom Filter）
    • 使用多个哈希函数将元素映射到位图的多个位置，用于高效判断元素是否存在（可能有误判，但不会漏判）。
  3. 数据库索引
    • 对低基数字段（如性别、状态）建立位图索引，加速查询。
  4. 垃圾回收标记
    • 标记内存中的存活对象。
  5. 权限管理
    • 每个位表示一种权限（如读、写、执行）。
  6. 图像处理
    • 二值图像（黑白图）的像素存储。

5. 优缺点分析

优点 缺点
空间效率极高（1位/元素） 元素范围过大时内存消耗高（稀疏数据不适用）
集合操作高效（位运算） 无法直接存储额外信息（仅能表示存在性）
查询和修改速度快（O(1)） 动态扩容成本高（需重新分配内存）

6. 优化与变体

  1. 压缩位图（如Roaring Bitmap）
    • 将位图分段，稀疏段用数组存储，密集段用位图，兼顾空间和性能。
  2. 分层位图
    • 使用多级位图减少内存占用，例如高16位和低16位分层存储。
  3. 动态扩容
    • 初始分配较小内存，按需扩展（需复制旧数据）。

7. 代码示例（C语言）

 1#include <stdio.h>
 2#include <stdlib.h>
 3#include <stdbool.h>
 4
 5typedef struct {
 6    unsigned char *data;
 7    size_t size;  // 最大元素值（位数）
 8} Bitmap;
 9
10// 初始化位图
11Bitmap* bitmap_create(size_t size) {
12    Bitmap *bm = (Bitmap*)malloc(sizeof(Bitmap));
13    bm->size = size;
14    size_t bytes = (size + 7) / 8; // 计算所需字节数
15    bm->data = (unsigned char*)calloc(bytes, 1);
16    return bm;
17}
18
19// 设置位
20void bitmap_set(Bitmap *bm, size_t k) {
21    if (k >= bm->size) return;
22    size_t byte_idx = k / 8;
23    size_t bit_offset = k % 8;
24    bm->data[byte_idx] |= (1 << bit_offset);
25}
26
27// 清除位
28void bitmap_clear(Bitmap *bm, size_t k) {
29    if (k >= bm->size) return;
30    size_t byte_idx = k / 8;
31    size_t bit_offset = k % 8;
32    bm->data[byte_idx] &= ~(1 << bit_offset);
33}
34
35// 查询位
36bool bitmap_get(Bitmap *bm, size_t k) {
37    if (k >= bm->size) return false;
38    size_t byte_idx = k / 8;
39    size_t bit_offset = k % 8;
40    return (bm->data[byte_idx] & (1 << bit_offset)) != 0;
41}
42
43// 释放内存
44void bitmap_free(Bitmap *bm) {
45    free(bm->data);
46    free(bm);
47}
48
49int main() {
50    Bitmap *bm = bitmap_create(1000); // 存储0~999
51    bitmap_set(bm, 100);
52    printf("Bit 100: %d\n", bitmap_get(bm, 100)); // 输出1
53    bitmap_clear(bm, 100);
54    printf("Bit 100: %d\n", bitmap_get(bm, 100)); // 输出0
55    bitmap_free(bm);
56    return 0;
57}

8. 总结

位图是一种以空间换时间的高效数据结构，适用于元素范围明确且密集的场景。通过位运算，它能快速完成集合操作和状态管理。