C++拓展：吊打海量数据！哈希扩展之位图与布隆过滤器实战解析

_OP_CHEN

发布于 2026-01-14 11:15:47

1210

文章被收录于专栏：C++C++

前言

在日常开发和面试中，我们总会遇到各类 “海量数据” 处理问题：40 亿个整数快速查重、100 亿个 URL 去重、1G 内存找两个 500G 文件的交集…… 常规的暴力遍历、哈希表解法在这些场景下要么效率拉胯，要么直接撑爆内存。而哈希扩展技术 —— 位图（Bitset）和布隆过滤器（Bloom Filter），正是为解决这类 “内存不够、效率要高” 的问题而生。本文将从面试题切入，手把手拆解位图和布隆过滤器的原理、实现、应用，让你彻底吃透这两大海量数据处理神器！下面就让我们正式开始吧！

一、从一道经典面试题，解锁位图的核心逻辑

先看一道腾讯和百度都出过的高频面试题：

给 40 亿个不重复的无符号整数（未排序），给定一个无符号整数，如何快速判断它是否在这 40 亿个数中？

1.1 常规思路的 “死穴”

拿到这个问题，很多人第一反应是 “暴力遍历” 或 “排序 + 二分查找”，但我们先算一笔账：

暴力遍历：时间复杂度 O (N)，40 亿次循环，哪怕每秒处理 1 亿次，也要 40 秒，完全达不到 “快速” 要求；
排序 + 二分查找：排序时间复杂度 O (N log N)，二分查找 O (log N)，看似效率提升，但关键问题在内存——40 亿个无符号整数，每个占 4 字节，总大小 = 40 亿 ×4B=16GB，普通机器的内存根本装不下，只能存在硬盘里，而二分查找只能对内存中的有序数组生效，硬盘 IO 的耗时会让这个方案直接作废。

1.2 位图：用 “位” 撬动海量数据

既然 “存整数本身” 内存不够，那我们换个思路：判断一个数 “在或不在”，本质是两种状态，刚好可以用1 个二进制比特位表示（1 = 存在，0 = 不存在）。这种用比特位映射数据状态的结构，就是位图（Bitset）。

（1）位图的核心原理

无符号整数的范围是 0~2³²-1（约 42 亿），我们只需要开辟 2³² 个比特位的空间，就能映射所有无符号整数的状态：

空间计算：2³² bit = 2³² / 8 / 1024 / 1024 / 1024 ≈ 0.5GB，1G 内存完全能装下；
映射规则：对于整数 x，计算它在位图中的位置：
- 第 i 个整数块：i = x / 32（因为 1 个 int 占 32 位，对应 32 个整数）；
- 第 j 个比特位：j = x % 32；
- 例如 x=50，i=50/32=1，j=50%32=18，即位图中第 1 个 int 的第 18 位。

（2）位图的 C++ 实现

位图的核心操作是设置位（set）、清空位（reset）、检测位（test），以下是完整实现：

#include <iostream>
#include <vector>
using namespace std;

namespace bit
{
    // N是需要的比特位总数
    template<size_t N>
    class bitset
    {
    public:
        bitset()
        {
            // 初始化数组大小：N/32 + 1（向上取整），用右移5位代替除以32，效率更高
            _bits.resize((N >> 5) + 1, 0);
        }

        // 标记x存在（将对应位设为1）
        void set(size_t x)
        {
            if (x >= N) return; // 超出范围直接返回
            size_t i = x / 32;   // 找到对应的int块
            size_t j = x % 32;   // 找到对应的比特位
            _bits[i] |= (1 << j); // 位或操作置1
        }

        // 标记x不存在（将对应位设为0）
        void reset(size_t x)
        {
            if (x >= N) return;
            size_t i = x / 32;
            size_t j = x % 32;
            _bits[i] &= ~(1 << j); // 位与取反操作置0
        }

        // 检测x是否存在（返回对应位的值）
        bool test(size_t x)
        {
            if (x >= N) return false;
            size_t i = x / 32;
            size_t j = x % 32;
            return _bits[i] & (1 << j); // 位与操作检测
        }

