前言
前几天的面试有问到海量数字去重的问题，当时知道能用位图法来解决，但却对其原理不是太了解所有有了这篇文章。
什么是位图法？
位图法即bitmap，就是使用每一个bit来存储数据状态，来表示数据是否存在，适合用于大规模的数据去重。
由上图可以知道，每一 bit 位代表一位数字，bit置为1表示数据存在。上图数组是从0开始的，可能出
现数字最小值很大的问题，那么小于最小值的bit位就空置了，所以我们需要关注最大数与最小数，这样
方便设置数组的大小。除了最大值与最小值的问题，我们还需关注数据是否有负数，如果有我们就需要使
用2个 bit 来存储数据。
位图法解决什么样的问题？
- 给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在
那40亿个数当中？
首先，将这40亿个数字存储到`bitmap`中，然后对于给出的数，判断是否在 `bitmap` 中即可。 - 使用位图法判断整形数组是否存在重复
遍历数组，一个一个放入 `bitmap`，并且检查其是否在 `bitmap` 中出现过，如果没出现放入，否则即为重复的元素。
- 使用位图法进行整形数组排序
首先遍历数组，得到数组的最大最小值，然后根据这个最大最小值来缩小`bitmap` 的范围。这里需要注意对于int的负数，都要转化为 unsigned int 来处理，而且取位的时候，数字要减去最小值。
- 在2.5亿个整数中找出不重复的整数，注，内存不足以容纳这2.5亿个整数
采用2-`bitmap`（每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义）。其实，这里可以使用两个普 通的`bitmap`，即第一个`bitmap`存储的是整数是否出现，如果再次出现，则在第二个`bitmap`中设置即可。这样的话，就可以使用简单的1- `bitmap`了。
BitSet源码分析
set源码
//BitSet 使用 long 数组存储bit位,一个long可以存64位
public void set(int bitIndex) {
if (bitIndex < 0)
throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
//获取数组下标
int wordIndex = wordIndex(bitIndex);
//如果数组长度小了，扩容
expandTo(wordIndex);
//1L << bitIndex 是设置该 long 元素的位置，与 words[wordIndex]
//或运算是为了保留前面设置的数
words[wordIndex] |= (1L << bitIndex); // Restores invariants
checkInvariants();
}
private static int wordIndex(int bitIndex) {
//bitIndex 除以 64，即获取long数组的下标
return bitIndex >> 6;
}
