【C++高阶】哈希—— 位图 | 布隆过滤器 | 哈希切分

✨                                          人生如梦，朝露夕花，宛若泡影     🌏

📃个人主页：island1314

🔥个人专栏：C++学习

⛺️ 欢迎关注：👍点赞 👂🏽留言 😍收藏  💞 💞 💞

  

---

🚀引言

 之前我们已经在这篇文章中 【C++高阶】哈希函数底层原理全面探索和深度解析-CSDN博客 

了解到了哈希的一些相关知识，现在我们来对哈希进行一些扩展了解

1.  位图

🥃问题：

• 给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中？

根据我们现有的知识，该如何处理上诉问题呢？

方法一：排序 + 二分查找

• 因为二分查找的效率还是比较高的，logN的时间复杂度，但是磁盘上面无法进行排序，排序要支持下标的随机访问，这40亿个整数又无法加载到内存里面，你怎么进行排序呢？所以这样的方式也是不可行的。

方法二：红黑树 或者 哈希表

• 红黑树查找的效率是logN，哈希表可以直接映射，查找的效率接近常数次，虽然他们查找的效率确实很快，但是40亿个整数，那就是160亿字节，10亿字节是1GB，16GB字节红黑树和哈希表怎么能存的下呢？这还没有算红黑树的三叉链结构，每个结点有三个指针，而且哈希表每个结点会有一个next指针，算上这些的话需要的内存会更大，所以用红黑树或哈希表也是无法解决问题的。

但是这些方式都行不通，先来看一下40亿的无符号整数占用多大的内存空间：

• 10亿个字节 ≈ 1GB。
• 40亿个字节 ≈ 4GB。
• 40亿个无符号整数 ≈ 16GB。

而一般的内存根本放不下这么多的数据，无论是上面的哪种方法，都需要存放数据本身，即使是用数组来存放都需要16GB，如果用红黑树(有三叉链，颜色)需要大的内存，哈希表虽然少一点，但是仍然有next指针，还是存放不下.

• 问题中只要求判断一个数是否在这40亿个数据中，所以可以不存放数据本。

因此我们可以采用 位图 的方式来处理这个问题。

1.1 位图概念

• 所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。

🍉对于40亿个数据，至少需要40亿个比特位才能标识它们的状态，对于这种情况一般选择个比特位：因为  < 40亿 < 

232 = 42亿9千多万，40亿个数据完全可以表示的下，此时相当于一个数组，有232个元素，每个元素是一个比特位。

使用位图方式占用的内存就小多了：

•   个比特位 = 个字节 = KB = MB = 512MB = 0.5GB
• 从最开始需要16GB内存空间直接下降到了需要0.5GB的空间。

但是在语言层面上并没有比特位的数组。

•   个比特位可以用个int类型的数组来表示。
•  也可以用个char类型的数组来表示。

🌰🌰随便例举一些数字，如下图所示，这里采用char类型为数组的基本单位。

• 数据范围是1到22，所以需要3个char类型的变量。
• 下标为1的比特位表示数字1的存在情况，下标为18的比特位表示数字18是否存在
• 这3个char类型的变量是用一个数组实现的，即char [3]。这3个char类型变量的地址从左到右依次升高，但是每个char类型中比特位却是：低的比特位在右，高的比特位在左。

确定数据的映射位置：

如何确定一个数据映射在位图的哪个比特位呢？以整数18为例说明：

•  18映射在位图下标为2的八个比特位中，即第三个char类型变量。（18 / 8 ）
•  具体映射在下标为2的char类型变量中下标为2的比特位上，也就是在这个char类型中第三个比特位上。（18 % 2）

💢💢注：如果数据相对集中，而且从比较大的数字开始的，可以采用相对值，比如最小的数据是1000，最大的数据是2000，可以开辟1000个比特位的位图，下标为0的比特位表示数字1000是否存在，依此类推。

不适用int类型数组的原因：

💢我们知道，数据在内存中的存储是有大小端的，如果使用int类型的数组，上图就变成：

只需要一个int类型的数据就够了，并且还多出8个比特位。

💢假设上图中是小端存储方式，并且是处理完的位图，此时将这份代码换到了大端存储方式的机器上：

此时位图结构就变成了上图中所示，原本表示数字0~7的8个比特位放在了高地址处，变成了表示24 ~31的8个比特位。

 原本在小端机上的程序在大端机上极有可能出现BUG。而采用char类型数组就不用考虑大小端的问题，因为一个char类型就是一个字节，每个char都是从低地址到高地址排列。

