[算法系列之十八]海量数据处理之BitMap

我会带着你远行 2023-06-16 07:56 60阅读 0赞

***一：简介***

*所谓的BitMap就是用一个bit位来标记某个元素对应的Value， 而Key即是该元素。由于采用了bit为单位来存储数据，因此在存储空间方面，可以大大节省。*

***二：基本思想***

*我们用一个具体的例子来讲解，假设我们要对0-7内的5个元素(4,7,2,5,3)排序（这里假设这些元素没有重复）。那么我们就可以采用BitMap的方法来达到排序的目的。要表示8个数，我们就只需要8个bit（1Bytes）。   
（1）首先我们开辟1字节（8bit）的空间，将这些空间的所有bit位都置为0，如下图：*

![20150207143647124][]

*（2）然后遍历这5个元素，首先第1个元素是4，那么就把4对应的位置为1,因为是从零开始的，所以要把第5个位置为1（如下图）：*

![20150207143740102][]

*然后再处理第2个元素7，将第8个位置为1,，接着再处理第3个元素，一直到处理完所有元素，将相应的位置为1，这时候的内存的bit位的状态如下：*

![20150207143819256][]

*（3）然后我们现在遍历一遍bit区域，将该位是1的位的编号输出（2，3，4，5，7），这样就达到了排序的目的。*

*算法思想比较简单，但关键是如何确定十进制的数映射到二进制bit位的map图。*

***三：Map映射***

*假设需要排序或者查找的总数N=10000000。   
BitMap中1bit代表一个数字   
1个int = 4Bytes = 4\*8bit = 32 bit,那么N个数需要N/32 int空间。所以我们需要申请内存空间的大小为int a\[1 + N/32\]，其中：a\[0\]在内存中占32为可以对应十进制数0-31，依次类推：*

*BitMap表为：*

a[0]  --------->  0-31 
     a[1]  --------->  32-63 
     a[2]  --------->  64-95 
     a[3]  --------->  96-127 
     ..........

*     
那么十进制数如何转换为对应的bit位，下面介绍用位移将十进制数转换为对应的bit位。*

*申请一个int一维数组，那么可以当作为列为32位的二维数组。*

*a\[0\]*

![20150207145851221][]  
*a\[1\]*

![20150207145851221][]  
*a\[2\]*

![20150207145851221][]  
*a\[3\]*

![20150207145851221][]

*a\[i\] ……………………………….*

*a\[n\]*

![20150207145851221][]

*例如：   
十进制1 在a\[0\]中，位置如下图： *

![20150207150658412][]

*十进制31 在a\[0\]中，位置如下图： *

![20150207150846177][]

*十进制32 在a\[1\]中，位置如下图： *

![20150207150937127][]

*十进制33 在a\[1\]中，位置如下图： *

![20150207151111539][]

*通过上图分析得出通过以下几步将十进制数如何转换为对应的bit位：*

***（1）求十进制数在对应数组a中的下标***

*十进制数0-31，对应在数组a\[0\]中，32-63对应在数组a\[1\]中，64-95对应在数组a\[2\]中………   
**分析得出：对于一个十进制数n,对应在数组a\[n/32\]中 **  
例如n=11,那么 n/32=0，则11对应在数组a中的下标为0，n=32,那么n/32=1，则32对应在数组a中的下标为1，n = 106,那么n/32 = 3，则106对应数组a中的下标为3。*

***（2）求十进制数在对应数组a\[i\]中的下标***

*例如十进制数1在a\[0\]的下标为1，十进制数31在a\[0\]中下标为31，十进制数32在a\[1\]中下标为0。   
在十进制0-31就对应0-31，而32-63则对应也是0-31，即给定一个数n可以通过模32求得在对应数组a\[i\]中的下标。   
**分析得出：对于一个十进制数n,对应在数组a\[n/32\]\[n%32\]中***

***（3）移位***

*对于一个十进制数n,对应在数组a\[n/32\]\[n%32\]中，但数组a毕竟不是一个二维数组，我们通过移位操作实现置1。   
a\[n/32\] |= 1 << n % 32   
移位操作：   
a\[n>>5\] |= 1 << (n & 0x1F)*

*n & 0x1F 保留n的后五位 相当于 n % 32 求十进制数在数组a\[i\]中的下标*

/*--------------------------------
    *   日期：2015-02-07
    *   作者：SJF0115
    *   题目: BitMap
    *   博客：
    ------------------------------------*/
    #include <iostream>
    #include <vector>
    using namespace std;
    
    #define N 1000000000
    
    //申请内存的大小
    int a[1 + N/32];
    
    // 设置所在的bit位为1
    void BitMap(int n){
        // row = n / 32 求十进制数在数组a中的下标
        int row = n >> 5;
        // n & 0x1F 保留n的后五位
        // 相当于 n % 32 求十进制数在数组a[i]中的下标
        a[row] |= 1 << (n & 0x1F);
    }
    // 判断所在的bit为是否为1
    bool Exits(int n){
        int row = n >> 5;
        return a[row] & ( 1 << (n & 0x1F));
    }
    
    void Show(int row){
        cout<<"BitMap位图展示："<<endl;
        for(int i = 0;i < row;++i){
            vector<int> vec;
            int tmp = a[i];
            for(int i = 0;i < 32;++i){
                vec.push_back(tmp & 1);
                tmp >>= 1;
            }//for
            cout<<"a["<<i<<"]"<<"->";
            for(int i = vec.size()-1;i >= 0;--i){
                cout<<vec[i]<<" ";
            }//for
            cout<<endl;
        }//for
    }
    
    int main(){
        int num[] = {1,5,30,32,64,56,159,120,21,17,35,45};
        for(int i = 0;i < 12;++i){
            BitMap(num[i]);
        }//for
        int row = 5;
        Show(5);
        /*if(Exits(n)){
            cout<<"该数字已经存在"<<endl;
        }//if
        else{
            cout<<"该数字不存在"<<endl;
        }//else*/
        return 0;
    }

