BitSet原理以及应用

╰半橙微兮° 2022-11-25 04:28 172阅读 0赞

#### 场景 ####

*  一个经典的面试题目：对应一个包含上亿没有排序的整数int文件，给定一个整数K，如何快速的判断这个整数是否存在这个文件中。
 *  面试者A：把整个文件读入内存中，挨个数据遍历一下就知道了。
 *  面试官： 下一位…

注意哦： int 类型在计算机中存储是4字节，而上亿个数据差不多需要占用 400M 内存，而且每次遍历数据时间复杂度是：o(n) 是不符合要求的，其实不管是什么类型的面试题，我们都需要先进行数据整理存储然后在处理对应的业务场景。

#### 初级方案： ####

上述问题要求我们查询整数K 存不存在，**我们可以新建一个长度为 Integer.MAX\_VALUE 的数组，数组的下标表示当前的数字，值 1 表示存在， 值为 0 表示不存在**

数据结构示意图：

*  表示 0、2、4 … 101、102、105 存在于文件中

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5neW9uZzAxMjQ1_size_16_color_FFFFFF_t_70_pic_left]  
代码：

public class SeachNum {
    
        // 定义保存 num 是否存在的数组
        private byte[] words = new byte[Integer.MAX_VALUE-2];
    
        public void set(int num){
            words[num] = 1;
        }
    
        public boolean get(int num){
            return words[num] == 1;
        }
    }

*  通过上面的设计，当我们把文件中的数字 全部 set 到数组中，后续判定 K 存在与否都是 o(1) 的复杂度
 *  我们在继续思考一下，上面的设计有没有什么缺陷？
    
     *  数组本身占用大量内存
     *  当我们文件的数据 全部集中在 一个小范围内， 我们定义的 长度为 Integer.MAX\_VALUE 的数组大部分下标是用不到的，存在很大的空间浪费
     *  而且定义超大型数组需要一段连续的内存，极有可能 JVM 内存直接分配在老年代，只有当 fullgc 时才会被回收，是不合理的。
 *  如何进行优化

*  通过我们细心的观察可以发现，数组中的值一直 0101011010， 这不就是二进制吗？何不把二进制转化为10进制来存储数据， java.util.BitSet 则基于上述原理实现的

#### BitSet： ####

为了解决上问题，以及初级设计方案存在的问题， BitSet 油然而生~

*  BitSet 存储数据是一个 long 类型的数组，每个位置储存64个数字是否存在的状态，二进制转化为十进制，根据上面的数组假设4~63 之间的数组值都为0，那么 long\[0\] = 21 【由二进制 10101 转化而来】
 *  所以 long\[0\] 代表的是 0 ~ 63 下标位的状态
 *  long\[1\] 代表的是 64 ~ 127 下标位的状态
 *  依次类推

我们来看源码：

*  其中最关键的是 get、set 方法， 即对数组中指定下标位置数据的二进制某个位置的 修改、查询操作等等。

public class BitSet implements Cloneable, java.io.Serializable {
    
        private final static int ADDRESS_BITS_PER_WORD = 6;
        // 64
        private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;
        // 63  数组每个位置储存的最大数量【位运算】
        private final static int BIT_INDEX_MASK = BITS_PER_WORD - 1;
    
        // 保存数组
        private long[] words;
    
    
        // 初始化， 默认数组长度 1
        public BitSet() {
            initWords(BITS_PER_WORD);
            sizeIsSticky = false;
        }
    
        private void initWords(int nbits) {
            words = new long[wordIndex(nbits-1) + 1];
        }
    
        // 计算 bitIndex 在数组中的下标
        private static int wordIndex(int bitIndex) {
            // 等同于 bitIndex / 64
            return bitIndex >> ADDRESS_BITS_PER_WORD;
        }
    
        // set
        public void set(int bitIndex) {
            if (bitIndex < 0)
                throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
            // 计算 bitIndex 在数组中的下标
            int wordIndex = wordIndex(bitIndex);
            // 计算数组的长度，是否需要扩容
            expandTo(wordIndex);
    
            // 重点！!
            // 1L << bitIndex: 位运算，结果等于 bitIndex % 2^64
            // |= 运算：将words[wordIndex] 位置数字的二进制第 (1L << bitIndex) 置位1
            words[wordIndex] |= (1L << bitIndex); // Restores invariants
    
            checkInvariants();
        }
    
        // get
        public boolean get(int bitIndex) {
            if (bitIndex < 0)
                throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
    
            checkInvariants();
            // 计算 bitIndex 在数组中的下标
            int wordIndex = wordIndex(bitIndex);
            // 返回 bitIndex 在 words[wordIndex] 二进制值 第 (1L << bitIndex)位是否不等于0 【1-存在-true， 0-不存在-false】
            return (wordIndex < wordsInUse)
                    && ((words[wordIndex] & (1L << bitIndex)) != 0);
        }
    
        private void expandTo(int wordIndex) {
            int wordsRequired = wordIndex+1;
            if (wordsInUse < wordsRequired) {
                ensureCapacity(wordsRequired);
                wordsInUse = wordsRequired;
            }
        }
    
        // words 数组扩容
        private void ensureCapacity(int wordsRequired) {
            if (words.length < wordsRequired) {
                // Allocate larger of doubled size or required size
                int request = Math.max(2 * words.length, wordsRequired);
                words = Arrays.copyOf(words, request);
                sizeIsSticky = false;
            }
        }
    
    }

总体而言，BitSet 的原理并不是很难理解， 这里仅仅介绍了其中比较核心的方法，其类中也实现了很多其他方法，有兴趣的小伙伴可以继续深入一下，

#### BitSet 中常用的方法： ####

*  int cardinality( ) 返回此BitSet 中设置为 true 的位数。
 *  void clear( ) 将此BitSet 中的所有位设置为 false。
 *  void clear(int index) 将索引指定处的位设置为 false。
 *  void clear(int startIndex, int endIndex) 将指定的 fromIndex（包括）到指定的 toIndex（不包括）范围内的位设置为 false。
 *  boolean get(int index) 返回指定索引处的位值。
 *  BitSet get(int startIndex, int endIndex) 返回一个新的 BitSet，它由此 BitSet 中从 fromIndex（包括）到 toIndex（不包括）范围内的位组成。
 *  boolean isEmpty( ) 如果此 BitSet 中没有包含任何设置为 true 的位，则返回 ture。
 *  int length( ) 返回此 BitSet 的"逻辑大小"：BitSet 中最高设置位的索引加 1
 *  void set(int index) 将指定索引处的位设置为 true。
 *  int size( )返回此 BitSet 表示位值时实际使用空间的位数。

#### Thanks a lot ！！！ ####

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5neW9uZzAxMjQ1_size_16_color_FFFFFF_t_70_pic_left]: /images/20221124/11d250f7757546d1a5375a68f4a580bb.png