C++ 哈希扩展：位图与布隆过滤器详解及实现

简单测试一下，开 $2^{32}$ 个比特位不在话下：

#include "bitset.h"
int main() {
    lydly::Bitset<0xffffffff> bs; // 开 2^32 位
    for (size_t i = 0; i < 5000; i++) {
        bs.set(i);
    }
    for (int i = 0; i < 100; i++) {
        int n = rand() % 10000;
        if (bs.test(n)) {
            cout << n << "存在" << endl;
        } else {
            cout << n << "不存在" << endl;
        }
    }
    return 0;
}

有了位图这样的数据结构，解决上面的问题就很轻松了。40 亿个无符号整数，数的范围是 0~$2^{32}$，所以要给位图开 $2^{32}$ 个位。然后从文件中依次读取每个数存放到位图中，之后的每次查询，就可以达到 O(1) 的速度了。

2. std::bitset

实际上，C++ 库中已经提供了位图 std::bitset，核心接口还是 set、reset、test 等。还有一些其他功能，如 operator[] 允许我们像数组一样用下标控制位，to_string 可以将位图转化为一个 01 字符串。

位图的优点是增删查改的效率很高，节省空间。缺点是他只适用于整型数据。

二、布隆过滤器（Bloom Filter）

1. 概念

在一些场景下，有海量数据需要查询判断是否存在，但这些数据不是整型，那么就无法使用位图了，红黑树、哈希表这些内存空间不足。这种场景下就可以使用布隆过滤器。

布隆过滤器是由布隆提出的一种概率型数据结构，特点是可以高效插入和查询，很难进行删除，它可以查询某个数据'可能在'或'一定不在'，其思路是利用哈希函数将一个非整型数据映射为整型，再映射到比特位中。这种方式不仅可以提升查询效率，也能节省大量内存。

但是，只用一个哈希函数映射到一个位时，很容易造成哈希冲突。为了降低哈希冲突，一般会通过使用多个哈希函数，映射到多个位上，共同表示数据是否存在，这些位都为 1 才表示这个数据存在。布隆过滤器和哈希桶不一样，它始终无法解决哈希冲突，只能尽可能降低冲突率。因此，用布隆过滤器判断一个数据是否存在，不是完全准确的！判断一个数据不存在，是准确的！

2. 布隆过滤器误判率数学推导

布隆过滤器的数学推导过程比较复杂，这里梳理关键步骤：

假设变量：

• m：布隆过滤器的 bit 长度
• n：插入布隆过滤器的元素个数
• k：哈希函数的个数

概率推导：

1. 布隆过滤器哈希函数条件下某个位设置为 1 的概率：$\frac{1}{m}$
2. 布隆过滤器哈希函数条件下某个位设置不为 1 的概率：$1 - \frac{1}{m}$
3. 经过 k 次哈希后，某个位置依旧不为 1 的概率：$(1 - \frac{1}{m})^k$ 根据极限公式：$\lim_{n \to \infty}(1 - \frac{1}{m})^{-m} = e$ 推导出：$(1 - \frac{1}{m})^k = ((1 - \frac{1}{m})^m)^{\frac{k}{m}} \approx e^{-\frac{k}{m}}$
4. 添加 n 个元素某个位置不置为 1 的概率：$(1 - \frac{1}{m})^{kn} \approx e^{-\frac{kn}{m}}$
5. 添加 n 个元素某个位置置为 1 的概率：$1 - (1 - \frac{1}{m})^{kn} \approx 1 - e^{-\frac{kn}{m}}$
6. 查询一个元素，k 次 hash 后误判的概率（都命中 1 的概率）：$(1 - (1 - \frac{1}{m})^{kn})^k \approx (1 - e^{-\frac{kn}{m}})^k$

结论：

• 布隆过滤器的误判率为： $f(k) = (1 - e^{-\frac{kn}{m}})^k$
• 误判率变化规律：在 k 一定的情况下，n 增加时误判率增加，m 增加时误判率减少。
• 最优哈希函数个数：在 m 和 n 一定时，对误判率公式求导，可得 $k = \frac{m}{n} \ln 2$ 时误判率最低。
• 期望的误判率 p 和插入数据个数 n 确定时，再把上面的公式带入误判率公式可得到布隆过滤器 bit 长度：$m = -\frac{n \times \ln p}{(\ln 2)^2}$

3. 实现

