【C++笔记】位图和布隆过滤器

【C++笔记】位图和布隆过滤器

?个人主页：大白的编程日记

?专栏：C++笔记

---

文章目录

【C++笔记】位图和布隆过滤器前言一. 位图1.1 位图相关面试题1.2 C++库中的位图1.3位图优缺点1.4位图相关考察题目 二.布隆过滤器2.1 什么是布隆过滤器2.2 布隆过滤器器误判率推导2.3 布隆过滤器代码实现2.4 布隆过滤器删除问题2.5 布隆过滤器的应用 三.海量数据处理问题3.1题目一3.2 题目二3.3 题目三 后言

前言

哈喽，各位小伙伴大家好!上期我们讲了二叉搜索树。今天我们来讲一下位图和布隆过滤器。话不多说，我们进入正题！向大厂冲锋

一. 位图

1.1 位图相关面试题

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

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

解题思路2
排序+二分查找。
时间复杂度消耗 O(N*logN) + O(logN)
深入分析：解题思路2是否可行。

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

1.2 位图的设计及实现
位图本质是⼀个直接定址法的哈希表，每个整型值映射⼀个bit位，位图提供控制这个bit的相关接口。

bit映射关系
实现中需要注意的是，C/C++没有对应位的类型，只能看int/char这样整形类型，我们再通过位运算去控制对应的比特位。比如我们数据存到vector中，相当于每个int值映射对应的32个值，比如第⼀个整形映射0-31对应的位，第⼆个整形映射32-63对应的位，后面的以此类推，那么来了⼀个整形值x，
i = x / 32；j = x % 32；计算出x映射的值在vector的第i个整形数据的第j位。

数据范围
解决给40亿个不重复的无符号整数，查找⼀个数据的问题，我们要给位图开2^32个位，注意不能开40 亿个位，因为映射是按大小映射的，我们要按数据大小范围开空间，范围是是0-2^32-1，所以需要开
2^32个位。然后从文件中依次读取每个set到位图中，然后就可以快速判断⼀个值是否在这40亿个数中
了。

代码实现
这里注意我们映射的数据范围/32可能不整除，所以多开一个int即可。其他都是简单的使用位运算的标记和检测接口。

