C++进阶(五) 哈希

1. unordered系列关联式容器

1.1 unordered_map

1.2 unordered_map的接口说明

2. 底层结构

2.1 哈希概念

2.2 哈希冲突

2.3 哈希函数

2.4 哈希冲突解决

2.4.1 闭散列

2.4.2 开散列

3. 模拟实现

3.1 unordered_set

3.2 unordered_map

4.哈希的应用

4.1 位图

4.1.1 位图概念

4.1.2 位图的实现

4.1.3 位图的应用

4.2 布隆过滤器

4.2.1 布隆过滤器提出

4.2.2 布隆过滤器概念

4.2.3 布隆过滤器的插入

4.2.4 布隆过滤器的查找

4.2.5 布隆过滤器删除

4.2.6 布隆过滤器优点

4.2.7 布隆过滤器缺陷

5.海量数据处理面试题

1. unordered系列关联式容器

在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到log_2 N，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个 unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同，因为接口类似本文中只对unordered_map进行介绍，unordered_set,unordered_multimap和unordered_multiset可查看文档介绍。

1.1 unordered_map

unordered_map在线文档说明

1. unordered_map是存储<key,value>键值对的关联式容器，其允许通过keys快速的索引到与其对应的value。

2. 在unordered_map中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。

3. 在内部,unordered_map没有对<key,value>按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。

4. unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低。

5. unordered_maps实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问 value。

6. 它的迭代器至少是前向迭代器。

1.2 unordered_map的接口说明

1. unordered_map的构造

函数声明	功能介绍
unordered_map	构造不同格式的unordered_map对象

2. unordered_map的容量

函数声明	功能介绍
bool empty() const	检测unordered_map是否为空
size_t size() const	获取unordered_map的有效元素个数

3. unordered_map的迭代器

函数声明	功能介绍
begin	返回unordered_map第一个元素的迭代器
end	返回unordered_map最后一个元素下一个位置的迭代器
cbegin	返回unordered_map第一个元素的const迭代器
cend	返回unordered_map最后一个元素下一个位置的const迭代器

4. unordered_map的元素访问

函数声明	功能介绍
operator[]	返回与key对应的value，没有一个默认值

注意：该函数中实际调用哈希桶(在哈希表中用来存储元素的桶或槽)的插入操作，用参数key与V()构造一个默认值往底层哈希桶中插入，如果key不在哈希桶中，插入成功，返回V()，插入失败，说明key已经在哈希桶中，将key对应的value返回。

5. unordered_map的查询

函数声明	功能介绍
iterator find(const K& key)	返回key在哈希桶中的位置
size_t count(const K& key)	返回哈希桶中关键码为key的键值对的个数

注意：unordered_map中key是不能重复的，因此count函数的返回值最大为1

6. unordered_map的修改操作

函数声明	功能介绍
insert	向容器中插入键值对
erase	删除容器中的键值对
void clear()	清空容器中有效元素个数
void swap(unordered_map&)	交换两个容器中的元素

7. unordered_map的桶操作

函数声明	功能介绍
size_t bucket_count()const	返回哈希桶中桶的总个数
size_t bucket_size(size_t n)const	返回n号桶中有效元素的总个数
size_t bucket(const K& key)	返回元素key所在的桶号

下面代码简单展示set 、 unordered_set 、map、unordered_map 的对比

#include<iostream>
#include<unordered_map>
#include<unordered_set>
#include<set>
#include<map>
using namespace std;void test_set1()
{set<int> s;s.insert(3);s.insert(1);s.insert(5);s.insert(7);for (auto e : s){cout << e << " ";}cout << endl;unordered_set<int> us;us.insert(3);us.insert(1);us.insert(5);us.insert(7);for (auto e : us){cout << e << " ";}cout << endl;
}void test_map1()
{unordered_map<string, string> dict;dict.insert(make_pair("sort", "排序"));dict.insert(make_pair("string", "字符串"));dict.insert(make_pair("left", "左边"));dict.insert(make_pair("right", "右边"));// 遍历映射中的键值对for (auto& kv : dict){//kv.first += 'x';kv.second += 'y';cout << kv.first << ":" << kv.second << endl;}/*加载因子是一个衡量哈希表负载程度的指标，它表示当前存储元素数量与桶的数量之比。默认情况下哈希表的桶数量是根据元素数量进行自动调整的，且初始桶数量通常为质数。最大加载因子是在哈希表自动扩容之前允许的最大加载因子值。默认情况下，最大加载因子为1.0，表示当元素数量达到当前桶数量时，哈希表将进行扩容。*/cout << dict.load_factor() << endl;cout << dict.max_load_factor() << endl;}
int main()
{test_set1();cout << "---------------" << endl;test_map1();return 0;}

2. 底层结构

unordered系列的关联式容器之所以效率比较高，是因为其底层使用了哈希结构。

2.1 哈希概念

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即 O(log_2 N)，搜索的效率取决于搜索过程中元素的比较次数。

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。 如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

当向该结构中：

插入元素
根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放
搜索元素
对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)

