位图（Bitmap）原理与应用

位图是一种使用位数组来表示数据集合的高效数据结构，特别适合处理大规模整数的存在性判断和去重问题。我将从基本概念开始，逐步讲解其实现原理和实际应用。

一、位图的基本概念
位图的核心思想是用一个比特（bit）来表示一个数字的存在状态。每个比特有两种状态：0表示数字不存在，1表示数字存在。例如，要表示数字集合{2, 5, 8}，需要9个比特（索引0-8）：
索引：0 1 2 3 4 5 6 7 8
比特：0 0 1 0 0 1 0 0 1

二、位运算基础
实现位图需要掌握三个基本位运算：

1. 定位到具体比特：数字n所在的字节索引为 n/8（或n>>3），比特偏移量为 n%8（或n&0x07）
2. 设置比特为1：使用按位或运算 |，例如 byte |= (1 << offset)
3. 判断比特是否为1：使用按位与运算 &，例如 (byte & (1 << offset)) != 0

三、位图的具体实现步骤
假设我们要表示0到99999范围内的数字：

1. 内存分配计算

• 需要100000个比特
• 总字节数 = ceil(100000/8) = 12500字节 ≈ 12.2KB
• 相比存储100000个int（400KB），节省了97%空间

2. 关键操作实现

• 添加数字n：
  byteIndex = n / 8 // 确定字节位置
  bitOffset = n % 8 // 确定比特偏移
  bitmap[byteIndex] |= (1 << bitOffset) // 设置对应比特为1

• 检查数字n是否存在：
  byteIndex = n / 8
  bitOffset = n % 8
  return (bitmap[byteIndex] & (1 << bitOffset)) != 0

四、实际应用场景

1. 大数据去重
   案例：统计10亿个IP地址的去重数量（IP转为32位整数）

• 传统方法：使用HashSet需要约4GB内存
• 位图方法：需要2^32比特 = 512MB内存
• 节省87.5%内存空间

2. 数据库索引优化
   在数据库中对低基数列（如性别、状态码）建立位图索引：

• 每个取值对应一个位图
• 多条件查询时通过位运算快速合并
  示例：查询"性别=男且状态=活跃"
  直接对男性位图和活跃位图做按位与运算

3. 布隆过滤器的基础
   位图是布隆过滤器的底层存储结构，布隆过滤器使用多个哈希函数将元素映射到位图的不同位置。

五、位图的局限性及解决方案

1. 稀疏数据问题
   当数据稀疏时（如存储{1, 1000000}），位图仍需要125KB内存
   解决方案：使用压缩位图（如EWAH、Roaring Bitmap）

2. 动态范围问题
   当数字范围不确定时，需要可扩展位图
   解决方案：分层位图或动态数组

六、进阶优化技巧

1. 位运算优化
   使用移位代替乘除：n/8 改为 n>>3，n%8 改为 n&7

2. 批量操作优化
   支持批量设置和查询，减少函数调用开销

3. 缓存友好布局
   将频繁访问的位图区域放在连续内存中

位图通过极致的空间效率，在特定场景下实现了O(1)时间复杂度的存在性判断，是大数据处理中不可或缺的基础数据结构。理解位图的工作原理有助于在内存敏感的应用中做出合理的技术选型。