美文网首页
简析Java中BitSet

简析Java中BitSet

作者: LoWang | 来源:发表于2019-07-17 15:39 被阅读0次

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  平时刷面试题的时候,经常会有类似的问题: 统计40亿个数据中没有出现的数据,将40亿个不...

  • JAVA中BitSet

    JAVA中BitSet就是“位图”数据结构,根据“位图”的语义,数据的存在性可以使用bit位上的1或0来表示;一个...

  • Java中的BitSet

    最近看到ES在缓存filter的结果时用到了BitSet的数据结构,用一个bit来标识文档是否满足这个filter...

  • 2018-03-28bitset疑惑

    http://www.runoob.com/java/java-bitset-class.html import ...

  • Lock接口

    Java并发编程简析 @[toc]并发编程在Java实际开发中,占有举足轻重的地位,在接下来的篇幅中,以java....

  • Java数据结构

    Java工具包中包含许多强大的数据结构,主要包括 枚举(Enumeration); 位集合(BitSet); 向量...

  • mybatis-spring解析

    1、概述 原生Mybatis源码简析(上)原生Mybatis源码简析(下)在介绍原生Mybatis源码简析文章中,...

  • java.util.BitSet处理海量数据【转】

    Java.util.BitSet可以按位存储。 计算机中一个字节(byte)占8位(bit),我们java中数据至...

  • BitSet实现原理及源码解析

    BitSet的结构原理 BitSet, 是Java对位集合抽象出的一种数据结构。它的内部维护了一个long数组,数...

  • Java异常的分类

    参考Java异常体系简析深入理解Java中异常体系 简单的介绍一下: Throwable是所有异常的父类 Erro...

网友评论

      本文标题:简析Java中BitSet

      本文链接:https://www.haomeiwen.com/subject/uqzqlctx.html