例如：数据集合{1，7，6，4，5，9}；

哈希函数设置为：hash(key) = key % capacity;

capacity为存储元素底层空间总的大小。

用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快

问题：按照上述哈希方式，向集合中插入元素44，会出现什么问题？

hash(44) = 44 % 10 = 4,根据哈希函数的结果，元素 44 将要插入的第 4 个桶已经有一个元素 4。这意味着发生了哈希冲突，因为两个不同的键（44 和 4）映射到了同一个哈希桶中。

2.2 哈希冲突

哈希冲突/哈希碰撞指的是两个或更多不同的键被哈希函数映射到了同一个哈希表的索引位置上。

2.3 哈希函数

引起哈希冲突的一个原因可能是：哈希函数设计不够合理。

哈希函数设计原则：

哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
哈希函数计算出来的地址能均匀分布在整个空间中
哈希函数应该比较简单

常见哈希函数

直接定址法--(常用)
取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
优点：简单、均匀
缺点：需要事先知道关键字的分布情况
使用场景：适合查找比较小且连续的情况
除留余数法--(常用)
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p (p<=m),将关键码转换成哈希地址
平方取中法--(了解)
假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址；再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况
折叠法--(了解)
折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况
随机数法--(了解)
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中 random为随机数函数。通常应用于关键字长度不等时采用此法
数学分析法--(了解)
设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。例如：

数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀的情况

注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突

2.4 哈希冲突解决

解决哈希冲突两种常见的方法是：闭散列和开散列

2.4.1 闭散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置呢？

1. 线性探测

比如2.1中的场景，现在需要插入元素44，先通过哈希函数计算哈希地址，hashAddr为4，因此44理论上应该插在该位置，但是该位置已经放了值为4的元素，即发生哈希冲突。线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

插入

通过哈希函数获取待插入元素在哈希表中的位置
如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素

删除

采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。

思考：哈希表什么情况下进行扩容? 如何扩容?
散列表的载荷因子定义为：α=填入表中的元素个数 / 散列表的长度
α是散列表装满程度的标志因子。由于表长是定值，α与“填入表中的元素个数”成正比，所以，α越大，表明填入表中的元素越多，产生冲突的可能性就越大；反之， α越小，标明填入表中的元素越少，产生冲突的可能性就越小。实际上，散列表的平均查找长度是载荷因子α的函数，只是不同处理冲突的方法有不同的函数。
对于开放定址法，荷载因子是特别重要因素，应严格限制在0.7-0.8以下。超过0.8，查表时的CPU缓存不命中(cachemissing) 按照指数曲线上升。因此，一些采用开放定址法的hash库，如Java的系统库限制了荷载因子为0.75，超过此值将resize散列表。

