布隆过滤器到底有多强？用 1MB 内存拦住百万级无效请求

在后端开发里，我们经常会遇到这样一种问题：系统需要先判断一个数据是否存在。如果不存在，就没必要继续查缓存、查数据库，甚至调用后面的服务。

比如用户请求：

GET /user/10086

正常情况下，系统可能会先查缓存，缓存没有再查数据库。这个流程本身没有问题，但如果有人故意请求大量不存在的用户 ID、商品 ID、订单号，就会出现一个很典型的问题：缓存穿透。

也就是说，请求的 key 根本不存在，缓存里查不到，于是每次都打到数据库。请求量一大，数据库就很容易被拖垮。

这时候，布隆过滤器就派上用场了。

一句话理解布隆过滤器：
布隆过滤器是一种用极小空间判断“某个元素是否可能存在”的数据结构。
它不保存元素本身，只用一段位图和多个哈希函数完成判断。

它的判断结果只有两种：

判断结果	含义
不存在	一定不存在
可能存在	不一定真的存在，需要继续确认

也就是说，布隆过滤器不会漏判，但可能误判。

核心结论：
布隆过滤器说“不存在”，那就一定不存在；
布隆过滤器说“存在”，只能说明可能存在。

一、布隆过滤器到底解决了什么问题

如果只是判断一个元素是否存在，我们第一反应可能是用哈希表，比如：

std::unordered_set<std::string> users;

这样当然可以，而且判断结果也准确。但问题是：数据量一旦变大，哈希表会非常占内存。

假设有 10 亿个用户 ID，如果全部放进哈希表里，除了 key 本身，还要考虑哈希桶、指针、扩容冗余等额外开销。真实项目里，这部分内存消耗往往比想象中大得多。

布隆过滤器的思路不一样。

它不存储元素本身，而是维护一段二进制位图。刚开始，所有 bit 都是 0：

下标	0	1	2	3	4	5	6	7	8	9
bit	0	0	0	0	0	0	0	0	0	0

当插入一个元素时，布隆过滤器会通过多个哈希函数算出多个位置，然后把这些位置设置成 1。

比如插入：

user:1001

经过三个哈希函数计算后，得到的位置是：

哈希函数	计算结果
hash1(user:1001)	3
hash2(user:1001)	8
hash3(user:1001)	14

于是位图中的 3、8、14 号位置会被设置为 1。

查询的时候，再用同样的哈希函数算一遍。如果这些位置都为 1，就说明这个元素可能存在；如果其中有任何一个位置是 0，就说明这个元素一定不存在。

二、插入和查询的核心原理

布隆过滤器主要由两个部分组成：

组成部分	作用
位图 bitmap	用 bit 记录元素映射过的位置
多个哈希函数	把同一个 key 映射到多个位置

插入一个元素时，流程大概是：

计算多个哈希值 → 得到多个下标 → 把这些下标对应的 bit 设置成 1

用伪代码表示就是：

for i in [1, k]:
    index = hash_i(key) % m
    bitmap[index] = 1

其中：

参数	含义
m	位图长度
k	哈希函数个数
key	要插入的元素

查询过程也差不多，只不过不是设置 bit，而是检查 bit：

for i in [1, k]:
    index = hash_i(key) % m

    if bitmap[index] == 0:
        return 一定不存在

return 可能存在

这里最关键的是理解为什么“有 0 就一定不存在”。

因为一个元素只要插入过，它对应的几个位置一定会被设置成 1。如果查询时发现某个位置还是 0，就说明这个元素根本没有插入过。

记住这句话就够了：
有 0 必不存在，全 1 可能存在。

这句话基本说完了布隆过滤器的核心逻辑。

三、为什么布隆过滤器会误判

布隆过滤器会误判，是因为不同元素经过哈希之后，可能会命中相同的位置。

假设 A、B、C 已经插入过，它们把位图中的一些位置设置成了 1。后来查询一个从未插入过的元素 X，理论上它应该不存在。

但是，如果 X 经过几个哈希函数算出来的位置，刚好都已经被 A、B、C 设置成了 1，那么布隆过滤器就会认为：

这些位置全是 1，所以 X 可能存在。

可实际上，X 并没有插入过。

这就是误判。

不过，布隆过滤器的误判是单向的。

