从位图原理到布隆过滤器的实现

bitmap位图

引子

首先通过一道题来理解什么是bitmap。

1. 题目：我有40亿个整数，再给一个新的整数，我需要判断新的整数是否在40亿个整数中，你会怎么做？
2. 分析：

假设一个int占4个字节（32位），40个亿个整数就是160亿个字节，大概相当于16GB，假设一台计算机只有2GB内存，则16GB一次加载不完，需要分8次加载，从磁盘加载数据是磁盘io操作，是非常慢的（比内存中的操作要慢100倍），每次加载这么大的数据，并且要8次，那么查找的时间可以达到分钟甚至小时级别。

还有一个办法是把数据分散在8台计算机上，然后来一个新数据，8台计算机同时找，然后再汇总结果。这样每台计算机都可以一次性把数据读入内存中，查找就不用来回加载数据，省去了加载数据的开销，是个好方法。

但是否还有其他更好的方法呢？那就是bitmap。bitmap存值的思路：每一个int有32位，int整数的范围是-2147483648 ~ 2147483647。为简化理解，这里先假设每一个整数位均为正整数（如果存在负整数需分开处理），2147483647/32 = 67108863，即只需要67108863个int型整数就可以表示 [0，2147483647] 范围的数字，即需要67108863*4 = 268,435,452‬个字节的内存，相当于0.2GB，即使加上负整数部分也才需要0.4GB的内存，一台计算机完全足够。这里将开辟67108863int型数组，数组中的每一位代表依次代表 [0，2147483647]。而且而且判断新的整数也只需要O(1)的时间复杂度，性能非常高

bitmap定义

位图是一个数组的每一个数据的每一个二进制位表示一个数据，0表示数据不存在，1表示数据存在。

例如存储136这个数：

• 确定136在整个数据的那个区间，136/32 = 4，即在第四个区间；
• 确定136在这个区间的第几位（bit），136%32 = 25，即在第四区间的第25位上；
• 将这个位置置为1，表示存在这个数。

由于bitmap的数据存储方式，具有升序排序的性质。

代码实现

class Bitmap {
public:
    Bitmap(size_t size) : size(size) 
    {
        // 多开辟一个空间,原因是数组只能表示区间[0,size)
        bits.resize((size >> 5) + 1);  
    }
    void bitmapSet(int val) 
    {
        int index = val >> 5;  // 相当于除以32，用移位操作可提高性能
        int offset = val % 32;
        bits[index] |= (1 << offset);
        int capacity = bits.capacity();
    }
    bool bitmapGet(int val) {
        int index = val >> 5;   // 第几个区间
        int offset = val % 32;  // 偏移位数
        return bits[index] & (1 << offset);
    }

private:
    vector<unsigned int> bits;
    size_t size;
};

bloom filter布隆过滤器

引子

《数学之美》介绍布隆过滤器非常经典：在日常生活中，包括设计计算机软件时，经常要判断一个元素是否在一个集合中。比如：

• 在字处理软件中，需要检查一个英语单词是否拼写正确（也就是要判断它是否在已知的字典中）；
• 在FBI，一个嫌疑人的名字是否已经在嫌疑犯的名单上；
• 在网络爬虫里，一个网站是否已访问过；
• yahoo, gmail等邮箱垃圾邮件过滤功能，等等 ...

以上场景需要解决的共同问题是：如何查看一件事物是否在有大量数据的集合里。

通常的做法有以下几种思路：数组，链表，树，平衡二叉树，Trie，map (红黑树)，哈希表等

上面这几种数据结构配合一些搜索算法是可以解决数据量不大的问题，但当集合里面的数据量非常大的时候，就会出现问题。比如：有500万条记录甚至1亿条记录？这个时候常规的数据结构的问题就凸显出来了。数组、链表、树等数据结构会存储元素的内容，一旦数据量过大，消耗的内存也会呈现线性增长，最终达到瓶颈。哈希表查询效率可以达到O(1)。但是哈希表需要消耗的内存依然很高。使用哈希表存储一亿 个垃圾 email 地址的消耗？哈希表的做法：首先，哈希函数将一个email地址映射成8字节信息指纹；考虑到哈希表存储效率通常小于50%（哈希冲突）；因此消耗的内存：8 * 2 * 1亿 字节 = 1.6GB 内存。因此，存储几十亿个邮件地址就可能需要上百GB的内存。除非是超级计算机，一般服务器是无法存储的。这个时候，布隆过滤器（Bloom Filter）就应运而生。

