java数据结构与算法总结(二十三)--通过BitSet源码来理解BitMap算法

今天药忘吃喽~ 2022-10-31 04:17 284阅读 0赞

[原文链接][Link 1]

BitMap是一种很常用的数据结构，它的思想的和原理是很多算法的基础，当然，并且在索引，数据压缩，海量数据处理等方面有广泛应用。

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

## 一、简介 ##

BitMap 是一种很常用的数据结构，它的思想和原理是很多算法的基础，比如Bloom Filter 。

BitMap 的基本原理就是用一个 bit 位来存放某种状态（如果理解不了，看完下文再回头来看即可），适用于拥有大规模数据，但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。  
它最大的一个特点就是对内存的占用极小，所以经常在大数据中被优化使用。

为什么说占用内存小呢？其实从名字就可以看出端倪，直译过来叫位图，但不是图形学里面的位图哦，关键单词是**Bit**。比如通过某种方法用一个 bit 来表示一个 int，这样的话内存足足压缩至 1/32（1 int = 4 byte = 32 bit，PS：理论计算而已，实操时并不会有 1/32 这么夸张，下文会解释），所以原先需要8G内存的数据，现在只需要256M，岂不乐哉？当然了，其中算法的一些概念在下文会详解。

## 二、初窥 BitMap ##

1、概念理解

所谓的 BitMap 就是用一个 Bit 位来标记某个元素对应的 Value， 而 Key 即是该元素。由于采用了 Bit 为单位来存储数据，因此在存储空间方面，可以大大节省。

比如有个 int 数组 \[2,6,1,7,3\]，内含5个元素，存储的空间大小为 5 \* 32 = 160 bit，取的时候，使用元素的下标来获取对应位上的元素。

但是如果换种思路，把元素的值作为下标，每个下标位使用 bit 来标记，有值则为1，否则为0，此时我们只需要在内存上开辟一个**连续的二进制位**空间，长度为8（因为上面数据最大的元素是7，但是需要考虑下标起点为0），则可以表示成：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xzeDIwMTc_size_16_color_FFFFFF_t_70][]

BitMap 最简单的说明图，蓝色代表有值

说明：初始化一个长度是8的 BitMap，初始值均为0，然后将\[2,6,1,7,3\]填入对应的下标处，上图中蓝色域，即将这几个下标处的值设置为1，所以表示为：**1 1 0 0 1 1 1 0**。此时占用的内存空间为 8 bit，而原来是 160 bit（顺便解释下上文提到的 1/32，因为我们开辟的是连续的内容空间，所以会有冗余）。

2、案例说明

① 案例一：还是上文的数组，需求是查询元素6是否在数组中。  
原先我们需要遍历整个数组，时间复杂度为 O(n);  
而现在我们只需要查验下标为6的字节是0还是1即可，如果是1，则代表存在，时间复杂度直接降为 O(1)。  
所以，**最直接的应用场景便是：**数据的查重。

② 案例二：有两个数组，判断这两个数组中的重复元素。  
原先的最浅显的做法是双层for循环进行判断比较。  
而现在，只需要将转换完成的两个BirMap进行与运算即可，如：11001110B & 10100000B = 10000000B，所有得出结果，只有元素 7 重复。  
当然，**最直接的应用场景是：**每个客户都有不同的标签，当需要查找同时符合标签a和标签b的客户的时候，只需要将标签a和标签b的客户查出来进行如上的**与运算**即可。

3、补充说明

① 实际使用的时候，并不会向上面一样很随意地将长度设置为8，一般会设置为32（int型）或64（long型），理由见下文 BitSet 源码即可。  
② 除了上文提到的与运算，当然了，逻辑或和逻辑异或操作都是OK的。  
③ 每个Bit位只能是0或1，所以只能代表true or false，当我们要进行少量统计的时候，可以使用2-BitMap，即每个位上可以使用 00、01、10、11来分别表示数量为 0、1、2，此时的 11 一般无意义。

## 三、BitSet 源码 ##

1、简述

对于 BitMap 这种经典的数据结构，在 Java 语言里面，其实已经有对应实现的数据结构类 java.util.BitSet 了（\*\**@since \*\*\*\*JDK1.0*），而 BitSet 的底层原理，其实就是用 long 类型的数组来存储元素，所以回过头来看上文提到的为什么实际使用的时候，长度一般会是有规则的，因为此处使用的是long类型的数组，而 1 long = 64 bit，所以数据大小会是64的整数倍。

/**
    * The internal field corresponding to the serialField "bits".
    */
    private  long[]  words;

