Bitmap和BloomFilter

旧城等待， 2022-05-22 09:07 158阅读 0赞

# 题目 #

5TB的硬盘上放满了数据，请写一个算法将这些数据进行排重。如果这些数据是一些32bit大小的数据该如何解决？如果是64bit的呢？

# 1、Bitmap #

Bitmap又叫做位图，判断数组中的某位索引值下的位是否为1，来表示这个数是否存在。假如53存在，那么就将数组中的第53位置1。这样Bitmap极大地压缩了所需要的内存空间，并且还额外地完成了对原始大型数据的排序工作。使用位图可以大大节省元素存储空间，并进行快速查找、排序、判重、删除等工作。下面是一个位图的简单实现，原理是通过数据的最大值，确定数组的大小。然后将数组中对应的位置1表示数据中的数。

/* 位图 */
    #define BITWORD 32
    //一个int占用4字节，对应32位
    
    #define SHIFT 5
    //判断数据在哪个数组中的哪一位，通常的做法就是 num/32 = n余m,n代表第几个数组，m代表这个数组的第几位，
    //shift = 5 通过移位简化了除法。
    
    #define MASK 31
    //通过&简化了取余操作。
    
    #define MaxNum 10000000
    //定义最大数值
    
    unsigned int a[1+N/BITWORD];
    //申请总共位N位的数组
    
    void SetBit(unsigned int i){
        a[i>>SHIFT] |= (1<<(i & MASK));//第几个数组的第几位
    }
    void ClrBit(unsigned int i){
        a[i>>SHIFT] &= ~(1<<(i & MASK));
    }
    bool TestBit(unsigned int i){
        return a[i>>SHIFT] & (1<<(i & MASK));//这一位是否为1
    }
    int main(void)
    {
        //。。。。。。。操作处理//
        return 0;
    }

可以处理的问题如下：

1、判断集合中是否存在重复的问题。当数据比较大的时候，位图法比较合适。还是可以使用hashtable实现，但是比较浪费内存空间，这就可以使用位图。  
2、某个文件中有一些电话号码，每个号码8位数，统计不同号码的个数。  
使用set，内部实际上使用了hashtable，或者使用位图，然后统计1的个数。  
统计1的个数有快速方法。

int NumberOf1_1(int num)
    {
        int count = 0;
        unsigned int flag = 1;//左移动，全部补0，对于逻辑右移，负数补1，正数补0，所以得用flag移动，避免了负数的问题。
        while(flag){
            if(num & flag)
                count++;
            flag <<= 1;
        }
        return count;
    }
    int NumberOf1(unsigned int num)
    {
        int count = 0;
        while(num){
            count++;
            num = (num-1)&num;//将最右边1变成0，再重复判断，避免了移位负数的处理
        }
        return count;
    }

3、给出40亿个不重复的unsigned int的数，没排序，如何快速再给一个数，快速判断这个树知否存在于40亿个数之中。申请512M的内存。然后通过位图即可。如果内存需要进一步压缩，那么就使用布隆过滤器实现。

# 2、BloomFilter #

然而Bitmap不是万能的，如果数据量大到一定程度，如开头写的64bit类型的数据，那么就算使用位图，也需要2EB的内存空间，这是不可能的。所以接下来要引入另一个著名的工业实现——布隆过滤器（Bloom Filter）。  
![这里写图片描述][70]  
![这里写图片描述][70 1]  
![这里写图片描述][70 2]  
![这里写图片描述][70 3]

[至于判定的错误概率有多大，这就是一个数学问题了。][Link 1]

[70]: /images/20220522/1dffe584b932412a8756740f2c090832.png
[70 1]: /images/20220522/cce802528dc8403a8c9952b4f31561a6.png
[70 2]: /images/20220522/1bc2c9f1adf54598b0d39b33daee7858.png
[70 3]: /images/20220522/2c17045ae4db40c7a50e29a9d6d7b705.png
[Link 1]: https://blog.csdn.net/zdxiq000/article/details/57626464