C++ 哈希结构进阶：位图与布隆过滤器详解

测试一下，开 2^32 个比特位不在话下：

#include "BitMap.h"
int main() {
    lydly::BitMap<0xFFFFFFFF> bm; // 开 2^32 位
    for (size_t i = 0; i < 5000; i++) {
        bm.Set(i);
    }
    for (int i = 0; i < 100; i++) {
        int n = rand() % 10000;
        if (bm.Test(n)) {
            std::cout << n << " 存在" << std::endl;
        } else {
            std::cout << n << " 不存在" << std::endl;
        }
    }
    return 0;
}

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

C++ 标准库 bitset

实际上 C++ 库中已经提供了位图 std::bitset，核心接口还是 set、reset、test 等。此外还支持 operator[] 像数组一样控制位，to_string 转化为 01 字符串。

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

布隆过滤器

概念

如果海量数据不是整型，红黑树、哈希表内存空间不足，位图也无法直接使用。这时可以用布隆过滤器（Bloom Filter）。

布隆过滤器是一种概率型数据结构，由布隆提出。特点是高效插入和查询，很难删除。它可以查询某个数据'可能在'或'一定不在'。思路是利用哈希函数将非整型数据映射为整型，再映射到比特位中。

只用一个哈希函数容易冲突，为了降低冲突率，通常使用多个哈希函数，映射到多个位上，这些位都为 1 才表示数据存在。布隆过滤器始终无法完全解决哈希冲突，只能尽可能降低。因此，判断数据不存在是准确的，但判断存在可能存在误判。

误判率数学推导

假设变量：

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

概率推导：

1. 某位被设置为 1 的概率：1/m
2. 某位不为 1 的概率：1 - 1/m
3. 经过 k 次哈希后，某位置依旧不为 1 的概率：(1 - 1/m)^k ≈ e^(-k/m)
4. 添加 n 个元素后，某位置不为 1 的概率：(1 - 1/m)^(kn) ≈ e^(-kn/m)
5. 添加 n 个元素后，某位置置为 1 的概率：1 - e^(-kn/m)
6. 查询一个元素，k 次 hash 后误判的概率（都命中 1 的概率）：(1 - e^(-kn/m))^k

结论：

• 误判率公式： f(k) = (1 - e^(-kn/m))^k
• 规律： k 一定时，n 增加误判率增加，m 增加误判率减少。
• 最优哈希函数个数： k = (m/n) * ln2 时误判率最低。
• bit 长度计算： m = -(n * ln p) / (ln 2)^2

实现

我们需要多个哈希函数算法，这里借鉴几种经典算法：

struct HashFuncBKDR {
    // Brian Kernighan 与 Dennis Ritchie 的《The C Programming Language》展示算法
    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 "BitMap.h"
#include <string>

template<size_t N,      // 数据个数
           size_t X = 5, // 每个数据占用的平均 bit 位数
           class K = std::string,
           class Hash1 = HashFuncBKDR,
           class Hash2 = HashFuncAP,
           class Hash3 = HashFuncDJB>
class BloomFilter {
public:
    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);
    }

    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::BitMap<M> _bs;
};

简单测试：

#include "BloomFilter.h"
int main() {
    BloomFilter<100> bf;
    // 插入 test1...test99
    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)) {
            std::cout << s << " 存在" << std::endl;
        }
    }
    // 测试不存在的数据 test1000...test1500
    for (int i = 1000; i < 1500; i++) {
        std::string s("test");
        s += std::to_string(i);
        if (bf.Test(s)) {
            std::cout << s << " 存在 (误判)" << std::endl;
        }
    }
    return 0;
}

第一段测试没问题，字符串都存在。到了后面，会发现个别字符串不存在但判断成了存在，这就是误判。

布隆过滤器的优点是效率高，节省空间，适用于各种类型数据。缺点是存在误判，且不支持删除操作（删除一个数据不能直接将其所有位设为 0，因为可能还有其他数据映射到了该位）。