JAVA中BitSet就是“位图”数据结构，根据“位图”的语义，数据的存在性可以使用bit位上的1或0来表示；一个bit具有2个值：0和1，正好可以用来表示false和true。对于判断“数据是否存在”的场景，我们通常使用HashMap来存储，不过hashmap这个数据结构KEY和Value的保存需要消耗较多的内存，不适合保存较多的数据，即大数据场景；比如在有10亿条URL中判定一个“www.baidu.com/a”是否存在，如果我们使用常规的hashmap来保存将是不现实的，因为URL本身需要占据较多的内存而无法直接操作。如果我们使用bitset来保存，那么可以对一条URL求hashcode，并将数字映射在bitset上，那么事实上它只需要bitset上的一个bit位即可，即我们1位空间即可表达一个URL字符串的存在性。
所谓“存在性”，就是通过BitSet来检测一个数字是否存在。
bitset 原理
JAVA中，一个long型数字占用64位空间，根据上述“位图”的概念，那么一个long型数字（4个字节）就可以保存64个数字的“存在性”状态(无碰撞冲突时，即true、false状态)。比如50个数字{0,1,10,...63}，判定“15”是否存在，那么我们通常会首先将这些数字使用数组或者hashmap保存，然后再去判定，那么保存这些这些数据需要占用64 * 64位；如果使用位图，那么一个long型数字即可。（如果换成50个字符串，那么其节约的空间可能更大）。
- BitSet只面向数字比较，比如set(int a,boolean value)方法，将数字a在bitSet中设定为true或者false；此后可以通过get(int a)方法检测结果。对于string类型的数据，如果像使用BitSet，那么可以将其hashcode值映射在bitset中。
- 首先我们需要知道：1，1<<64，1<<128，1<<192...等，这些数字的计算结果是相等的（位运算）；这也是一个long数字，只能表达连续的(或者无冲突的)64个数字的状态，即如果把数字1在long中用位表示，那么数字64将无法通过同一个long数字中位表示--冲突；BitSet内部，是一个long[]数组，数组的大小由bitSet接收的最大数字决定，这个数组将数字分段表示[0,63],[64,127],[128,191]...。即long[0]用来存储[0,63]这个范围的数字的“存在性”，long[1]用来存储[64,127]，依次轮推，这样就避免了位运算导致的冲突.
|------------|----------|----------|----------|----------| | | 数字范围 [0,63] [64,127] [128,191] ... | |------------|----------|----------|----------|----------| | |long数组索引 0 1 2 ... | |------------|----------|----------|----------|----------| - bitSet内部的long[]数组是基于向量的，即随着set的最大数字而动态扩展。数组的最大长度计算：
(maxValue - 1) >> 6 + 1 - BitSet中set方法伪代码：
public void set(int number){ int index = number >> 6;//找到number需要映射的数组的index if(index + 1 > length){ ensureCapacity(index + 1);//重新扩展long[]数组 } long[index] |= (1L << number);//冲突解决 }
