当前位置：首页 > news >正文

C++进阶——位图+布隆过滤器+海量数据处理

news 2025/4/2 6:32:43

1、位图

1.1 位图的引入

1.2 位图的设计

1.3 位图的优缺点

1.4 位图的代码实现

2、布隆过滤器

2.1 什么是布隆过滤器

2.2 布隆过滤器的误判率推导

2.3 布隆过滤器的实现思路

2.4 布隆过滤器的删除访问

2.5 布隆过滤器的应用

2.4.1 爬虫系统中 URL 去重

2.4.2 垃圾邮件过滤

2.4.3 预防缓存穿透

2.4.4 对数据库查询提效

3、海量数据处理

3.1 10亿个整数里面求最大的前100个

3.2 位图和布隆过滤器相关题目

3.3 给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？

3.4 给一个超过100G大小的logfile,log中存着ip地址,设计算法查找出现次数前10的ip地址

1、位图

1.1 位图的引入

给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。（本题为腾讯/百度等公司出过的一个面试题）

解题思路1：暴力遍历，时间复杂度O(N)，每次都是O(N)，太慢。

解题思路2：排序+二分查找。时间复杂度消耗O(N*logN)+O(logN)

深入分析：解题思路2是否可行，我们先算算40亿个数据大概需要多少内存。

1G = 1024MB = 1024*1024KB = 1024*1024*1024Byte约等于10亿多Byte
那么40亿个整数约等于16G，说明40亿个数是无法直接放到内存中的，只能放到硬盘文件中。而二分查找只能对内存数组中的有序数据进行查找。

解题思路3：数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位，为1，代表存在，为0，代表不存在。那么我们设计一个用二进制比特位表示数据是否存在的数据结构，这个数据结构就叫位图。

1.2 位图的设计

C/C++没有对应二进制比特位的类型，只能有char/int/size_t这样整型类型，我们可以通过位运算去控制对应的比特位。

比如我们数据存到vector<size_t>中，相当于每个size_t值映射对应的32个位，那么来了一个无符号整型值 x，i=x/32；j=x%32；计算出x映射的值在vector的第i个整型数据的第j位。

注意：

1. 位图是直接定址法(根据数据范围开空间)，如果数据范围是size_t(4字节)，2^32个数，就需要2^32位，512MB。

2. 一般不用vector<int>，int 是有符号的，位操作可能有问题（如右移补符号位），

可以使用vector<uint32_t>，1u<<j，1u在x86和x64都是32位。

3. std::bitset是使用静态数组，栈上的空间只有几MB，但是可以在堆上开数组，

std::bitset<数据个数>* ptr = new std::bitset<数据个数>();

bitset - C++ Reference

1.3 位图的优缺点

优点：增删查快，节省空间。

缺点：只适用于整形。

1.4 位图的代码实现

问题 1：给定 100 亿个整数，设计算法找到只出现一次的整数？

虽然是 100 亿个数，但是还是按范围开空间，所以还是开 2^32 个位，跟前面的题目是一样的。

问题 2：给两个文件，分别有 100 亿个整数，我们只有 1G 内存，如何找到两个文件交集？

把数据读出来，分别放到两个位图，依次遍历，同时在两个位图的值就是交集。

问题 3：一个文件有 100 亿个整数，1G 内存，设计算法找到出现次数不超过 2 次的所有整数？

之前标记在不在，只需要一个位即可，这里要统计出现次数不超过2次的，可以每个值用两个位标记即可，00代表出现0次，01代表出现1次，10代表出现2次，11代表出现2次以上。最后统计出所有 01和10标记的值即可。

以下使用简单的数据模拟并解决问题2和问题3。

