如何使用2G内存装载8G的数据？

背景

有一次和几位同事展开头脑风暴聊天的时候，其中一位同事提出了这样一个问题 “如何用2G内存装载8G的数据？”，当时听到该问题的时候，很多人都表示不太可能，后来翻阅资料才发现有一种数据结构叫BitMap 是可以做到这样的神奇的事情的。

BitMap 简介

BitMap从字面的意思，很多人认为是位图，其实准确的来说，翻译成基于位的映射。在所有具有性能优化的数据结构中，大家使用最多的就是hash表，是的，在具有定位查找上具有O(1)的常量时间，多么的简洁优美。但是数据量大了，内存就不够了。所谓的Bit-map就是用一个bit位来标记某个元素对应的Value， 而Key即是该元素。由于采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节省。

Bitmap应用

Bitmap 主要用于两大块，分别是：

1. 可进行数据的快速查找，判重，删除，一般来说数据范围是int的10倍以下。
2. 去重数据而达到压缩数据

1、Bitmap应用之快速排序

假设我们要对0-7内的5个元素(4,7,2,5,3)排序（这里假设这些元素没有重复）,我们就可以采用Bit-map的方法来达到排序的目的。要表示8个数，我们就只需要8个Bit（1Bytes），首先我们开辟1Byte的空间，将这些空间的所有Bit位都置为0，

对应位设置为1:

遍历一遍Bit区域，将该位是一的位的编号输出（2，3，4，5，7），这样就达到了排序的目的，时间复杂度O(n)。

优点：

运算效率高，不需要进行比较和移位；

占用内存少，比如N=10000000；只需占用内存为N/8=1250000Byte=1.25M。

缺点：

所有的数据不能重复。即不可对重复的数据进行排序和查找。

2、Bit-map应用之快速去重

2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。

首先，根据“内存空间不足以容纳这2.5亿个整数”我们可以快速的联想到Bit-map。下边关键的问题就是怎么设计我们的Bit-map来表示这2.5亿个数字的状态了。其实这个问题很简单，一个数字的状态只有三种，分别为不存在，只有一个，有重复。因此，我们只需要2bits就可以对一个数字的状态进行存储了，假设我们设定一个数字不存在为00，存在一次01，存在两次及其以上为11。那我们大概需要存储空间几十兆左右。

接下来的任务就是遍历一次这2.5亿个数字，如果对应的状态位为00，则将其变为01；如果对应的状态位为01，则将其变为11；如果为11，,对应的转态位保持不变。

最后，我们将状态位为01的进行统计，就得到了不重复的数字个数，时间复杂度为O(n)。

3、Bitmap应用之快速查询

同样，我们利用Bit-map也可以进行快速查询，这种情况下对于一个数字只需要一个bit位就可以了，0表示不存在，1表示存在。假设上述的题目改为，如何快速判断一个数字是够存在于上述的2.5亿个数字集合中。

同之前一样，首先我们先对所有的数字进行一次遍历，然后将相应的转态位改为1。遍历完以后就是查询，由于我们的Bit-map采取的是连续存储（整型数组形式，一个数组元素对应32bits），我们实际上是采用了一种分桶的思想。一个数组元素可以存储32个状态位，那将待查询的数字除以32，定位到对应的数组元素（桶），然后再求余（%32），就可以定位到相应的状态位。如果为1，则代表改数字存在；否则，该数字不存在。

5、Bitmap扩展——Bloom Filter(布隆过滤器)

当一个元素被加入集合中时,通过k各散列函数将这个元素映射成一个位数组中的k个点,并将这k个点全部置为1.

有一定的误判率--在判断一个元素是否属于某个集合时,有可能会把不属于这个集合的元素误判为属于这个集合.因此,它不适合那些"零误判"的应用场合.在能容忍低误判的应用场景下,布隆过滤器通过极少的误判换区了存储空间的极大节省.

Bloom Filter使用k个相互独立的哈希函数（Hash Function），它们分别将集合中的每个元素映射到{1,…,m}的范围中。对任意一个元素x，第i个哈希函数映射的位置hi(x)就会被置为1（1≤i≤k）。注：如果一个位置多次被置为1，那么只有第一次会起作用，后面几次将没有任何效果。

在判断y是否属于这个集合时，对y应用k次哈希函数，若所有hi(y)的位置都是1（1≤i≤k），就认为y是集合中的元素，否则就认为y不是集合中的元素。

BitMap算法流程

