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
网友评论