上面是在内存中存储的真实样子，但是我们在使用的时候无需知道位图在内存中样子。

这种方式其实就是一种哈希思想，将数据直接映射到位图上。

1.2 位图实现

namespace qian
{// 非类型模板参数template <size_t N>class bitset{public:bitset() 构造函数{//_bits.resize(N / 8 + 1, 0);//可能开的比特位恰好满足数字的个数，也可能最多浪费7个比特位//_bits.resize(N >> 3 + 1, 0);//位运算符优先级过低，这里先进行+运算，则结果和我们预想的不一致，发生错误。_bits.resize((N >> 3) + 1, 0);}void set(size_t x)  // x 映射的位标记为 1{size_t i = x >> 3; //映射到第几个char中size_t j = x % 8; //映射到char中第几个比特位//将映射到位图中的比特位置一_bits[i] |= 1 << j;}void reset(size_t x)  // x 映射的位标记为 0{size_t i = x >> 3;size_t j = x % 8;_bits[i] &= ~(1 << j);}bool test(size_t x) // x 映射位为1返回真，0返回假{size_t i = x / 8;size_t j = x % 8;return _bits[i] & (1 << j);//这里不是&=，因为test不改变位图，只是判断一下而已//有些编译器bool值是四个字节，返回时会发生整型提升，高位补符号位，但这些都不重要，只要是非0就行，判断为真//我的编译器bool值是一个字节}private:vector<char> _bits;};}

基本构造剖析

•  使用非类型模板参数，该参数用来指定位图比特位的个数。
•  底层使用的是vector，vector中是char类型变量。

在构造函数中需要指定vector的大小，否则vector的大小是0，一个比特位也没有。

• 非类型模板参数N指定是比特位的个数，而构造函数开辟的是char类型变量的个数，所以需要N / 8。
• 由于N / 8的结果不是整数时会取整而抛弃小数部分，所以需要在N /8 后再加1，也就是再增加 8 个比特位来确保位图够用。

CPU在计算除法的时候，其实是很复杂的，而进行移位运算就很简单，效率也非常高。

• N / 8相当于N右移3位。

因此我们使用移位运算来代替除法来提高效率

需要注意的是：加法的优先级比移位运算高，所以必须给(N>>3)加括号

函数剖析：

🍅set()

该接口的作用是将x映射在位图中的比特位置1，表示该数据存在。

•  首先将x映射在位图中的位置计算出来。
•  然后将映射的比特位置一。

💢如上图所示，要将一个char类型中的8个比特位的某一个位置一而不影响其他位，就需要或等一个只有那个位是1其他位都是0的char类型，这样一个char类型可以通过1左移固定位数得到。

🍍reset()：

void reset(size_t x) // x 映射的位标记为 0
{size_t i = x >> 3;size_t j = x % 8;_bits[i] &= ~(1 << j);
}

该接口的作用是将x映射在位图中的比特位清0，表示数据x不存在。

•  同样先计算处x所在位图中的位置。
•  然后再进行清0。

💢如上图所示，将char类型中的某个比特位清0而不影响其他位，需要与等一个只有那个位是0其他位都是1的char类型变量，这样一个char类型可以通过1左移固定位数，然后取反得到。

🍌test()

该接口的作用是在位图中查找数据x是否存在。

•  首先计算出x映射在位图中的位置。
•  然后看该比特位是0还是1。

判断某个比特位是1还是0，需要与一个只有这个位是1其他位都是0的char类型变量，如果这个bit是0，那么与以后的结果就是0，对应的bool值flase，如果这个bit是1，那么与以后的结果就不是0，对应的bool值是true。

• bool值本质上是4个字节的整形，所以这里涉及到了整形提升，但是并没有影响。
• 如果与以后的结果是0，整形提升后的结果仍然是0，bool值就是false。
• 如果与以后的结果非0，即使符号位是1，整形提升和的结果仍然非0，bool的值就是true。

位图的测试

创建个比特位的位图方式：

第一种方式：指定大小位-1，因为非类型模板参数是size_t类型的，所以-1强转位size_t以后，32个比特位都是1，所以就是232。
第二种方式：使用十六进制的方式，指定非类型模板参数的size_t类型的32个比特位都是1，此时也是
比较差的方式：使用的十进制，也就4294967296，这个数字容易记错。

根据上面程序运行结果，可以看到，置一，清零，判断都符合我们的预期。

从任务管理器中查看我们的程序所占的内存，当32个比特位的位图没有创建的时候，所占内存大小7.9MB，位图创建以后，所占内存变成了519.8MB，增加了512MB，也就是0.5GB，这和我们之前分析的一样。

• 任何一个数据集，使用32个比特位的位图都可以统计的下，也就是最多占用0.5GB的空间。
• 因为整数的最大值就是232，也就是4294967296，32个比特位的位图足够放的下。
• 即使数据集的数据个数是10个亿，但是这里有很多的重复的数据，而最大值也不会超过232。

注意：位图只能判断整数存不存在，并不存放数据本身。

---

1.3 位图应用

首先我们分析⼀下哈希位图的优缺点：

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

缺点：一般要求数据相对集中，否则会导致空间消耗上升。并且只适⽤于整形

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

🍈应用一

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

分析：

• 首先这100亿个数据在内存中肯定是放不下的，所以之前学习的存放数据本身的数据结构都用不了，只能用位图。
• 位图的一个比特位只有两种状态来表示数据的有无，这里是要统计次数，所以就要让位图不仅仅只有两种状态。

解决办法：

💢之前是判断整数是否出现，现在是判断只出现一次的整数，那就说明有的整数出现了多次，其实解决起来也很简单，我们

• 只需要开两个位图即可，用两个比特位去标识即可，两个位图相同下标的两个比特位来表示一个数据的状态。
• 00表示0次，01表示1次，10及11表示一次1以上。

💢有人可能会觉得100亿个整数太多了，担心位图存不下，别说100亿，就是1000亿，1w亿都能存的下，因为位图存的是一个范围内有多少种数，与数据的个数完全无关，仅仅和数据的范围有关系，所以根本不用担心存不下这样的事情，因为整数最多就42亿多个。

代码如下：

template <size_t N>
class twobitset
{
public:twobitset()//初始化列表会初始化{}void set(size_t x){if (!_bs1.test(x) && !_bs2.test(x)){//出现0次，则搞成01_bs2.set(x);}else if (!_bs1.test(x) && _bs2.test(x)){//出现1次，则搞成10_bs1.set(x);_bs2.reset(x);}//10出现1次以上，不需要变他}void PrintOnce(){for (size_t i = 0; i < N; i++){if (!_bs1.test(i) && _bs2.test(i)){//如果是01，说明出现一次，可以打印出来cout << i << " ";}}}private:bitset<N> _bs1;bitset<N> _bs2;
};

测试结果如下：

🍅应用二

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

解决办法：

• 两个文件都有100一个整数，必然放不进内存中，所以同样采用位图结构。
• 每个文件使用一个232个比特位的位图，两个文件就是两个位图，占用的内存也就是1GB，符合要求。

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

测试代码如下：

// 模拟位图找交集
void test_interbitset()
{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);}cout << "交集为：" << endl;for (size_t i = 0; i < 100; i++){if (bs1.test(i) && bs2.test(i)){cout << i << " " << endl;}}
}

