Java BitSet的理解与使用

浅浅的花香味﹌ 2022-01-23 05:27 235阅读 0赞

## 一,概括 ##

BitSet是位操作的对象，值只有0或1即false和true，内部维护了一个long数组，初始只有一个long，所以BitSet最小的size是64，当随着存储的元素越来越多，BitSet内部会动态扩充，一次扩充64位，最终内部是由N个long来存储。  
默认情况下，BitSet的所有位都是false即0。  
在没有外部同步的情况下，多个线程操作一个BitSet是不安全的。  
一个1GB的空间，有8*1024*1024*1024 = 8.58*10^9bit，也就是1GB的空间可以表示85亿多个数.

应用场景：  
1,统计一组大数据中没有出现过的数；  
将这组数据映射到BitSet，然后遍历BitSet，对应位为0的数表示没有出现过的数据。  
2. 对大数据进行排序；  
将数据映射到BitSet，遍历BitSet得到的就是有序数据。  
3. 在内存对大数据进行压缩存储等等。  
一个GB的内存空间可以存储85亿多个数，可以有效实现数据的压缩存储，节省内存空间开销。

## 二.源码分析 ##

1,构造函数  
1.1无参构造  
默认创建长度为1的long数组

public BitSet() {
            initWords(BITS_PER_WORD); //初始化 数组
            sizeIsSticky = false; //所有位都设置为false
        }
    private void initWords(int nbits) {
            words = new long[wordIndex(nbits-1) + 1];
        }
        /**
       *符号右移6位 也就是除64
       */
     private static int wordIndex(int bitIndex) {
            return bitIndex >> ADDRESS_BITS_PER_WORD;
        }

2.2参数构造  
2.2.1 数组大小为参数 (64的整数倍)  
2.2.2 long数组为参数

2.set方法

public void set(int bitIndex) {
            if (bitIndex < 0)
                throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
    		
            int wordIndex = wordIndex(bitIndex);
         
            expandTo(wordIndex);
    
            words[wordIndex] |= (1L << bitIndex); // Restores invariants
    
            checkInvariants();
        }
        private void expandTo(int wordIndex) {
        //set的值所需要的size
            int wordsRequired = wordIndex+1;
            //当前使用的< 需要的
            if (wordsInUse < wordsRequired) {
            //扩容
                ensureCapacity(wordsRequired);
                wordsInUse = wordsRequired;
            }
        }
     private void ensureCapacity(int wordsRequired) {
            if (words.length < wordsRequired) {
                //当需要的 大于当前的long数组的size 扩容
                int request = Math.max(2 * words.length, wordsRequired);
                words = Arrays.copyOf(words, request);
                sizeIsSticky = false;
            }
        }
    
    ``
    3.get方法

public boolean get(int bitIndex) \{  
if (bitIndex < 0)  
throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

checkInvariants();
    
        int wordIndex = wordIndex(bitIndex);
        return (wordIndex < wordsInUse)
            && ((words[wordIndex] & (1L << bitIndex)) != 0);
    }

为什么BitSet使用long数组做内部存储？
            JDK选择long数组作为BitSet的内部存储结构是出于性能的考虑，因为BitSet提供and和or这种操作，需要对两个BitSet中的所有bit位做and或者or，实现的时候需要遍历所有的数组元素。使用long能够使得循环的次数降到最低，所以Java选择使用long数组作为BitSet的内部存储结构。
    
            从数据在栈上的存储来说，使用long和byte基本是没有什么差别的，除了编译器强制地址对齐的时候，使用byte最多会浪费7个字节(强制按照8的倍数做地址对其)，另外从内存读数组元素的时候，也是没有什么区别的，因为汇编指令有对不同长度数据的mov指令。所以说，JDK选择使用long数组作为BitSet的内部存储结构的根本原因就是在and和or的时候减少循环次数，提高性能。
    
            例如我们进行BitSet中的and, or,xor操作时，要对整个bitset中的bit都进行操作，需要依次读出bitset中所有的word，如果是long数组存储，我们可以每次读入64个bit,而int数组存储时，只能每次读入32个bit。另外我们在查找bitset中下一个置为1的bit时,word首先会和0进行比较，如果word的值为0，则表示该word中没有为1的bit，可以忽略这个word，如果是long数组存储，可以一次跳过64个bit，如果是int数组存储时，一次只能跳过32个bit。