    private:
        vector<int> _bits; // 存储比特位的数组，每个int占32位
    };
}

// 测试位图功能
int main()
{
    bit::bitset<100> bs;
    // 设置几个数存在
    bs.set(50);
    bs.set(30);
    bs.set(90);

    // 遍历检测0~99的数
    cout << "第一次检测结果：" << endl;
    for (size_t i = 0; i < 100; ++i)
    {
        if (bs.test(i))
        {
            cout << i << " -> 存在" << endl;
        }
        else
        {
            cout << i << " -> 不存在" << endl;
        }
    }

    // 修改状态：清空90，设置91
    bs.reset(90);
    bs.set(91);

    cout << "\n修改后检测结果：" << endl;
    for (size_t i = 0; i < 100; ++i)
    {
        if (bs.test(i))
        {
            cout << i << " -> 存在" << endl;
        }
        else
        {
            cout << i << " -> 不存在" << endl;
        }
    }

    // 处理40亿个数时，只需初始化bit::bitset<UINT_MAX> bs;
    return 0;
}

（3）C++ 标准库中的 bitset

C++ 标准库也提供了std::bitset，核心接口和我们实现的一致，还扩展了更多功能：

接口	功能
set()	设置指定位为 1（默认全部）
reset()	清空指定位为 0（默认全部）
test()	检测指定位的值
count()	统计为 1 的位的数量
any()	判断是否有位为 1
none()	判断是否所有位为 0
flip()	翻转指定位（0 变 1，1 变 0）
operator[]	像数组一样访问指定位

需要注意：std::bitset的大小是编译期确定的（模板参数），如果需要动态大小，可使用vector<bool>（本质也是位图实现）。

其技术文档链接如下：https://legacy.cplusplus.com/reference/bitset/bitset/

1.3 位图的进阶应用

位图不仅能解决 “查重” 问题，还能处理更复杂的海量数据场景：

（1）找只出现一次的整数（100 亿个整数）

思路：依旧开辟 2³² 个位的位图，遍历所有数，第一次遇到设为 1，第二次遇到设为 0（重复），最终值为 1 的位对应的数就是只出现一次的数。

（2）找两个大文件的交集（各 100 亿个整数，1G 内存）

思路：

遍历第一个文件，将所有整数存入位图 1；
遍历第二个文件，用位图 1 检测每个整数，存在的就是交集；

// 位图找交集示例
void test_bitset_intersection()
{
    int a1[] = {5,7,9,2,5,99,5,5,7,5,3,9,2,55,1,5,6};
    int a2[] = {5,3,5,99,6,99,33,66};

    bit::bitset<100> bs1, bs2;
    // 第一个数组存入bs1
    for (auto e : a1) bs1.set(e);
    // 第二个数组存入bs2
    for (auto e : a2) bs2.set(e);

    // 找交集
    cout << "两个数组的交集：" << endl;
    for (size_t i = 0; i < 100; ++i)
    {
        if (bs1.test(i) && bs2.test(i))
        {
            cout << i << " ";
        }
    }
    cout << endl;
}

（3）找出现次数不超过 2 次的整数（100 亿个整数，1G 内存）

思路：每个数用2 个比特位标记次数（00=0 次，01=1 次，10=2 次，11=2 次以上），最终筛选出 01 和 10 对应的数：

namespace bit
{
    // 双位图：每个数用2位标记出现次数
    template<size_t N>
    class twobitset
    {
    public:
        // 标记数x出现一次
        void set(size_t x)
        {
            bool bit1 = _bs1.test(x); // 高位
            bool bit2 = _bs2.test(x); // 低位

            if (!bit1 && !bit2) // 00 -> 01（第一次出现）
            {
                _bs2.set(x);
            }
            else if (!bit1 && bit2) // 01 -> 10（第二次出现）
            {
                _bs2.reset(x);
                _bs1.set(x);
            }
            else if (bit1 && !bit2) // 10 -> 11（第三次及以上）
            {
                _bs2.set(x);
            }
            // 11则不处理
        }

