理解BitSet

Bertha 。 2022-09-24 06:29 178阅读 0赞

先来看几道面试题：

> 1、统计40亿个数据中没有出现的数据，将40亿个不同数据进行排序。
> 
> 2、现在有1千万个随机数，随机数的范围在1到1亿之间，要求写出一种算法，将1到1亿之间没有在随机数中的数求出来。
> 
> 3、有一个40G大小的文件，里面存的是32位正整数记录，我需要查找其中一个文件，问如何查找？
> 
> ……

有木有被上面的大大大数据吓到了无从下手啊？今天介绍的BitSet就可以解决这一问题。

## 简介 ##

一个按需增长的位向量，C++和java都有提供实现。

BitSet是位操作的对象，值只有1和0。用1位来表示一个数据是否出现过，0为没有出现过，1表示出现过。使用用的时候既可根据某一个是否为0表示此数是否出现过。

比较  
一般，int占4个字节，long占8个字节。而一个字节是由8个位组成的。  
粗略估计，int和BitSet的比例为4\*8:1，即32：1。如果是long，差距就更大了。

## 基本操作 ##

### 1、重要属性 ###

BitSet在java.util包下，初始大小为64位。

/*
         * BitSets are packed into arrays of "words."  Currently a word is
         * a long, which consists of 64 bits, requiring 6 address bits.
         * The choice of word size is determined purely by performance concerns.
         */
    private final static int ADDRESS_BITS_PER_WORD = 6;
    
    private long[] words;

### 2、构造函数 ###

//构造函数一
      public BitSet(int nbits) {
            // nbits can't be negative; size 0 is OK
            if (nbits < 0)
                throw new NegativeArraySizeException("nbits < 0: " + nbits);
            //new 一个long数组
            initWords(nbits);
            sizeIsSticky = true;
        }
    
    private void initWords(int nbits) {
            words = new long[wordIndex(nbits-1) + 1];
        }    
    //构造函数二
     private BitSet(long[] words) {
            this.words = words;
            this.wordsInUse = words.length;
            checkInvariants();
        }

### 3、检查函数 ###

BitSet类中提供了两个内部检查的函数。

/** * Sets the field wordsInUse to the logical size in words of the bit set. * WARNING:This method assumes that the number of words actually in use is * less than or equal to the current value of wordsInUse! */
        private void recalculateWordsInUse() {
            // Traverse the bitset until a used word is found
            int i;
            for (i = wordsInUse-1; i >= 0; i--)
                if (words[i] != 0)
                    break;
    
            wordsInUse = i+1; // The new logical size
        }
    
      /** * Every public method must preserve these invariants. */
        private void checkInvariants() {
        //wordsInUse 实际使用的long的个数
            assert(wordsInUse == 0 || words[wordsInUse - 1] != 0);
            assert(wordsInUse >= 0 && wordsInUse <= words.length);
            assert(wordsInUse == words.length || words[wordsInUse] == 0);
        }

### 4、扩容 ###

跟其他可以自动扩容类相同，扩容发生在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) {
            int wordsRequired = wordIndex+1;
            if (wordsInUse < wordsRequired) {
                ensureCapacity(wordsRequired);
                wordsInUse = wordsRequired;
            }
        }
    
    //核心扩容方法
     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;
            }
        }

## 应用实例 ##

为了方便演示，就把数字改小了。需求就是生成10个10以内的随机数，并求出20以内哪些数字没在生成的随机数中。

// 先把随机数放入list中
            Random random = new Random();
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < 10; i++) {
                int randomResult = random.nextInt(10);
                list.add(randomResult);
            }
            //查看生产的随机数
            System.out.println("产生的随机数有");
            for (int i = 0; i < list.size(); i++) {
                System.out.println(list.get(i));
            }
            System.out.println("the end");
    
            //将随机数放入bitset中
            BitSet bit = new BitSet();
    
            for (int i = 0; i < 10; i++) {
                bit.set(list.get(i));
            }
            //打印没有随机生产的数
            for (int i = 0; i < 20; i++) {
                if (!bit.get(i)) {
                    System.out.println(i);
                }
            }