# bitmap位图 ## 引子 首先通过一道题来理解什么是bitmap。 1. **题目**：我有40亿个整数，再给一个新的整数，我需要判断新的整数是否在40亿个整数中，你会怎么做？ 2. **分析** 假设一个int占4个字节（32位），40个亿个整数就是160亿个字节，大概相当于16GB，假设一台计算机只有2GB内存，则16GB一次加载不完，需要分8次加载，从磁盘加载数据是磁盘io操作，是非常慢的（比内存中的操作要慢100倍），每次加载这么大的数据，并且要8次，那么查找的时间可以达到分钟甚至小时级别。 还有一个办法是把数据分散在8台计算机上，然后来一个新数据，8台计算机同时找，然后再汇总结果。这样每台计算机都可以一次性把数据读入内存中，查找就不用来回加载数据，省去了加载数据的开销，是个好方法。 但是否还有其他更好的方法呢？那就是bitmap。bitmap存值的思路：每一个int有32位，int整数的范围是-2147483648 ~ 2147483647。为简化理解，这里先假设每一个整数位均为正整数（如果存在负整数需分开处理），2147483647/32 = 67108863，即只需要67108863个int型整数就可以表示 [0，2147483647] 范围的数字，即需要67108863*4 = 268,435,452‬个字节的内存，相当于0.2GB，即使加上负整数部分也才需要0.4GB的内存，一台计算机完全足够。这里将开辟67108863int型数组，数组中的每一位代表依次代表 [0，2147483647]。而且而且判断新的整数也只需要O(1)的时间复杂度，性能非常高 ## bitmap定义 位图是一个数组的每一个数据的每一个二进制位表示一个数据，0表示数据不存在，1表示数据存在。 例如存储136这个数： * 确定136在整个数据的那个区间，136/32 = 4，即在第四个区间； * 确定136在这个区间的第几位（bit），136%32 = 25，即在第四区间的第25位上； * 将这个位置置为1，表示存在这个数。 由于bitmap的数据存储方式，具有升序排序的性质。 ## 代码实现 ```cpp class Bitmap { public: Bitmap() { // 多开辟一个空间,原因是数组只能表示区间[0,size) bits.resize((INT_MAX >> 5) + 1); } void bitmapSet(int val) { int index = val >> 5; // 相当于除以32，用移位操作可提高性能 int offset = val % 32; bits[index] |= (1 << offset); int capacity = bits.capacity(); } bool bitmapGet(int val) { int index = val >> 5; // 第几个区间 int offset = val % 32; // 偏移位数 return bits[index] & (1 << offset); } private: vector<unsigned int> bits; }; ```