C++ 位图与布隆过滤器实现及应用

1. 位图

给 40 亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这 40 亿个数中？

放在哈希表中去寻找？不，这并不现实，因为哈希表的存储也是需要空间消耗的，况且是 40 亿个数据，如此庞大的数据计算机一般是很难存储。

因此就诞生了位图的概念，位图简单来说就是把每个数按照哈希函数的计算，存储到每个比特位上。数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为 1，代表存在，为 0 代表不存在。

1.1 位图的结构

template<size_t N>
class bitset {
public:
    bitset() { _a.resize(N / 32 + 1); }
private:
    std::vector<int> _a;
};

开辟一个 vector 数组 _a，这里我们以 int 作为位图的基本单位，那么就是把每个数据存储到 int 的比特位上。

值得注意的是：resize 的时候无论如何都要加 1，比如 100 个数据，除以 32，等于 3，余 4，那么就需要多一个 int 空间来存储，不能说每次都卡好刚好 32 整除。

1.2 位图映射的比特位标记成 1

// x 映射的那个标记成 1
void set(size_t x) {
    size_t i = x / 32;
    size_t j = x % 32;
    _a[i] |= (1 << j);
}

i 用于确定在第几个 int 里，j 用于确定在第几个 int 的第几位上。

二进制位从右到左是最低位到最高位，所以左移即可。

1.3 位图映射的比特位标记成 0

// x 映射的那个标记成 0
void reset(size_t x) {
    size_t i = x / 32;
    size_t j = x % 32;
    _a[i] &= (~(1 << j));
}

同理，因为按位与是有 0 就是 0，直接计算即可。

1.4 位图映射判断为 1 or 0

bool test(size_t x) {
    size_t i = x / 32;
    size_t j = x % 32;
    return _a[i] & (1 << j);
}

注意这里是 &，而不是 &=，因为只需要判断，而不是修改。

位图通常不支持删除功能，因为没有必要删除。

2. 布隆过滤器

我们在存储字符串数据时，是通过计算这个字符串的 ASCII 码值之和，然后通过哈希函数计算存入的，但是这可能会产生哈希冲突，但是数据量太大了，无法通过常规的方法解决。

那么最简单的方法就是降低误判率，通过多个不同哈希函数计算，将一个值映射多个位置，这样不至于每次查找都会产生冲突。

1. 用哈希表存储用户记录，缺点：浪费空间
2. 用位图存储用户记录，缺点：位图一般只能处理整形，如果内容编号是字符串，就无法处理了
3. 将哈希与位图结合，即布隆过滤器

再举个现实点的例子，就能理解布隆过滤器存在的必要：

比如我们在注册账号昵称时，会显示是否已经被取过，先在布隆过滤器中进行查找，若不在，那么成功注册；如果在，那么就到数据库中查询，这样能减少数据库查询次数，降低负载压力，提升整体查询效率。

2.1 布隆过滤器的结构

template<size_t N, class K = string, class Hash1 = BKDRHash, class Hash2 = APHash, class Hash3 = DJBHash>
class BloomFilter {
private:
    std::bitset<N> _bs;
};

Hash1、Hash2、Hash3 是用于计算 string 存储的哈希函数，STL 库里是有 bitset 使用的，直接开辟位图空间即可。

2.2 布隆过滤器的哈希函数

struct BKDRHash {
    size_t operator()(const string& str) {
        size_t hash = 0;
        for (auto ch : str) {
            hash = hash * 131 + ch;
        }
        return hash;
    }
};

struct APHash {
    size_t operator()(const string& str) {
        size_t hash = 0;
        for (size_t i = 0; i < str.size(); i++) {
            size_t ch = str[i];
            if ((i & 1) == 0) {
                hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
            } else {
                hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
            }
        }
        return hash;
    }
};

struct DJBHash {
    size_t operator()(const string& str) {
        size_t hash = 5381;
        for (auto ch : str) {
            hash += (hash << 5) + ch;
        }
        return hash;
    }
};

选取了三种计算冲突较小的哈希函数算法进行计算，因为需要多处使用，以仿函数的形式更加方便快捷。

2.3 布隆过滤器的插入

void Set(const K& key) {
    size_t hash1 = Hash1()(key) % N;
    _bs.set(hash1);
    size_t hash2 = Hash2()(key) % N;
    _bs.set(hash2);
    size_t hash3 = Hash3()(key) % N;
    _bs.set(hash3);
}

由于是以仿函数的方式进行，Hash1() 是匿名对象，有了对象才能以函数的形式调用参数。

2.4 布隆过滤器映射判断为 true or false