🍍应用三

• ⼀个⽂件有100亿个整数，1G内存，设计算法找到出现次数不超过2次的所有整数

解决办法：

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

1.4 其他写法

比如我们数据存到vector中，相当于每个int值映射对应的32个值，比如第⼀个整形映射0-31对应的位，第⼆个整形映射32-63对应的位，后面的以此类推，那么来了⼀个整形值 x，i=x/32；j=x%32；计算出x映射的值在vector的第i个整形数据的第j位。

namespace island
{template<size_t N> // N是需要多少⽐特位class bitset{public:bitset(){_bs.resize(N / 32 + 1);}// x 映射的位标记为 1void set(size_t x){ //在第 i 个值的 第 j 位 size_t i = x / 32;size_t j = x % 32;_bs[i] |= (1 << j);}// x 映射的位标记为 0void reset(size_t x){size_t i = x / 32;size_t j = x % 32;_bs[i] &= (~(1 << j)); // 让1左移j 位}// x 映射位为1返回真，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;};//模拟位图找交集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 };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;}}}//模拟 找到出现次数不超过2次的所有整数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 出现 3 次及以上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;}}}}

2. 布隆过滤器

2.1 布隆过滤器的概念

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

 布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的⼀种紧凑型的、比较巧妙的概率型 数据结构，特点是高效地插⼊和查询，可以⽤来告诉你 “某样东西⼀定不存在或者可能存在”，它是 ⽤多个哈希函数，将⼀个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。 布隆过滤器的思路就是把key先映射转成哈希整型值，再映射一个位，如果只映射一个位的话，冲突率会比较多，所以可以通过多个哈希函数映射多个位，降低冲突率。 布隆过滤器这里跟哈希表不一样，它无法解决哈希冲突的，因为他压根就不存储这个值，只标记映射 的位。它的思路是尽可能降低哈希冲突。判断一个值key在是不准确的，判断一个值key不在是准确 的。

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

如果大家还想更深了解可以参考下面这篇文章

如何选择哈希函数个数和布隆过滤器长度一文中，对这个问题做了详细的研究和论证。

 

2.3 布隆过滤器的实现

哈希函数

首先需要写几个哈希函数来将字符串转换成整形，各种字符串Hash函数一文中，介绍了多种字符串转换成整数的哈希函数，并且根据冲突概率进行了性能比较，有兴趣的朋友可以自行研究一下。

//下面三个字符串转换成整形的仿函数
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;island::bitset<M> _bs;
};

