【java基础】BitSet基本说明和使用

ゝ一纸荒年。 2023-09-25 16:28 65阅读 0赞

### 文章目录 ###

*  基本介绍
 *  基本使用
 *   *  创建对象
     *  设置值
     *  获取值
     *  遍历BitSet
     *  BitSet转数组
 *  原理说明
 *  总结

# 基本介绍 #

Java平台的BitSet类用于存储一个位序列（它不是数学上的集，如果称为位向量或位数组可能更为合适)。如果需要高效地存储位序列（例如，标志），就可以使用位集。由于位集将位包装在字节里，所以使用位集要比使用Boolean对象的ArrayList高效得多。

说人话就是使用位来存储boolean信息，0表示假，1表示真。

# 基本使用 #

这里介绍一些BitSet的基本用法

## 创建对象 ##

// 使用无参构造器，还有2个有参构造器使用不多
            BitSet bitSet = new BitSet();

## 设置值 ##

可以将对于比特位的值设置为1（默认是0）

// 把bit位2位置设置为1
            bitSet.set(2);
            
            // 把3-5设置为1，[) 左闭右开
            bitSet.set(3, 5);
            
            // 把bit位2设置位0
            bitSet.set(2, false);
            
            // 把3-5设置为0，[) 左闭右开
            bitSet.set(3, 5, false);

## 获取值 ##

可以获取指定位置上的bit位

// 得到bit位2的值，0返回false，1返回true
            boolean flag = bitSet.get(2);
    
            // 得到2-5位置的比特信息，[) 左闭右开
            BitSet subBitSet = bitSet.get(1, 5);

## 遍历BitSet ##

**第一种方式就是通过stream流来完成**

// 使用stream流来完成
            BitSet bitSet = new BitSet();
            bitSet.set(5);
            bitSet.set(10);
            bitSet.set(16);
            bitSet.stream().forEach(System.out::println);

上面代码输出如下

![在这里插入图片描述][657790abf54d42b69b475dbf5f99e598.png]

--------------------

**第二种方式就是通过nextSetBit来完成**

// 使用nextSetBit流来完成
            BitSet bitSet = new BitSet();
            bitSet.set(5);
            bitSet.set(10);
            bitSet.set(16);
            int k = 0;
            while ((k = bitSet.nextSetBit(k)) != -1) {
        
                System.out.println(k);
                k++;
            }

nextSetBit会返回在指定的起始索引上或之后出现的第一个被设置为true的位的索引。如果不存在这样的位，则返回-1。下面为该方法的源代码注释  
![在这里插入图片描述][e6221b5c8aea4d7fb0d0e84e1fd748a0.png]

上面的代码输出如下

![在这里插入图片描述][912b86f7d6cd4b5db796952a85737570.png]

## BitSet转数组 ##

我们可以将BitSet存储的信息转化为数组，通过stream完成

BitSet bitSet = new BitSet();
            bitSet.set(5);
            bitSet.set(10);
            bitSet.set(16);
            int[] nums = bitSet.stream().toArray();
            System.out.println(Arrays.toString(nums));

--------------------

# 原理说明 #

前面说了，BitSet是通过位的0和1来存储信息的，但是java并没有bit这种数据类型。于是java就是通过long来完成这个功能的，一个long表示64位，相当于一个long就可以表示0-63，2个long就可以表示0-127，以此类推

BitSet底层就是通过words数组来存储bit信息的，通过各种位操作来完成  
![在这里插入图片描述][0b955743c9714239aea50b635569c9d0.png]

这里举几个例子，我们set(1)，那么就会算出设置的值是第几个64，这里显然就是第0个(数组从0开始)，然后将word\[0\]的63-1位设置为1(从0开始)，也就是从右往左的第 x % 64位设置为1。set(1)，那么words\[0\]应该等于 2，继续set\[2\]，那么words\[0\]应该等于4+2=6

下面就通过debug几个不同的值来深入了解

![在这里插入图片描述][90dc44fbfda94a85b5371a90915c6aca.png]  
![在这里插入图片描述][8e91c5059c594f26817e2a6b3361f09f.png]  
![在这里插入图片描述][c0d2b973fac046a88ca6a8de36bda227.png]

![在这里插入图片描述][fce21b108e8b441b824b6dd93a810405.png]  
![在这里插入图片描述][2ea7805cb283443a87525ec92199288e.png]

> 同过上面的例子，想必大家对BitSet的存储方式应该有一定认识了，下面就来看一下set的源代码

![在这里插入图片描述][0a3f9c7e313941468f3df05d5dfa5fca.png]

可以发现，其实就是先获得该bitIndex要放到words的哪个索引，然后通过位操作完成设置。

# 总结 #

BitSet由于使用bit位来存储信息，所以占用空间会比boolean数组使用空间更小，并且带有去重功能。

该数据结构的一个应用就是10亿个手机号码去重（面试造火箭）

[657790abf54d42b69b475dbf5f99e598.png]: https://img-blog.csdnimg.cn/657790abf54d42b69b475dbf5f99e598.png
[e6221b5c8aea4d7fb0d0e84e1fd748a0.png]: https://img-blog.csdnimg.cn/e6221b5c8aea4d7fb0d0e84e1fd748a0.png
[912b86f7d6cd4b5db796952a85737570.png]: https://img-blog.csdnimg.cn/912b86f7d6cd4b5db796952a85737570.png
[0b955743c9714239aea50b635569c9d0.png]: https://img-blog.csdnimg.cn/0b955743c9714239aea50b635569c9d0.png
[90dc44fbfda94a85b5371a90915c6aca.png]: https://img-blog.csdnimg.cn/90dc44fbfda94a85b5371a90915c6aca.png
[8e91c5059c594f26817e2a6b3361f09f.png]: https://img-blog.csdnimg.cn/8e91c5059c594f26817e2a6b3361f09f.png
[c0d2b973fac046a88ca6a8de36bda227.png]: https://img-blog.csdnimg.cn/c0d2b973fac046a88ca6a8de36bda227.png
[fce21b108e8b441b824b6dd93a810405.png]: https://img-blog.csdnimg.cn/fce21b108e8b441b824b6dd93a810405.png
[2ea7805cb283443a87525ec92199288e.png]: https://img-blog.csdnimg.cn/2ea7805cb283443a87525ec92199288e.png
[0a3f9c7e313941468f3df05d5dfa5fca.png]: https://img-blog.csdnimg.cn/0a3f9c7e313941468f3df05d5dfa5fca.png