Bitmap在Java中的实现和应用

1.40亿数据排序问题

给定一个最多包含40亿个随机排列的32位整数的顺序文件，找出一个不在文件中的32位整数(在文件中至少缺失这样一个数——为什么？)。在具有足够内存的情况下，如何解决该问题？（编程珠玑）

2.应用BitMap存储大数据

数据的存在性可以使用bit位上的1或0来表示；一个bit具有2个值：0和1，正好可以用来表示false和true。

对于判断“数据是否存在”的场景，我们通常使用HashMap来存储，不过hashmap这个数据结构KEY和Value的保存需要消耗较多的内存，不适合保存较多的数据，比如上面的问题中，如果使用哈希表，每条记录保存一个int型的key和一个boolean型的value，
每条至少需要4字节，假设40亿条数据全部不相同，40亿条记录占据160亿字节，即需要16G内存，明显太高。

如何减少数据占用存储空间可以使用位示图解决，java.util.BitSet可以按位存储，提供了BitMap的典型实现。

比如有一堆数字，需要存储，source=[3,5,6,9]
用int就需要4*4个字节。
java.util.BitSet可以存true/false。
如果用java.util.BitSet，则会少很多，其原理是：
1，先找出数据中最大值maxvalue=9
2，声明一个BitSet bs,它的size是maxvalue+1=10
3，遍历数据source，bs[source[i]]设置成true.
最后的值是：
(0为false;1为true)
bs [0,0,0,1,0,1,1,0,0,1]
3, 5,6, 9
这样一个本来要int型需要占4字节共32位的数字现在只用了1位，这样就省下了很大空间。

常见的应用场景是那些需要对海量数据进行一些统计工作的时候，比如日志分析、用户数统计等等。
如统计40亿个数据中没有出现的数据，将40亿个不同数据进行排序等。

3.如何应用BitSet

BitSet实现了Vector接口，BitSet中数组大小会随需要增加，位的值为布尔型，
bitSet内部是通过一个long[]数组实现的，
所以初始大小为64bit，初始值均为“false”。

先看一下API中的说明
This class implements a vector of bits that grows as needed. 
BitSet类实现了一个按需增长的比特向量，
Each component of the bit set has a boolean value. 
每个元素都有一个boolean值，
The bits of a BitSet are indexed by nonnegative integers.
使用非负整数对每个位进行索引，
Individual indexed bits can be examined, set, or cleared. 
可以对每个编入索引的位进行测试、设置或者清除。
One BitSet may be used to modify the contents of another BitSet through logical AND, logical inclusive OR, and logical exclusive OR operations.
通过逻辑与、逻辑或和逻辑异或操作，可以使用一个 BitSet 修改另一个 BitSet 的内容。

By default, all bits in the set initially have the value false.
默认情况下，set 中所有位的初始值都是 false。

Every bit set has a current size, which is the number of bits of space currently in use by the bit set. Note that the size is related to the implementation of a bit set, so it may change with implementation. The length of a bit set relates to logical length of a bit set and is defined independently of implementation.
每个位 set 都有一个当前大小，也就是该位 set 当前所用空间的位数。注意，这个大小与位 set 的实现有关，所以它可能随实现的不同而更改。位 set 的长度与位 set 的逻辑长度有关，并且是与实现无关而定义的。