布隆过滤器

Bloom Filter是由伯顿 · 布隆（Burton Bloom）于1970年提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。我们由上面的例子来说明其工作原理。

假定存储一亿个电子邮件地址，先建立一个16亿二进制（比特），即两亿字节的向量，然后将这个16亿二进制位全部清零。对于每一个电子邮件地址X，用8个不同的随机数产生器（F1，F2，...，F8）产生8个信息指纹（f1，f2，...，f8）。再用一个随机产生器G把这8个信息指纹映射到1-16亿中的8个自然数g1，g2，...，g8（其实就是8个哈希函数）。现在把这8个位置的二进制全部设置为1。对这一亿个电子邮件地址都进行这样的处理后，一个针对这些电子邮件地址的布隆过滤器就建成了，这个过程如下图。另外值得注意的是，想要保持错误率低，最好让位数组有一半还空着。即16亿个二进制位最多有8亿个二进制位被置为1，误识别率就会降到很低。

布隆过滤器过程

现在，让我们看看如何用布隆过滤器来监测一个可疑的电子邮件地址Y是否在黑名单中。用相同的8个随机产生器（F1，F2，...，F8）产生这个地址的8个信息指纹s1，s2，...，s8，然后将这个8个指纹对应到布隆过滤器的8个二进制位，分别为t1，t2，...，t8。如果Y在黑名单中，显然，t1，t2，...，t8对应的二进制数一定是1。这样，再遇到任何在黑名单中的电子邮件地址都能准确发现。布隆过滤器绝不会漏掉黑名单中的任何一个可疑地址。但是，它有一个不足之处。也就是它有极小的可能将一个不在黑名单中的电子邮件地址也判定为黑名单中，因为有可能某个好的邮件地址在布隆过滤器中对应的8个位置“恰巧”被（其他地址）设置为1。好在这种可能性很小。我们称之为误识别率。在上面的例子中，误识别率在万分之一以下。布隆过滤器的好处在于快速、省时间，但是有一定的误识别率。常见的补救办法是再建立一个小的白名单，存储那些可能被误判的邮件地址

代码实现

class BloomFilter {
private:
    struct SimpleHash {
        SimpleHash() {}
        SimpleHash(size_t cap, size_t seed)
        : capacity(cap), seed(seed) {}
        int hash(const string& s) 
        {
            int result = 0;
            for (auto c : s) 
                result = result * seed + c;
            return (capacity - 1) & result;
        }
        private:
            size_t capacity;
            size_t seed;
    };
    enum { kDefaultSize = 100000000 * 16 };  //16亿
public:
    BloomFilter() 
    {
        bitmap = new Bitmap(kDefaultSize);
        hashs.reserve(seeds.size());
        for (int i = 0; i < seeds.size(); ++i) {
            SimpleHash* hash = new SimpleHash(kDefaultSize, seeds[i]);
            hashs.push_back(hash);
        }
    }
    ~BloomFilter() 
    {
        delete bitmap;
        for (auto h : hashs) {
            delete h;
        }
    }
    void add(const string& s) 
    {
        for (auto h : hashs) 
            bitmap->bitmapSet(h->hash(s));
    }
    bool contain(const string& s) 
    {
        bool result = true;
        for (auto h : hashs) 
            result = result && bitmap->bitmapGet(h->hash(s));
        return result;
    }
private:
    vector<int> seeds = { 7, 11, 13, 31, 37, 61, 73, 97 };  //还不是随机生成
    vector<SimpleHash*> hashs;
    Bitmap* bitmap;
};