Bitmap和2-Bitmap海量数据处理问题

内容会持续更新，有错误的地方欢迎指正，谢谢!

题目

题1：在2.5亿个整数找出不重复的整数，内存不足以容纳着2.5亿个整数。
题2：给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？
题3：“游戏任务标记”的编程题，请见链接：
http://blog.csdn.net/billcyj/article/details/78948402

分析

要解决上面的问题，都需可以用Bitmap或2-Bitmap。

Bitmap

BitMap也就是位图

引出Bitmap

举一个小例子，有一个无序整形数组{8,4,9}，也就占用内存3*4=12字节，这很正常，但如果有1亿个这样的数呢？1亿*4/(1024*1024*1024)=0.372G左右。如果对该数据做查找，那内存压力很大，我们想要高性能地解决这个问题，就得引出Bitmap。

Bitmap概念

一个byte占8个bit，如果每一个bit的值就是有或没有，也就是二进制的0或1。那就可用bit的0或1代表某数组值有或没有。0代表该数值没有出现过，1代表该数组值出现过。具体如下图：

那1亿的数据现在所需的空间0.372G/32，一个原占32bit的数据现在只占用1bit，节省了不少内存。

应用和代码

疑问：一个数怎么快速定位它的索引，也就是说搞清楚byte[index]的索引号index是多少，位置号position是哪一位。

例子：例如add(14)。14已经超出byte[0]的映射范围，在byte[1]的范围内。那怎么快速定位它的索引号？如果找到它的索引号，又怎么找到它的位置号？Index(N)代表N的索引号，Position(N)代表N的位置号。

公式：
Index(N) = N/8 = N >> 3;
Position(N) = N%8 = N & 7;（对于2的幂的数才能这样干！）

例子：
add(int num)向Bitmap里add数据该怎么办?
上面已分析了，add的目的是为了将所在的位置从0变成1，其他位置不变。
（图中间，不是“作与操作”，是“作或操作”。“a|=b”表示a和b作或操作，结果赋给a。）

代码：

public void add(int num)
{
    int index=num>>3;
    int position=num&7;
    byte[index] |= 1<<position;//如图，将1左移position位，使目标位置1
}

Bitmap的其他操作与此类似。还可把byte换成unsigned int，即用32位的unsigned来存。

总结： Bitmap是简单快速的数据结构，常用于空间的优化。

2-Bitmap

每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，其他同Bitmap。

求解

题1答案

也就是出现过但只出现过一次的整数。

方案1：使用2-Bitmap
每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义。然后遍历修改Bitmap中的对应位，如果是00则变01，01则变10，10则保持不变。遍历修改完后，最后遍历输出对应位是01的整数。

方案2：分治法
先将2.5亿个数划分成 2.5亿/2 个组，每个组里2个整数，再在每个组里去掉重复的整数后进行排序，然后再进行归并，最终便可得到只出现过一次的整数。

总结：还是感觉位图好。。。

题2答案

方案1：使用Bitmap
一个bit位代表一个unsigned int值。读入40亿个数，设置相应的bit位。由于2^32=42.9+亿，那么2^32bit才能存下40亿个数，也就需要2^32=4Gb=0.5GB=512M内存。读入要查询的数，查看相应bit位是否为1，为1表示存在，为0表示不存在。

方案2：二分法
我们把40亿个数中的每一个数都用32位的二进制来表示，因为它们的二进制中每一位要么是0要么是1，因此可以根据数据的某一位来分，该位为1的在分配在一组，该位为0的分配在另一组。这里的二分法就是采用了这种思想。
已知需要查询的这位数的二进制的每位是0还是1，所以从最高位到最低位，总共需进行31次二分查找（由于是unsigned类型，所以最高那位都为0），时间复杂度为O(logn)。

总结： 用位图法很直接，但占用内存量会大点；利用二分法比较巧妙，不太容易想到。