海量数据面试题总结(2)-BitMap

本系列文章对海量数据面试题进行了归类和总结，给出海量数据处理问题的通用解决思路，后面附有例题，希望大家能够举一反三。

模式二：BitMap

所谓BitMap就是用一个bit位来标记某个元素所对应的value，而key即是该元素，由于BitMap使用了bit位来存储数据，因此可以大大节省存储空间。

一、BitMap基本思想

用一个简单例子来介绍BitMap算法原理。假设要对0-7内的5个元素[4,7,2,5,3]进行排序(元素没有重复)。我们可以使用BitMap算法达到排序目的。要表示8个数，我们需要8个bit。

1. 首先我们开辟一个字节(8bit)的空间，将这些空间的所有bit位都设置为0；

2. 然后遍历这5个元素，第一个元素是4，因为下边从0开始，因此我们把第五个字节的值设置为1；

3. 然后再处理剩下的四个元素，最终8个字节的状态如下图：

4. 现在我们遍历一次bytes区域，把值为1的byte的位置输出(2,3,4,5,7)，这样便达到了排序的目的。

二、解决思路

1. 先确定每个数字的存储空间。如int32类型的每个数字需要32位存储空间，共有2^32种数，需要2^32=4G的连续内存空间才可以将所有数字一一表示。

2. 如果所需内存空间够小或可以满足计算需求，直接用BitMap算法，遍历每个数i，将a[i]置为1。

3. 根据不同情况，对a的键进行排序或查找某个键。

三、经典例题

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

采用2-BitMap（每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义）进行，共需内存2^32 * 2 bit = 8GB内存。然后扫描这2.5亿个整数，查看BitMap中相对应位，如果是00变01，01变10，10保持不变。扫描完后，查看BitMap，把对应位是01的整数输出即可。

2. 给40亿个不重复的int型整数(32位)，乱序，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？

用BitMap的方法，申请4GB的内存，一个bit位代表一个int值。遍历40亿个数，设置相应的bit位为1。读入要查询的数，查看相应bit位是否为1，为1表示存在，为0表示不存在。