template<size_t N>class Bit_Set{public:Bit_Set(){bitmap.resize(N / 32 + 1);//多开一个防止不整除}//将第N个数据标记为1void set(size_t n){int i = n / 32;int j = n  % 32;bitmap[i] |= (1 << j);}//将第N个数据标记为0void reset(size_t n){int i = n / 32;int j = n  % 32;bitmap[i] &= (~(1 << j));}//查看第N个数据是否标记bool test(size_t n){int i = n / 32;int j = n  % 32;return bitmap[i] & (1 << j);}private:std::vector<int> bitmap;//封装vector};

这里纠正一下左移的问题。

1.2 C++库中的位图

库里的位图


可以看到核心接口还是set/reset/和test，当然后面还实现了⼀些其他接口，如to_string将位图按位转成01字符串，再包括operator[]等⽀持像数组⼀样控制⼀个位的实现。

但是库的bitset有个小bug就是底层使用的是静态数组。
如果数据范围太大就会越界

1.3位图优缺点

优点：增删查改快，节省空间
缺点：只适用于整形。浮点数字符串这些都不行

1.4位图相关考察题目

给定100亿个整数，设计算法找到只出现一次的整数？
虽然是100亿个数，但是还是按范围开空间，所以还是开2^32个位，跟前面的题目是⼀样的。

⼀个文件有100亿个整数，1G内存，设计算法找到出现次数不超过2次的所有整数
这题目和上题一样只不过需要四种状态，两个bitset也能表示四种状态修改一下即可。

template<size_t N>class TwoBitSet{public:void Set(size_t n){bool bit1 = b1.test(n);bool bit2 = b2.test(n);if (!bit1 && !bit2)//00->01{b2.set(n);}else if (!bit1&&bit2)//01->10{b1.set(n);b2.reset(n);}else//10->11 11->11{b1.set(n);b2.set(n);}}int get_count(size_t n)//检测出现次数{bool bit1 = b1.test(n);bool bit2 = b2.test(n);if (!bit1 && !bit2){return 0;//没出现}else if (!bit1 && bit2){return 1;//出现1次}else if (bit1 && !bit2){return 2;//出现2次}else{return 3;//出现3次及以上}}private:Bit_Set<N> b1;Bit_Set<N> b2;//封装};

这样这两道题都能解决了。

给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
把数据读出来，分别放到两个位图，依次遍历，同时在两个位图的值都在就是交集。

二.布隆过滤器

2.1 什么是布隆过滤器

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

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

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

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

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

那我们的哈希函数给几个比较好呢？空间又该开几个bit呢？

所以后来有人推导了一下：

推导过程： 说明：这个比较复杂，涉及概率论、极限、对数运算，求导函数等知识，有兴趣且数学功底比较好的可以看细看⼀下，其他同学记⼀下结论即可！

推导
假设
m：布隆过滤器的bit长度。
n：插入过滤器的元素个数。
k：哈希函数的个数。
布隆过滤器哈希函数等条件下某个位设置为1的概率： 1 / m 1/m 1/m
布隆过滤器哈希函数等条件下某个位设置不为1的概率： 1 − 1 / m 1-1/m 1−1/m
在经过k次哈希后，某个位置依旧不为1的概率： ( 1 − 1 / m ) k (1 − 1/m)^k (1−1/m)k
根据极限公式： lim ⁡ m → ∞ ( 1 − 1 m ) − m = e \lim_{m \to \infty} \left( 1 - \frac{1}{m} \right)^{-m} = e m→∞lim​(1−m1​)−m=e ( 1 − 1 m ) k = ( ( 1 − 1 m ) m ) k m ≈ e − k m \left(1 - \frac{1}{m}\right)^k = \left(\left(1 - \frac{1}{m}\right)^m\right)^{\frac{k}{m}} \approx e^{-\frac{k}{m}} (1−m1​)k=((1−m1​)m)mk​≈e−mk​
添加n个元素某个位置不置为1的概率： ( 1 − 1 m ) k n ≈ e − k n m \left(1 - \frac{1}{m}\right)^{kn} \approx e^{-\frac{kn}{m}} (1−m1​)kn≈e−mkn​
添加n个元素某个位置置为1的概率： 1 − ( 1 − 1 m ) k n ≈ 1 − e − k n m 1 - \left(1 - \frac{1}{m}\right)^{kn} \approx 1 - e^{-\frac{kn}{m}} 1−(1−m1​)kn≈1−e−mkn​
查询⼀个元素，k次hash后误判的概率为都命中1的概率： ( 1 − ( 1 − 1 m ) k n ) k ≈ ( 1 − e − k n m ) k \left(1 - \left(1 - \frac{1}{m}\right)^{kn}\right)^k \approx \left(1 - e^{-\frac{kn}{m}}\right)^k (1−(1−m1​)kn)k≈(1−e−mkn​)k结论
结论：
布隆过滤器的误判率为： f ( k ) = ( 1 − e − k n m ) k f(k) = \left(1 - e^{-\frac{kn}{m}}\right)^k f(k)=(1−e−mkn​)k f ( k ) = ( 1 − 1 e k n m ) k f(k) = \left(1 - \frac{1}{e^{\frac{kn}{m}}}\right)^k f(k)=(1−emkn​1​)k
由误判率公式可知，在k⼀定的情况下，当n增加时，误判率增加，m增加时，误判率减少。
在m和n⼀定，在对误判率公式求导，误判率尽可能小的情况下，可以得到hash函数个数：
k = m n ln ⁡ 2 k = \frac{m}{n} \ln 2 k=nm​ln2时误判率最低。
期望的误判率p和插⼊数据个数n确定的情况下，再把上面的公式带入误判率公式可以得到，通过期望的误判率和插入数据个数n得到bit长度： m = − n ⋅ ln ⁡ p ( ln ⁡ 2 ) 2 m = -\frac{n \cdot \ln p}{(\ln 2)^2} m=−(ln2)2n⋅lnp​

以上两个公式的推导过程尤其复杂，这里放两篇博客链接布隆过滤器（Bloom Filter）- 原理、实现和推导和[布隆过滤器BloomFilter] 举例说明+证明推导。

2.3 布隆过滤器代码实现

首先我们需要几个哈希函数，这里我们就简单的以字符串的哈希函数为例。
各种字符串Hash函数-clq-博客
这里有几个比较好的字符串哈希函数。

struct HashFuncBKDR{/// @detail 本 算法由于在Brian Kernighan与Dennis Ritchie的《The C //Programming Language》// ⼀书被展⽰⽽得 名，是⼀种简单快捷的hash算法，也是Java⽬前采⽤的字符串的Hash//算法累乘因⼦为31。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;}};template<size_t N>class Bit_Set{public:Bit_Set(){bitmap.resize(N / 32 + 1);}//将第N个数据标记为1void set(size_t n){int i = n / 32;int j = n % 32;bitmap[i] |= (1 << j);}//将第N个数据标记为0void reset(size_t n){int i = n / 32;int j = n % 32;bitmap[i] &= (~(1 << j));}//查看第N个数据是否标记bool test(size_t n){int i = n / 32;int j = n % 32;return bitmap[i] & (1 << j);}private:std::vector<int> bitmap;};template<size_t N,      size_t X=6,         class K=string,         class Hash1= HashFuncBKDR,         class Hash2= HashFuncAP,         class Hash3= HashFuncDJB>class Bloom{public:void Set(const K& key){size_t b1 = Hash1()(key) % M;size_t b2 = Hash2()(key) % M;size_t b3 = Hash3()(key) % M;//三个哈希函数映射的值b.set(b1);b.set(b2);b.set(b3);//标记}bool Test(const K& key){size_t b1 = Hash1()(key) % M;size_t b2 = Hash2()(key) % M;size_t b3 = Hash3()(key) % M;//三个哈希函数映射的值if (!b.test(b1))//只要有一个没标记就返回0说明不在{return 0;}if (!b.test(b2))//只要有一个没标记就返回0说明不在{return 0;}if (!b.test(b3))//只要有一个没标记就返回0说明不在{return 0;}return true;//可能存在误判}// 获取公式计算出的误判率double getFalseProbability(){double p = pow((1.0 - pow(2.71, -3.0 / X)), 3.0);return p;}private:static const size_t M = X * N;Bit_Set<M> b;};

测试

void Test(){qcj::Bloom<10> b;b.Set("孙悟空");b.Set("猪八戒");b.Set("唐僧");cout << b.Test("孙悟空") << endl;;cout << b.Test("猪八戒") << endl;;cout << b.Test("唐僧") << endl;cout << b.Test("沙僧") << endl;;cout << b.Test("猪八戒1") << endl;;}

void TestBloomFilter2(){srand(time(0));const size_t N = 100000;/*qcj::Bloom<N> bf;*/qcj::Bloom<N, 3> bf;/*qcj::Bloom<N, 10> bf;*/std::vector<std::string> v1;std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";//std::string url = "https://www.baidu.com/s?ie=utf8&f=8&rsv_bp=1&rsv_idx=1&tn=65081411_1_oem_dg&wd=ln2&fenlei=256&rsv_pq=0x8d9962630072789f & rsv_t = ceda1rulSdBxDLjBdX4484KaopD % 2BzBFgV1uZn4271RV0PonRFJm0i5xAJ % 2FDo & rqlang = en & rsv_enter = 1 & rsv_dl = ib & rsv_sug3 = 3 & rsv_sug1 = 2 & rsv_sug7 = 100 & rsv_sug2 =0 & rsv_btype = i & inputT = 330 & rsv_sug4 = 2535";//std::string url = "猪⼋戒";for (size_t i = 0; i < N; ++i){v1.push_back(url + std::to_string(i));}for (auto& str : v1){bf.Set(str);}// v2跟v1是相似字符串集（前缀⼀样），但是后缀不⼀样v1.clear();for (size_t i = 0; i < N; ++i){std::string urlstr = url;urlstr += std::to_string(9999999 + i);v1.push_back(urlstr);}size_t n2 = 0;for (auto& str : v1){if (bf.Test(str)) // 误判{++n2;}}cout << "相似字符串误判率:" << (double)n2 / (double)N << endl;// 不相似字符串集 前缀后缀都不⼀样v1.clear();for (size_t i = 0; i < N; ++i){//string url = "zhihu.com";string url = "孙悟空";url += std::to_string(i + rand());v1.push_back(url);}size_t n3 = 0;for (auto& str : v1){if (bf.Test(str)){++n3;}}cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;cout << "公式计算出的误判率:" << bf.getFalseProbability() << endl;}

这里我们用相似字符串，不相似字符串，和公式计算的误判率对比。

可以发现这里我们公式算的还是非常的准的。

2.4 布隆过滤器删除问题

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

所以删除一个值可能会影响另外一个值。

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

解决方案二
当然也有⼈提出，我们可以考虑计数方式支持删除，但是定期重建⼀
下布隆过滤器，这样也是⼀种思路。

所以严格来说布隆过滤器不支持删除，因为会进一步导致误判。但是可以结合实际场景和需求进行挑选删除的解决方案。

2.5 布隆过滤器的应用

首先我们分析⼀下布隆过滤器的优缺点：
优点：效率高，节省空间，相比位图，可以适⽤于各种类型的标记过滤
缺点：存在误判(在是不准确的，不在是准确的)，不好支持删除
布隆过滤器在实际中的⼀些应用：

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

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

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

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

三.海量数据处理问题

3.1题目一

100亿个整数里面求最大的前100个。
这里我们建一个100的小堆。在把100亿个整数比堆顶元素大的进堆即可。
剩下的100堆元素就是最大的100个数。
具体细节看这篇博文：Top_K问题

3.2 题目二

给两个文件，分别有100亿个query(字符串)，我们只有1G内存，如何找到两个文件交集
分析：假设平均每个query字符串50byte，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就进入的编号相同的小文件就可以编号相同的我文件直接找交集，不用交叉找，效率就提升了。
• 本质是相同的query在哈希切分过程中，一定进入的同一个小问件Ai和Bi，不可能出现A中的的query进入Ai，但是B中的相同query进入了和Bj的情况，所以对Ai和Bi进行求交集即可，不需要Ai和Bj求交集。（本段表述中i和j是不同的整数）
• 哈希切分的问题就是每个小文件不是均匀切分的，可能会导致某个小文件很大内存放不下。我们细细分析⼀下某个小文件很大有两种情况：
1.这个小文件中大部分是同⼀个query。
2.这个小文件是有很多的不同query构成，本质是这些query冲突了。针对情况1，其实放到内存的set中是可以放下的，因为set是去重的。针对情况2，需要换个哈希函数继续⼆次哈希切分。所以本体我们遇到大于1G小文件，可以继续读到set中找交集，若set insert时抛出了异常(set插⼊数据抛异常只可能是申请内存失败了，不会有其他情况)，那么就说明内存放不下是情况2，换个哈希函进行⼆次哈希切分后再对应找交集。

3.3 题目三

给⼀个超过100G大小的log file, log中存着ip地址, 设计算法找到出现次数最
多的ip地址？查找出现次数前10的ip地址
本题的思路跟上题完全类似，依次读取文件A中query，i = HashFunc(query)%500，query放进Ai号小文件，然后依次⽤map<string, int>对每个Ai小文件统计ip次数，同时求出现次数最多的ip或者topkip。本质是相同的ip在哈希切分过程中，⼀定进⼊的同⼀个小文件Ai，不可能出现同一个ip进入Ai和Aj的情况，所以对Ai进行统计次数就是准确的ip次数。

后言

这就是位图和布隆过滤器。大家自己好好消化！今天就分享到这！感谢各位的耐心垂阅！咱们下期见！拜拜~