一、简介

Bit-map就是用一个bit位来标记某个元素对应的Value， 而Key即是该元素。由于采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节省。

可以把16GB的存储空间缩小为16GB/32 = 512M,就可以大大减少读取文件的工作。直接读一次文件存入内存，然后遍历输出就完成了排序。

优点：

1.运算效率高，不许进行比较和移位；

2.占用内存少，比如N=10000000；只需占用内存为N/8=1250000Byte=1.25M。 

10000000个bit占用的空间：

1byte = 8bit

1kb = 1024byte

1mb = 1024kb

占用的空间为：10000000/8/1024/1024mb。

大概为1mb多一些。

缺点：

       所有的数据不能重复。即不可对重复的数据进行排序和查找。  

二、具体思路

1个int占4字节即4*8=32位，那么我们只需要申请一个int数组长度为 int tmp[1+N/32]即可存储完这些数据，其中N代表要进行查找的总数，tmp中的每个元素在内存在占32位可以对应表示十进制数0~31,所以可得到BitMap表:

tmp[0]:可表示0~31

tmp[1]:可表示32~63

tmp[2]可表示64~95

即：

1.求十进制0-N对应在数组a中的下标： n/32 

2.求0-N对应0-31中的数：N%32=M

3.利用移位0-31使得对应32bit位为1: 1<<M，并置1;

三、Bit-Map的应用

1）可进行数据的快速查找，判重，删除，一般来说数据范围是int的10倍以下。

 2）去重数据而达到压缩数据

四、在Java中的实现

 @Testpublic void size() {int [] array = new int [] {3,64,65,3};BitSet bitSet  = new BitSet();//默认 8byte = 64bitSystem.out.println(bitSet.size());//将数组内容组bitmapfor(int i=0;i<array.length;i++){bitSet.set(array[i], true);}System.out.println(bitSet.size());System.out.println(bitSet.get(3));System.out.println(bitSet.get(64));System.out.println(bitSet.get(66));}Console:
64
128
true
true
false