实战：布隆过滤器（位图+哈希函数）

布隆过滤器这东西，我第一次接触是在做爬虫去重的时候。那时候内存吃紧，几亿个URL全塞进哈希表，服务器直接罢工。后来一位老同事跟我说：「试试布隆过滤器，省内存得很。」一试，果然香。

说白了，布隆过滤器就是一个概率型数据结构。它用位图加多个哈希函数，来判断一个元素「可能在集合里」还是「绝对不在」。注意，它可能会误判——把不在的说成在的，但绝不会把在的说成不在的。

核心思想：用空间换时间，再用概率换空间。允许少量误判，换来极低的内存占用。

基本原理

布隆过滤器的工作原理，其实就三步：

  1. 准备一个长度为 m 的位图（bit array），初始全为 0。
  2. 准备 k 个独立的哈希函数。
  3. 插入元素时，用 k 个哈希函数算出 k 个位置，把这些位置都置为 1。
  4. 查询元素时，同样算出 k 个位置，如果全部都是 1，就说「可能在」；但凡有一个是 0，就说「绝对不在」。

你想想看，为什么会有误判？因为不同的元素可能把同一个位置置为 1，查询时这些位置恰好都被别的元素填满了，就会误以为当前元素存在。嗯，这就是概率的来源。

我的经验：布隆过滤器特别适合「允许少量误判」的场景。比如缓存穿透防护、爬虫URL去重、垃圾邮件过滤。如果要求100%准确，那还是老老实实用哈希表吧。

SVG：布隆过滤器核心流程

布隆过滤器核心流程 输入元素 k 个哈希函数 Hash₁(x) Hash₂(x) ... Hashₖ(x) 位图（Bit Array） 位置₁ → 1 | 位置₂ → 1 | ... | 位置ₖ → 1 全为1？ 可能在 绝对不在

代码实现

我习惯用 C++ 写一个轻量版的布隆过滤器。这里用 std::bitset 模拟位图，用 std::hash 作为哈希函数族。当然，生产环境里建议用更高质量的哈希函数，比如 MurmurHash 或 xxHash。

#include <bitset>
#include <functional>
#include <vector>
#include <string>

template<size_t N>
class BloomFilter {
public:
    // 构造函数：指定哈希函数个数
    BloomFilter(size_t k = 3) : hash_count_(k) {
        // 预生成 k 个不同的哈希种子
        for (size_t i = 0; i < k; ++i) {
            seeds_.push_back(i * 131 + 97);
        }
    }

    // 插入元素
    void insert(const std::string& key) {
        for (size_t i = 0; i < hash_count_; ++i) {
            size_t pos = hash(key, seeds_[i]) % N;
            bits_.set(pos);
        }
    }

    // 查询元素
    bool contains(const std::string& key) const {
        for (size_t i = 0; i < hash_count_; ++i) {
            size_t pos = hash(key, seeds_[i]) % N;
            if (!bits_.test(pos)) {
                return false;  // 只要有一个为0，绝对不在
            }
        }
        return true;  // 全部为1，可能在
    }

private:
    // 带种子的哈希函数
    size_t hash(const std::string& key, size_t seed) const {
        size_t h = seed;
        for (char c : key) {
            h = h * 131 + c;
        }
        return h;
    }

    std::bitset<N> bits_;
    size_t hash_count_;
    std::vector<size_t> seeds_;
};
避坑指南：我曾经在项目里把位图大小设得太小，结果误判率飙升到 30% 以上，线上数据直接乱套。后来总结：位图大小 m 和元素数量 n 的比例，建议在 10:1 以上。哈希函数个数 k 取 ln2 * (m/n) 左右最优。

参数选择与误判率

布隆过滤器的误判率不是玄学，是可以算出来的。公式长这样：

P ≈ (1 - e-kn/m)k

其中 m 是位图大小，n 是插入元素数量，k 是哈希函数个数。我一般直接用这个表来快速选参数：

期望误判率 m/n 比值 推荐 k 值
10% 4.8 3
1% 9.6 7
0.1% 14.4 10
0.01% 19.2 13
我的习惯：一般取 m/n = 10，k = 7，误判率大约 1% 左右。这个配置在大多数场景下够用，内存也省。如果对误判率要求极高，可以考虑用计数布隆过滤器或者布谷鸟过滤器。

实战场景：缓存穿透防护

我记得有一次做高并发系统，Redis 缓存扛不住，大量请求直接打到数据库。原因是有恶意用户疯狂请求不存在的 key，每次都要查数据库。这就是典型的缓存穿透。

解决方案很简单：在 Redis 前面加一层布隆过滤器。把所有合法 key 都插入过滤器。请求来了先问过滤器：

  • 如果过滤器说「不在」，直接返回空，不用查 Redis 和数据库。
  • 如果过滤器说「可能在」，才去查 Redis。

这样一来，99% 的无效请求在第一层就被拦住了。数据库压力骤降，系统稳如老狗。

// 伪代码示例
BloomFilter<1000000> filter;

// 初始化：加载所有合法 key
for (auto& key : valid_keys) {
    filter.insert(key);
}

// 请求处理
std::string result = handle_request(key) {
    if (!filter.contains(key)) {
        return "not_found";  // 直接返回，不查数据库
    }
    // 查 Redis 或数据库
    return query_database(key);
}
注意：布隆过滤器不支持删除操作！如果你需要删除元素，可以考虑计数布隆过滤器（每个位置用计数器代替位），但代价是内存占用翻几倍。我一般只在「只增不删」的场景下用布隆过滤器。

优缺点总结

最后，我帮你把布隆过滤器的优缺点捋一捋：

  • 优点：内存极省，查询和插入都是 O(k)，k 一般是个位数。适合海量数据场景。
  • 缺点：有误判率，不支持删除，无法遍历所有元素。

说白了，布隆过滤器就是一把「快刀」。它不完美，但在对的地方用对，能解决大问题。我这些年做过的项目里，至少有三四个都用到了它——爬虫去重、缓存防护、黑名单过滤……每次都能省下不少内存和 CPU。

嗯，如果你在实际项目中遇到「数据量大、允许少量误判、内存吃紧」的情况，不妨试试布隆过滤器。代码简单，效果立竿见影。

公众号：蓝海资料掘金营，微信 deep3321

← 上一章 📖 返回目录 下一章 →