1.5 unordered_map&unordered_set的封装实现
在上文中，我们完善了unordered系列容器的底层：哈希桶的代码，现在哈希桶的底层就能够通过传出的参数类型不行而同时支持map和set的实现了。
现在简易实现unordered系列容器就非常简单了，直接调用接口即可
//unordered_map #pragma once #include "BucketHash.hpp" namespace zht { template<class K, class V, class Hash> class unordered_map { struct MapKeyOfT//在unoredred_map的层面我们知道传入的V的类型是一个pair，所以这里对于仿函数的实现就和清晰了，直接拿到kv的first即可。 { const K operator()(const std::pair<const K,V>& kv) { return kv.first; } }; public: //迭代器类直接使用哈希桶的迭代器类 typedef typename zht::BucketHash::HashTable<K, std::pair<const K, V>, MapKeyOfT>::iterator iterator; //迭代器直接调用哈希桶的迭代器封装即可 iterator begin() { return _ht.begin(); } iterator end() { return _ht.end(); } //insert直接调用哈希桶的insert std::pair<iterator, bool> insert(const std::pair<K, V>& data) { return _ht.Insert(data); } //这里对于[]的重载可以去看博主的红黑树封装map和set，原理是相同的，链接在附在下面了 V& operator[](const K& key) { std::pair<iterator,bool> ret = _ht.Insert(make_pair(key, V())); return ret.first->second; } private: BucketHash::HashTable<K, std::pair<const K, V>, MapKeyOfT, Hash> _ht;//底层容器直接使用哈希桶 }; }
红黑树封装map和set
//unordered_set #pragma once #include "BucketHash.hpp" namespace zht { template<class K, class Hash> class unordered_set { struct SetKeyOfT//这里KV结构中的V的类型就是Key本身，所以直接返回key即可 { const K operator()(const K& key) { return key; } }; public: //迭代器类直接使用哈希桶的迭代器类 typedef typename zht::BucketHash::HashTable<K, K, SetKeyOfT>::iteraotr iterator; //迭代器直接调用哈希桶的迭代器封装即可 iterator begin() { return _ht.begin(); } iterator end() { return _ht.end(); } //insert直接调用哈希桶的insert std::pair<iterator,bool> insert(const K& key) { return _ht.Insert(key); } private: BucketHash::HashTable<K, K, SetKeyOfT, Hash> _ht; }; }
到这里我们的简化模拟实现基本就结束了。
但是，如果我们去查看源码就会发现，对于const迭代器的实现，stl源码里面的实现方式并不是和之前的实现的容器的const迭代器一样，复用普通迭代器的代码
❓那么为什么不能够复用普通迭代器的代码嘞？
✅这是因为如果使用const版本，那么_tables使用[]返回的就是const版本，那么Node*就相当于是const Node*,就会导致权限放大，无法构造;如果改成const HT* _ht; const Node* _node;，又会导致[]不能修改的问题:
2. 哈希的应用
2.1 位图
2.1.1 位图的概念
接下来，我们通过一个面试题来里了解位图的概念
已知40亿个不重复的无符号整数，没有排过序。现在给你一个无符号整数，如何快速判断这个数是否在已知的40亿个数中
根据我们的所学知识，我们很轻松的能够想到如下的方法
- 遍历这40亿个数，时间复杂度为O(N)
- 排序（O(NlogN)）,然后进行二分查找（O(logN)）
但是，这个数据量是非常大的，大家想一下，40亿个不重复的无符号整数如果需要被存储起来，需要多大的空间？
一个整型需要4个字节，40亿个整型，为了方便计算，我们假设它是整型能够存放的最大值，也就是42亿9千万左右，即232，所以需要的大小为234 Byte = 224 KB = 214 MB = 24 GB = 16 GB。
所以上述的两种方法用来解决这个问题都是比较麻烦的，效率很低。在上文中，我们学习了哈希的思想，所以可以考虑使用哈希的方式来解决这个问题。
首先想到的就是直接映射，但是还是同样的问题，如果直接开辟一个整型数组的话，由于这些数据是不重复的，而且范围在无符号整数，所以需要开辟的数组的大小为16G左右，我们不可能把这个数组放进内存中。所以需要想办法优化它。注意审题，我们可以发现，这个数据只有在和不在两种状态，那么就可以考虑使用一个比特位来表示一个数据的状态，也就是说每个数据映射到一个比特位，那么这个数组的大小也就缩小了很多倍，经过计算可以得到数组大小为512MB。这种方式就是位图。
位图：就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的
2.2.2 位图的代码实现
在STL库中也实现了一个位图的容器
可以看到，这里有很多接口，实际上我们需要掌握的常用的接口只有一下几个
| 接口 | 说明 |
| void set (size_t x) | 标记x所处位置的位（值设为1） |
| void reset(size_t x) | 去除x所处位置的标记（值设为0） |
| bool test(size_t x) | 判断x是否存在(拿到x所处的位的值) |
那么现在我们模拟实现一下bitset，根据STL所提供的接口，所以这里我们尝试实现上述接口即可：
1. 结构设计
首先按照我们的设计思路，这里使用一个vector用来作为底层容器存放数据，在创建bitset类型的变量的时候，需要指定存放数据范围大小，所以这里使用一个非模板类型参数
template<size_t N> class bitset { public: //... private: vector<char> _bit; };
2. 接口设计
bitset() { //由于底层存储使用的是vector<char>，所以一个char中可以存放8个数据，因为N需要左移3位，又因为N不一定是8的倍数，所以需要再开一个char的大小用于存储余数部分 _bit.resize((N >> 3) + 1, 0); } void set(size_t x)//将表示的位的值置为1 { //i表示在第几个char中，j表示在这个char中的偏移量 int i = x / 8; int j = x % 8; _bit[i] |= (1 << j); } void reset(size_t x) // 将表示的位的值置为1 { //i表示在第几个char中，j表示在这个char中的偏移量 int i = x / 8; int j = x % 8; _bit[i] &= ~(1 << j); } bool test(size_t x) { int i = x / 8; int j = x % 8; return _bit[i] & (1 << j); }
2.2 布隆过滤器
虽然位图能够做到快速判断某个数是否在一个集合中，但是仍然存在一些缺点：
- 位图更适合数据范围较集中的情况：当数据范围比较分散的时候，位图需要开辟的空间会大很多，但是真正使用到的比较少，会造成空间浪费
- 位图只能针对整型家族：对于非整型类型的数据（例如字符串）不能处理。
为了解决这个问题，我们可以考虑使用哈希的思想：将字符串通过哈希转换成整型，再进行映射。但是使用哈希方法必然会遇到哈希冲突的问题，这里由于我们想要使用位图的思想，必然不能进行开散列，所以一定会出现误判的情况。
此时，布隆过滤器就诞生了。
2.2.1 布隆过滤器的概念
布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”，它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。
2.2.2 布隆过滤器代码实现
布隆过滤器的插入原理是通过多个哈希函数将同一个元素进行多次插入，这样就能显著的降低误判的概率。
但是这种方式只能降低误判的概率，不能完全避免误判，唯一能够确认的就是有0的地方对应的一定是没有出现过的。
1. 类结构构造
布隆过滤器的插入元素可能是字符串，也可能是其他类型，只要提供对应的哈希函数将该类型的数据转换成整型就可以了。
一般情况下布隆过滤器都是用来处理字符串的，所以布隆过滤器可以实现为一个模板类，将模板参数 T 的缺省类型设置为 string：
template <size_t N, size_t X = 5, class K = string, class HashFunc1, class HashFunc2, class HashFunc3>//模板参数中HashFunc的个数就是映射时哈希函数的个数 class BloomFilter { public: //... private: bitset<N* X> _bs; };
2. 插入
由于布隆过滤器底层使用的是bitset，因此插入可以复用
void set(const K& key) { //分别计算出对应的位置，然后进行将该位置的值置为1即可 size_t hash1 = HashFunc1()(key) % (N * X); size_t hash2 = HashFunc2()(key) % (N * X); size_t hash3 = HashFunc3()(key) % (N * X); _bs.set(hash1); _bs.set(hash2); _bs.set(hash3); }
3. 布隆过滤器的查找
通过三个哈希函数分别算出对应元素的三个哈希地址，得到对应的比特位，然后去判断这三个比特位是否都被设置成了1
如果出现一个比特位未被设置成1说明该元素一定不存在，也就是如果一个比特位为0就是false；而如果三个比特位全部都被设置，则return true表示该元素已经存在（注：可能会出现误判）
bool test(const K& key) { size_t hash1 = HashFunc1()(key) % (N * X); if (!_bs.test(hash1)) return false; size_t hash2 = HashFunc1()(key) % (N * X); if (!_bs.test(hash2)) return false; size_t hash1 = HashFunc3()(key) % (N * X); if (!_bs.test(hash3)) return false; return true; }
4. 布隆过滤器的删除
布隆过滤器一般没有删除，因为布隆过滤器判断一个元素是会存在误判，此时无法保证要删除的元素在布隆过滤器中，如果此时将位图中对应的比特位清0，就会影响到其他元素了
为了实现删除这个目的，我们可以考虑给每个比特位加上一个计数器，当存在插入操作时，计数器++，有数据删除时，计数器--即可。
但是布隆过滤器的本来目的就是为了提高效率和节省空间，在每个比特位增加额外的计数器，空间消耗那就更多了，所以我们不考虑此方向
2.2.3 布隆过滤器的评价
优点
- 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无
关- 哈希函数相互之间没有关系，方便硬件并行运算
- 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
- 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势
- 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能
- 使用同一组散列函数的布隆过滤器可以进行交、并、差运算
缺点
- 有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再建立一个白名单，存储可能会误判的数据)
- 不能获取元素本身
- 一般情况下不能从布隆过滤器中删除元素
- 如果采用计数方式删除，可能会存在计数回绕问题
布隆过滤器参考博客：详解布隆过滤器的原理，使用场景和注意事项 - 知乎 (zhihu.com)