线性探测的实现

 namespace open_address
{// 定义哈希表中每个槽位的状态enum State{EMPTY,  // 空槽EXIST,  // 存在键值对DELETE  // 被标记为删除的槽};// 哈希表中存储的数据结构template<class K, class V>struct HashData{pair<K, V> _kv; // 键值对State _state = EMPTY; // 标记};// 哈希函数模板template<class K>struct HashFunc{// 默认哈希函数，将键转换为 size_t 类型的哈希值size_t operator()(const K& key){return (size_t)key;}};// 对 string 类型的键进行特化的哈希函数template<>struct HashFunc<string>{size_t operator()(const string& s){size_t hash = 0;for (auto e : s){hash += e;	// 将字符的 ASCII 值累加到哈希值中hash *= 131; // 使用质数 131 进行乘法混合}return hash;}};template<class K, class V, class Hash = HashFunc<K>>class HashTable{public:// 构造函数，初始化哈希表大小HashTable(size_t size = 10){_tables.resize(size);}// 根据键值查找对应的数据项HashData<K, V>* Find(const K& key){Hash hs;// 计算哈希值并取模得到哈希桶索引size_t hashi = hs(key) % _tables.size();// 线性探测，直到找到空槽或者找到对应的键值对while (_tables[hashi]._state != EMPTY){if (key == _tables[hashi]._kv.first&& _tables[hashi]._state == EXIST){return &_tables[hashi];}++hashi; // 线性探测下一个位置hashi %= _tables.size(); // 确保索引在合法范围内}return nullptr;}// 插入新的键值对bool Insert(const pair<K, V>& kv){if (Find(kv.first))return false;// 检查是否需要扩容if (_n * 10 / _tables.size() >= 7){HashTable<K, V, Hash> newHT(_tables.size() * 2);// 遍历旧表，插入到新表for (auto& e : _tables){if (e._state == EXIST){newHT.Insert(e._kv);}}_tables.swap(newHT._tables);}Hash hs;// 计算哈希值并取模得到哈希桶索引size_t hashi = hs(kv.first) % _tables.size();// 线性探测，直到找到空槽while (_tables[hashi]._state == EXIST){++hashi;hashi %= _tables.size();}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;	// 更新实际存储的数据个数return true;}//根据键删除对应的键值对bool Erase(const K& key){HashData<K, V>* ret = Find(key);if (ret){_n--;	// 更新实际存储的数据个数ret->_state = DELETE;return true;}else{return false;}}private:vector<HashData<K, V>> _tables; // 存储哈希表的向量size_t _n = 0;  // 实际存储的数据个数};void TestHT1(){int a[] = { 1,4,24,34,7,44,17,37 };HashTable<int, int> ht;for (auto e : a){ht.Insert(make_pair(e, e));}for (auto e : a){auto ret = ht.Find(e);if (ret){cout << ret->_kv.first << ":找到了" << endl;}else{cout << ret->_kv.first << ":未找到" << endl;}}cout << endl;ht.Erase(34);ht.Erase(4);for (auto e : a){auto ret = ht.Find(e);if (ret){cout << ret->_kv.first << ":找到了" << endl;}else{cout << e << ":未找到" << endl;}}cout << endl;}}

线性探测优点：实现非常简单，线性探测缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。如何缓解呢？

可以采取以下几种方法：

增加哈希表的容量：增加哈希表的容量可以减少哈希冲突的概率。当哈希表的负载因子（已存储元素个数与哈希表容量的比值）超过某个阈值时，可以考虑扩大哈希表的容量，并重新哈希已有的元素，使得元素分布更加均匀。
使用更好的哈希函数：选择一个更好的哈希函数可以减少哈希冲突的发生。好的哈希函数能够将元素均匀地分布在哈希表中，减少冲突的概率。
引入更高级的冲突解决策略：除了线性探测，还有其他的冲突解决策略，如二次探测、双重哈希、链地址法等。这些方法可以更有效地处理哈希冲突，减少数据堆积的问题。
动态调整哈希表的容量：如果哈希表的负载因子过高，可以考虑动态调整哈希表的容量，使其保持在一个合适的范围内，以减少冲突的发生。

综合运用上述方法，可以有效地缓解线性探测带来的数据堆积问题，提高哈希表的性能和效率。

2. 二次探测

线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测的主要思想是通过一个二次方程来计算下一个探测位置，以此来避免线性探测中的数据堆积问题。在二次探测中，寻找下一个空位置的方法可以描述如下：

假设发生哈希冲突，即在哈希表中已经有了一个元素占据了哈希函数计算出的位置。此时，我们想要寻找下一个空槽位来插入新元素。

设当前冲突位置为 h(k)，其中 k是要插入的关键字，h(k)是哈希函数计算出的位置。

计算下一个探测位置的增量：i^2，其中 ii 是探测的次数，从 1 开始逐步增加。
计算下一个探测位置：h′(k)=(h(k)+i^2) mod m ，其中 m 是哈希表的大小。
如果 h′(k)对应的位置已经被占据（发生了冲突），则继续增加 i，重复步骤 2 直到找到一个空位置或者遍历整个哈希表。

这样，通过使用二次方程 i^2作为探测位置的增量，我们可以在哈希表中以二次的步长来查找下一个空槽位，从而更加均匀地分散冲突元素，减少数据堆积的可能性。

对于2.1中如果要插入44，产生冲突，使用解决后的情况为：

从原始冲突位置开始，使用二次增量进行探测：

第一次尝试：h′(44)=(4+12)%10=5，第 5 个位置已经被元素 5 占据了。
第二次尝试：h′(44)=(4+22)%10=8，第 8 个位置为空，插入成功。

当表的长度为质数且表装载因子a（表中已占用位置与总位置的比率）不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。因此：闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。

2.4.2 开散列

1. 开散列概念

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。

对于开散列增容问题，桶的个数是一定的，随着元素的不断插入，每个桶中元素的个数不断增多，极端情况下，可能会导致一个桶中链表节点非常多，会影响的哈希表的性能，因此在一定条件下需要对哈希表进行增容，那该条件怎么确认呢？开散列最好的情况是：每个哈希桶中刚好挂一个节点，再继续插入元素时，每一次都会发生哈希冲突，因此，在元素个数刚好等于桶的个数时，可以给哈希表增容。

2. 开散列实现

namespace hash_bucket
{// 哈希桶节点结构体template<class T>struct HashNode{HashNode<T>* _next;	// 指向下一个节点的指针T _data;	// 节点存储的数据// 构造函数，初始化节点HashNode(const T& data):_next(nullptr), _data(data){}};// 前置声明/*K: 键的类型，即哈希表中每个元素的键的类型。T: 值的类型，即哈希表中每个元素的值的类型。KeyOfT: 一个函数对象，用于从值中提取键。通常情况下，KeyOfT 的作用是返回值类型的键。Hash: 哈希函数对象，用于计算键的哈希值。它必须定义一个函数调用运算符，以便对键进行哈希计算。
*/template<class K, class T, class KeyOfT, class Hash>class HashTable;// 哈希表迭代器结构体template<class K, class T, class KeyOfT, class Hash>struct __HTIterator{typedef HashNode<T> Node;	//哈希表中的节点typedef HashTable<K, T, KeyOfT, Hash> HT;	//哈希表typedef __HTIterator<K, T, KeyOfT, Hash> Self;	//迭代器自身Node* _node; // 当前节点指针HT* _ht;	// 哈希表指针// 构造函数，初始化迭代器__HTIterator(Node* node, HT* ht):_node(node), _ht(ht){}// 重载解引用操作符*T& operator*(){return _node->_data;}// 重载前置递增操作符++Self& operator++(){if (_node->_next){// 当前桶还有下一个节点_node = _node->_next;}else{// 当前桶走完了，找下一个桶KeyOfT kot;Hash hs;size_t hashi = hs(kot(_node->_data)) % _ht->_tables.size();// 找下一个桶hashi++;while (hashi < _ht->_tables.size()){if (_ht->_tables[hashi]){_node = _ht->_tables[hashi];break;}hashi++;}// 后面没有桶了if (hashi == _ht->_tables.size()){_node = nullptr;}}return *this;}// 重载不等于操作符!=bool operator!=(const Self& s){return _node != s._node;}};// 哈希表类模板template<class K, class T, class KeyOfT, class Hash>class HashTable{// 声明迭代器为友元template<class K, class T, class KeyOfT, class Hash>friend struct __HTIterator;typedef HashNode<T> Node;	public:typedef __HTIterator<K, T, KeyOfT, Hash> iterator; // 返回哈希表的起始迭代器iterator begin(){for (size_t i = 0; i < _tables.size(); i++){// 找到第一个桶的第一个节点if (_tables[i]){return iterator(_tables[i], this);}}return end();}// 返回哈希表的结束迭代器iterator end(){return iterator(nullptr, this);}// 构造函数，初始化哈希表HashTable(){_tables.resize(10, nullptr);_n = 0;}// 析构函数，释放内存~HashTable(){for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_tables[i] = nullptr;}}// 插入bool Insert(const T& data){KeyOfT kot;	// 键提取函数对象// 检查键是否已存在，如果存在则不插入if (Find(kot(data)))return false;Hash hs;	 // 哈希函数对象// 负载因子到1就扩容if (_n == _tables.size()){// 创建新的指针数组vector<Node*> newTables(_tables.size() * 2, nullptr);for (size_t i = 0; i < _tables.size(); i++){// 取出旧表中节点，重新计算挂到新表桶中Node* cur = _tables[i];while (cur){Node* next = cur->_next;// 头插到新表size_t hashi = hs(kot(cur->_data)) % newTables.size();cur->_next = newTables[hashi];newTables[hashi] = cur;cur = next;}_tables[i] = nullptr;}// 使用新表替换旧表_tables.swap(newTables);}// 计算哈希值size_t hashi = hs(kot(data)) % _tables.size();Node* newnode = new Node(data);// 头插newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;	// 更新元素数量return true;}// 查找Node* Find(const K& key){KeyOfT kot;Hash hs;size_t hashi = hs(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == key){return cur;}cur = cur->_next;}return nullptr;}// 删除bool Erase(const K& key){KeyOfT kot;	Hash hs;size_t hashi = hs(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == key){if (prev){prev->_next = cur->_next;}
// 如果前一个节点不存在，则说明当前节点是链表头节点，更新哈希桶中的指针else{_tables[hashi] = cur->_next;}delete cur;--_n;return true;}prev = cur;cur = cur->_next;}return false;}private:vector<Node*> _tables; // 哈希桶指针数组size_t _n;	 // 哈希表中元素的数量};
}

开散列与闭散列比较

应用链地址法处理溢出，需要增设链接指针，似乎增加了存储开销。事实上：由于开地址法必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子a <= 0.7，而表项所占空间又比指针大的多，所以使用链地址法反而比开地址法节省存储空间。

3. 模拟实现

3.1 unordered_set

MyOrderedSet.h

#pragma once
#include"HashTable.h"namespace my
{// 自定义无序集合类模板template<class K, class Hash = HashFunc<K>>class unordered_set{// 键提取函数结构体，用于从元素中提取键struct SetKeyOfT{const K& operator()(const K& key){// 返回元素本身作为键return key;}};public:// 哈希表迭代器typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::iterator iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}bool insert(const K& key){return _ht.Insert(key);}private:// 哈希表对象，用于存储元素hash_bucket::HashTable<K, const K, SetKeyOfT, Hash> _ht;};void test_set1(){unordered_set<int> us;us.insert(3);us.insert(1);us.insert(5);us.insert(15);us.insert(45);us.insert(7);unordered_set<int>::iterator it = us.begin();while (it != us.end()){//*it += 100;cout << *it << " ";++it;}cout << endl;for (auto e : us){cout << e << " ";}cout << endl;}}

3.2 unordered_map

MyOrderedMap.h

#pragma once
#include"HashTable.h"namespace my
{// 自定义无序映射类模板template<class K, class V, class Hash = HashFunc<K>>class unordered_map{// 键提取函数结构体，用于从键值对中提取键struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){// 返回键值对中的键return kv.first;}};public:// 哈希表迭代器typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::iterator iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}bool insert(const pair<K, V>& kv){return _ht.Insert(kv);}private:// 哈希表对象，用于存储键值对hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;};void test_map1(){unordered_map<string, string> dict;dict.insert(make_pair("sort", "排序"));dict.insert(make_pair("left", "左边"));dict.insert(make_pair("right", "右边"));// 遍历映射中的键值对for (auto& kv : dict){//kv.first += 'x';kv.second += 'y';cout << kv.first << ":" << kv.second << endl;}}
}

4.哈希的应用

4.1 位图

4.1.1 位图概念

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

面试题

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

1. 遍历，时间复杂度O(N)

2. 排序(O(NlogN))，利用二分查找: logN

3. 位图解决数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0 代表不存在。比如：

4.1.2 位图的实现

#define _CRT_SECURE_NO_WARNINGS	
#include <vector>
#include <iostream>
using namespace std;
class bitset
{
public:// 构造函数，初始化位图大小/*bitCount 是指定的位图大小，表示位图中比特位的总个数。
(bitCount >> 5) 是将 bitCount 向右移动 5 位，
相当于除以 32，因为每个 int 类型可以存储 32 位。
这个操作确定了需要多少个 int 类型的元素来存储 bitCount 个比特位。加 1 因为右移操作 (bitCount >> 5) 会向下取整，导致即使 bitCount 恰好是 32 的倍数，结果也会是一个整数。因此，为了确保容器足够大来存储所有的比特位，需要在计算容器大小时额外加 1。所有这些 int 类型的元素初始化为 0，表示初始状态下所有比特位都是 0。*/bitset(size_t bitCount): _bit((bitCount >> 5) + 1, 0), _bitCount(bitCount){}// 将x比特位 置1void set(size_t x){// 检查x是否超出位图的范围if (x > _bitCount)return;// 计算x位置在位图数组中的索引size_t index = (x >> 5);// 计算x位置在位图数组元素中的具体偏移位置size_t pos = x % 32;//将数字 1 左移 pos 位/* 按位或| 只要一个操作数的对应位是 1 时，结果都是 1*/_bit[index] |= (1 << pos);}// 将x比特位 置0void reset(size_t x){if (x > _bitCount)return;size_t index = (x >> 5);size_t pos = x % 32;//~按位取反/* 按位与& 只有当两个操作数的对应位都是 1 时，结果才是 1，否则结果为 0。*/_bit[index] &= ~(1 << pos);}// 检测位图中x是否为1bool test(size_t x){if (x > _bitCount)return false;size_t index = (x >> 5);size_t pos = x % 32;/*：如果只返回 _bit[index]，实际上返回的是位图数组中第 index 个元素的值，而不是检查特定位是否为1。如果只返回 (1 << pos)，这只是一个表示特定位是否为1的数值，但不会对位图数组进行实际的检查。*/return _bit[index] & (1 << pos);}// 获取位图中比特位的总个数size_t size() const { return _bitCount; }// 位图中比特为1的个数size_t Count() const{// 预先计算的查找表，用于统计每个8位数值(0~255)中比特为1的个数int bitCntTable[256] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2,3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3,3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3,4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4,3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5,6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4,4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5,6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5,3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3,4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6,6, 7, 6, 7, 7, 8 };// 初始化比特为1的计数器size_t count = 0;// 获取位图数组的大小size_t size = _bit.size();for (size_t i = 0; i < size; ++i){// 获取当前元素int value = _bit[i];// 初始化字节偏移量int j = 0;// 循环处理当前元素中的每个字节while (j < sizeof(_bit[0])){// 将当前值转换为无符号字符型，以便处理每个字节中的比特unsigned char c = value;// 根据查找表统计当前字节中比特为1的个数，并累加到计数器中count += bitCntTable[c];// 更新字节偏移量++j;// 右移8位，以处理下一个字节value >>= 8;}}return count;}private:std::vector<int> _bit;  // 存储位图数据的数组size_t _bitCount;   // 位图中比特位的总个数
};int main()
{// 创建一个包含10个比特位的位图bitset bit(10);// 设置某些比特位为1bit.set(1);bit.set(3);bit.set(5);bit.set(7);bit.set(9);// 检测某些比特位状态cout << "Bit 1 is set: " << bit.test(1) << endl;cout << "Bit 2 is set: "  << bit.test(2) << endl;cout << "Bit 5 is set: " << bit.test(5) << endl;// 重置某些比特位为0bit.reset(3);bit.reset(7);// 再次检测某些比特位状态cout << "Bit 3 is set: "  << bit.test(3) << endl;cout << "Bit 7 is set: "  << bit.test(7) << endl;// 输出位图中比特位为1的个数cout << "Number of set bits: " << bit.Count() << endl;return 0;
}

4.1.3 位图的应用

快速查找某个数据是否在一个集合中
排序 + 去重
求两个集合的交集、并集等
操作系统中磁盘块标记

4.2 布隆过滤器

4.2.1 布隆过滤器提出

我们在使用新闻客户端看新闻时，它会给我们不停地推荐新的内容，它每次推荐时要去重，去掉那些已经看过的内容。问题来了，新闻客户端推荐系统如何实现推送去重的？用服务器记录了用户看过的所有历史记录，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录。如何快速查找呢？

用哈希表存储用户记录，缺点：浪费空间
用位图存储用户记录，缺点：位图一般只能处理整形，如果内容编号是字符串，就无法处理了。
将哈希与位图结合，即布隆过滤器

4.2.2 布隆过滤器概念

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

4.2.3 布隆过滤器的插入

向布隆过滤器中插入："baidu"

BloomFilter.h

#pragma once
#include<iostream>
#include<bitset>
#include<string>
#include<vector>
using namespace std;
struct HashFuncBKDR
{// BKDR哈希函数size_t operator()(const string& s){size_t hash = 0;for (auto ch : s){hash *= 131;hash += ch;}return hash;}
};struct HashFuncAP
{// AP哈希函数size_t operator()(const 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
{// DJB哈希函数size_t operator()(const string& s){size_t hash = 5381;for (auto ch : s){hash = hash * 33 ^ ch;}return hash;}
};// 布隆过滤器类模板
template<size_t N,class K = 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;// 将三个哈希值对应的位设为1_bs->set(hash1);_bs->set(hash2);_bs->set(hash3);}// 检查哈希值对应的位是否为1bool Test(const K& key){size_t hash1 = Hash1()(key) % M;if (_bs->test(hash1) == false)return false;size_t hash2 = Hash2()(key) % M;if (_bs->test(hash2) == false)return false;size_t hash3 = Hash3()(key) % M;if (_bs->test(hash3) == false)return false;return true; // 存在误判(有可能3个位都是跟别人冲突的，所以误判)}private://位图大小static const size_t M = 10 * N;// 使用位图存储数据std::bitset<M>* _bs = new std::bitset<M>;
};void TestBloomFilter1()
{string strs[] = { "百度","字节","腾讯" };BloomFilter<10> bf;for (auto& s : strs){bf.Set(s);}for (auto& s : strs){cout << bf.Test(s) << endl;}for (auto& s : strs){cout << bf.Test(s + 'a') << endl;}cout << bf.Test("摆渡") << endl;cout << bf.Test("百渡") << endl;
}void TestBloomFilter2()
{srand(time(0));// 设置随机数种子为当前时间const size_t N = 10000;BloomFilter<N> bf;// 创建相似字符串集合 v1std::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是相似字符串集（前缀一样），但是后缀不一样std::vector<std::string> v2;for (size_t i = 0; i < N; ++i){std::string urlstr = url;urlstr += std::to_string(9999 + i);v2.push_back(urlstr);}// 统计相似字符串集合 v2 中的误判数量size_t n2 = 0;for (auto& str : v2){// 如果布隆过滤器判断为存在，说明发生了误判if (bf.Test(str)) {++n2;}}cout << "相似字符串误判率:" << (double)n2 / (double)N << endl;// 不相似字符串集  前缀后缀都不一样std::vector<std::string> v3;for (size_t i = 0; i < N; ++i){string url = "孙悟空";url += std::to_string(i + rand());v3.push_back(url);}size_t n3 = 0;for (auto& str : v3){if (bf.Test(str)){++n3;}}cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;
}

4.2.4 布隆过滤器的查找

布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中，因此被映射到的位置的比特位一定为1。所以可以按照以下方式进行查找：分别计算每个哈希值对应的比特位置存储的是否为零，只要有一个为零，代表该元素一定不在哈希表中，否则可能在哈希表中。

注意：布隆过滤器如果说某个元素不存在时，该元素一定不存在，如果该元素存在时，该元素可能存在，因为有些哈希函数存在一定的误判。

比如：在布隆过滤器中查找"alibaba"时，假设3个哈希函数计算的哈希值为：1、3、7，刚好和其他元素的比特位重叠，此时布隆过滤器告诉该元素存在，但实该元素是不存在的。

4.2.5 布隆过滤器删除

布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素。 比如：删除上图中"tencent"元素，如果直接将该元素所对应的二进制比特位置0，“baidu”元素也被删除了，因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。

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

4.2.6 布隆过滤器优点

增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关
哈希函数相互之间没有关系，方便硬件并行运算
布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势
数据量很大时，布隆过滤器可以表示全集，其他数据结构不能
使用同一组散列函数的布隆过滤器可以进行交、并、差运算

4.2.7 布隆过滤器缺陷

有误判率，即存在假阳性(False Position)，即布隆过滤器误判某个元素存在于集合中，但实际上该元素并不在集合中。(补救方法：再建立一个白名单，存储可能会误判的数据)
不能获取元素本身(隆过滤器是一种概率型数据结构，其设计目的是快速判断一个元素是否可能存在于一个集合中，而不是存储元素本身。)
一般情况下不能从布隆过滤器中删除元素(这是因为删除元素需要将对应的位数组位置重置为0，但如果直接重置某个位置，可能会影响其他元素的判断结果，导致误判率增加。因此，一般情况下不建议直接从布隆过滤器中删除元素。)
如果采用计数方式删除，可能会存在计数回绕问题(计数型布隆过滤器存在一个潜在的问题，即当某个元素被删除的次数超过了计数器的最大值，计数器会发生回绕，导致计数器重新从零开始计数。这种情况下，虽然元素实际上可能已经被删除了多次，但是计数器仍然显示为零，从而使得布隆过滤器无法准确地反映元素的删除状态。计数回绕问题可能会导致误判，因为即使一个元素已经被删除多次，但是由于计数器的回绕，布隆过滤器仍然可能会认为该元素存在于集合中，从而产生误报。)

5.海量数据处理面试题

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

哈希切割：
将大文件切割成多个小文件，每个小文件的大小适中，比如1GB到2GB左右。切割的方式可以使用哈希函数，将不同的IP地址映射到不同的小文件中，确保相同的IP地址总是出现在同一个小文件中。
在每个小文件中找到出现次数最多的IP地址：
对于每个小文件，使用哈希表来统计每个IP地址出现的次数，并记录出现次数最多的IP地址。
合并结果：
在所有的小文件中找到出现次数最多的IP地址，并记录其出现次数。

给定100亿个整数，设计算法找到只出现一次的整数？
解决方法一：
1.将100亿个整数切分成100份，每份大约500MB
2.将每一份加载到内存中放在一个哈希表中，通过哈希表找出只出现一次的数
3.将100份中所有只出现一次的数合并在一起
解决方法二：
借助位图解决。在前边的位图实现中，只有两个状态0(不存在)、1（存在）。要解决找出只出现一次的数字，我们可以增加状态，用两个比特位作为哈希映射的地址，我们可以让00(不存在)、01(只出现一次)、11(出现两次)、10(出现两次以上)。

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

解决方法一：

1.将其中的一个文件切分成100份
2.将每一份加载到内存中
3.用第二个文件中的数据到每一份中去查找
时间复杂度O(100n*n),既O(n^2)
解决方法二：
哈希切割。
1.两个文件用相同的哈希函数映射到各自的编号文件中
2.如果两个数相同，他们一定会在编号相同的两个文件
3.对编号相同的两个文件求交集(可以放在内存中)
时间复杂度O(n)
解决方法三：位图
1.将一个文件中的整数映射到位图中。
2.用第二个文件中的数到位图中查找
3.存在，则是交集，不存在，不是交集里的数
时间复杂度O(n)

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

解决方法：借助位图解决。

要解决找出只出现次数不超过2次的数字，我们可以增加位图状态，用两个比特位作为哈希映射的地址，我们可以让00(不存在)、01(只出现一次)、11(出现两次)、10(出现两次以上)。

    建两个文件，设置一个值key,大于这个key的数进入第一个文件；小于key值的数进入第二个文件（设置的key尽量使得这两个文件中数的数目差不多）
    将第一个文件中的所有数的状态存到一个位图中（第一个文件以位图存储大约需要9540多MB的内存），然后通过查找，找出文件一中出现次数不超过两次的所有整数
    第二个文件和第一个文件方法一样
    合并两个文件中所有找到的数

给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法

精确算法：哈希切分

哈希切分：
   将每个文件中的query按照一定的哈希函数分配到不同的桶中，确保相同的query被分配到相同的桶中。
        由于内存有限，无法将所有的query都加载到内存中，因此需要使用一种哈希函数，使得每个桶中的query数量尽量均匀，同时保证哈希后的桶数不超过内存限制。
内存中处理：
一次性将一个文件中的一个桶加载到内存中。
   对于另一个文件，逐个读取query，并使用相同的哈希函数确定它所属的桶，然后在内存中的相应桶中查找是否存在相同的query。
如果存在相同的query，则将其添加到结果集中。
处理重复项：
为了避免重复项，可以使用一个集合（例如哈希集合）来存储结果，确保每个query只被添加一次。

近似算法：布隆过滤器

构建布隆过滤器：
        对其中一个文件的query进行哈希处理，并将哈希后的结果存储在布隆过滤器中。布隆过滤器可以是一个位数组，数组的大小根据预期的查询数量和误判率进行确定。
        对于每个query，使用多个哈希函数对其进行哈希，然后将得到的哈希值对布隆过滤器的相应位置进行置位。
检查另一个文件中的query：
   对另一个文件中的每个query，同样使用相同的多个哈希函数进行哈希处理。
检查对应的布隆过滤器位置是否都被置位，如果有任何一个位置未被置位，则可以确定该query不在第一个文件中；如果所有位置都被置位，则该query可能存在于第一个文件中。
误判处理：
对于可能存在于第一个文件中的query，再进行一次精确的查找以确认是否真正存在。这两种算法都可以在有限的内存条件下有效地找到两个文件的交集。精确算法提供确切的结果，但需要更多的内存和计算资源；而布隆过滤器作为近似算法可以在牺牲一定准确性的情况下节省资源。

如何扩展BloomFilter使得它支持删除元素的操作

解决方法：因为一个布隆过滤器的key对应多个位，冲突的概率比较大，所以不支持删除，因为删除有可能影响到其他元素。如果要对其元素进行删除，就不得不对每一个位进行引用计数。将BloomFilter中的每一位扩展为一个计数器，记录有多少个hash函数映射到这一位；删除的时候，只有当引用计数变为0时，才真正将该位置为0否则减1即可。

如何扩展BloomFilter使得它支持引用计数操作？

解决方法：将BloomFilter中的每一位扩展为一个计数器，每个输入元素都要把对应位置加1，从而支持计数操作。但是有一个问题，1个比特位只能是两个状态0和1，我们只能把位图扩大成1字节或者更多，1个字节仅仅能存放计数256，但代价依旧是浪费内存。