简析Java中BitSet

2019-07-17 本文已影响0人 LoWang

40亿/1千万/40G

平时刷面试题的时候，经常会有类似的问题:

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

这类问题，最简答的做法都是读取，遍历，分析。但是针对于大数据量的数据做这种操作，内存消耗是非常严重的，所以常规的做法是不可取的。

BitMap

针对上述的一些大数据量的操作，BitMap的数据结构就非常适用。

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

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

简单案例: 有两个数组，判断这两个数组中的重复元素。
简单解释: 先把数组转换为BitMap，在对BitMap的二进制进行与运算，根据所在位数为1，则得知该位数的数重复。

实际使用的时候，并不会向上面一样很随意地将长度设置为8，一般会设置为32（int型）或64（long型），理由见下文 BitSet 源码即可。

除了上文提到的与运算，当然了，逻辑或和逻辑异或操作都是OK的。

每个Bit位只能是0或1，所以只能代表true or false，当我们要进行少量统计的时候，可以使用2-BitMap，即每个位上可以使用 00、01、10、11来分别表示数量为 0、1、2，此时的 11 一般无意义。

Java > BitSet

在Java中，已经有成熟的BitMap的实现，那么就是BitSet，原理类似，但是他默认是的使用单个数组索引可以表示更长的位(64bit)的long数据类型。

简单描述一下他的结果，BitSet实例中没存放了一个long[] words数组，他实际的存储数据，给我们看到的是如下的结果: [1,2,5,9,343,234]，而对于BitSet的视图来说，他会把数组总的long数据类型，拆分成bit，也就是每个long可以表达的64个位。例如刚才的那个long数组，可以表示的位数是：384位，实际使用字节：8byte*6=48个字节，相当于8个字节可以表示64位，如果40亿，只需要476M左右的内存。
BitSet的视图:

[1,2,5,9,343,234]
[00000000000000..1, 00000000...11, 00000000000101, ....]

几处关键代码

/*
* 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;


...


/**
 * Given a bit index, return word index containing it.
 */
private static int wordIndex(int bitIndex) {
    return bitIndex >> ADDRESS_BITS_PER_WORD;
}

这个静态属性用的比较多，主要用于向右移位运算，X >>> 6，就表示 X/2^6次方，也就是除以64。最开始将的，数组中每个元素表示64位，除以64位就能算出X所在的数组索引的long数字。

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

根据构造函数传入的参数，生成能表达指定数据的数组长度。

/**
 * Sets the bit at the specified index to {@code true}.
 *
 * @param  bitIndex a bit index
 * @throws IndexOutOfBoundsException if the specified index is negative
 * @since  JDK1.0
 */
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();
}

设置自定位数的数据为true。bitIndex可能是一个大的数，需要注意的是java中的移位操作会模除位数，也就是说，long类型的移位会模除64。

java中int型数据占4字节，每字节是8个二进制位，也就是int型占了32个二进制位。

当进行移位运算时，无论左移还是右移，移动超过32位的话，意味着所有的位都移出了，数据变得毫无意义，因此java在int型移位时会先对移位运算符右边的值（需要移动的位数）对32取模，模就是最后要移动的位数。

以此类推，long型占用8字节，因此需要对64取模。

words[wordIndex] |= (1L << bitIndex); // Restores invariants

等同于

int transderBits = bitIndex % 64;
words[wordsIndex] |= (1L << transferBits);

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

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

>>> 表示向右移位，左填充0(不带符号的移位) , 1111 >>> 2 = 0011
>> 表示向右移位，左填充同最高位(带符号), 1111 >> 2 = 1111
<< 表示向右移位，右填充0
| 表示或运算 (二进制,如果有1是1,否则为0)
& 表示与运算 (二进制,都为1是1,否则为0)
~ 表示非运算 (二进制,取反)
^ 表示异或运算 (二进制,相同为0,不相同为1)

https://blog.csdn.net/lujianhao_ios/article/details/76767981
https://www.jianshu.com/p/0f653d2302a0
https://blog.csdn.net/u010066934/article/details/52047310
https://www.cnblogs.com/lqminn/archive/2012/08/30/2664122.html

简析Java中BitSet

40亿/1千万/40G

BitMap

Java > BitSet

几处关键代码

猜你喜欢

热点阅读