【C++】哈希扩展
🌈个人主页：秦jh_-ZEEKLOG博客
🔥 系列专栏：https://blog.ZEEKLOG.net/qinjh_/category_12575764.html?spm=1001.2014.3001.5482
目录
给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交 集？
给一个超过100G大小的log file, log中存着ip地址, 设计算法找到出现次数最 多的ip地址？查找出现次数前10的ip地址
前言
💬 hello! 各位铁子们大家好哇。
今日更新了位图的相关内容
🎉 欢迎大家关注🔍点赞👍收藏⭐️留言📝
位图
位图相关面试题
给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个 数中。
解题思路1：暴力遍历，时间复杂度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代表不存在。那么 我们设计一个用位表示数据是否存在的数据结构，这个数据结构就叫位图。
位图的设计及实现
位图本质是一个直接定址法的哈希表，每个整型值映射一个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亿个数中 了。
模拟实现
#pragma once #include<vector> namespace bit { template<size_t N> class bitset { public: bitset() { _bs.resize(N / 32 + 1); } // x映射的位标记成1 void set(size_t x) { size_t i = x / 32; size_t j = x % 32; _bs[i] |= (1 << j); } // x映射的位标记成0 void reset(size_t x) { size_t i = x / 32; size_t j = x % 32; _bs[i] &= (~(1 << j)); } // x映射的位是1返回真 // x映射的位是0返回假 bool test(size_t x) { size_t i = x / 32; size_t j = x % 32; return _bs[i] & (1 << j); } private: std::vector<int> _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->01 { _bs2.set(x); } else if (!bit1 && bit2) // 01->10 { _bs1.set(x); _bs2.reset(x); } else if (bit1 && !bit2) // 10->11 { _bs1.set(x); _bs2.set(x); } } // 返回0 出现0次数 // 返回1 出现1次数 // 返回2 出现2次数 // 返回3 出现2次及以上 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; } } 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); } for (size_t i = 0; i < 100; ++i) { //cout << i << "->" << tbs.get_count(i) << endl; if (tbs.get_count(i) == 1 || tbs.get_count(i) == 2) { cout << i << endl; } } } void test_bitset1() { 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 }; bitset<100> bs1; 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)) { cout << i << endl; } } } C++库中的位图 bitset
https://legacy.cplusplus.com/reference/bitset/bitset/
可以看到核心接口还是set/reset/和test，当然后面还实现了一些其他接口，如to_string将位图按位转 成01字符串，再包括operator[]等支持像数组一样控制一个位的实现
位图的优缺点
优点：增删查改快，节省空间
缺点：只适用于整形
位图相关考察题目
- 给定100亿个整数，设计算法找到只出现一次的整数？
虽然是100亿个数，但是还是按范围开空间，所以还是开2^32个位，跟前面的题目是一样的
- 给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
把数据读出来，分别放到两个位图，依次遍历，同时在两个位图的值就是交集
- 一个文件有100亿个整数，1G内存，设计算法找到出现次数不超过2次的所有整数
之前我们是标记在不在，只需要一个位即可，这里要统计出现次数不超过2次的，可以每个值用两个位 标记即可，00代表出现0次，01代表出现1次，10代表出现2次，11代表出现2次以上。最后统计出所有 01和10标记的值即可。
布隆过滤器
什么是布隆过滤器
有一些场景下面，有大量数据需要判断是否存在，而这些数据不是整形，那么位图就不能使用了，使 用红黑树/哈希表等内存空间可能不够。这些场景就需要布隆过滤器来解决。
布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的 一种紧凑型的、比较巧妙的概率型 数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”，它是 用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量 的内存空间。
布隆过滤器的思路就是把key先映射转成哈希整型值，再映射一个位，如果只映射一个位的话，冲突率 会比较多，所以可以通过多个哈希函数映射多个位，降低冲突率。
布隆过滤器这里跟哈希表不一样，它无法解决哈希冲突的，因为他压根就不存储这个值，只标记映射 的位。它的思路是尽可能降低哈希冲突。判断一个值key在是不准确的，判断一个值key不在是准确 的。
布隆过滤器器误判率推导
推导过程：
记一下结论即可！
假设
m：布隆过滤器的bit长度。
n：插入过滤器的元素个数。
k：哈希函数的个数。
结论：
布隆过滤器代码实现
#pragma once #include<string> #include"BitSet.h" struct HashFuncBKDR { // @detail 本 算法由于在Brian Kernighan与Dennis Ritchie的《The CProgramming 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, size_t X = 5, class K = std::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; //cout << hash1 <<" "<< hash2 <<" "<< hash3 << endl; _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.71, -3.0 / X)), 3.0); return p; } private: static const size_t M = N * X; bit::bitset<M> _bs; }; void TestBloomFilter1() { BloomFilter<10> bf; bf.Set("猪八戒"); bf.Set("孙悟空"); bf.Set("唐僧"); cout << bf.Test("猪八戒") << endl; cout << bf.Test("孙悟空") << endl; cout << bf.Test("唐僧") << endl; cout << bf.Test("沙僧") << endl; cout << bf.Test("猪八戒1") << endl; cout << bf.Test("猪戒八") << endl; } void TestBloomFilter2() { srand(time(0)); const size_t N = 1000000; BloomFilter<N> bf; //BloomFilter<N, 3> bf; //BloomFilter<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=utf-8&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; }布隆过滤器删除问题
布隆过滤器默认是不支持删除的，因为比如"猪八戒“和”孙悟空“都映射在布隆过滤器中，他们映射 的位有一个位是共同映射的(冲突的)，如果我们把孙悟空删掉，那么再去查找“猪八戒”会查找不到， 因为那么“猪八戒”间接被删掉了。
解决方案：可以考虑计数标记的方式，一个位置用多个位标记，记录映射这个位的计数值，删除时， 仅仅减减计数，那么就可以某种程度支持删除。但是这个方案也有缺陷，如果一个值不在布隆过滤器 中，我们去删除，减减了映射位的计数，那么会影响已存在的值，也就是说，一个确定存在的值，可 能会变成不存在，这里就很坑。当然也有人提出，我们可以考虑计数方式支持删除，但是定期重建一 下布隆过滤器，这样也是一种思路。
布隆过滤器的应用
首先我们分析一下布隆过滤器的优缺点：
优点：效率高，节省空间，相比位图，可以适用于各种类型的标记过滤
缺点：存在误判(在是不准确的，不在是准确的)，不好支持删除
一些应用：
- 爬虫系统中URL去重：
在爬虫系统中，为了避免重复爬取相同的URL，可以使用布隆过滤器来进行URL去重。爬取到的URL可 以通过布隆过滤器进行判断，已经存在的URL则可以直接忽略，避免重复的网络请求和数据处理。
- 垃圾邮件过滤：
在垃圾邮件过滤系统中，布隆过滤器可以用来判断邮件是否是垃圾邮件。系统可以将已知的垃圾邮件 的特征信息存储在布隆过滤器中，当新的邮件到达时，可以通过布隆过滤器快速判断是否为垃圾邮 件，从而提高过滤的效率。
- 预防缓存穿透
在分布式缓存系统中，布隆过滤器可以用来解决缓存穿透的问题。缓存穿透是指恶意用户请求一个不 存在的数据，导致请求直接访问数据库，造成数据库压力过大。布隆过滤器可以先判断请求的数据是 否存在于布隆过滤器中，如果不存在，直接返回不存在，避免对数据库的无效查询。
- 对数据库查询提效
在数据库中，布隆过滤器可以用来加速查询操作。例如：一个app要快速判断一个电话号码是否注册 过，可以使用布隆过滤器来判断一个用户电话号码是否存在于表中，如果不存在，可以直接返回不存 在，避免对数据库进行无用的查询操作。如果在，再去数据库查询进行二次确认。
海量数据处理问题
给两个文件，分别有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，换个哈希函数进行二次哈希 切分后再对应找交集。
给一个超过100G大小的log file, log中存着ip地址, 设计算法找到出现次数最 多的ip地址？查找出现次数前10的ip地址
本题的思路跟上题完全类似，依次读取文件A中query，i = HashFunc(query)%500，query放进Ai号小 文件，然后依次用map对每个Ai小文件统计ip次数，同时求出现次数最多的ip或者topk ip。本质是相同的ip在哈希切分过程中，一定进入的同一个小文件Ai，不可能出现同一个ip进入Ai和Aj 的情况，所以对Ai进行统计次数就是准确的ip次数
