java数据结构与算法总结(二十五)--初识BitSet之API

深碍√TFBOYSˉ_ 2022-10-31 04:22 185阅读 0赞

[原文链接][Link 1]

## 1.BitSet类的基本原理 ##

类实现了一个按需增长的位向量。用一位来表示一个数据是否出现过，0表示没有出现过，1表示没有出现过

默认情况下，set中所有位的初识值都是0（或者false）。

多个线程操作一个BitSet是不安全的。

## 2.API解析 ##

### 2.1 底层数据结构 ###

*  内部维护了一个long数组，所以数组words中的每个元素word默认是64位的long值。

![70][]

*  * ADDRESS\_BITS\_PER\_WORD = 6：*每个word值需要6个bit来表示地址：64 = 2^6
 *  *BITS\_PER\_WORD = 64：*每个word有64位，即一个long数据
 *  *BIT\_INDEX\_MASK：*每个word有64位，最大索引值是64 - 1 = 63

![70 1][]

*  *wordsInUse：*BitSet的逻辑大小，即底层long数组的size
 *  *sizeIsSticky：*BitSet的大小是否是用户指定的，默认是false

### 2.2 构造函数 ###

*  默认的构造参数
 *  带参数的构造参数

public BitSet() {
        initWords(BITS_PER_WORD);
        sizeIsSticky = false;//用户未指定大小
    }

public BitSet(int nbits) {
            // nbits can't be negative; size 0 is OK
            if (nbits < 0)
                throw new NegativeArraySizeException("nbits < 0: " + nbits);
     
            initWords(nbits);
            sizeIsSticky = true;//用户指定大小
        }

其中主要包括的方法是：

private void initWords(int nbits) {
            words = new long[wordIndex(nbits-1) + 1];
        }

根据默认的数据的个数或是用户指定的个数来初始化long数组：

当nbits <= 64时，words = new long\[1\];

当nbits > 64 and nbits <= 128时，words = new long\[2\];

以此类推，即用户需要存储的数据个数

*  私有的构造参数
    
        private BitSet(long[] words) {
                this.words = words;
                this.wordsInUse = words.length;
                checkInvariants();
            }
    
     
 *  不允许外部类 构建本类的实例 常见于单例模式
 *  ###  ###
    
    ### 2.3 常用方法 ###
 *  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();
            }
    
     
    
        public void set(int bitIndex, boolean value) {
                if (value)
                    set(bitIndex);
                else
                    clear(bitIndex);
            }
    
    其中 wordIndex = wordIndex(bitIndex) 是通过简单的右移运算来判断这个值代表的索引在long数组中的下标索引。
    
    比如：bitIndex = 16
    
     
 *  16 >> 6 = 0,代表16这个值存储在数组words\[0\]中,
 *  然后通过位运算中的或运算 ：words\[0\] = words\[0\] | (1L << 16) 将words\[0\]中从右往左数第16个bit位置为1(即true).
 *  clear方法

public void clear(int bitIndex) {
            if (bitIndex < 0)
                throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
            int wordIndex = wordIndex(bitIndex);
            if (wordIndex >= wordsInUse)
                return;
            words[wordIndex] &= ~(1L << bitIndex);
            recalculateWordsInUse();
            checkInvariants();
        }

跟set方法一样，通过位运算中的与运算：words\[wordIndex\] &= ~(1L << bitIndex)

将从右往左数，第bitIndex位的bit置为0(即false)。不管原来该位上是否是0，都置为0

*  and方法

public void and(BitSet set) {
            if (this == set)
                return;
            while (wordsInUse > set.wordsInUse)
                words[--wordsInUse] = 0;
            // Perform logical AND on words in common
            for (int i = 0; i < wordsInUse; i++)
                words[i] &= set.words[i];
            recalculateWordsInUse();
            checkInvariants();
        }

得到的结果是两个BitSet中共有的数据，相当于交集

*  or方法

