导语：位图（Bitmap）是一种高效存储和操作大量布尔值的数据结构。本文将从基础概念讲起，逐步深入位图的原理、应用场景及Java实现，助你轻松掌握这一高频面试知识点。
一、什么是位图？
位图（Bitmap） 是一种利用二进制位（0或1）来存储数据的数据结构。每个二进制位代表一个状态，常用于高效处理存在性判断、去重、签到统计等场景。
传统方案 vs 位图
传统方案：使用boolean数组存储数据，每个元素占1字节（8位）。
位图方案：每个元素仅占1位，空间利用率提升8倍！
示例：存储1000万个用户的签到状态
boolean[]需要约10MB（10000000 / 1024 / 1024 ≈ 9.54MB）
位图仅需约1.25MB（10000000 / 8 / 1024 / 1024 ≈ 1.19MB）
二、位图核心原理
1. 存储结构
使用连续的内存块（如int[]或long[]数组）存储位数据。
计算位置：确定元素在数组中的索引和偏移量。
索引：元素值 / 32（int占32位）
偏移：元素值 % 32
2. 核心操作
设置位：将指定位置为1
清除位：将指定位置为0
查询位：判断指定位置是否为1
三、位图应用场景
1. 用户签到统计
用位图的每一位代表用户某天是否签到。
每月签到仅需31位，全年仅需365位。
2. 数据去重
快速判断元素是否存在，避免重复插入。
3. 布隆过滤器
位图是布隆过滤器实现的基础结构，用于高效判断元素可能存在或绝对不存在。
四、Java位图实现
1. 使用BitSet类
Java内置的BitSet类提供了位图操作API。
import java.util.BitSet;
public class BitSetDemo {
public static void main(String[] args) {
BitSet bitmap = new BitSet(100); // 初始化100位的位图
// 设置第5位为1（签到）
bitmap.set(5);
// 检查第5位是否为1
System.out.println("第5天是否签到：" + bitmap.get(5)); // true
// 清除第5位
bitmap.clear(5);
System.out.println("清除后：" + bitmap.get(5)); // false
}
}
2. 手动实现位图
通过int[]数组和位运算手动实现位图：
public class CustomBitmap {
private int[] bits; // 存储位数据
public CustomBitmap(int capacity) {
// 计算需要多少个int来存储capacity位
bits = new int[(capacity >> 5) + 1]; // capacity/32 +1
}
// 设置位
public void set(int pos) {
int index = pos >> 5; // 计算数组索引（等价于pos/32）
int offset = pos & 0x1F; // 计算偏移量（等价于pos%32）
bits[index] |= (1 << offset); // 将指定位置1
}
// 清除位
public void clear(int pos) {
int index = pos >> 5;
int offset = pos & 0x1F;
bits[index] &= ~(1 << offset); // 将指定位清0
}
// 查询位
public boolean get(int pos) {
int index = pos >> 5;
int offset = pos & 0x1F;
return (bits[index] & (1 << offset)) != 0;
}
public static void main(String[] args) {
CustomBitmap bitmap = new CustomBitmap(100);
bitmap.set(10); // 设置第10位
System.out.println("第10位状态：" + bitmap.get(10)); // true
bitmap.clear(10);
System.out.println("清除后：" + bitmap.get(10)); // false
}
}
五、注意事项与优化
1. 稀疏数据处理
当数据非常稀疏时（如存储1和1,000,000两个值），位图可能浪费空间。
解决方案：使用压缩位图（如Roaring Bitmap）。
2. 线程安全
BitSet非线程安全！多线程环境下需使用Collections.synchronized包装或自定义锁。
3. 动态扩容
BitSet自动扩容，手动实现的位图需处理数组扩容逻辑。
六、总结
位图通过将每个元素压缩到1位，大幅节省存储空间，尤其适合处理海量布尔值场景。合理使用位图，可显著提升程序性能。但需根据数据分布选择合适方案，避免空间浪费。