假设需要排序或者查找的最大数MAX=10000000（lz:这里MAX应该是最大的数而不是int数据的总数！），那么我们需要申请内存空间的大小为int a[1 + MAX/32]。

其中：a[0]在内存中占32为可以对应十进制数0-31，依次类推：

bitmap表为：

a[0]--------->0-31

a[1]--------->32-63

a[2]--------->64-95

a[3]--------->96-127

我们要把一个整数N映射到Bit-Map中去，首先要确定把这个N Mapping到哪一个数组元素中去，即确定映射元素的index。我们用int类型的数组作为map的元素，这样我们就知道了一个元素能够表示的数字个数(这里是32)。于是N/32就可以知道我们需要映射的key了。所以余下来的那个N%32就是要映射到的位数。

1.求十进制数对应在数组a中的下标：

先由十进制数n转换为与32的余可转化为对应在数组a中的下标。

如十进制数0-31，都应该对应在a[0]中，比如n=24,那么 n/32=0，则24对应在数组a中的下标为0。又比如n=60,那么n/32=1，则60对应在数组a中的下标为1，同理可以计算0-N在数组a中的下标。

i = N>>K % 结果就是N/(2^K)

Note: map的范围是[0, 原数组最大的数对应的2的整次方数-1]。

2.求十进制数对应数组元素a[i]在0-31中的位m：

十进制数0-31就对应0-31，而32-63则对应也是0-31，即给定一个数n可以通过模32求得对应0-31中的数。

m = n & ((1 << K) - 1) %结果就是n%(2^K)

3.利用移位0-31使得对应第m个bit位为1

如a[i]的第m位置1：a[i] = a[i] | (1<

如：将当前4对应的bit位置1的话，只需要1左移4位与B[0] | 即可。

Note: 1 p+(i/8)|(0×01<

2 同理将int型变量a的第k位清0，即a=a&~(1<

Java BitSet可以按位存储，计算机中一个字节(byte)占8位(bit)；

而BitSet是位操作的对象，值只有0或1（即true 和 false），内部维护一个long数组，初始化只有一个long segement，所以BitSet最小的size是64；随着存储的元素越来越多，BitSet内部会自动扩充，一次扩充64位，最终内部是由N个long segement 来存储；

默认情况下，BitSet所有位都是0即false；

Bitset使用如下：

 1import java.util.BitSet; 2public class BitSetDemo { 3 public static void main(String args[]) { 4 BitSet bits1 = new BitSet(16); 5 BitSet bits2 = new BitSet(16); 6 // set some bits 7 for(int i=0; i<16; i++) { 8 if((i%2) == 0) bits1.set(i); 9 if((i%5) != 0) bits2.set(i);10 }11 System.out.println("Initial pattern in bits1: ");12 System.out.println(bits1);13 System.out.println("\nInitial pattern in bits2: ");14 System.out.println(bits2);15 // AND bits16 bits2.and(bits1);17 System.out.println("\nbits2 AND bits1: ");18 System.out.println(bits2);19 // OR bits20 bits2.or(bits1);21 System.out.println("\nbits2 OR bits1: ");22 System.out.println(bits2);23 // XOR bits24 bits2.xor(bits1);25 System.out.println("\nbits2 XOR bits1: ");26 System.out.println(bits2);27 }28}

输出结果如下：

 1Initial pattern in bits1: 2{0, 2, 4, 6, 8, 10, 12, 14} 3Initial pattern in bits2: 4{1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14} 5bits2 AND bits1: 6{2, 4, 6, 8, 12, 14} 7bits2 OR bits1: 8{0, 2, 4, 6, 8, 10, 12, 14} 9bits2 XOR bits1:10{}

BitSet为什么选择long型数组作为内部存储结构

JDK选择long数组作为BitSet的内部存储结构是出于性能的考虑，在and和or的时候减少循环次数，提高性能；

因为BitSet提供and和or这种操作，需要对两个BitSet中的所有bit位做and或者or，实现的时候需要遍历所有的数组元素。使用long能够使得循环的次数降到最低，所以Java选择使用long数组作为BitSet的内部存储结构。

举个例子：

当我们进行BitSet中的and, or, xor操作时，要对整个bitset中的bit都进行操作，需要依次读出bitset中所有的word，如果是long数组存储，我们可以每次读入64个bit,而int数组存储时，只能每次读入32个bit。

本头条号由饿了么、阿里、蚂蚁等同事组成，关注v信公众号：jiagoushizhidian , 获取更前言的架构咨询。

閱讀更多 科技伍小黑 的文章

關鍵字: out 内存 System