        // 获取数x的出现次数
        int get_count(size_t x)
        {
            bool bit1 = _bs1.test(x);
            bool bit2 = _bs2.test(x);

            if (!bit1 && !bit2) return 0;
            else if (!bit1 && bit2) return 1;
            else if (bit1 && !bit2) return 2;
            else return 3; // 2次以上
        }

    private:
        bitset<N> _bs1; // 高位
        bitset<N> _bs2; // 低位
    };
}

// 测试双位图
void test_twobitset()
{
    bit::twobitset<100> tbs;
    int a[] = {5,7,9,2,5,99,5,5,7,5,3,9,2,55,1,5,6,6,6,6,7,9};

    // 标记所有数的出现次数
    for (auto e : a) tbs.set(e);

    // 找出现次数1或2次的数
    cout << "出现次数不超过2次的数：" << endl;
    for (size_t i = 0; i < 100; ++i)
    {
        int cnt = tbs.get_count(i);
        if (cnt == 1 || cnt == 2)
        {
            cout << i << " ";
        }
    }
    cout << endl;
}

1.4 位图的优缺点

优点：增删查改时间复杂度 O (1)，极致节省空间（比存整数少 32 倍）；
缺点：仅支持整形数据，无法处理字符串、对象等非整形类型。

二、布隆过滤器：位图的 “升级版”，支持任意类型

位图的局限性很明显 —— 只能处理整形，而实际开发中，我们常需要判断 “字符串（如 URL、手机号）是否存在”，这时候就需要布隆过滤器登场了。

2.1 布隆过滤器的核心原理

布隆过滤器是 1970 年由 Burton Howard Bloom 提出的概率型数据结构，核心思路：

将任意类型的 key 通过多个哈希函数映射为多个整数；
将这些整数对应的位图位设为 1；
查询时，用同样的哈希函数映射 key，若所有对应位都是 1，则 “可能存在”；若有任意一位是 0，则 “一定不存在”。

关键特性：不存在是 100% 准确的，存在可能误判（哈希冲突导致），但误判率可通过参数调控。

2.2 误判率的数学推导

布隆过滤器的误判率和三个参数相关：

m：位图的 bit 长度；
n：插入的元素个数；
k：哈希函数的个数。

（1）核心推导过程

单个位被设为 1 的概率：

；

单个位未被设为 1 的概率：1-

；

k 次哈希后，单个位仍未被设为 1 的概率：

；

插入 n 个元素后，单个位未被设为 1 的概率：

；

插入 n 个元素后，单个位被设为 1 的概率：

；

误判率（查询时所有位都被设为 1）：

。

这里的推导实际上是很复杂的，大家如果感兴趣的话，这里推荐两篇博客供大家参考：

布隆过滤器（Bloom Filter）- 原理、实现和推导、[布隆过滤器BloomFilter] 举例说明+证明推导。

（2）最优参数结论

当哈希函数个数

时，误判率最低；

已知期望误判率 p 和插入元素数 n，位图长度

。

2.3 布隆过滤器的 C++ 实现

我们实现一个支持字符串的布隆过滤器，使用 3 种经典哈希函数（BKDR、AP、DJB）降低冲突率：

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <ctime>
using namespace std;

// 位图实现（复用之前的bitset）
namespace bit
{
    template<size_t N>
    class bitset
    {
    public:
        bitset() { _bits.resize((N >> 5) + 1, 0); }
        void set(size_t x) { if(x<N) _bits[x/32] |= (1 << (x%32)); }
        void reset(size_t x) { if(x<N) _bits[x/32] &= ~(1 << (x%32)); }
        bool test(size_t x) { return x<N && (_bits[x/32] & (1 << (x%32))); }
    private:
        vector<int> _bits;
    };
}

