有一道流传广泛的面试题：
给你一台 4G 内存的机器，一组 20 亿个无序正整数，如何快速地判断一个正整数 N 是否在这组数字中？或者如何快速地对这组数据排重后排序？
让我们先算算 20 亿个整数会占用多大的内存空间，Java 的 int 类型占用 4 个字节，那么 20 亿 * 4 再换算成 G 大约是 7.5G，大于题目中 4G 内存的限制，无法一次性地放到内存中；
这时候有些伙伴会说：“把数据放到磁盘上，然后分批将数据读取到内存中就行查询”，但是这种方法会导致多次磁盘 IO，而且只能解决第一个查找的问题，排序就没有办法做到了。
BitMap 的概念
BitMap 能够很好地解决这个问题；它是用一个 Bit 位来标记某个元素对应的 Value， 而 Key 即是该元素，比如我们初始化一个类型为 bit、长度为 8 的数组，数组下标 0-7，数组中的内容 1 表示存在，0 表示不存在，那么：
00000001 下标为 0 的位置，对应值是1，那么表示 0；同理：
00000010 表示 1；
00000100 表示 2；
00001000 表示 3；
…
10000000 表示 7；
如果一组数据 {2,3,4,7} 放到同一个数组中的话，就是 10011100：
如果按照 int 数组存储，{2,3,4,7} 需要 4 * 4 * 8 个 bit 才能存储的数据，但是现在 BitMap 只需要 8 个 bit 就可以存储，很大地节省了存储空间，并且排重后的排序也变的非常简单了；如果用 byte 实现的话，只需要 1 个 byte 就可以（1 byte = 8 bits）。
如果增加了一个数字 10 呢，那么 1 个 byte 就不够了：
数据结构及初始化
我们可以得知，BitMap 的容量大小取决于最大的那个数值，比如要存储 {2,3,4,7,10}：
- 如果用 bit 数组实现（假如有的话），那么需要 10 + 1 个长度；
- 如果是用 byte 数组实现，那么需要 10/8 + 1 个长度；
- 如果是用 int 数组实现，那么就需要 10/32 + 1 个长度（1 个 int 等于 4 个 bytes，等于 32 个 bits）；
明白了这点之后，一个简单的 BitMap 数据结构也就可以确定了：
public class BitMap {
//数据
private byte[] bits;
//最大值
private int max_value;
//容量
private int capacity;
/**
* 初始化
* @param capacity
*/
public BitMap(int max_value){
this.max_value = max_value;
//1bit存储8个数据，存储最大值为 max_value 的数组需要 max_value/8+1 个 byte，除以8就是右移3位
this.capacity = (max_value >> 3 ) + 1;
bits = new byte[capacity];
}
}
添加数据
添加数据，需要快速地定位到这个元素要存到整个数组中的哪个位置，这里有两个概念：
- 索引号 index：数据保存在整个数组的哪个下标中；
- 位置号 position：数据在这个下标元素的哪个位置；
比如 10 保存在 index = 1，position = 2（从 0 开始） 这个位置中，经推算可得：
index = N / 8
position = N % 8
知道了 10 保存的位置之后，怎么把对应位置的数据更改成 1 呢？可以用“位或”运算。将 10 添加到 BitMap 中的完整步骤如下：
- 计算 index = 10/8 = 1 ；
- 计算 position = 10%8 = 2 ；
- 将 byte[1] 的数据与 0000100 做“位或”运算，其中 0000100 是通过对 1 左移 2 得到。
完整的代码如下：
public void add(int num){
//数据保存在整个数组的哪个下标中
int index = num / 8;
//数据在这个下标元素的哪个位置
int position = num % 8;
bits[index] |= 1<<position;
}
判断数字是否存在
知道了如何判断数字的索引号和位置号之后，判断数字是否存在也就容易了，直接使用“位与”运算，代码如下：
public boolean contains(int num){
if(num > max_value){
return false;
}
//数据保存在整个数组的哪个下标中
int index = num / 8;
//数据在这个下标元素的哪个位置
int position = num % 8;
return (bits[index] & 1<<position) != 0;
}
测试
让我们做一下测试吧：
public class BitMapTest {
public static void main(String[] agrs){
BitMap bm = new BitMap(100);
bm.add(1);
bm.add(12);
bm.add(14);
bm.add(51);
bm.add(71);
bm.add(100);
System.out.println("12:" + (bm.contains(12)?"存在":"不存在"));
System.out.println("13:" + (bm.contains(13)?"存在":"不存在"));
System.out.println("51:" + (bm.contains(51)?"存在":"不存在"));
System.out.println("66:" + (bm.contains(66)?"存在":"不存在"));
System.out.println("100:" + (bm.contains(100)?"存在":"不存在"));
}
}
运行结果：
12:存在
13:不存在
51:存在
66:不存在
100:存在
从结果可以看到，判断的都很准确，当然这只是一个最简单的BitMap实现，它还存在着很多问题，比如我们必须知道数据中最大的那个数字是多少，这个可以采用动态扩容的方式解决；
在 JDK 中，已经有对应实现的数据结构类 java.util.BitSet，我们可以不用强撸 BitMap，直接使用 BitSet 就好了，或者使用谷歌封装的 EWAHCompressedBitmap。
优缺点
优点：
- 占用内存空间低，可以极大地节约空间；
- 运算效率高，查找、去重都不需要遍历全部数据；
缺点：
- 所有的数据不能重复，相当于直接就是排重过的；
- 如果数据只有两个：1 和 10000000，使用 BitMap 得不偿失，只有当数据比较密集时才有优势。
本章节介绍了 BitMap 的概念和基本实现，后续会介绍 BitMap 在实际开发中的应用。