![20150207162831312][]

***应用范围***

*可以运用在快速查找、去重、排序、压缩数据等。*

***c++版BitMap***

*在C++中提供了bitset这种集合，专门用来进行位操作，因此实现起来比较容易。   
具体参考：STL bitset用法总结*

***扩展***

*Bloom filter可以看做是对BitMap的扩展   
布隆过滤器具体参考：\[算法系列之十\]大数据量处理利器：布隆过滤器*

***具体应用***

*（1）已知某个文件内包含一些电话号码，每个号码为8位数字，统计不同号码的个数。*

***思路 **  
电话号码每个为8位数字，最小电话号码为00 000 000，最大99 999 999，一共100 000 000个电话号码，   
100 000 000bit = 12 500 000Bytes = 12MBytes 故需要12Mbytes的内存即可存储所有的电话号码。   
可以理解为从00 000 000 - 99 999 999的数字，每个数字对应一个bit位，所以只需要12MBytes，这样，就用了小小的12M左右的内存表示了所有的8位数的电话。*

***代码***

/*-------------------------------------
        *   日期：2015-03-27
        *   作者：SJF0115
        *   题目: 统计电话号码个数
        *   来源：海量数据
        *   博客：
        ------------------------------------*/
        #include <iostream>
        #include <vector>
        #include <time.h>
        using namespace std;
        // 给定的电话号码个数
        #define NUM 1000
        // 电话号码的最小值
        #define MIN 10000000
        // 电话号码的最大值
        #define MAX 99999999
        // 电话号码总共个数
        #define N (MAX - MIN + 1)
    
        // 置1
        void SetBitMap(int bitMap[],int num){
            num -= MIN;
            //bitMap[num/32] |= 1 << num % 32;
            bitMap[num >> 5] |= (1 << (num % 32));
        }//void
    
        // 置0
        void ClearBitMap(int bitMap[],int num){
            bitMap[num >> 5] &= ~(1 << (num % 32));
        }//void
    
        // 获取
        bool GetBitMap(int bitMap[],int num){
            return bitMap[num >> 5] & (1 << (num % 32));
        }//void
        // 统计电话号码个数
        int PhoneCount(int phone[],int n,int bitMap[]){
            for(int i = 0;i < n;++i){
                SetBitMap(bitMap,phone[i]);
            }//for
            // 统计个数
            int count = 0;
            for(int i = 0;i < N;++i){
                if(GetBitMap(bitMap,i)){
                    ++count;
                }//if
            }//for
            return count;
        }
    
        int main(){
            // 随机生成NUM个电话号码
            int phone[NUM];
            // 位图大小
            int* bitMap = new int[N/32+1];
            // 清空
            for(int i = 0;i < N;++i){
                ClearBitMap(bitMap,i);
            }//for
            // 随机生成100个电话号码
            srand((unsigned)time(nullptr));
            for(int i = 0;i < NUM;++i){
                phone[i] = rand() % N + MIN;
                cout<<phone[i]<<endl;
            }//for
            cout<<"电话号码个数->"<<PhoneCount(phone,NUM,bitMap)<<endl;
            return 0;
        }

*待完善…….*

*引用：   
http://blog.csdn.net/hguisu/article/details/7880288   
http://blog.csdn.net/v\_july\_v/article/details/6685962   
http://www.tuicool.com/articles/mUb2Qnn   
http://nemogu.iteye.com/blog/1522332   
http://blog.csdn.net/v\_july\_v/article/details/7382693*

*本文原文地址：*[https://blog.csdn.net/SunnyYoona/article/details/43604387][https_blog.csdn.net_SunnyYoona_article_details_43604387]

[20150207143647124]: https://img-blog.csdn.net/20150207143647124
[20150207143740102]: https://img-blog.csdn.net/20150207143740102
[20150207143819256]: https://img-blog.csdn.net/20150207143819256
[20150207145851221]: https://img-blog.csdn.net/20150207145851221
[20150207150658412]: https://img-blog.csdn.net/20150207150658412
[20150207150846177]: https://img-blog.csdn.net/20150207150846177
[20150207150937127]: https://img-blog.csdn.net/20150207150937127
[20150207151111539]: https://img-blog.csdn.net/20150207151111539
[20150207162831312]: https://img-blog.csdn.net/20150207162831312
[https_blog.csdn.net_SunnyYoona_article_details_43604387]: https://blog.csdn.net/SunnyYoona/article/details/43604387