bool Test(const K& key) {
    size_t hash1 = Hash1()(key) % N;
    if (_bs.test(hash1) == false) return false;
    size_t hash2 = Hash2()(key) % N;
    if (_bs.test(hash2) == false) return false;
    size_t hash3 = Hash3()(key) % N;
    if (_bs.test(hash3) == false) return false;
    return true;
}

2.5 布隆过滤器的优缺点

优点：

1. 增加和查询元素的时间复杂度为：O(K)，(K 为哈希函数的个数，一般比较小)，与数据量大小无关
2. 哈希函数相互之间没有关系，方便硬件并行运算
3. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
4. 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势
5. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能
6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算

缺点：

1. 有误判率，即存在假阳性 (False Positive)，即不能准确判断元素是否在集合中 (补救方法：再建立一个白名单，存储可能会误判的数据)
2. 不能获取元素本身
3. 一般情况下不能从布隆过滤器中删除元素
4. 如果采用计数方式删除，可能会存在计数回绕问题

3. 常见面试题

3.1 哈希切割

3.1.1 问题一

给一个超过 100G 大小的 log file，log 中存着 IP 地址，设计算法找到出现次数最多的 IP 地址？

解决方法：

对于超过 100G 的日志文件，直接加载到内存是不可行的，既然大的不行，就把文件分割为小文件一个个进行。

使用哈希函数计算将 IP 映射到不同的小文件中，确保相同 IP 进入同一个文件，对每个小文件，使用哈希表统计 IP 频率，合并所有小文件的统计结果，就能找出出现次数最多的 IP。

3.1.2 问题二

与上题条件相同，如何找到 top K 的 IP？

解决方法：

既然相同 IP 一定进入同一个小文件，用 map 去统计每个文件中 IP 出现的次数即可。

3.2 位图应用

3.2.1 问题一

给定 100 亿个整数，设计算法找到只出现一次的整数？

解决方法：

对于 100 亿个整数（约 40GB 数据），直接加载到内存显然不可行。我们可以使用位图和哈希分治相结合的方法高效解决这个问题——双位图法。

使用两个位图，每个整数对应两位：

• 00：整数未出现
• 01：整数出现 1 次
• 10：整数出现 2 次及以上

假设计算出第一个数据映射第一个位置，且第一次出现，则上面的位图第一位设置为 0，下面位图的第一位设置为 1。其他情况依次类推。

template<size_t N>
class twobitset {
public:
    void set(size_t x) {
        // 00 -> 01
        if (!_bs1.test(x) && !_bs2.test(x)) {
            _bs2.set(x);
        }
        // 01 -> 10
        else if (!_bs1.test(x) && _bs2.test(x)) {
            _bs1.set(x);
            _bs2.reset(x);
        }
        // 本身 10 代表出现 2 次及以上，就不变了
    }
    bool is_once(size_t x) {
        return !_bs1.test(x) && _bs2.test(x);
    }
private:
    std::bitset<N> _bs1;
    std::bitset<N> _bs2;
};

最后遍历位图对每一位进行 is_once 函数的判断，符合一次的存入哈希表即可。

3.2.2 问题二

给两个文件，分别有 100 亿个整数，我们只有 1G 内存，如何找到两个文件交集？

解决方法：

还是利用两个位图的方式解决，一个文件映射一个位图，对应的位置 & 按位与一下，两个位置都为 1，则这个位置是交集，注意存储的值应该放在 set 里去重。

3.2.3 问题三

1 个文件有 100 亿个 int，1G 内存，设计算法找到出现次数不超过 2 次的所有整数

解决方法：

和问题一的方法是一样的，只不过改一下表示方法而已。

• 00：整数未出现
• 01：整数出现 1 次
• 10：整数出现 2 次
• 11：整数出现 3 次及以上

3.3 布隆过滤器应用

3.3.1 问题一

给两个文件，分别有 100 亿个 query，我们只有 1G 内存，如何找到两个文件交集？分别给出精确算法和近似算法

解决方法：

近似算法：

用文件 A 的所有 query 构建布隆过滤器，遍历文件 B 的每个 query，判断是否可能在 A 中，对布隆过滤器返回'可能存在'的 query，再在文件 A 中精确验证，但是这种方法并不百分百准确，可能存在误判。

精确算法：

将 A、B 文件都分割为同样数量的小文件，都上好编号，因为经过相同哈希函数计算，所以 A 和 B 中相同的 query 必定分别进入 Ai 和 Bi 文件中，因此 A0 和 B0 比较，A1 和 B1 进行比较，以此类推即可。

3.3.2 问题二

如何扩展 BloomFilter 使得它支持删除元素的操作？

解决方法：

将标准布隆过滤器的每个二进制位扩展为一个小计数器（通常 4-8 位），当插入元素时增加计数器，删除时减少计数器。只有当计数器为 0 时，才表示该位置未被占用。