基本框架分析：

该模板有多个参数，但是大部分都是使用的缺省值，不用必须去传参，底层使用的上面1.4中实现的bitset。

• size_t N：最多存储的数据个数。
• size_t X = 5, //平均存储一个值，需开辟X个位，该值根据前面公式得来，此时哈希函数是3个，故m=3n/ln2=4.3n，向上取整后X为5，先给个缺省值是5。
• class K：布隆过滤器处理的数据类型，默认情况下是string，也可以是其他类型。
• 哈希函数：将字符串或者其他类型转换成整形进行映射，给的缺省值是将字符串转换成整形的仿函数。

函数剖析：

set():

• 将数据经过三个哈希函数的处理得到三个整数，然后将这三个整数都映射到位图中来表示这个数据存在。

Test():

• 对每一个哈希函数得到的整数所映射的位置进行判断，如果某个位置不存在直接返回false，说明这个字符串不存在，当四个整数所映射的位置都存在，说明这个字符串存在。

getFalseProbability():

• 获取公式的误判率

布隆过滤器的测试

测试1：

测试2：

void TestBloomFilter2()
{srand(time(0));const size_t N = 10000;BloomFilter<N> bf;//BloomFilter<N, 3> bf;//BloomFilter<N, 10> bf;std::vector<std::string> v1;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 = "孙悟空";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;
}

可以看到，X值越大，也就是一个字符串所需要的映射比特位越多，布隆过滤器的误判率越小。但是空间消耗也增加了。

• 哈希函数的个数越多，误判率也会越小，但是对于的空间消耗也会增加。

综上我们可知布隆过滤器只能提高存在判断的准确率，并不能让它完全准确。

2.4 布隆过滤器的删除

• 布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素。

“猪八戒” 和 “孙悟空”  映射的比特位都有第4个比特位。删除上图中 “猪八戒” 元素，如果直接将该元素所对应的二进制比特位置0，“孙悟空” 的元素也被删除了，因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。

一种支持删除的方法：将布隆过滤器中的每个比特位扩展成一个小的计数器，插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一，删除元素时，给k个计数器减一，通过多占用几倍存储空间的代价来增加删除操作。

缺陷：

1. 无法确认元素是否真正在布隆过滤器中
2. 如果采用计数方式删除，存在计数回绕

2.5 布隆过滤器的应用

首先我们分析⼀下布隆过滤器的优缺点：

优点：效率高，增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关。数据量很大时，布隆过滤器可以表示全集，其他数据结构不能
6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算。哈希函数相互之间没有关系，方便硬件并行运算。相比位图，可以适用于各种类型的标记过滤

缺点：存在误判(在是不准确的，不在是准确的)，不好支持删除，不能获取元素本身。

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

• 爬虫系统URL去重

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

• 垃圾邮件过滤

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

• 预防缓存穿透

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

• 对数据库查询提效

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

3. 哈希切分

我们可以用哈希切分对海量数据处理问题

3.1 应用一

给两个⽂件，分别有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.2 应用二

给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？

本题的思路跟上题完全类似，依次读取文件A中query，i=HashFunc(query)%500，query放进Ai号小文件，然后依次⽤map对每个A小文件统计 ip 次数，同时求出现次数最多的 ip或者topk ip。本质是相同的 ip 在哈希切分过程中，⼀定进⼊的同⼀个小文件Ai，不可能出现同⼀个ip进⼊Ai和Aj 的情况，所以对Ai进行统计次数就是准确的ip次数。