至于 Java 中的 BitSet 为什么使用 long 数组而不使用 int 数组，我觉得应该是出于 Java 语言的性能考虑的，因为在进行**逻辑与等一系列位运算**的时候，是需要将两个数组中的元素一一进行位运算的，而使用 long 的一个好处是数组的长度减少了，从而遍历的次数也就减少了。

总之就是和场景有关系，抽象概念上就有点类似 Java 中字符串的匹配算法（indexOf）使用的是 BF（暴力检索）算法一样，为什么不用更优解呢？还不是因为更优解在少量数据的情况下反而是拖后腿的那一位。

2、成员变量

![ddcf42e55c04e1b74a3950cd33fefee5.png][]

3、构造方法

有参构造的参数代表的是元素的长度，不是数组的大小，比如传参1和64，数组的长度均为1，整个size均为64，但是传参65的时候，数组长度为2，size为128，因为数组是long类型，而一个long可以存储64个bit元素。

![0cd01187c29f324957ba6ba0365b29ae.png][]

BitSet 构造函数

4、 initWords 函数

该函数只在两个构造方法中调用，作用是初始化数组，而数组的长度则会通过 workIndex(nbits-1) + 1 来获取。

5、 wordIndex 函数

这个方法很重要， 它是用来获取某个数在 words 数组中的索引的，采用的算法是将这个数右移6位，why？因为 bitIndex >> 6 == bitIndex / (2^6) == bitIndex /64，而long就是64个字节。

![dcdceeec30866463f64f33ef59c555e9.png][]

获取元素在 work 数组中的下标

6、ensureCapacity 函数

又是一个很重要的方法，作用是动态扩容，因为在初始化的时候，我们并不知道将来会需要存储多大的数据。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xzeDIwMTc_size_16_color_FFFFFF_t_70 1][]

数组动态扩容

7、size 和 length 函数

size 方法很好理解，返回的其实就是数组的空间大小，即*数组长度64**。  
而 length 方法，看源码其实有点晦(qu)涩(qiao)，简言之，返回的是 BitSet 的“逻辑大小”，即**BitSet 中最高设置位的索引加 1*\* 。

举个栗子，一个 BitSet 中存储了两个元素，10和50，那么，此时这个 BitMap 的：size = 64；length = 51。

![9bdc2bca375cefa6a7ca0b2e8d469516.png][]

计算 length

8、题外话

其余的 set、get等方法暂不赘述，总之一句话，想要深刻理解 BitSet 的源码，对于二进制的计算需要有一定的掌握水准。不得不承认，BitSet 的源码，很多细节的设计太精妙了。

## 四、拓展 ##

如要论述拓展，要么就是论述场景的高层次应用，要么就是论述此算法的不足之处，此处各提一个点：

① **不足**：数据稀疏问题，比如三个元素(1,100,10000000)，则需要初始化的长度为 10000000，很不合理，此时可以使用 **Roaring BitMap** 算法来解决，而 Java 程序可以使用goolge的 \*\*EWAHCompressedBitmap \*\*来解决。

② **拓展**：数据碰撞问题，比如上文提到的爬虫应用场景是将URL进行哈希运算，然后将hash值存入BitMap之中，但是不得不面临一个尴尬的情况，那就是哈希碰撞，而**布隆算法**（**Bloom Filter**）就可以解决这个问题，为什么是拓展呢？因为它是以 BitMap 为基础的排重算法。

原文地址：[http://www.jetchen.cn/algorithm-bitmap-bitset/][http_www.jetchen.cn_algorithm-bitmap-bitset]

[Link 1]: https://www.jianshu.com/p/0f653d2302a0
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xzeDIwMTc_size_16_color_FFFFFF_t_70]: /images/20221024/1d808c83bd00451eb5e38ee40702b1a0.png
[ddcf42e55c04e1b74a3950cd33fefee5.png]: /images/20221024/586d5b9854b047488e676d997960a4b0.png
[0cd01187c29f324957ba6ba0365b29ae.png]: /images/20221024/8fd28c2ee7674520b5f89b99c5f5cb79.png
[dcdceeec30866463f64f33ef59c555e9.png]: /images/20221024/6244fb8e540047b1bca54bab0d2cc431.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xzeDIwMTc_size_16_color_FFFFFF_t_70 1]: /images/20221024/16287f943e0a45ccbcfb3f661c95a269.png
[9bdc2bca375cefa6a7ca0b2e8d469516.png]: /images/20221024/4f42d4d2476a4c1ba13f059863cbf6b3.png
[http_www.jetchen.cn_algorithm-bitmap-bitset]: http://www.jetchen.cn/algorithm-bitmap-bitset/