我们要给布隆过滤器多个哈希函数算法，可以借鉴前人创造的一些算法：

struct HashFuncBKDR {
    /* 本算法由于在 Brian Kernighan 与 Dennis Ritchie 的《The C Programming Language》一书被展示而得名，是一种简单快捷的 hash 算法，也是 Java 目前采用的字符串的 Hash 算法，累乘因子为 31*/
    size_t operator()(const std::string& s) {
        size_t hash = 0;
        for (auto ch : s) {
            hash *= 31;
            hash += ch;
        }
        return hash;
    }
};

struct HashFuncAP {
    // 由 Arash Partow 发明的一种 hash 算法。
    size_t operator()(const std::string& s) {
        size_t hash = 0;
        for (size_t i = 0; i < s.size(); i++) {
            if ((i & 1) == 0) {
                hash ^= ((hash << 7) ^ (s[i]) ^ (hash >> 3));
            } else {
                hash ^= (~((hash << 11) ^ (s[i]) ^ (hash >> 5)));
            }
        }
        return hash;
    }
};

struct HashFuncDJB {
    // 由 Daniel J. Bernstein 教授发明的一种 hash 算法。
    size_t operator()(const std::string& s) {
        size_t hash = 5381;
        for (auto ch : s) {
            hash = hash * 33 ^ ch;
        }
        return hash;
    }
};

布隆过滤器的实现：

#include "bitset.h"
#include <string>

// 此处省略上述 HashFunc 定义，实际使用时需包含

template<size_t N, // 数据个数
           size_t X = 5, // 每个数据占用的平均 bit 位数（默认 5）
           class K = std::string, // 数据类型，默认设为 string
           class Hash1 = HashFuncBKDR,
           class Hash2 = HashFuncAP,
           class Hash3 = HashFuncDJB> // 哈希函数个数 k = m/n*ln2 时误判率最低，这里计算约为 3，所以给出三个不同的哈希函数
class BloomFilter {
public:
    // 将一个数据映射的每个位设为 1
    void set(const K& key) {
        size_t hash1 = Hash1()(key) % M;
        size_t hash2 = Hash2()(key) % M;
        size_t hash3 = Hash3()(key) % M;
        _bs.set(hash1);
        _bs.set(hash2);
        _bs.set(hash3);
    }

    // 判断一个数据是否存在，要判断映射的每一位是否都为 1
    // 返回 true 不一定准确，因为这一位 1 可能是别人的 1
    // 返回 false 一定准确，因为这一位是 0，数据一定不存在
    bool test(const K& key) {
        size_t hash1 = Hash1()(key) % M;
        if (!_bs.test(hash1)) return false;
        size_t hash2 = Hash2()(key) % M;
        if (!_bs.test(hash2)) return false;
        size_t hash3 = Hash3()(key) % M;
        if (!_bs.test(hash3)) return false;
        return true; // 可能存在误判
    }

private:
    static const size_t M = N * X;
    lydly::Bitset<M> _bs;
};

简单测试一下：

#include "BloomFilter.h"
int main() {
    BloomFilter<100> bf; // 生成 "test1"、"test2"..."test99" 字符串，插入 bf 中
    for (int i = 0; i < 100; i++) {
        std::string s("test");
        s += std::to_string(i);
        bf.set(s);
    }

    // 测试判断确定存在的数据
    for (int i = 0; i < 100; i++) {
        std::string s("test");
        s += std::to_string(i);
        if (bf.test(s)) {
            cout << s << "存在" << endl;
        } else {
            cout << s << "不存在" << endl;
        }
    }

    // 测试判断不存在的数据，生成 "test1000"、...、"test1500" 字符串
    for (int i = 1000; i < 1500; i++) {
        std::string s("test");
        s += std::to_string(i);
        if (bf.test(s)) {
            cout << s << "存在" << endl;
        } else {
            cout << s << "不存在" << endl;
        }
    }
    return 0;
}

第一段测试没问题，这些字符串都是存在的：

而到了后面，就发现出现了误判，个别字符串不存在，但是判断成了存在：

布隆过滤器的优点是，效率高，节省空间，相比于位图可以适用于记录各种类型的数据。 缺点很明显，存在误判的情况，不是完全准确的。而且布隆过滤器不好支持删除，删除一个数据，不能直接将它的所有位设为 0，因为可能还有别的数据映射到了这个位，具体分析十分复杂。