#pragma once#include <iostream>
#include <vector>namespace Lzc
{template<size_t N> // N是数据范围，位图的位数class bitset{public:bitset():_bs(N / 32 + 1,0) // 100/32=3，要开4个{ }void set(size_t x){size_t i = x / 32;size_t j = x % 32;_bs[i] |= (1u << j);}void reset(size_t x){size_t i = x / 32;size_t j = x % 32;_bs[i] &= (~(1u << j));}bool test(size_t x){size_t i = x / 32;size_t j = x % 32;return _bs[i] & (1u << j);}private:std::vector<uint32_t> _bs;};template<size_t N>class twobitset{public:void set(size_t x){bool bit1 = _bs1.test(x);bool bit2 = _bs2.test(x);if (!bit1&&!bit2) //00{_bs2.set(x); // 00->01return;}else if (!bit1 && bit2) // 01{_bs1.set(x); // 01->10_bs2.reset(x);return;}else if (bit1 && !bit2) // 10{_bs1.set(x); // 10->11_bs2.set(x);return;}}// 返回0 出现0次数// 返回1 出现1次数// 返回2 出现2次数// 返回3 出现2次及以上size_t get_count(size_t x){bool bit1 = _bs1.test(x);bool bit2 = _bs2.test(x);if (!bit1 && !bit2) //00{return 0;}else if (!bit1 && bit2) // 01{return 1;}else if (bit1 && !bit2) // 10{return 2;}else{return 3;}}private:bitset<N> _bs1;bitset<N> _bs2;};
}void test_bitset()
{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 };Lzc::bitset<100> bs1;Lzc::bitset<100> bs2;for (auto e : a1){bs1.set(e);}for (auto e : a2){bs2.set(e);}for (size_t i = 0; i < 100; i++){if (bs1.test(i) && bs2.test(i)){std::cout << i << std::endl;}}
}void test_twobitset()
{Lzc::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);}for (size_t i = 0; i < 100; ++i){std::cout << i << "->" << tbs.get_count(i) << std::endl;if (tbs.get_count(i) == 1 || tbs.get_count(i) == 2){std::cout << i << std::endl;}}
}

2、布隆过滤器

2.1 什么是布隆过滤器

有一些场景下面，有大量数据需要判断是否存在，而这些数据不是整型，那么位图就不能使用了，使用红黑树/哈希表等内存空间可能不够。这些场景就需要布隆过滤器来解决。

布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询，可以用来告诉你“某样东西一定不存在或者可能存在”，它是用多个哈希函数(将数据类型转为整型)，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。

布隆过滤器的思路就是把 key 先映射转成哈希整型值，再映射一个位，如果只映射一个位的话，冲突较多，所以可以通过多个哈希函数映射多个位，降低冲突。

布隆过滤器这里跟哈希表不一样，它无法解决哈希冲突的，因为它压根就不存储这个值，只标记映射的位。它的思路是尽可能降低哈希冲突。

注意：布隆过滤器，判断一个值 key 在是不准确的，判断一个值 key 不在是准确的。

如：插入了B，映射的几个位都为1，但是查询一个没有插入的A，如果A映射的位与B映射的位相同，就会认为A在，其实不在。

2.2 布隆过滤器的误判率推导

布隆过滤器误判率推导过程：
基本假设
m：布隆过滤器的bit长度

n：插入过滤器的元素个数

k：哈希函数的个数

推导过程
单个bit位被设置为1的概率：
P(1) = 1/m

单个bit位不被设置为1的概率：
P(0) = 1 - 1/m

经过k次哈希后，某bit位仍为0的概率：
P(0)^k = (1 - 1/m)^k

根据极限公式（当m→∞时）：
lim (1 - 1/m)^m = e^(-1)
因此近似：
(1 - 1/m)^k ≈ e^(-k/m)

插入n个元素后，某bit位仍为0的概率：
(1 - 1/m)^(kn) ≈ e^(-kn/m)

插入n个元素后，某bit位被置1的概率：
1 - e^(-kn/m)

查询误判概率（所有k个哈希位都为1）：
f(k) = (1 - e^(-kn/m))^k

结论
布隆过滤器误判率公式：
f(k) = (1 - e^(-kn/m))^k

参数影响：

当k固定时：n增加 → 误判率↑，m增加 → 误判率↓

最优哈希函数个数（使误判率最低）：
k = (m/n) * ln2

给定误判率p时的bit长度：
m = - (n * lnp) / (ln2)^2

参考文献：布隆过滤器（Bloom Filter）- 原理、实现和推导_布隆过滤器原理-CSDN博客

[布隆过滤器BloomFilter] 举例说明+证明推导_bloom filter 最佳hash函数数量推导-CSDN博客

2.3 布隆过滤器的实现思路

给定误判率p，插入的元素个数n，

通过m = - (n * lnp) / (ln2)^2，算出布隆过滤器的bit长度m，

再通过k = (m/n) * ln2，算出哈希函数的个数k

template<size_t m,class K(数据类型),class k(哈希函数的个数)>

class bloomfilter{};

2.4 布隆过滤器的删除访问

布隆过滤器默认是不支持删除的，因为比如“猪八戒”和“孙悟空”都映射在布隆过滤器中，他们映射的位有一个位是共同映射的（冲突的）。如果我们把“孙悟空”删掉，那么再去查找“猪八戒”会查找不到，因为“猪八戒”间接被删掉了。