情况	是否可能发生
把不存在的数据判断为可能存在	可能
把已经存在的数据判断为不存在	不会

所以它适合用来做第一层过滤。

如果它判断不存在，那我们可以放心拦截；如果它判断可能存在，再继续查缓存或数据库确认。

四、误判率和参数怎么选

布隆过滤器有三个核心参数：

参数	含义	对误判率的影响
n	预计插入的元素数量	n 越大，误判率越高
m	位图长度，也就是 bit 数	m 越大，误判率越低
k	哈希函数个数	需要合适，过多过少都不好

误判率可以近似表示为：

p ≈ (1 - e^(-kn/m))^k

这个公式不需要死记，重点理解趋势：

• 元素越多，位图越容易被填满，误判率越高；
• 位图越长，空间越充足，误判率越低；
• 哈希函数个数不是越多越好，需要取一个合适值。

工程里常用下面两个公式估算参数：

m ≈ -n * ln(p) / (ln2)^2
k ≈ (m / n) * ln2

举个例子，假设预计插入 100 万个元素，希望误判率控制在 1% 左右：

项目	数值
预计元素数量 n	1,000,000
期望误判率 p	0.01
位图大小 m	约 9,585,058 bit
内存占用	约 1.14 MB
哈希函数个数 k	约 7

也就是说，只需要一兆多内存，就能对 100 万个元素做一次比较可靠的存在性过滤。

这就是布隆过滤器非常吸引人的地方：

它牺牲了一点点准确性，换来了极高的空间效率。

五、用 C++ 实现一个简单版本

下面写一个简单的 C++ 版本，帮助理解布隆过滤器的实现过程。

这里没有直接使用 vector<bool>，而是使用 vector<uint8_t> 自己管理 bit。因为 vector<bool> 在 C++ 里是一个特化版本，行为和普通 vector 不完全一样，实际工程中我更倾向于自己控制位操作。

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <cstdint>

class BloomFilter {
public:
    BloomFilter(size_t expected_items, double false_positive_rate) {
        if (expected_items == 0) {
            expected_items = 1;
        }

        if (false_positive_rate <= 0 || false_positive_rate >= 1) {
            false_positive_rate = 0.01;
        }

        bit_size_ = calcBitSize(expected_items, false_positive_rate);
        hash_count_ = calcHashCount(expected_items, bit_size_);

        bits_.resize((bit_size_ + 7) / 8, 0);
    }

    void add(const std::string& key) {
        uint64_t h1 = hash1(key);
        uint64_t h2 = hash2(key);

        for (size_t i = 0; i < hash_count_; ++i) {
            size_t index = (h1 + i * h2) % bit_size_;
            setBit(index);
        }
    }

    bool possiblyContains(const std::string& key) const {
        uint64_t h1 = hash1(key);
        uint64_t h2 = hash2(key);

        for (size_t i = 0; i < hash_count_; ++i) {
            size_t index = (h1 + i * h2) % bit_size_;

            if (!getBit(index)) {
                return false;
            }
        }

        return true;
    }

    size_t bitSize() const {
        return bit_size_;
    }

    size_t hashCount() const {
        return hash_count_;
    }

private:
    std::vector<uint8_t> bits_;
    size_t bit_size_;
    size_t hash_count_;

private:
    static size_t calcBitSize(size_t n, double p) {
        double m = -1.0 * n * std::log(p) / (std::log(2) * std::log(2));
        return static_cast<size_t>(m);
    }

    static size_t calcHashCount(size_t n, size_t m) {
        double k = (static_cast<double>(m) / n) * std::log(2);
        return std::max<size_t>(1, static_cast<size_t>(std::round(k)));
    }

    void setBit(size_t index) {
        size_t byte_index = index / 8;
        size_t bit_index = index % 8;

        bits_[byte_index] |= (1 << bit_index);
    }

    bool getBit(size_t index) const {
        size_t byte_index = index / 8;
        size_t bit_index = index % 8;

        return bits_[byte_index] & (1 << bit_index);
    }

    static uint64_t hash1(const std::string& s) {
        uint64_t hash = 1469598103934665603ULL;

        for (char c : s) {
            hash ^= static_cast<unsigned char>(c);
            hash *= 1099511628211ULL;
        }

        return hash;
    }