// 哈希函数1：BKDR（Java字符串哈希同款）
struct HashFuncBKDR
{
    size_t operator()(const string& s)
    {
        size_t hash = 0;
        for (char ch : s)
        {
            hash *= 31; // 31是经典素数，减少冲突
            hash += ch;
        }
        return hash;
    }
};

// 哈希函数2：AP
struct HashFuncAP
{
    size_t operator()(const string& s)
    {
        size_t hash = 0;
        for (size_t i = 0; i < s.size(); ++i)
        {
            if (i % 2 == 0) // 偶数位
            {
                hash = ((hash << 7) ^ s[i]) ^ (hash >> 3);
            }
            else // 奇数位
            {
                hash ^= (~((hash << 11) ^ s[i]) ^ (hash >> 5));
            }
        }
        return hash;
    }
};

// 哈希函数3：DJB
struct HashFuncDJB
{
    size_t operator()(const string& s)
    {
        size_t hash = 5381; // 初始值，经典素数
        for (char ch : s)
        {
            hash = hash * 33 ^ ch; // 33=32+1，位运算高效
        }
        return hash;
    }
};

// 布隆过滤器实现
template<size_t N, size_t X = 6, 
         class K = 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; // 可能误判
    }

    // 计算理论误判率
    double GetFalseProbability()
    {
        double p = pow((1.0 - pow(2.71828, -3.0 / X)), 3.0);
        return p;
    }

private:
    static const size_t M = X * N; // 位图总长度
    bit::bitset<M> _bs; // 底层位图
};

// 测试布隆过滤器
void TestBloomFilter()
{
    // 测试基础功能
    BloomFilter<10> bf1;
    string strs[] = {"百度", "字节", "腾讯"};
    for (auto& s : strs) bf1.Set(s);

    cout << "基础查询测试：" << endl;
    for (auto& s : strs)
    {
        cout << s << " -> " << (bf1.Test(s) ? "可能存在" : "一定不存在") << endl;
    }
    // 测试不存在的元素
    cout << "摆渡 -> " << (bf1.Test("摆渡") ? "可能存在" : "一定不存在") << endl;
    cout << "百渡 -> " << (bf1.Test("百渡") ? "可能存在" : "一定不存在") << endl;

    // 测试误判率
    cout << "\n误判率测试（1000万个URL）：" << endl;
    const size_t N = 10000000;
    BloomFilter<N> bf2;
    vector<string> v1;
    string base_url = "https://www.cnblogs.com/clq/archive/2012/05/31/2528153.html";

    // 插入1000万个不同的URL
    for (size_t i = 0; i < N; ++i)
    {
        v1.push_back(base_url + to_string(i));
    }
    for (auto& s : v1) bf2.Set(s);

    // 测试相似URL的误判率（前缀相同，后缀不同）
    v1.clear();
    size_t false_cnt1 = 0;
    for (size_t i = 0; i < N; ++i)
    {
        string s = base_url + to_string(9999999 + i);
        v1.push_back(s);
        if (bf2.Test(s)) false_cnt1++;
    }
    cout << "相似URL误判率：" << (double)false_cnt1 / N << endl;

    // 测试不相似URL的误判率
    v1.clear();
    size_t false_cnt2 = 0;
    srand(time(0));
    for (size_t i = 0; i < N; ++i)
    {
        string s = "孙悟空" + to_string(i + rand());
        v1.push_back(s);
        if (bf2.Test(s)) false_cnt2++;
    }
    cout << "不相似URL误判率：" << (double)false_cnt2 / N << endl;
    cout << "理论误判率：" << bf2.GetFalseProbability() << endl;
}

int main()
{
    TestBloomFilter();
    return 0;
}

2.4 布隆过滤器的删除问题

布隆过滤器默认不支持删除，原因：

多个 key 可能映射到同一个位，删除其中一个 key 的位，会导致其他 key 的查询结果错误（例如 “猪八戒” 和 “孙悟空” 共享某个位，删除 “孙悟空” 后，“猪八戒” 也会被判定为不存在）。

解决方案：计数布隆过滤器

给每个位分配多个比特位（如 4 位），记录该位被映射的次数：

