什么是 BigMap 算法
所谓 BitMap 就是用一个 bit 位来标记某个元素对应的 value，而 key 即是这个元素。由于采用bit为单位来存储数据，因此在可以大大的节省存储空间。
算法思想
32位机器上，一个整形，比如 int a; 在内存中占32bit，可以用对应的32个bit位来表示十进制的0-31个数，bitmap算法利用这种思想处理大量数据的排序与查询。
优点：
- 效率高，不许进行比较和移位
- 占用内存少，比如N=10000000;只需占用内存为N/8 = 1250000Bytes = 1.2M，如果采用int数组存储，则需要38M多
缺点：
- 无法对存在重复的数据进行排序和查找
示例：
申请一个int型的内存空间，则有4Byte，32bit。输入 4， 2, 1, 3时：
输入4：
输入2：
输入1：
输入3：
思想比较简单，关键是十进制和二进制bit位需要一个 map 映射表，把10进制映射到bit位上。
map映射表
假设需要排序或者查找的总数N=10000000,那么我们需要申请的内存空间为 int a[N/32 + 1].其中a[0]在内存中占32位,依此类推：
bitmap表为：
a[0] ------> 0 - 31
a[1] ------> 32 - 63
a[2] ------> 64 - 95
a[3] ------> 96 - 127
......
下面介绍用位移将十进制数转换为对应的bit位
位移转换
（1） 求十进制数 0-N 对应的在数组 a 中的下标
index_loc = N / 32即可，index_loc即为n对应的数组下标。例如n = 76, 则loc = 76 / 32 = 2,因此76在a[2]中。
（2）求十进制数0-N对应的bit位
bit_loc = N % 32即可，例如 n = 76, bit_loc = 76 % 32 = 12
（3）利用移位0-31使得对应的32bit位为1
代码示例(c语言)
#include#include #define SHIFT 5#define MASK 0x1F/** * 设置所在的bit位为1 * * T = O(1) * */void set(int n, int *arr){ int index_loc, bit_loc; index_loc = n >> SHIFT; // 等价于n / 32 bit_loc = n & MASK; // 等价于n % 32 。 h%2^n = h & (2^n -1) arr[index_loc] |= 1 << bit_loc;}/** * 初始化arr[index_loc]所有bit位为0 * * T = O(1) * */void clr(int n, int *arr){ int index_loc; index_loc = n >> SHIFT; arr[index_loc] &= 0;}/** * 测试n所在的bit位是否为1 * * T = O(1) * */int test(int n, int *arr){ int i, flag; i = 1 << (n & MASK); flag = arr[n >> SHIFT] & i; return flag;}int main(void){ int i, num, space, *arr; while (scanf("%d", &num) != EOF) { // 确定大小&&动态申请数组 space = num / 32 + 1; arr = (int *)malloc(sizeof(int) * space); // 初始化bit位为0 for (i = 0; i <= num; i ++) clr(i, arr); // 设置num的比特位为1 set(num, arr); // 测试 if (test(num, arr)) { printf("成功！\n"); } else { printf("失败!\n"); } } return 0;}
MARK 补充 Java 实现
参考：