BitSetjava 集合

一、BitSetjava 集合

BitSet是Java中基于二进制位的高效集合，主要用于存储大量"开-关"信息。它的主要优势在于空间效率，但访问速度可能不如固定类型数组。BitSet的最小长度是64位，这意味着如果需要存储小于64位的数据，可能会浪费资源。在这种情况下，建议自定义类来存储特定的标志位。

在使用过程中，BitSet的大小会随元素增加动态调整，但在早期版本的Java（如1.0）中，这种动态扩展存在一些问题。例如，当创建一个大于64位的BitSet时，尝试设置高于当前分配空间的位（如1024）可能会引发错误。这是由于早期版本的BitSet在扩展处理上存在缺陷。在Java 1.1及后续版本中，这个问题得到了修正，但针对Java 1.0，需要特别注意避免使用BitSet的此类问题。

以下代码展示了如何使用BitSet处理不同类型的数值，并演示了1.0版本的问题。在测试大于64位的BitSet时，务必注意边界处理，以避免潜在的异常。

二、BitMap和BitSet

Bit-map的基本思想就是用一个bit位来标记某个元素对应的Value，而Key即是该元素。由于采用了Bit为单位来存储数据，可以很大力度的节省空间，常用于对大量整数做去重和查询操作。

java中 int类型占用4个字节=4*8=32bit

从上述结果来看，按位存储比按字节存储数字节约了（7.45/0.233-1约等于31倍空间），而且按字节存储根据内存4G的要求无法一次性在内存中进行处理。

众所周知，每一位的取值无非就是0和1，给每一位编号，那么用0表示数字存在，1表示数字不存在。

假如现在有一个字节也就是8位的空间，那么按照BitMap，可以表示8个数字，

按照上图所示，该字节的8位表示了整数数组[6,5,2,0]。那么java中int类型占用了4个字节，也就是32位，那么就可以最多表示32个数字。超过32位数字呢？那就使用两个以上int去表示。

假设我们要存储的数字最大值位N，则申请int temp[1+N/32]的数组空间，其中：

给定任一整数M，M数字所在数组中的下标位置就应该是M/32，M数字所在的位就是M%32

temp[index]=temp[index]|(1<<(M%32))

根据bitMap的原理可知，想要清除掉一个数字，那就是将对应的位置0

temp[index]=temp[index]&（~(1<<(M%32))）

根据每一位代表一个数字，1表示存在，0表示不存在，那么只需要判断整数对应位是否位1即可

temp[index]&(1<<(M%32)！= 0？"存在":"不存在"

BitSet就是实现了Bit-Map算法。BitSet位于java.util包下，从JDK1.0开始就已经有了。该类实现了一个按需增长的位向量。位集的每一个组件都有一个boolean类型的值。BitSet的每一位代表着一个非负整数。可以检查、设置、清除单个位。一个BitSet可以通过逻辑与、逻辑或、逻辑异或去修改另一个BitSet。默认情况下，所有位的标识都是false。

BitSet有三种构造方法，我们直接来看无参构造器

可以看到BitSet是使用long数组存储。那么long类型占用8个字节，即64位，一个long类型可表示64个数字。默认设置BitSet可表示最大的位数为64位。与上述自己实现的基本类似。

可以看到JDK中的BitSet实现原理与第三节中一样，采用Bit-Map思想，BitSet封装较多的API，可供开发者们随意使用。

三、BitSet简介

BitSet即位图，是一个很长的“0/1”序列，他的功能就是存储0或者1。

他的这个特点使得在java环境中存储一个数要比直接存一个int节省很多内存空间（一个int占4个字节32位，而用BItSet“存放”一个数只需要1个位）。

比如我们有{1,3,5,7}需要存放，内存中占用了4个int的长度即32*4(bit)，如果使用BitSet，就是这个样的[...,1,0,1,0,1,0,1]，只需要占用几个bit就可以表示。1个G的内存有8* 1024* 1024* 1024= 8.58* 10^9个bit，也就是可以存放85亿+个数。

BitSet的初始大小为1个long的大小，即8字节64个bit。如果我们创建的BitSet指定了位数，系统会根据情况取成64的整数倍个bit，即整数个long的位数，这样做是为了内存补齐。

BitSet适合用于无重复，整数，常用于大数据场景或者日志统计。