-
【C++】哈希的应用：位图（bitset）和布隆过滤器（bloomfilter）
一、位图
1.1 前言（bitset 的提出）
哈希是一种映射的思想。
先来看一道面试题：
给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何 快速判断 一个数是否在这40亿个数中。
首先想到的解法可能有这几种：
解法1：遍历40亿个数，O(N)
解法2：先排序，快排 O(Nlog2N)，再利用二分查找 O(log2N)
解法3：40亿个数放进 set / unordered_set 中，然后查找 key 在不在。
思考：上面的解法看似可行，实际上有很大的问题：内存消耗太大。同时面试官也不会很满意。
40亿个整数要占用多少空间？大约16GB
- 1GB = 1024 * 1024 * 1024 = 210 * 210 * 210 = 230 （大约是10亿 byte）
- 4GB = 4 * 230 = 232 byte（大约是42亿9九千多万 byte）
- 40亿个 unsigned int 整数 = 40亿 x 4字节 = 160亿字节 = 16 x 10亿字节 ≈ 16GB
这40亿个数据是放在文件中的，要对这40亿个整数进行排序：
-
难道在内存中开一个16GB空间的数组存放这些数据吗？显然不太现实，内存消耗太大，玩不起。
-
虽然归并排序可以对文件中的数据做外排序，但是效率很低，磁盘读写速度是很慢的，即使在文件中对40亿个数据排完了序，但是很难去算数据的下标位置，不能进行二分查找，那意义也不大了。
解法三，把数据放进 set / unordered_set 中，因为其底层是链式结构，除了存数据，还要存指针，所以附带的内存消耗更大，需要的空间比 16GB 还要大很多，更不可行。
所以我们一定要从 节省内存的角度 出发去思考，才能更好的解决问题。同时题目要求是：快速判断。
这里是判断一个数在不在数据集中，仔细想一想，也并不需要把这个数存起来，只需要有个标记去 标记某个数在不在 就行了。（就好比统计数组中数字的出现次数，我们用数的数值作为下标，在该下标处存储出现的次数，也并没有把数存下来）
标记一个数在不在，最小的标记单位是比特位（0 / 1），我们用一个比特位标记一个数，这样就节省空间了。
解法4：位图
某个数是否在给定的数据集中，有两种结果：「存在」或「不存在」，刚好是两种状态，那么可以使用一个二进制比特位来代表某个数是否存在的信息，比如二进制比特位为 1 代表存在，为 0 代表不存在。
我们把数据集的所有数用「直接定址法」映射到一张二进制表中，并用二进制值（1 / 0）标记其是否存在，这样每个数都有「唯一的」映射位置，不会出现哈希冲突。如果要判断某个数在不在数据集中时，只需要找到这个数映射到表中的位置，然后查看该位置的比特位为 1 还是 0
我们是用每个「无符号整数 unsigned int 的值」来映射其哈希位置（比如 25，就映射到第 25 个二进制位）：
- 因为 unsigned int 的 取值范围 是 0 ~ 232 - 1，所以一个无符号整数最小值为 0，最大值为 232 - 1（4,294,967,295，42亿9千多万）。
- 所以我们要开有 232 个二进制位的表，才能映射完所有的无符号整数，但实际上只能开到有 232 - 1 个二进制位的表（因为 size_t 最大为
0xffffffff），也就是开 ( 232 - 1 ) / 8 个字节 ≈ 5亿多个字节 ≈ 0.5GB = 512MB 的内存空间。
一个 bit 位标记一个 unsigned int 值，512GB 的内存就可以标记完42亿9千多万个整数的存在状态了，极大的节省了内存。
注意：位图并没有把整个数据集存储起来，而是将所有数映射到哈希表中，在映射的哈希位置上标记这个数在不在。
1.2 位图的概念
面对判断一个数在不在海量数据中的问题，红黑树和哈希表查找效率是挺高的，但是我们光把海量数据存起来够呛，同时红黑树和哈希表附带的内存消耗，所需空间更大，基于这样的原因，提出了位图这种数据结构。
template <size_t N> class bitset; // 位图存储位（只有两个可能值的元素：0 或 1，真或假，...）- 1
- 2
位图（bitset）是一种常用的数据结构，常用在给一个很大范围的数，判断其中的一个数是不是在其中。在索引、数据压缩方面有很大的应用。
位图是用数组实现的，数组的每一个元素的每一个二进制位都表示一个数据，0 表示该数据不存在，1 表示该数据存在。
位图最大的特点就是：快、节省空间，因为它不需要存储数据集，只是标记某个数在不在这个数据集中。
1.3 位图的模拟实现
1.3.1 位图的底层结构
如图，我们开一个数组，数组的每个元素是一个 char（8个 bit 位），当然，是一个 int （32个 bit 位）也可以，只是计算数据映射的比特位的方法略有差别。
这个 0 ~ 7 是比特位的编号，比特位的规则就是这样子的，从右到左编号。
思考：如何计算这个数据映射在数组中第几个 char(字节) 中的第几个比特位上：
- 字节位置 = 数据 / 8，得出 x 映射在第几个 char 中
- 位位置 = 数据 % 8，得出 x 映射在这个 char 中的第几个比特位上
- 注意：如果数组的每个元素是一个 int，改成除以 32 就好了
比如数据 x = 10，则：
- 字节位置 = 10 / 8 = 1，说明 10 映射在第 1 个 char(字节) 中
- 位位置 = 10 % 8 = 2，说明 10 映射在第 1 个 char(字节) 中的第 2 个比特位上
位图的结构：
namespace winter { /* 位图 * N: 非类型模板参数，表示至少需要开N个比特位的存储空间 */ template<size_t N> class bitset { public: /* * 构造有N个比特位的位图，等价于要开N/8个字节(char)的空间 * 为了防止N不是8的整数倍，所以要+1，多开1个字节(char)的空间 */ bitset() { _bits.resize(N / 8 + 1, 0); } // 把数据 x 映射的比特位设置成 1，表示数据 x 存在 void set(size_t x); // 把数据 x 映射的比特位设置成 0，表示数据 x 不存在 void reset(size_t x); // 检测数据 x 映射的比特位是否为 1（即数据 x 是否存在） bool test(size_t x) const; private: vector<char> _bits; // 位数组 }; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
1.3.2 位图的一些成员函数
① 位图的构造
👉 默认构造函数：
bitset() { // 构造至少有N个比特位的位图，等价于开N/8个字节(char)的空间 // 为了防止N不是8的整数倍，所以要+1，多开1个字节(char)的空间 _bits.resize(N / 8 + 1, 0); }- 1
- 2
- 3
- 4
- 5
- 6
② 位图的插入：set
👉 set 函数：
修改数据映射的比特位位置。位位置从最右边的位开始计数，即从 0 位置开始计数。
// 把数据 x 映射的比特位设置成 1，表示数据 x 存在 void set(size_t x) { // 计算出这个数据映射在数组中第几个 char(字节) 中的第几个比特位上 size_t i = x / 8; // 计算出 x 映射在第 i 个 char(字节) 中 size_t j = x % 8; // 计算出 x 映射在第 i 个 char(字节) 中的第 j 个比特位上 // 把数组中第i个char的第j位设置成1，其它位不受影响 _bits[i] |= (1 << j); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
分析：
// 比如: 数据5映射在第0个char的第5个比特位 // 现在要用set函数把数据5映射的第0个char的第5个比特位设置成1 0000 1111 -> _bits[0] // 第0个char 0010 0000 -> 1 << 5 // 将1左移5位 // 将1左移5位后的结果按位或上 _bits[0] 0010 0000 -> 1 << 5 | 0000 1111 -> _bits[0] ----------------------- 0010 1111 -> _bits[0] // 此时第0个char的第5个比特位已经被设置成1了- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
③ 位图的删除：reset
👉 reset 函数：
修改数据映射的比特位位置。位位置从最右边的位开始计数，即从 0 位置开始计数。
// 把数据 x 映射的比特位设置成 0，表示数据 x 不存在 void reset(size_t x) { size_t i = x / 8; // 映射在第i个char中 size_t j = x % 8; // 映射在第i个char中的第j个比特位上 // 把数组中第i个char的第j位设置成0，其它位不受影响 _bits[i] &= (~(1 << j)); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
这里需要注意：
-
_bits[i] ^= (1 << j);不能用异或，如果第 j 个比特位本身就是 0，异或之后就变成 1 了。// 比如: 数据5映射在第0个char的第5个比特位 // 现在要用reset函数把数据5映射的第0个char的第5个比特位设置成0 0010 1111 -> _bits[0] // 第0个char 0010 0000 -> 1 << 5 // 将1左移5位 // 将1左移5位后的结果按位取反，然后按位与上 _bits[0] 1101 1111 -> ~(1 << 5) & 0010 1111 -> _bits[0] ----------------------- 0000 1111 -> _bits[0] // 此时第0个char的第5个比特位已经被设置成0了- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
④ 位图的查找：test
👉 test 函数：检测数据 x 映射的比特位是否为 1，即数据 x 是否存在
// 检测数据 x 映射的比特位是否为 1（即数据 x 是否存在） // 是1返回true，是0返回false bool test(size_t x) const { size_t i = x / 8; // 映射在第i个char中 size_t j = x % 8; // 映射在第i个char中的第j个比特位上 return _bits[i] & (1 << j); // 0000 1111 -> _bits[0] // & 0010 0000 -> 1 << 5 // ---------------------- // 0000 0000 -> 说明第0个char的第5个比特位是0，数据 x 不存在 }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
测试：
void test_bitset1() { bitset<100> bs; // 开至少有100个比特位的位数组 bs.set(4); cout << bs.test(4) << endl; // 输出1 bs.reset(4); cout << bs.test(4) << endl; // 输出0 }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
1.3.3 思考 & 提问
如何开出有42亿9千多万个比特位的位图呢？来映射42亿9千多万个无符号整型数，标记其存在状态。
void test_bitset() { // (size_t)4,294,967,295U bitset<-1> bs1; // 方式一 bitset<0xffffffff> bs2; // 方式二 }- 1
- 2
- 3
- 4
- 5
- 6
通过调试可以看到，开了 512MB 的空间（即 4,294,967,295U 个比特位）
1.4 位图的应用
- 快速查找某个数据是否在一个集合中
- 排序
- 求两个集合的交集、并集等
- 操作系统中磁盘块标记
二、布隆过滤器
2.1 前言（BloomFilter 的提出）
我们在使用新闻客户端看新闻时，它会给我们不停地推荐新的内容，它每次推荐时要去重，去掉那些已经看过的内容。问题来了，新闻客户端推荐系统如何实现推送去重的？ 用服务器记录了用户看过的所有历史记录，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录。 如何快速查找到已经存在的记录呢？
判断一个元素是不是在一个集合里，这是一个典型的 key 模型。
- 思路1：用哈希表存储用户记录，缺点：浪费空间。
- 思路2：用位图存储用户记录，缺点：不能处理哈希冲突。
- 思路3：将哈希与位图结合，即布隆过滤器。
【场景一】
现在有 1 亿个 IP 地址（字符串），给你一个 IP，需要 快速判断 这个 IP 在不在其中，如何处理？
思路 1：哈希切分。太慢了，还有没有更快的办法呢？
思路 2：用一个 字符串哈希算法，把 IP 地址转换成可以取模的整型（size_t），然后映射到位图的某一个比特位中，进行标记，0 表示这个 IP 不存在，1 表示这个 IP 存在。
问题是：如果不同的 IP 地址映射的是同一个比特位，会发生哈希冲突，可能存在误判：
- 判断一个值是否「在」，就是判断其映射的比特位是否为 1。判断结果是不准确的，可能存在误判。
- 判断一个值是否「不在」，就是判断其映射的比特位是否为 0。判断结果一定是准确的。（因为如果这个值在，其映射的比特位一定是1）
那该怎么办呢？布隆左思右想，发现想要判断一个值是否「在」，变得一定是准确的，几乎是不可能的。
因为总会存在哈希冲突。
虽然无法解决冲突，但是可以缓解冲突。
解决思路2的改进：
一个 IP 映射位图中的一个比特位，冲突概率大，误判概率大。
那么我们对同一个 IP 使用不同的哈希算法，让其映射多个比特位，缓解冲突，降低误判的概率。
虽然还存在一定的误判，但至少节省了空间。
【场景二】
判断一个人是不是这个学校的学生：
-
思路 1：用「姓名」作为标识，来表示一个人，万一同姓名的人比较多，就会导致误判。
-
思路 2：用「姓名」、「性别」、「出生年月」作为标识，来表示一个人，同姓名的人比较多容易导致误判，而同姓名同性别同出生年月的人，可能有，但没有那么多，这样就缓解了冲突，降低误判概率。
核心思想：一个值映射多个位。
2.2 布隆过滤器的概念
布隆过滤器（Bloom Filter）是由布隆在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询，它的实现是一个「很长的二进制向量（位数组）」和「一系列哈希函数」。
可以用来快速判断 “一个元素一定不存在或者可能存在一个集合中”，它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。
-
优点：是空间效率和查询时间 O(1) 都比一般的算法要好的多。
-
缺点：是有一定的误识别率和删除困难。
核心思想：一个值映射多个位。
【拓展】
先思考：
- 哈希函数的个数需要权衡一下，映射的位越多，冲突的概率也越低，但是消耗的空间的也越大；但是映射的位少，误判率就会变高，那映射多少位是合理的呢？
- 布隆过滤器的底层就是一个位数组，一次性开 0xffffffff 个位空间也没必要，很浪费，那如何控制开多少个位是合理的呢？
如何选择哈希函数个数和布隆过滤器的长度（并非官方测试结果）：
比如：规定哈希函数个数 k = 3，布隆过滤器长度 m = ( k / ln2 ) * n ≈ 4.2 * n（大约是插入元素个数的4.2倍）
2.3 BloomFilter 的优缺点
① BloomFilter 的优点
- 增加和查询元素的时间复杂度为：O(K)，【K为哈希函数的个数，一般比较小】，与数据量大小无关
- 哈希函数相互之间没有关系，方便硬件并行运算
- 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
- 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势
- 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能
- 使用同一组散列函数的布隆过滤器可以进行交、并、差运算
② BloomFilter 的缺点
- 有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再建立一个白名单，存储可能会误判的数据)
- 不能获取元素本身
- 一般情况下不能从布隆过滤器中删除元素
- 如果采用计数方式删除，可能会存在计数回绕问题
2.4 BloomFilter 的模拟实现
位图一般标记的是 整数，或者通过哈希函数转成整数的元素。
布隆过滤器标记的基本上都是 字符串。
布隆过滤器的核心实现就是一个「很长的二进制向量（位数组）」和「一系列哈希函数」。
① 布隆过滤器的底层结构
这里实现时，默认布隆过滤器标记的元素都是 string 类型的，所以只写了针对 string 类型的哈希函数
namespace winter { // 仿函数类（把string类型转换成可以取模的size_t类型） struct HashStr1 { size_t operator()(const string& s) { // BKDR Hash Function size_t hash = 0; for (const auto& e : s) { hash *= 131; hash += e; } return hash; } }; struct HashStr2 { size_t operator()(const string& s) { // SDBM Hash Function size_t hash = 0; for (const auto& e : s) { hash = hash * 65599 + e; } return hash; } }; struct HashStr3 { size_t operator()(const string& s) { // RS Hash Function size_t hash = 0; size_t magic = 63689; for (const auto& e : s) { hash = hash * magic + e; magic *= 378551; } return hash; } }; /* 布隆过滤器 * N: 非类型模板参数，表示最多插入 N 个值 * K: 键值 key（要标记的元素的类型，一般都是字符串） * Hash1...: 仿函数类型（哈希算法，把string类型的键值key转换成可以取模的size_t数） */ template<size_t N, class K = string, class Hash1 = HashStr1, class Hash2 = HashStr2, class Hash3 = HashStr3> class BloomFilter { public: void set(const K& key); // 把键值key映射的几个比特位设置成 1 bool test(const K& key); // 检查键值key映射的几个比特位的值，判断键值key在不在 private: bitset<len> _bs; // 位图，开len个比特位的空间 size_t len = 5 * N; // 布隆过滤器的长度（等于插入元素个数N的5倍） }; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
② 布隆过滤器的插入：set
向布隆过滤器中插入：”192.0.0.1“
void set(const K& key) // 把键值key映射的几个比特位设置成 1 { // 对键值 Key 使用不同的哈希算法，得到其映射的三个比特位的位置 // 注意：计算的比特位的位置可能超过了布隆过滤器的长度，需要对长度 len 取模 size_t index1 = Hash1()(key) % len; size_t index2 = Hash2()(key) % len; size_t index3 = Hash3()(key) % len; // 把键值 key 映射的三个比特位设置成 1 _bs.set(index1); _bs.set(index2); _bs.set(index3); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
③ 布隆过滤器的查找：test
布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中，因此被映射到的位置的比特位一定为1。
所以按照以下方式进行查找：分别计算每个哈希值对应的比特位置存储的是否为0，只要有一个为0，代表该元素一定不在哈希表中，否则可能在哈希表中。
bool test(const K& key) // 检查键值key映射的几个比特位的值，判断键值key在不在 { // 对键值 Key 使用不同的哈希算法，得到其映射的三个比特位的位置 // 注意：计算的比特位的位置可能超过了布隆过滤器的长度，需要对长度 len 取模 size_t index1 = Hash1()(key) % len; if (_bs.test(index1) == false) return false; // 检测该比特位的值是否为0，若为0，说明不在，直接返回false size_t index2 = Hash2()(key) % len; if (_bs.test(index2) == false) return false; size_t index3 = Hash3()(key) % len; if (_bs.test(index3) == false) return false; return true; // 注意：当三个比特位的值都为 1 时，可能存在误判 }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
测试：
void test_bloomfilter1() { BloomFilter<100> bf; // 最多向布隆过滤器中插入100个元素 bf.set("hello"); cout << bf.test("hello") << endl; // 输出1 cout << bf.test("world") << endl; // 输出0 }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
拓展：测试布隆过滤器的误判率
相似字符串的误判率：测试发现，哈希函数个数和插入元素个数确定情况下，布隆过滤器长度越长，误判率越低
void test_bloomfilter2() { BloomFilter<100> bf; // 最多向布隆过滤器中插入100个元素 // 1、构造100个不同的字符串，存放到 v1 中 vector<string> v1; for (size_t i = 0; i < 100; i++) { string url = "https://www.bilibili.com/"; url += std::to_string(123 + i); // 构造出100个不同的字符串 v1.push_back(url); } // 把100个不同的字符串插入到布隆过滤器中 for (const auto& e : v1) bf.set(e); /*--------------------------------------------------------*/ // 2、构造100个不同的相似字符串，存放到 v2 中 vector<string> v2; for (size_t i = 0; i < 100; i++) { string url = "https://www.bilibili.com/"; // 用了相同的网址 url += std::to_string(456 + i); // 构造出100个不同的相似字符串 v2.push_back(url); } // 检测这100个不同的相似字符串是否在布隆过滤器中（按理来说应该不在） size_t count1 = 0; for (const auto& e : v2) { if (bf.test(e)) count1++; // 如果判断在，说明误判了 // 统计出有多少个字符串误判了 } cout << "相似字符串的误判率：" << (double)count1 / (double)100 << endl; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
④ 布隆过滤器的删除
一般情况下，布隆过滤器不能直接支持删除操作，因为在删除一个元素时，可能会影响其他元素。
比如：删除上图中 “hello” 元素，如果直接将该元素所对应的二进制比特位置0，“world” 元素也被删除了，因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。
一种支持删除的方法：将布隆过滤器中的每个比特位扩展成一个小的计数器，记录有多少个值映射到这个位了（比如使用两个比特位来记录，最多可以记录 3 个值），插入元素时给 k 个计数器加 1，删除元素时，给 k 个计数器减 1，通过多占用几倍存储空间的代价来增加删除操作。
缺陷：
- 无法确认元素是否真正在布隆过滤器中
- 存在计数回绕
2.5 BloomFilter 的应用场景
布隆过滤器的应用场景：在一些允许误判的地方。
场景一：假设这里有一个网站，注册的时候需要每个用户取一个昵称，要求昵称不能重复。
用户在注册的时候，输入一个昵称，系统需要判断一下这个昵称是否已被注册。
-
用户输入昵称点击提交后，先到后台数据库中去查，再返回判断这个昵称是否存在的结果。这种方式太麻烦了。
-
思考：那能不能当用户刚输入完昵称后，还没有点提交，切换到下一个输入框，这个时候就会提示用户，该昵称是否被占用。
解决思路：
我们可以使用一个布隆过滤器，标记所有使用过的昵称，就能快速判断一个昵称是否被使用过。
这里虽然会存在误判，但在这种场景下，误判的影响并不大（因为判断一个昵称没被使用过，一定是准确的。判断一个昵称被使用过，可能存在误判，但没啥影响，大不了不用这个昵称了呗）
场景二：如果要求判断在或不在的结果都要是准确的，能否使用布隆过滤器呢？
也是可以的，比如验证一个手机号是否在系统中注册过，要求验证结果是准确的。
解决思路：使用一个布隆过滤器，标记所有注册过的手机号，判断这个手机号在不在布隆过滤器中：
-
如果不在，直接返回结果：未注册。
-
如果在，因为可能存在误判，所以再去服务器的数据库中查询，然后返回查询结果：未注册 / 已注册。
虽然查询效率降低了，但比起每次判断都去访问数据库，还是要高效不少。
有些服务器就会采用这种方式，来提高效率。
场景三：比如判断垃圾邮件，垃圾邮件的地址都会被标记映射到一个黑名单（布隆过滤器）中，当有人给你发邮件时，系统会快速判断出这个是否是垃圾邮件，然后进行拦截或分类。
-
系统判断这个邮件不在黑名单中，一定不会被拦截。
-
系统判断这个邮件在黑名单中，但这个邮件实际上可能不在黑名单中，误判了，把正常邮件拦截了，但影响不大，在垃圾箱还是能够找到这封正常邮件。
三、海量数据面试题
海量数据处理，一般不能用我们常见的数据结构去处理，考验当常见数据结构都失效时该如何处理。
3.1 哈希切割
给一个超过 100G 大小的 log file（日志文件），log 中存着 IP 地址，设计算法找到出现次数最多的 IP 地址？
与上面的条件相同，如何找到 topK 的 IP？如何直接用 Linux 系统命令实现？
解决思路：
此题不能用位图来处理了，因为位图处理的是整数，而 IP 地址是字符串（比如：192.0.0.1）
这里就需要用到「哈希切分」，大文件我们处理不了，就想办法把它切分小文件处理。
假设我们有 4G 内存，我们就把这个大文件平均切分成 100 份小文件，每一份 1G，但这种 平均切分 实际上是不行的，因为同一个 IP 可能进入了多份小文件中，想要统计出每个 IP 最终出现的次数都是非常麻烦的，更别说找到出现次数最多的那个 IP 地址了。
那该怎么办呢？
使用「哈希切分」
切分操作：
-
先创建 100 个小文件，分别叫 0.txt、1.txt、2.txt、… 99.txt
-
然后读取 100G log file，依次获取每个 IP 地址，用 字符串哈希算法，把 IP 地址转换成可以取模的整型（size_t），比如使用 BKDR 算法：
- size_t num = BKDRHash(IP) % 100
- 然后这个 IP 地址就放入（映射到）第 num.txt 号小文件。依次对所有 IP 进行处理，进入（映射到）对应的小文件。
-
如果运气好一点，平均下来差不多每个小文件就是 1G 左右；如果运气不好，可能有些小文件是 512MB，有些小文件是 2 G，但至少是相对可控的。
思考：如果最小的小文件 num.txt 还是过大该怎么办呢？
我们可以限制一个大小，在处理操作之前，先检测一下当前小文件的大小，如果超过 2G，就换一个哈希算法把当前小文件再切小一些。
处理操作：
-
依次读取每个小文件，比如先读取 0.txt 中所有的 IP，用 map<string, int> 统计所有 IP 出现的次数，这里统计的 IP 出现次数，就是这个 IP 最终出现的次数。我们记录下 0.txt 中出现次数最多的 IP。
思考：这里为什么用了 map 呢？因为是小文件，内存消耗不大。
-
然后再 clear() 掉 map 中的元素，再读取 1.txt 中所有的 IP，继续统计所有 IP 出现的次数，不断走下去。
问题一：我们要找到出现次数最多的 IP 地址，在最开始记录下当前小文件中出现次数最多的 IP 地址，然后再读取后面小文件的过程中，不断更新这个 IP 地址，当最后一个小文件读取完，就找到出现次数最多的 IP 地址了。
问题二：如果要找到 topK 的 IP 地址，建立 K 个数的小堆即可。
⭐这里采用哈希切分的关键是：
- 相同的 IP 地址，一定会进入编号相同的小文件。
- 因为用字符串哈希算法，同一个 IP 地址转换出来的哈希位置一定是相同的。
可以理解为这里就是 100 个存着文件指针的哈希桶。
3.2 位图（⭐只能处理整数）
-
给定100亿个整数，设计算法找到只出现一次的整数？
前面的题目是
-
在没排过序的海量数据中快速判断一个数在不在其中，是一个典型的 key 模型。
-
所以我们只需要用位图标记 2 种状态：「存在」或「不存在」，用一个比特位 1 / 0 来标记。
而这里是：在海量数据中找到只出现一次的数，不仅要判断这个数在不在，还要知道这个数的出现次数。
错误思路：
- 显然是不能把这100亿个整数存储在 map/unordered_map（红黑树/哈希表） 中
正确思路：
-
我们需要标记 3 种状态：「不存在」或「出现一次」或「出现多次」，则要用两个比特位来标记。
-
因为两个比特位有 4 种表现形式 00 / 01 / 10 / 11
-
00：表示这个数不存在，01：表示这个数只出现一次，10：表示这个数出现多次
-
-
然后遍历位图，找到所有 01 标记的位置，此位置映射的就是只出现一次的整数。
那这里需要消耗多少空间呢？
-
这里要注意：虽然有100亿个整数，但并不是开100亿个比特位的表哦。
-
这100亿个 unsigned int 整数的取值范围都是 0 ~ 232 - 1（大约是42亿9千多万个整数），如果每个整数映射一个比特位，需要消耗 ( 232 - 1 ) / 8 个字节 ≈ 5亿多个字节 ≈ 0.5GB 的空间，则每个整数映射两个比特位，需要消耗 1GB 的空间。
具体做法：
方法一：用一个位图，用 2 个连续的比特位标识一个数。
需要修改 2 个不同位置的比特位的值，不方便。
方法二：封装两个位图，用两个位图的同一个位置的 2 个比特位来标识一个数。
所以修改两个位图的同一个位置的比特位的值就好了，还可以复用之前写的位图代码。
代码如下：
/* 封装了两个位图，找只出现一次的整数 * N: 非类型模板参数，表示至少要开N个比特位的存储空间 */ template<size_t N> class FindOnceValSet { public: void set(size_t x) // 把数据 x 映射的比特位设置成 01，表示数据 x 出现一次 { bool flag1 = _bs1.test(x); // 检测数据 x 在第1个位图中映射的比特位是否为 1 bool flag2 = _bs2.test(x); // 检测数据 x 在第2个位图中映射的比特位是否为 1 // 两个比特位分别为 00，说明数据 x 之前不存在 if (flag1 == false && flag2 == false) { // 00 -> 01，标识成出现一次 _bs2.set(x); } // 两个比特位分别为 01，说明数据 x 之前已经出现一次 else if (flag1 == false && flag2 == true) { // 01 -> 10，标识成出现多次 _bs1.set(x); // 1 _bs2.reset(x); // 0 } // 两个比特位分别为 10，说明数据 x 之前已经出现多次了，不用处理 // 10 -> 10 } void print_once_num() // 输出所有只出现一次的数据 { // 遍历位图中的 N 个比特位 for (size_t i = 0; i < N; i++) { // 检测两个位图的同一个位置的比特位是否分别为 0、1 if (_bs1.test(i) == false && _bs2.test(i) == true) { cout << i << endl; // 输出此位置映射的数据 i } } } private: bitset<N> _bs1; // 位图1 bitset<N> _bs2; // 位图2 };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
测试：
void testFindOnceValSet() { int a[] = { 1,20,23,23,20,5,20,7,3,7 }; // 测试数据 FindOnceValSet<100> bs; // 开至少有100个比特位的位数组 for (const auto& e : a) { bs.set(e); // 把数组a的每个元素的出现次数映射到位图bs中 } bs.print_once_num(); // 输出所有只出现一次的数据 }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
运行结果：1 3 5
-
-
给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
分析问题：找到两个文件的交集，只需要判断这个数是否分别在两个文件中，是一个典型的 key 模型。
解决思路：定义两个位图。
-
位图 1 标识第一个文件中所有数的存在状态（1 存在、0 不存在）
-
位图 2 标识第二个文件中所有数的存在状态（1 存在、0 不存在）
-
遍历位图中的 N 个比特位，检测两个位图的同一个位置的比特位的值是否都为 1，如果都为 1，说明此位置映射的这个数就是交集
需要消耗的内存：
- 因为 unsigned int 整数的取值范围是 0 ~ 232 - 1（大约是42亿9千多万个整数），每个整数映射一个比特位，需要消耗 ( 232 - 1 ) / 8 个字节 ≈ 5亿多个字节 ≈ 0.5GB 的空间，这里开了两个位图，需要消耗 1GB 的空间。
-
-
位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数？
和问题一类似。
解决思路：封装两个位图，用两个位图的同一个位置的 2 个比特位来标识一个数。
-
我们需要标记 4 种状态：「不存在」或「出现一次」或「出现两次」或「出现多次」
因为两个比特位有 4 种表现形式 00 / 01 / 10 / 11，所以：
- 00 - 表示这个数不存在
- 01 - 表示这个数只出现 1 次
- 10 - 表示这个数出现 2 次
- 11 - 表示这个数出现 2 次及以上
-
然后遍历位图，找到所有不是 11 标记的位置，此位置映射的就是出现次数不超过2次的整数。
-
-
这里的位图问题也可以用哈希切分的思路来解决。但我们还是优先选择位图，更优一些。
3.3 布隆过滤器
-
给两个文件，分别存有100亿个 query（查询），我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法。
近似算法：把第一个文件中的100亿个查询插入布隆过滤器，再读取第二个文件，看当前查询在不在布隆过滤器中。如果不在，说明一定不是交集；如果在，说明可能是交集（因为存在误判）
精确算法：「哈希切分」
假设一个 query 平均 20 字节，则 100 亿个 query 大约是 2000 亿字节，则文件大约是 200 G
第一步：
先创建 200 个小文件，分别叫 A0.txt、A1.txt、A2.txt、… A199.txt
先创建 200 个小文件，分别叫 B0.txt、B1.txt、B2.txt、… B199.txt
第二步：
依次读取 A 文件中的 query，使用字符串哈希算法转成可以取模的整型：
- size_t i = Hash( query ) % 200，把这个 query 放入到（映射到）第 Ai.txt 号小文件中
依次读取 B 文件中的 query，使用字符串哈希算法转成可以取模的整型：
- size_t i = Hash( query ) % 200，把这个 query 放入到（映射到）第 Bi.txt 号小文件中
注意：平均下来，每个小文件是 1G 左右（可能有些文件大，有些文件小）
第二步结束后，文件中相同的 query 会分别进入编号相同的小文件，只需要去编号相同的小文件中找交集即可。
第三步：
第四步：
i = [0, 199]，把 Ai.txt 读进 setA 中，Bi.txt 读进 setB 中，setA 和 setB 相同的 query 就是交集。
核心思想：
原文件太大，存在磁盘中，直接读取去找交集效率太低，先切分成一个一个的小文件，然后再去读取小文件找交集。
-
如何扩展 BloomFilter 使得它支持删除元素的操作。
一般情况下，布隆过滤器不支持删除 reset 接口，因为多个值可能会映射到同一个位，有哈希冲突，把该位置 0 可能会影响到其它值的状态。
如果想要支持删除 reset 接口呢？
可以弄一个计数器记录有多少个值映射到这个位了（比如使用两个比特位来记录，最多可以记录 3 个值），但是会付出更多空间消耗的代价。
3.3 其它
哈希在加密中的应用
哈希在存储中的应用：
-
当我们存储量超级大的时候，比如日常生活中使用的QQ，我们要把每个用户的用户数据、QQ空间中相册等数据存储起来，这是非常庞大的数据量，需要用服务器存储起来，一台服务器存不下，就弄多台服务器，每个服务器上存一部分，这就是分布式，然后对服务器进行集群管理（通过监控程序监控所有服务器的状态）
-
有个问题：假设我有个好友发了一个朋友圈，数据提交到某台服务器上，我刷新朋友圈，会显示他发的朋友圈，但是怎么知道朋友圈数据是存在哪一台服务器上的呢？
-
每个用户都会有一个唯一 ID（比如手机号，身份证）标识该用户，一个用户的数据要存在哪台服务器上，就可以使用哈希映射，比如：Hash( ID ) % 服务器台数。所以这种分布式存储是一定要用哈希的。
-
但实际上远远比这复杂的多，比如万一某台服务器坏了呢？所以数据一般不会只存在一台服务器上，而是建立多副本，如果一台服务器坏了，就会重新建立映射，在其它服务器上建立新的副本。副本越多，越稳定，但空间消耗越大。还有比如新增或者减少了一些新服务器，那原先用户数据映射的位置也会发生改变，该如何解决呢？这就需要用到一致性哈希了。
-
相关阅读:
vue全局使用sass变量
四种自动化测试模型实例及优缺点
Go 的三种指针
XSS详解
C++保姆级入门教程（10）—— 一维数组练习
如何实现虹科物联网HMI/网关的调度器功能？
Preliminaries
Python-VBA编程500例-033(入门级)
【MySQL】查询优化
数据结构与算法--算法
- 原文地址：https://blog.csdn.net/weixin_48025315/article/details/125571445