插入时，对应位计数 + 1；
删除时，对应位计数 - 1；
查询时，计数 > 0 则 “可能存在”。

缺点：

增加空间消耗（4 位则空间扩大 4 倍）；
若删除不存在的 key，会导致计数错误，影响其他 key 的查询。

优化思路：定期重建布隆过滤器，清空无效计数。

2.5 布隆过滤器的实际应用

布隆过滤器凭借 “高效、省空间” 的特性，广泛应用于海量数据场景：

（1）爬虫 URL 去重

爬虫爬取网页时，需要避免重复爬取相同 URL：

爬取到 URL 后，先用布隆过滤器判断是否已存在；
不存在则爬取，并将 URL 存入布隆过滤器；
存在则直接跳过，减少网络请求和 IO 开销。

（2）垃圾邮件过滤

将已知垃圾邮件的特征（如发件人、关键词、链接）存入布隆过滤器；
新邮件到达时，检测特征是否在布隆过滤器中，快速判断是否为垃圾邮件。

（3）解决缓存穿透

缓存穿透：恶意请求不存在的数据，导致请求直达数据库，压垮数据库。

在缓存前加布隆过滤器，存储所有存在的 key；
收到请求时，先查布隆过滤器，不存在则直接返回，避免访问数据库；
存在则查缓存，缓存未命中再查数据库。

（4）数据库查询提效

例如判断手机号是否注册：

将所有已注册的手机号存入布隆过滤器；
前端请求时，先查布隆过滤器，不存在则直接返回 “未注册”；
存在则查数据库二次确认，减少数据库查询次数。

2.6 布隆过滤器的优缺点

优点：支持任意类型，增删查改 O (1)，空间利用率高，误判率可调控；
缺点：存在误判，默认不支持删除，无法获取元素本身（仅能判断存在性）。

三、海量数据处理的通用思路

除了位图和布隆过滤器，海量数据处理还有一些通用技巧，核心是 “分而治之”。

3.1 TopK 问题（10 亿个整数找最大的前 100 个）

经典解法：小根堆

先取前 100 个数构建小根堆（堆顶是当前第 100 大的数）；
遍历剩余数，若数大于堆顶，则替换堆顶并调整堆；
遍历结束后，堆中就是最大的前 100 个数。

3.2 大文件交集问题（两个 100 亿个 query 的文件，1G 内存）

query 是字符串，每个约 50 字节，总大小约 500G，无法直接加载到内存。

方案 1：布隆过滤器（快速但有误差）

将第一个文件的 query 存入布隆过滤器；
遍历第二个文件的 query，检测是否存在，存在的即为交集（可能包含误判的结果）。

方案 2：哈希切分（准确）

核心思路：将大文件切分为小文件，让相同的 query 进入同一个小文件，再逐小文件找交集：

选择哈希函数 HashFunc，将 query 映射为 0~999 的整数 i；
遍历文件 A，将 query 存入 Ai 小文件（共 1000 个）；
遍历文件 B，将 query 存入 Bi 小文件（共 1000 个）；
对每一对 (Ai, Bi)，加载到内存用哈希表找交集；
若某个小文件过大（内存装不下），换哈希函数二次切分。

3.3 找出现次数最多的 IP（100G 的 log 文件）

思路：哈希切分 + 哈希表统计

用哈希函数将 IP 映射为 0~499 的整数 i，将 IP 存入 Ai 小文件；
遍历每个 Ai 小文件，用 map<string, int> 统计每个 IP 的出现次数；
记录每个 Ai 中出现次数最多的 IP，最终汇总所有 Ai 的结果，得到全局最多的 IP。

总结

哈希扩展技术是处理海量数据的 “利器”，核心是 “用空间换时间”，并通过巧妙的设计极致压缩空间。掌握这些技术，不仅能轻松应对面试中的海量数据问题，也能在实际开发中解决内存不足、效率低下的痛点。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2026-01-13，如有侵权请联系 cloudcommunity@tencent.com 删除

测试

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度