位图算法（BitMap）是一种通过二进制位来标记数据存在状态的数据结构，在处理海量数据去重、统计等场景时，相比传统的数据存储方案有极大的内存优势。比如要处理10亿个整数去重，传统HashSet每个整数至少占用16字节内存，总内存需求会超过10GB，而BitMap只需要约120MB内存即可完成全部标记。
BitMap核心原理
BitMap的本质是一个连续的二进制位数组，数组的每个下标对应一个数据值，每个二进制位的值（0或1）表示该数据是否存在。比如要标记数字5是否存在，只需要将位数组的第5位设置为1即可。
假设我们要处理的整数范围是0到N，那么需要的位数组长度就是N+1，对应的字节数为(N+1)/8。比如处理0到10亿的整数，需要的字节数是1000000001/8 ≈ 125000000字节，也就是约119MB，内存开销远低于传统方案。
基础操作逻辑
- 初始化：创建一个足够长度的字节数组，所有位默认值为0
- 标记存在：计算目标值对应的字节索引和位索引，将该位设置为1
- 检查存在：计算目标值对应的字节索引和位索引，判断该位是否为1
- 去重统计：遍历所有位，统计值为1的位的数量即为去重后的数据量
Java实现亿级数据去重
下面给出一个完整的BitMap实现示例，支持整数的添加、存在性检查、去重计数功能，可直接用于处理亿级规模的整型数据去重场景。
public class BitMap {
// 字节数组，用于存储位数据
private byte[] bits;
// 支持的最大数值
private int maxValue;
/**
* 初始化BitMap
* @param maxValue 支持处理的最大整数值，超过该值的数据无法处理
*/
public BitMap(int maxValue) {
this.maxValue = maxValue;
// 计算需要的字节数，+7是为了向上取整，保证所有位都被覆盖
int byteSize = (maxValue + 7) / 8;
this.bits = new byte[byteSize];
}
/**
* 标记数据存在，即添加数据到BitMap
* @param value 要添加的整数，必须在0到maxValue之间
*/
public void add(int value) {
if (value < 0 || value > maxValue) {
throw new IllegalArgumentException("value超出BitMap支持的范围");
}
// 计算字节索引：value / 8
int byteIndex = value >> 3;
// 计算位索引：value % 8
int bitIndex = value & 7;
// 将该位设置为1，使用或运算避免影响其他位
bits[byteIndex] |= (1 << bitIndex);
}
/**
* 检查数据是否已经存在
* @param value 要检查的整数
* @return 如果存在返回true，否则返回false
*/
public boolean contains(int value) {
if (value < 0 || value > maxValue) {
return false;
}
int byteIndex = value >> 3;
int bitIndex = value & 7;
// 判断该位是否为1，使用与运算
return (bits[byteIndex] & (1 << bitIndex)) != 0;
}
/**
* 统计去重后的数据总量
* @return 去重后的数据个数
*/
public int countUnique() {
int count = 0;
// 遍历所有字节
for (byte b : bits) {
// 统计每个字节中1的个数，使用位运算快速计算
int temp = b & 0xFF;
while (temp != 0) {
temp &= temp - 1;
count++;
}
}
return count;
}
// 测试示例
public static void main(String[] args) {
// 假设要处理0到10亿的整数去重
BitMap bitMap = new BitMap(1000000000);
// 模拟添加重复数据
int[] testData = {100, 200, 100, 300, 200, 400, 100};
for (int num : testData) {
if (!bitMap.contains(num)) {
bitMap.add(num);
System.out.println("添加新数据：" + num);
} else {
System.out.println("数据重复，跳过：" + num);
}
}
System.out.println("去重后的数据总量：" + bitMap.countUnique());
}
}
BitMap的适用场景与局限
BitMap非常适合处理范围明确、数据值分布相对集中的海量去重场景，比如用户ID去重、手机号尾号统计、整数型日志去重等。但它也有明显的局限性：
- 只能处理整型数据，字符串等非整型数据需要先哈希映射到整数范围，可能存在哈希冲突问题
- 数据值范围过大时，即使数据量很少，也需要分配对应范围的位数组，比如要处理0到100亿的整数，即使只有1个数据，也需要约1.16GB内存
- 不支持删除操作，一旦标记存在就无法将位重新设置为0，除非重新初始化整个BitMap
扩展方案：Roaring BitMap
如果数据值分布非常稀疏，普通BitMap会造成大量内存浪费，此时可以使用Roaring BitMap方案。它会将整数范围划分为多个块，每个块单独维护一个BitMap，只给有数据的块分配内存，在稀疏数据场景下内存效率远高于普通BitMap，目前已经在很多大数据组件中广泛应用。
实际业务中如果数据量达到亿级，建议先评估数据值的分布范围，再选择合适的位图方案，避免不必要的内存开销。