public void or(BitSet set) {
            if (this == set)
                return;
     
            int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);
     
            if (wordsInUse < set.wordsInUse) {
                ensureCapacity(set.wordsInUse);
                wordsInUse = set.wordsInUse;
            }
     
            // Perform logical OR on words in common
            for (int i = 0; i < wordsInCommon; i++)
                words[i] |= set.words[i];
     
            // Copy any remaining words
            if (wordsInCommon < set.wordsInUse)
                System.arraycopy(set.words, wordsInCommon,
                                 words, wordsInCommon,
                                 wordsInUse - wordsInCommon);
     
            // recalculateWordsInUse() is unnecessary
            checkInvariants();
        }

得到的是两个BitSet中的并集

*  xor方法

public void xor(BitSet set) {
            int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);
     
            if (wordsInUse < set.wordsInUse) {
                ensureCapacity(set.wordsInUse);
                wordsInUse = set.wordsInUse;
            }
     
            // Perform logical XOR on words in common
            for (int i = 0; i < wordsInCommon; i++)
                words[i] ^= set.words[i];
     
            // Copy any remaining words
            if (wordsInCommon < set.wordsInUse)
                System.arraycopy(set.words, wordsInCommon,
                                 words, wordsInCommon,
                                 set.wordsInUse - wordsInCommon);
     
            recalculateWordsInUse();
            checkInvariants();
        }

*  得到的是当前BitSet中独有的数据，相当于差集
 *  size方法

public int size() {
            return words.length * BITS_PER_WORD;
        }

*  返回的是BitSet的逻辑大小，即底层数组的大小 \* 每个word值占用的bit位(默认是64bit)

## 3.总结 ##

BitSet适用于存储无重复的整数。对于一堆无序的不重复的随机大数据，应用场景主要有：

*  统计没有出现的数
 *  对这些数据进行排序
 *  压缩存储(一个GB的内存可以存储 1024 \* 1024 \* 1024 \* 8 bit的数)

BitSet选择long数组作为底层数据结构是因为BitSet提供 and和or等的位运算，需要对BitSet中的所有bit位做and或者or，遍历数组的时候性能比较高，使用long可以使循环的次数达到最小。

##  ##

## 测试类 ##

import java.util.BitSet;
     
    public class BitSetDemo {
     
        public static void main(String args[]) {
            BitSet bits1 = new BitSet(16);//wordsInUse = 0,sizeIsSticky = true
            BitSet bits2 = new BitSet(16);
     
            BitSet bits3 = new BitSet();
            BitSet bits4 = new BitSet();//wordsInUse = 0,sizeIsSticky = false
     
            // set some bits
            for(int i=0; i<16; i++) {
                if((i%2) == 0) bits1.set(i);
                if((i%5) != 0) bits2.set(i);
            }
            for(int i = 0;i < 64;i++)
                bits3.set(i);
            for(int i = 0;i < 65;i++)
                bits4.set(i);
            System.out.println("Initial pattern in bits1: ");
            System.out.println(bits1);
            System.out.println(bits1.size());
     
            System.out.println("\nInitial pattern in bits2: ");
            System.out.println(bits2);
            System.out.println(bits2.size());
     
            System.out.println("Initial pattern in bits3: ");
            System.out.println(bits3);
            System.out.println(bits3.size());
     
            System.out.println("\nInitial pattern in bits4: ");
            System.out.println(bits4);
            System.out.println(bits4.size());
     
            // AND bits
            //相当于找过两个set的交集
            bits2.and(bits1);
            System.out.println("\nbits2 AND bits1: ");
            System.out.println(bits2);
     
            // OR bits
            //相当于并集
            bits2.or(bits1);
            System.out.println("\nbits2 OR bits1: ");
            System.out.println(bits2);
     
            // XOR bits
            //相当于差集
            bits2.xor(bits1);
            System.out.println("\nbits2 XOR bits1: ");
            System.out.println(bits2);
        }
    }

[Link 1]: https://blog.csdn.net/sinat_37803310/article/details/80683455
[70]: /images/20221024/93d564417cfb4667b48e73751ac80e91.png
[70 1]: /images/20221024/6897aeeb8d174b00a7b9d4187bbd63b4.png