实现大量数据的快速排序、查找、去重——BitMap（位图法）
问题引子
有1千万个随机数，随机数的范围在1到1亿之间。现在要求写出一种算法，将1到1亿之间没有在随机数中的数求出来。
BitMap（位图法）原理
用1位来标记一个数据是否出现过，0表示没有出现过，1表示出现过。使用的时候根据此位是否为0来判断此数是否存在。
用一个位（bit）来标记某个数据的存放状态，由于采用了位为单位来存放数据，所以节省了大量的空间。
一个1G的空间，有 8*1024*1024*1024bit，也就是大约可以表示85亿个不同的数。
BitMap（位图法）实现
public class BitMap {/*** 定义标记数据是否存在的数组*/private long[] words;/*** 定义需要标记数据的个数*/private int capacity;public BitMap(int capacity) {this.capacity = capacity;/* 1byte(字节)能存储8bit(位)数据，1long(长整型)占8个byte，那么capacity数据需要多少个long呢？* (capacity-1)/64+1,右移6位相当于除以64*/int length = ((this.capacity - 1) >> 6) + 1;words = new long[length];}// 标记数据public void set(int bitIndex) {// bitIndex/64得到long[] words的wordIndexint wordIndex = bitIndex >> 6;// // bitIndex%64得到在byte[index]的位置// int position = bitIndex & 0x3F;// // 将1左移position后，那个位置自然就是1，然后和以前的数据做|，这样，那个位置就替换成1了。// words[wordIndex] |= 1 << position;// 此步操作等价于上述注释的两步操作words[wordIndex] |= 1L << bitIndex;}// 判断数据是否存在public boolean contain(int bitIndex) {// bitIndex/64得到long[] words的wordIndexint wordIndex = bitIndex >> 6;// bitIndex%64得到在byte[index]的位置int position = bitIndex & 0x3F;// 将1左移position后，那个位置自然就是1，然后和以前的数据做&，判断是否为0即可return (words[wordIndex] & (1 << position)) != 0;}// 清除数据public void clear(int bitIndex) {// bitIndex/64得到long[] words的wordIndexint wordIndex = bitIndex >> 6;// bitIndex%64得到在byte[index]的位置int position = bitIndex & 0x3F;// 将1左移position后，那个位置自然就是1，然后对取反，再与当前值做&，即可清除当前的位置了.words[wordIndex] &= ~(1 << position);}}
问题解决：
public static void main(String[] args) {int oneBillion = 1000000000;int tenMillion = 100000000;BitMap bitmap = new BitMap(oneBillion);Random random = new Random();// 放入随机数for (int i = 0; i < tenMillion; i++) {bitmap.set(random.nextInt(oneBillion));}// 输出没有在随机数中的数字for (int i = 0; i < oneBillion; i++) {if (!bitmap.contain(i)) {System.out.println(i);}}}
JDK提供的BitMap（位图法）实现类
// 不需要自己实现，可以直接使用jdk提供的BitSet类java.util.BitSet
使用场景
对海量数据进行一些统计工作，比如日志分析、用户数统计等。