一篇文章搞懂bitmap算法（待更新）
BitMap算法
-
热点
-
什么是BitMap算法
-
- 问题
- 解法
- BitMap算法
-
BitMap算法举例
-
- 简单的排序问题
- 海量数据的查找问题
-
针对第二个问题
热点
BitMap算法，一直是面试的热点问题，当然它也是在海量数据进行快速查找，判重，删除的基本方法。什么是BitMap算法
问题
在介绍bitmap算法之前，先来看下面几个与bitmap有关的问题
1. 给40亿个不重复的int的整数，没排过序的，然后在给一个数，如何快速判断这个数是否在哪40亿个数当中。
2. 在2.5亿个整数中找出不重复的整数（内存不足以容纳这2.5亿个整数）解法
下面针对第一个问题分别给出不同的解法：
为了存储数据并进行搜索，在无序的数据集中找到特定数值是一项具有挑战性的任务。对于刚入门的学习者而言，在内存中临时存储所有数据是一种直观的选择。然而，在实际应用中存在一些局限性：首先，在机器内存资源较为紧张的情况下（如仅拥有4GB内存），即使采用线性查找或哈希表方法也无法避免效率上的瓶颈问题。例如，在32位平台上估算发现：将40亿个unsigned int整数装入内存总共需要16GB的空间（每个整数占用4字节空间），而这样的规模计算本身也需要耗费一定的时间资源。此外，在处理大量数据时还需要考虑时间复杂度的问题：即使设计了一个高效的哈希函数来加快定位速度，但磁盘IO操作的时间开销往往会显著增加整体运行时间。因此，在这种情况下单纯依靠内存计算的方式就显得力不从心了。聪明的学习者可能会想到另一种方法：通过外部存储进行查询无需加载全部数据到内存中
对于这个问题一些学习过大数据或分布式相关知识的同学会想到采用分布式的方法假设每台机器可分配用于该计算任务的内存为2.5G那么可以同时对不同数据块进行搜索最后将结果汇总即可这样的设计思路很好能够在短时间内完成任务但它过于直接不够聪明因为单独一台机器在解决问题时依然采取暴力的方式
BitMap算法
在分析海量整数查找问题的各种解决思路时发现：这些方法都致力于最大限度地将数据加载至内存以便进行查找操作。当单机内存不足以容纳全部数据时，则需要借助多台机器或者分批加载技术来完成任务。
进一步介绍一种高效算法：这种算法能够有效地将高达40亿个整数一次性加载至内存中，并且在占用较少内存资源的前提下实现快速查找功能。
利用每个bit位存储信息的方式——bitmap技术——能够简洁高效地表示数据集合的状态信息；其中每个bit位对应某个特定的数据元素；用来标识该元素的就是其对应的键值（Key）。
BitMap算法举例
简单的排序问题
为了对位于0至7范围内的5个元素进行排序（4、7、2、5、3），我们可以选择一种高效的数据处理方式来完成此任务
接下来，在对这5个待排序元素进行处理时，我们可以首先查看第一个元素的值为4，并将其对应的位置赋值为1（即p + (i/8) | (0x01 << (i % 8))）。需要注意的是，在大端与小端的处理上存在一定的差异，在网络编程领域对此有详细的讨论。因为索引是从0开始计算的，在这种情况下会使得第五位的位置将被赋值为1（如图2所示）。
重复上面步骤处理完所有的元素后，内存中bit位的状态如图3所示：
随后只需遍历单一遍历Bit域，并输出所有置位为1的位号（2、3、4、5、7），从而实现了排序效果
#include<memory.h>
#define BYTESIZE 8 //定义每个Byte中有8个bit位
void SetBit(char *p,int posi)
{
for(int i=0;i<(posi/BYTESIZE);i++)
{
p++;
}
*p=*p|(0x01<<(posi%BYTESIZE)); //将该bit位赋值为1
return；
}
void BitMapSortDemo(){
//为了简单起见，暂时不考虑负数
int num[]={3,5,2,10,6,12,8,14,9};
//bufferLen这个值时根据待排序的数据中最大值确定的
//待排序中的最大值是14，因此只需要2个Bytes（16个Bit）
const int BufferLen=2;
char *pBuffer=new char[BufferLen];
//将所有的Bit位置为0
memset(pBuffer,0,BufferLen);
for(int i=0;i<9;i++)
{
//将相应Bit位上置为1
SetBit(pBuffer,num[i]);
}
//输出排序结果
for(int i=0;i<BufferLen;i++){ //每次处理一个字节
for(int j=0;j<BYTESIZE;j++){ //每次处理字节中的每个Bit位
//判断该位置上是否为1，进行输出
//首先得到该第j位的掩码（0x01<<j）,将内存区中的位
//和此掩码作与操作，最后判断掩码是否和处理后的结果相同
if((*pBuffer&(0x01<<j))==(0x01<<j))
{
printf("%d ",i*BYTESIZE+j);
}
}
pBuffer++;
}
}
int _tmain(int argc,_TCHAR* argv[])
{
BitMapSortDemo();
return 0;
}程序的运行结果如图2所示：
海量数据的查找问题
通过几个简单的示例，我们可以初步了解bitmap算法的基本原理。为了进一步阐述bitmap如何高效解决在40亿个整数中快速查找的问题，请稍后继续阅读。实际上这一过程并不复杂。
内存中存储的是int类型的整数，在这种情况下我们通常关注的是32位int的取值范围（通常为-2^31到+ (2^31-1)）。总共有约2^{32}个可能值（约4, 但需要注意的是，在计算机系统中通常使用无符号int类型来处理这个问题）。因此我们需要分配一个包含足够空间表示所有可能整数值的bit数组。
每个bit位对应一个唯一的整数值。当某个特定的整数值存在时，其对应的bit位将被设置为1；否则该bit位将保持为0状态。
当需要验证一个特定的整数值是否存在时，请记住只需检查该整数值对应的bit位是否设置为1即可实现高效的查找操作。
值得注意的是，在内存占用方面这一方法具有显著优势：8 \times (511MB \sim 576MB)的空间需求相比传统的哈希表方法来说要低得多（例如需要至少~\text{大约}~ ~\text{具体数字}~ 的存储空间），从而显著减少了整体内存消耗量。
针对第二个问题
如何在2.5亿个整数中找出不重复的整数(内存不足容纳2.5亿个整数)
采用二进制位掩码（Bitmask）技术（每个数值分配占用两个二进制位），其中：
- 二进制值"00"表示该数值不存在于当前集合中；
- "01"表示该数值仅出现了一次；
- "10"表示该数值出现过两次及以上；
- "11"则表示该数值无意义。
所需内存为2^{32} \times 2{\text{bit}} = 1{\text{GB}}。
随后遍历超过2.5亿个整数，并对bitmap掩码中的相应位进行检查： - 若当前位值为"00"则将其更新为"01";
- 若当前位值为"01"则将其更新为"10";
- 若当前位值为"10"则保持不变。
完成上述操作后，
遍历bitmap掩码后将所有对应位为"01"的整数提取并输出即可。
另外一种方法类似于第[一]种方法，
只不过采用了划分小数据集的方式进行处理：
即首先将整个数据集划分为多个小数据集，
接着在每个小数据集中找出唯一的整数并排序，
最后对这些排序好的小数据集进行归并操作，
同时需注意去除归并过程中出现的重复元素。