    static uint64_t hash2(const std::string& s) {
        uint64_t hash = 1099511628211ULL;

        for (char c : s) {
            hash ^= static_cast<unsigned char>(c);
            hash *= 1469598103934665603ULL;
            hash ^= (hash >> 32);
        }

        return hash | 1;
    }
};

测试代码如下：

int main() {
    BloomFilter filter(1000000, 0.01);

    std::cout << "bit size: " << filter.bitSize() << std::endl;
    std::cout << "hash count: " << filter.hashCount() << std::endl;

    filter.add("user:1001");
    filter.add("user:1002");
    filter.add("user:1003");

    std::cout << std::boolalpha;

    std::cout << "user:1001 -> "
              << filter.possiblyContains("user:1001") << std::endl;

    std::cout << "user:9999 -> "
              << filter.possiblyContains("user:9999") << std::endl;

    return 0;
}

可能输出：

bit size: 9585058
hash count: 7
user:1001 -> true
user:9999 -> false

这里要特别注意：

返回值	含义
true	可能存在
false	一定不存在

代码中通过 hash1 + i * hash2 的方式生成多个哈希结果，这种写法叫 double hashing。它可以避免真的写很多个哈希函数，工程上也比较常见。

不过，真实项目中不建议随便写哈希函数。布隆过滤器非常依赖哈希分布，如果哈希函数分布不好，误判率会明显变高。

生产环境里可以考虑使用这些成熟哈希算法：

哈希算法	特点
MurmurHash	分布均匀，使用广泛
xxHash	速度非常快
CityHash	适合字符串哈希
FarmHash	Google 推出的哈希算法

六、实际使用场景和需要注意的坑

布隆过滤器最经典的使用场景就是防缓存穿透。

系统启动时，可以把数据库中已有的合法 ID 加入布隆过滤器。请求进来后，先问布隆过滤器：

如果 CSDN 不支持 Mermaid，也可以直接写成下面这种流程：

请求进来 → 查询布隆过滤器 → 一定不存在则直接返回 → 可能存在再查缓存或数据库

除了缓存穿透，它还常用于这些场景：

场景	使用方式
缓存穿透防护	提前拦截不存在的 key
爬虫 URL 去重	判断 URL 是否可能已经抓取
黑名单过滤	对恶意 IP、风险账号做初筛
垃圾邮件过滤	判断邮件来源是否可能命中黑名单
存储系统优化	减少无意义的磁盘查询

不过，使用布隆过滤器时有几个坑一定要注意。

如果业务确实需要删除，可以考虑计数布隆过滤器。它不是简单使用 bit，而是给每个位置维护一个计数器。插入时计数加一，删除时计数减一。

不过，计数布隆过滤器会占用更多空间，复杂度也更高。

严重时，布隆过滤器会变成“谁来都可能存在”，过滤效果就很差了。

常见流程是：

写数据库成功 → 更新缓存 → 把 key 加入布隆过滤器

如果系统比较复杂，也可以通过消息队列做异步补偿。

最后要记住，布隆过滤器不能当最终判断依据。

它适合做第一层过滤，不适合做最终裁判。像支付、库存、权限校验这种要求强准确性的业务，不能只依赖布隆过滤器。

比较合理的定位是：

布隆过滤器负责快速拦截明显不存在的数据；
数据库或缓存负责最终确认数据是否真的存在。

总结

布隆过滤器的思想其实很简单：它不保存元素本身，而是通过多个哈希函数，把元素映射到一段位图上。

它最大的特点是：

判断	结果
判断不存在	一定准确
判断存在	可能误判

正因为这个特点，它非常适合用来做大规模数据下的快速存在性判断，尤其适合缓存穿透防护、URL 去重、黑名单过滤、存储系统查询优化等场景。

但它也不是万能的。它有误判，普通版本不支持删除，也不能返回原始数据。使用之前，一定要估算好数据规模和误判率，选择合适的位图大小和哈希函数个数。

最后用一句话总结：
布隆过滤器不是最终裁判，而是挡在数据库前面的一道高效过滤网。

用得好，它能用很小的内存帮系统挡掉大量无效请求；用得不好，误判率失控之后，它也可能变成一个几乎什么都放行的摆设。