解决方案：可以考虑计数标记的方式，一个位置用多个位标记，记录映射这个位的计数值。删除时，仅仅减减计数，那么就可以某种程度支持删除。但是这个方案也有缺陷，如果一个值不在布隆过滤器中，我们去删除，减减了映射位的计数，那么会影响已存在的值。也就是说，一个确定存在的值，可能会变成不存在，这里就很坑。当然也有人提出，我们可以考虑计数方式支持删除，但是定期重建一下布隆过滤器，这样也是一种思路。

2.5 布隆过滤器的应用

布隆过滤器的优缺点分析

优点：效率高，节省空间，相比位图，可以适用于各种类型的标记过滤。
缺点：存在误判（在是不准确的，不在是准确的），不好支持删除。

布隆过滤器在实际中的一些应用

2.4.1 爬虫系统中 URL 去重

在爬虫系统中，为了避免重复爬取相同的 URL，可以使用布隆过滤器来进行 URL 去重。爬取到的 URL 可以通过布隆过滤器进行判断，已经存在的 URL 则可以直接忽略，避免重复的网络请求和数据处理。就算误判了，问题不大。

2.4.2 垃圾邮件过滤

在垃圾邮件过滤系统中，布隆过滤器可以用来判断邮件是否是垃圾邮件。系统可以将已知的垃圾邮件的特征信息存储在布隆过滤器中，当新的邮件到达时，可以通过布隆过滤器快速判断是否为垃圾邮件，不在(准确)，肯定不是垃圾邮件，从而提高过滤的效率。

2.4.3 预防缓存穿透

在分布式缓存系统中，布隆过滤器可以用来解决缓存穿透的问题。缓存穿透是指恶意用户请求一个不存在的数据，导致请求直接访问数据库，造成数据库压力过大。布隆过滤器可以先判断请求的数据是否存在于布隆过滤器中，如果不存在(准确)，直接返回不存在，避免对数据库的无效查询。

2.4.4 对数据库查询提效

在数据库中，布隆过滤器可以用来加速查询操作。例如：一个 App 要快速判断一个电话号码是否注册过，可以使用布隆过滤器来判断一个用户电话号码是否存在于表中，如果不存在(准确)，可以直接返回不存在，避免对数据库进行无用的查询操作。如果在，再去数据库查询进行二次确认。

3、海量数据处理

3.1 10亿个整数里面求最大的前100个

经典topk问题，用堆解决，堆+堆排序+topK问题-CSDN博客

3.2 位图和布隆过滤器相关题目

3.3 给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？

分析：

假设平均每个query(查询语句)字符串 50 byte，100 亿个query就是 5000 亿 byte，约等于 500G（1G 约等于 10 亿多 Byte）。
哈希表/红黑树等数据结构肯定是无能为力的。

解决方案 1：

这个首先可以用布隆过滤器解决，一个文件中的query放进布隆过滤器，另一个文件依次查找，在的就是交集。问题就是找到的交集不够准确，因为在的值可能是误判的，但是交集一定被找到了。

解决方案 2：

哈希切分。首先内存的访问速度远大于硬盘，大文件放到内存搞不定，那么我们可以考虑切分为小文件，再放进内存处理。

但是不要平均切分，因为平均切分以后，每个小文件都需要依次暴力处理，效率还是太低了。

可以利用哈希切分，依次读取文件中query，i = HashFunc(query)%N，N为准备切分多少份小文件，N取决于切成多少份内存能放下。query放进第 i 号小文件，这样A和B中相同的query算出的hash值 i 是一样的，相同的query就进入的编号相同的小文件。就可以编号相同的文件直接找交集，不用交叉找，效率就提升了。（本段表述中 i 和 j 是不同的整数）

哈希切分的问题就是每个小文件不是均匀切分的，可能会导致某个小文件很大内存放不下。我们细细分析一下某个小文件很大有两种情况：

这个小文件中大部分是同一个query。
这个小文件是有很多的不同query构成，本质是这些query冲突了。

针对情况 1，其实放到内存的set中是可以放下的，因为set是去重的。
针对情况 2，需要换个哈希函数继续分别对Ai和Bi 二次哈希切分。

所以本题我们遇到大于 1G 的小文件，可以继续读到set中找交集。若set.insert()时抛出了异常（set插入数据抛异常只可能是申请内存失败了，不会有其他情况），那么就说明内存放不下是情况 2，换个哈希函数进行二次哈希切分后再对应找交集。