Java BitSet（位集）

原理简介：

Java平台的BitSet用于存放一个位序列，如果要高效的存放一个位序列，就可以使用位集(BitSet)。由于位集将位包装在字节里，所以使用位集比使用Boolean对象的List更加高效和更加节省存储空间。

BitSet是位操作的对象，值只有0或1即false和true，内部维护了一个long数组，初始只有一个long，所以BitSet最小的size是64，当随着存储的元素越来越多，BitSet内部会动态扩充，一次扩充64位，最终内部是由N个long来存储。

默认情况下，BitSet的所有位都是false即0。

在没有外部同步的情况下，多个线程操作一个BitSet是不安全的。

一个1GB的空间，有8*1024*1024*1024 = 8.58*10^9bit，也就是1GB的空间可以表示85亿多个数。

应用场景：

1. 统计一组大数据中没有出现过的数；

将这组数据映射到BitSet，然后遍历BitSet，对应位为0的数表示没有出现过的数据。

2. 对大数据进行排序；

将数据映射到BitSet，遍历BitSet得到的就是有序数据。

3. 在内存对大数据进行压缩存储等等。

一个GB的内存空间可以存储85亿多个数，可以有效实现数据的压缩存储，节省内存空间开销。

为什么BitSet使用long数组做内部存储？

JDK选择long数组作为BitSet的内部存储结构是出于性能的考虑，因为BitSet提供and和or这种操作，需要对两个BitSet中的所有bit位做and或者or，实现的时候需要遍历所有的数组元素。使用long能够使得循环的次数降到最低，所以Java选择使用long数组作为BitSet的内部存储结构。

从数据在栈上的存储来说，使用long和byte基本是没有什么差别的，除了编译器强制地址对齐的时候，使用byte最多会浪费7个字节(强制按照8的倍数做地址对其)，另外从内存读数组元素的时候，也是没有什么区别的，因为汇编指令有对不同长度数据的mov指令。所以说，JDK选择使用long数组作为BitSet的内部存储结构的根本原因就是在and和or的时候减少循环次数，提高性能。

例如我们进行BitSet中的and, or,xor操作时，要对整个bitset中的bit都进行操作，需要依次读出bitset中所有的word，如果是long数组存储，我们可以每次读入64个bit,而int数组存储时，只能每次读入32个bit。另外我们在查找bitset中下一个置为1的bit时,word首先会和0进行比较，如果word的值为0，则表示该word中没有为1的bit，可以忽略这个word，如果是long数组存储，可以一次跳过64个bit，如果是int数组存储时，一次只能跳过32个bit。

（本段来源：知乎 http://www.zhihu.com/question/21061816）

BitSet API

BitSet()
创建一个新的位 set。

BitSet(int nbits)
创建一个位 set，它的初始大小足以显式表示索引范围在 0 到 nbits-1 的位。

`void`	`and(BitSet set)` 对此目标位 set 和参数位 set 执行逻辑与操作。
`void`	`andNot(BitSet set)` 清除此 `BitSet` 中所有的位，其相应的位在指定的 `BitSet` 中已设置。
`int`	`cardinality()` 返回此 `BitSet` 中设置为 `true` 的位数。
`void`	`clear()` 将此 BitSet 中的所有位设置为 `false`。
`void`	`clear(int bitIndex)` 将索引指定处的位设置为 `false`。
`void`	`clear(int fromIndex, int toIndex)` 将指定的 `fromIndex`（包括）到指定的 `toIndex`（不包括）范围内的位设置为 `false`。
`Object`	`clone()` 复制此 `BitSet`，生成一个与之相等的新 `BitSet`。
`boolean`	`equals(Object obj)` 将此对象与指定的对象进行比较。
`void`	`flip(int bitIndex)` 将指定索引处的位设置为其当前值的补码。
`void`	`flip(int fromIndex, int toIndex)` 将指定的 `fromIndex`（包括）到指定的 `toIndex`（不包括）范围内的每个位设置为其当前值的补码。
`boolean`	`get(int bitIndex)` 返回指定索引处的位值。
`BitSet`	`get(int fromIndex, int toIndex)` 返回一个新的 `BitSet`，它由此 `BitSet` 中从 `fromIndex`（包括）到 `toIndex`（不包括）范围内的位组成。
`int`	`hashCode()` 返回此位 set 的哈希码值。
`boolean`	`intersects(BitSet set)` 如果指定的 `BitSet` 中有设置为 `true` 的位，并且在此 `BitSet` 中也将其设置为`true`，则返回 ture。
`boolean`	`isEmpty()` 如果此 `BitSet` 中没有包含任何设置为 `true` 的位，则返回 ture。
`int`	`length()` 返回此 `BitSet` 的“逻辑大小”：`BitSet` 中最高设置位的索引加 1。
`int`	`nextClearBit(int fromIndex)` 返回第一个设置为 `false` 的位的索引，这发生在指定的起始索引或之后的索引上。
`int`	`nextSetBit(int fromIndex)` 返回第一个设置为 `true` 的位的索引，这发生在指定的起始索引或之后的索引上。
`void`	`or(BitSet set)` 对此位 set 和位 set 参数执行逻辑或操作。
`void`	`set(int bitIndex)` 将指定索引处的位设置为 `true`。
`void`	`set(int bitIndex, boolean value)` 将指定索引处的位设置为指定的值。
`void`	`set(int fromIndex, int toIndex)` 将指定的 `fromIndex`（包括）到指定的 `toIndex`（不包括）范围内的位设置为 `true`。
`void`	`set(int fromIndex, int toIndex, boolean value)` 将指定的 `fromIndex`（包括）到指定的 `toIndex`（不包括）范围内的位设置为指定的值。
`int`	`size()` 返回此 `BitSet` 表示位值时实际使用空间的位数。
`String`	`toString()` 返回此位 set 的字符串表示形式。
`void`	`xor(BitSet set)` 对此位 set 和位 set 参数执行逻辑异或操作。