泛黄的春联还残留在墙上..........................................................................................................

前言

哈希思想，作为计算机科学中的一项基石技术，以其卓越的性能优化能力，成为了连接数据海洋与精准查询的桥梁。对于搜索问题和排序问题，哈希思想都发挥着重大的作用，本篇博客将带你对哈希思想有一个清晰的认识。

一、【哈希结构的介绍】

1.1【哈希结构的概念】

顺序结构以及平衡树中，元素关键码（关键码_百度百科 (baidu.com)）与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较（比如顺序表中的下标，红黑树中的Key，链表中的节点值）。搜索的效率取决于搜索过程中元素的比较次数，因此顺序结构中查找的时间复杂度为O(N) ，平衡树中查找的时间复杂度为树的高度O(log N) 。而最理想的搜索方法是，可以不经过任何比较，一次直接从表中得到要搜索的元素，即查找的时间复杂度为O (1) 。

如果构造一种存储结构，该结构能够通过某种函数使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时就能通过该函数很快找到该元素，而这种结构就是我们今天要讲的哈希结构。

那么哈希结构是如何实现插入数据和搜索数据的呢？

• 插入元素： 根据待插入元素的关键码，用此函数计算出该元素的存储位置，并将元素存放到此位置。
• 搜索元素： 对元素的关键码进行同样的计算，把求得的函数值当作元素的存储位置，在结构中按此位置取元素进行比较，若关键码相等，则搜索成功。

例如，对于集合{1, 7, 6, 4, 5, 9}我们采用哈希结构来对进行存储。
可以将哈希函数设置为：hash( key) = key % size ，其中size为哈希结构中存储元素底层空间的总大小。
若我们将该集合存储在size为10的哈希表中，则各元素存储位置对应如下：

用该方法进行存储，在搜索时就只需通过哈希函数判断对应位置是否存放的是待查找元素，而不必进行多次关键码的比较，因此搜索的速度比较快。

1.2【哈希冲突】

不同关键字通过相同哈希函数计算出相同的哈希地址，这种现象称为哈希冲突或哈希碰撞。我们把关键码不同而具有相同哈希地址的数据元素称为“同义词”。

我们从上面可以知道，我们采用的哈希函数：hash( key) = key % size 其中会出现计算结果相同的情况，比如当key分别为2和12，size为10时，经过函数计算得到结果都为2，即它们都会存储到相同的位置。这种现象就叫做哈希冲突。

例如，在上述例子中，再将元素11插入当前的哈希表就会产生哈希冲突。 因为元素11通过该哈希函数得到的哈希地址与元素1相同，都是下标为1的位置
hash(1) = 1 % 10 = 1 ，hash(11)= 11 % 10= 1。

那为什么会造成哈希冲突呢？

大多数情况下，引起哈希冲突的一个原因可能是哈希函数设计不够合理，应该像如下设计。

1.3【哈希函数的设计】

哈希函数设计的原则：

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

下面是常见的几种函数设计方法：

一、直接定址法（常用）
取关键字的某个线性函数为哈希地址： Hash(Key)=A*Key+BHash(Key)=A∗Key+B。

优点：每个值都有一个唯一位置，效率很高，每个都是一次就能找到。
缺点：使用场景比较局限，通常要求数据是整数，范围比较集中。
使用场景：适用于整数，且数据范围比较集中的情况。

二、除留余数法（常用）
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：H a s h ( K e y ) = K e y % p ( p < = m ) ，将关键码转换成哈希地址。

优点：使用场景广泛，不受限制。
缺点：存在哈希冲突，需要解决哈希冲突，哈希冲突越多，效率下降越厉害。

三、平方取中法
假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址。

使用场景：不知道关键字的分布，而位数又不是很大的情况。

四、折叠法
折叠法是将关键字从左到右分割成位数相等的几部分（最后一部分位数可以短些），然后将这几部分叠加求和，并按哈希表表长，取后几位作为哈希地址。

使用场景：折叠法适合事先不需要知道关键字的分布，或关键字位数比较多的情况。

五、随机数法
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H a s h ( K e y ) = r a n d o m ( K e y ) Hash(Key)=random(Key)Hash(Key)=random(Key)，其中random为随机数函数。

使用场景：通常应用于关键字长度不等时。

六、数字分析法
设有n个d位数，每一位可能有r种不同的符号，这r中不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，而在某些位上分布不均匀，只有几种符号经常出现。此时，我们可根据哈希表的大小，选择其中各种符号分布均匀的若干位作为哈希地址。

假设要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前7位都是相同的，那么我们可以选择后面的四位作为哈希地址。如果这样的抽取方式还容易出现冲突，还可以对抽取出来的数字进行反转（如1234改成4321）、右环位移（如1234改成4123）、左环位移（如1234改成2341）、前两数与后两数叠加（如1234改成12+34=46）等操作。

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

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

1.4【应对哈希冲突的办法】

应对哈希冲突有两种常见的方法：闭散列和开散列。

一、【闭散列 —— 开放定址法】

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

寻找“下一个位置”的方式多种多样，常见的方式有以下两种：

1、线性探测

当发生哈希冲突时，从发生冲突的位置开始，依次向后探测，直到找到下一个空位置为止。

Hi=(H0+i)%m ( i = 1 , 2 , 3 , . . . ) 

H0：通过哈希函数对元素的关键码进行计算得到的位置。
Hi：冲突元素通过线性探测后得到的存放位置。
m：表的大小。

例如，我们用除留余数法将序列{1, 6, 10, 1000, 101, 18, 7, 40}插入到表长为10的哈希表中，当发生哈希冲突时我们采用闭散列的线性探测找到下一个空位置进行插入，插入过程如下：

通过上图可以看到，随着哈希表中数据的增多，产生哈希冲突的可能性也随着增加，最后在40进行插入的时候更是连续出现了四次哈希冲突。

我们将数据插入到有限的空间，那么空间中的元素越多，插入元素时产生冲突的概率也就越大，冲突多次后插入哈希表的元素，在查找时的效率必然也会降低。

介于此，哈希表当中引入了负载因子（载荷因子）：

负载因子 = 表中有效数据个数 / 空间的大小

• 负载因子越大，产出冲突的概率越高，增删查改的效率越低。
• 负载因子越小，产出冲突的概率越低，增删查改的效率越高。

例如，我们将哈希表的大小改为20，可以看到在插入相同序列时，产生的哈希冲突会有所减少：

但负载因子越小，也就意味着空间的利用率越低，此时大量的空间实际上都被浪费了。对于闭散列（开放定址法）来说，负载因子是特别重要的因素，一般控制在0.7~0.8以下，超过0.8会导致在查表时CPU缓存不命中（cache missing）按照指数曲线上升。
因此，一些采用开放定址法的hash库，如JAVA的系统库限制了负载因子为0.75，当超过该值时，会对哈希表进行增容。

【线性探测优缺点】

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

2、二次探测

线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为：

Hi=(H0+i ^2)%m，( i = 1 , 2 , 3 , . . . )

H0：通过哈希函数对元素的关键码进行计算得到的位置。
Hi：冲突元素通过二次探测后得到的存放位置。
m ：表的大小。

例如，我们用除留余数法将序列{1, 6, 10, 1000, 101, 18, 7, 40}插入到表长为10的哈希表中，当发生哈希冲突时我们采用闭散列的二次探测找到下一个空位置进行插入，插入过程如下：

采用二次探测为产生哈希冲突的数据寻找下一个位置，相比线性探测而言，采用二次探测的哈希表中元素的分布会相对稀疏一些，不容易导致数据堆积。

和线性探测一样，采用二次探测也需要关注哈希表的负载因子，例如，采用二次探测将上述数据插入到表长为20的哈希表，产生冲突的次数也会有所减少：

因此，闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。

二、【开散列 —— 链地址法（拉链法、哈希桶）】

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

例如，我们用除留余数法将序列{1, 6, 15, 60, 88, 7, 40, 5, 10}插入到表长为10的哈希表中，当发生哈希冲突时我们采用开散列的形式，将哈希地址相同的元素都链接到同一个哈希桶下，插入过程如下：

闭散列解决哈希冲突，采用的是一种报复的方式，“我的位置被占用了我就去占用其他位置”。而开散列解决哈希冲突，采用的是一种乐观的方式，“虽然我的位置被占用了，但是没关系，我可以‘挂’在这个位置下面”。

与闭散列不同的是，这种将相同哈希地址的元素通过单链表链接起来，然后将链表的头结点存储在哈希表中的方式，不会影响与自己哈希地址不同的元素的增删查改的效率，因此开散列的负载因子相比闭散列而言，可以稍微大一点。

• 闭散列的开放定址法，负载因子不能超过1，一般建议控制在[0.0, 0.7]之间。
• 开散列的哈希桶，负载因子可以超过1，一般建议控制在[0.0, 1.0]之间。

在实际中，开散列的哈希桶结构比闭散列更实用，主要原因有两点：

1. 哈希桶的负载因子可以更大，空间利用率高。
2. 哈希桶在极端情况下还有可用的解决方案。

哈希桶的极端情况就是，所有元素全部产生冲突，最终都放到了同一个哈希桶中，此时该哈希表增删查改的效率就退化成了O ( N ) ：

这时，我们可以考虑将这个桶中的元素，由单链表结构改为红黑树结构，并将红黑树的根结点存储在哈希表中。

在这种情况下，就算有十亿个元素全部冲突到一个哈希桶中，我们也只需要在这个哈希桶中查找30次左右，这就是所谓的“桶里种树”。

为了避免出现这种极端情况，当桶当中的元素个数超过一定长度，有些地方就会选择将该桶中的单链表结构换成红黑树结构，比如在JAVA中比较新一点的版本中，当桶当中的数据个数超过8时，就会将该桶当中的单链表结构换成红黑树结构，而当该桶当中的数据个数减少到8或8以下时，又会将该桶当中的红黑树结构换回单链表结构。

但有些地方也会选择不做此处理，因为随着哈希表中数据的增多，该哈希表的负载因子也会逐渐增大，最终会触发哈希表的增容条件，此时该哈希表当中的数据会全部重新插入到另一个空间更大的哈希表，此时同一个桶当中冲突的数据个数也会减少，因此不做处理问题也不大。

二、【哈希结构的两种实现】

2.1、【string类型无法取模的问题】

在实现之前我们有一个问题需要解决，就是我们是用取模的方式来实现映射关系，那么整形可以直接进行取模，如果是其他类型呢？比如string.....等其他类型，我们怎么进行取模呢？

字符串并不是整型，也就意味着字符串不能直接用于计算哈希地址，我们需要通过某种方法将字符串转换成整型后，才能代入哈希函数计算哈希地址。

但遗憾的是，我们无法找到一种能实现字符串和整型之间一对一转换的方法，因为在计算机中，整型的大小是有限的，比如用无符号整型能存储的最大数字是4294967295，而众多字符能构成的字符串的种类却是无限的。

鉴于此，无论我们用什么方法将字符串转换成整型，都会存在哈希冲突，只是产生冲突的概率不同而已。

经过前辈们实验后发现，BKDRHash算法无论是在实际效果还是编码实现中，效果都是最突出的。该算法由于在Brian Kernighan与Dennis Ritchie的《The C Programing Language》一书被展示而得名，是一种简单快捷的hash算法，也是Java目前采用的字符串的hash算法

因此，现在我们需要在哈希表的模板参数中再增加一个仿函数，用于将键值key转换成对应的整型。

template<class K, class T, class KeyOfT, class HashFunc = Hash<K>>
class HashTable

若是上层没有传入该仿函数，我们则使用默认的仿函数，该默认仿函数直接返回键值key即可，但是用字符串作为键值key是比较常见的，因此我们可以针对string类型写一个类模板的特化，此时当键值key为string类型时，该仿函数就会根据BKDRHash算法返回一个对应的整型。

template<class K>
struct Hash
{size_t operator()(const K& key) //返回键值key{return key;}
};
//string类型的特化
template<>
struct Hash<string>
{size_t operator()(const string& s) //BKDRHash算法{size_t value = 0;for (auto ch : s){value = value * 131 + ch;}return value;}
};

注意：对于其他类型，我们只需要像string一样实现相应的类模板特化即可，从而解决相应类型的取模问题。

2.2、【闭散列——哈希表的实现】

1、【状态标识】

在闭散列的哈希表中，哈希表每个位置除了存储所给数据之外，还应该存储该位置当前的状态，哈希表中每个位置的可能状态如下：

1. EMPTY（无数据的空位置）。
2. EXIST（已存储数据）。
3. DELETE（原本有数据，但现在被删除了）。

我们可以用枚举定义这三个状态。

enum Status
{EMPTY,EXIST,DELETE
};

那我们为什么需要标识哈希表中每个位置的状态呢？

若是不设置哈希表中每个位置的状态，那么在哈希表中查找数据的时候可能是这样的。以除留余数法的线性探测为例，我们若是要判断下面这个哈希表是否存在元素40，假设容器的总大小为10，则步骤如下：

1. 通过除留余数法求得元素40在该哈希表中的哈希地址是0。
2. 从0下标开始向后进行查找，若找到了40则说明存在。

但是我们在寻找元素40时，不是说从0下标开始将整个哈希表全部遍历一次，这样就失去了哈希的意义。由于哈希碰撞的存在，下标为0的位置不可能只有一个40，我们只需要从0下标开始往后查找，直到找到元素40判定为存在，或是找到一个空位置判定为不存在即可。

因为线性探测在为冲突元素寻找下一个位置时是依次往后寻找的，既然我们已经找到了一个空位置，那就说明这个空位置的后面不会再有从下标0位置开始冲突的元素了。比如我们要判断该哈希表中是否存在元素90，步骤如下：

1. 通过除留余数法求得元素90在该哈希表中的哈希地址是0。
2. 从0下标开始向后进行查找，直到找到下标为5的空位置，停止查找，判定元素90不存在。

但这种方式是不可行的，原因如下：

1. 如何标识一个空位置？用数字0吗？那如果我们要存储的元素就是0怎么办？因此我们必须要单独给每个位置设置一个状态字段。
2. 如果只给哈希表中的每个位置设置存在和不存在两种状态，那么当遇到下面这种情况时就会出现错误。

我们先将上述哈希表当中的元素1000找到，并将其删除，此时我们要判断当前哈希表当中是否存在元素40，当我们从0下标开始往后找到2下标（空位置）时，我们就应该停下来，此时并没有找到元素40，但是元素40却在哈希表中存在。

因此我们必须为哈希表中的每一个位置设置一个状态，并且每个位置的状态应该有三种可能，当哈希表中的一个元素被删除后，我们不应该简单的将该位置的状态设置为EMPTY，而是应该将该位置的状态设置为DELETE。
这样一来，当我们在哈希表中查找元素的过程中，若当前位置的元素与待查找的元素不匹配，但是当前位置的状态是EXIST或是DELETE，那么我们都应该继续往后进行查找，而当我们插入元素的时候，可以将元素插入到状态为EMPTY或是DELETE的位置。

因此，闭散列的哈希表中的每个位置存储的结构，应该包括所给数据和该位置的当前状态。

template<class K,class V>
struct HashData
{pair<K, V> _kv;Status _status;
};

而为了在插入元素时好计算当前哈希表的负载因子，我们还应该时刻存储整个哈希表中的有效元素个数，当负载因子过大时就应该进行哈希表的增容。

//哈希表
template<class K, class V>
class HashTable
{
public://...
private:vector<HashData<K, V>> _table; //哈希表size_t _n = 0; //哈希表中的有效元素个数
};

2、【哈希表的插入】

向哈希表中插入数据的步骤如下：

1. 查看哈希表中是否存在该键值的键值对，若已存在则插入失败。
2. 判断是否需要调整哈希表的大小，若哈希表的大小为0，或负载因子过大都需要对哈希表的大小进行调整。
3. 将键值对插入哈希表。
4. 哈希表中的有效元素个数加一。

其中，哈希表的大小调整方式如下：

• 若哈希表的大小为0，则将哈希表的初始大小设置为10。
• 若哈希表的负载因子大于0.7，则先创建一个新的哈希表，该哈希表的大小为原哈希表的两倍，之后遍历原哈希表，将原哈希表中的数据插入到新哈希表，最后将原哈希表与新哈希表交换即可。

注意： 在将原哈希表的数据插入到新哈希表的过程中，不能只是简单的将原哈希表中的数据对应的挪到新哈希表中，而是需要根据新哈希表的大小重新计算每个数据在新哈希表中的位置，然后再进行插入。

将键值对插入哈希表的具体步骤如下：

1. 通过哈希函数计算出对应的哈希地址。
2. 若产生哈希冲突，则从哈希地址处开始，采用线性探测向后寻找一个状态为EMPTY或DELETE的位置。
3. 将键值对插入到该位置，并将该位置的状态设置为EXIST。

注意： 产生哈希冲突向后进行探测时，一定会找到一个合适位置进行插入，因为哈希表的负载因子是控制在0.7以下的，也就是说哈希表永远都不会被装满。

【代码】：

//增bool Insert(const pair<K,V>& kv){HashData<K, V>* ret = Find(kv.first);if (ret != nullptr){return false;}else{//扩容if (_n * 10 / _table.size() == 7){size_t newSize = _table.size() * 2;HashTable<K, V> newHT;newHT._table.resize(newSize);// 遍历旧表for (size_t i = 0; i < _table.size(); i++){if (_table[i]._status == EXIST){newHT.Insert(_table[i]._kv);}}_table.swap(newHT._table);}Hash hf;size_t index = hf(kv.first) % _table.size();while (_table[index]._status == EXIST){index++;index %= _table.size();}_table[index]._kv = kv;_table[index]._status = EXIST;_n++;return true;}}

3、【哈希表的查找】

在哈希表中查找数据的步骤如下：

1. 先判断哈希表的大小是否为0，若为0则查找失败。
2. 通过哈希函数计算出对应的哈希地址。
3. 从哈希地址处开始，采用线性探测向后向后进行数据的查找，直到找到待查找的元素判定为查找成功，或找到一个状态为EMPTY的位置判定为查找失败。

注意： 在查找过程中，必须找到位置状态为EXIST，并且key值匹配的元素，才算查找成功。若仅仅是key值匹配，但该位置当前状态为DELETE，则还需继续进行查找，因为该位置的元素已经被删除了。

【代码】：

//查HashData<K, V>* Find(const K& key){Hash hf;if (_table.size() == 0){return nullptr;}size_t index = hf(key) % _table.size();while (_table[index]._status != EMPTY){if (_table[index]._status == EXIST && _table[index]._kv.first == key){return &(_table[index]);}index++;index %= _table.size();}return nullptr;}

4、【哈希表的删除】

删除哈希表中的元素非常简单，我们只需要进行伪删除即可，也就是将待删除元素所在位置的状态设置为DELETE。

在哈希表中删除数据的步骤如下：

1. 查看哈希表中是否存在该键值的键值对，若不存在则删除失败。
2. 若存在，则将该键值对所在位置的状态改为DELETE即可。
3. 哈希表中的有效元素个数减一。

注意： 虽然删除元素时没有将该位置的数据清0，只是将该元素所在状态设为了DELETE，但是并不会造成空间的浪费，因为我们在插入数据时是可以将数据插入到状态为DELETE的位置的，此时插入的数据就会把该数据覆盖。

【代码】：

bool Erase(const K& key){HashData<K, V>* ret = Find(key);if (ret == nullptr){return false;}else{ret->_status = DELETE;--_n;return true;}}

5、【完整代码】

HashTable.hpp:

#include<iostream>
#include<string>
#include<map>
#include<set>
#include <vector>
using namespace std;
enum Status
{EMPTY,EXIST,DELETE
};template<class K,class V>
struct HashData
{pair<K, V> _kv;Status _status;
};//仿函数提供键值类型为size_t
template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};
//特化后的，可以处理string
template<>
struct HashFunc<string>
{size_t operator()(const string& key){// BKDRsize_t hash = 0;for (auto e : key){hash *= 31;hash += e;}cout << key << ":" << hash << endl;return hash;}
};//哈希表
template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
public://查HashData<K, V>* Find(const K& key){Hash hf;if (_table.size() == 0){return nullptr;}size_t index = hf(key) % _table.size();while (_table[index]._status != EMPTY){if (_table[index]._status == EXIST && _table[index]._kv.first == key){return &(_table[index]);}index++;index %= _table.size();}return nullptr;}//增bool Insert(const pair<K,V>& kv){HashData<K, V>* ret = Find(kv.first);if (ret != nullptr){return false;}else{//扩容if (_n * 10 / _table.size() == 7){size_t newSize = _table.size() * 2;HashTable<K, V> newHT;newHT._table.resize(newSize);// 遍历旧表for (size_t i = 0; i < _table.size(); i++){if (_table[i]._status == EXIST){newHT.Insert(_table[i]._kv);}}_table.swap(newHT._table);}Hash hf;size_t index = hf(kv.first) % _table.size();while (_table[index]._status == EXIST){index++;index %= _table.size();}_table[index]._kv = kv;_table[index]._status = EXIST;_n++;return true;}}bool Erase(const K& key){HashData<K, V>* ret = Find(key);if (ret == nullptr){return false;}else{ret->_status = DELETE;--_n;return true;}}void Print(){for (size_t i = 0; i < _table.size(); i++){if (_table[i]._status == EXIST){cout << "[" << i << "]->" << _table[i]._kv.first << ":" << _table[i]._kv.second << endl;}else if (_table[i]._status == EMPTY){printf("[%d]->\n", i);}else{printf("[%d]->D\n", i);}}cout << endl;}HashTable(){_table.resize(10);}
private:vector<HashData<K, V>> _table; //哈希表size_t _n = 0; //哈希表中的有效元素个数
};

2.3、【开散列——哈希桶的实现】

1、【节点的定义】

在开散列的哈希表中，哈希表的每个位置存储的实际上是某个单链表的头结点，即每个哈希桶中存储的数据实际上是一个结点类型，该结点类型除了存储所给数据之外，还需要存储一个结点指针用于指向下一个结点。

template<class K,class V>
struct Hash_Node
{pair<K, V> _kv;Hash_Node<K, V>* _next;Hash_Node(const pair<K, V>& kv):_kv(kv),_next(nullptr){ }
};

与闭散列的哈希表不同的是，在实现开散列的哈希表时，我们不用为哈希表中的每个位置设置一个状态字段，因为在开散列的哈希表中，我们将哈希地址相同的元素都放到了同一个哈希桶中，并不需要经过探测寻找所谓的“下一个位置”。

哈希表的开散列实现方式，在插入数据时也需要根据负载因子判断是否需要增容，所以我们也应该时刻存储整个哈希表中的有效元素个数，当负载因子过大时就应该进行哈希表的增容。

//哈希桶
template<class K, class V>
class HashBucket
{
public://...
private:vector<Node*> _bucket; //哈希桶size_t _n = 0; //哈希桶中的有效元素个数
};

2、【哈希桶的插入】

向哈希桶中插入数据的步骤如下：

1. 查看哈希桶中是否存在该键值的键值对，若已存在则插入失败。
2. 判断是否需要调整哈希桶的大小，若哈希桶的大小为0，或负载因子过大都需要对哈希的桶大小进行调整。
3. 将键值对插入哈希桶。
4. 哈希桶中的有效元素个数加一。

其中，哈希桶的大小调整方式如下：

• 若哈希桶的大小为0，则将哈希桶的初始大小设置为10。
• 若哈希桶的负载因子已经等于1了，则先创建一个新的哈希桶，该哈希桶的大小为原哈希桶的两倍，之后遍历原哈希桶，将原哈希表中的数据插入到新哈希桶，最后将原哈希桶与新哈希交桶换即可。

注意： 在将原哈希桶的数据插入到新哈希桶的过程中，不要通过复用插入函数将原哈希桶中的数据插入到新哈希桶，因为在这个过程中我们需要创建相同数据的结点插入到新哈希桶，在插入完毕后还需要将原哈希桶中的结点进行释放，多此一举。

实际上，我们只需要遍历原表的每个哈希桶，通过哈希函数将每个哈希桶中的结点重新找到对应位置插入到新哈希表即可，不用进行结点的创建与释放。

说明一下： 下面代码中为了降低时间复杂度，在增容时取结点都是从单链表的表头开始向后依次取的，在插入结点时也是直接将结点头插到对应单链表，作图时不方便头取头插，于是图中都是尾取尾插。

将键值对插入哈希桶的具体步骤如下：

1. 通过哈希函数计算出对应的哈希地址。
2. 若产生哈希冲突，则直接将该结点头插到对应单链表即可。

bool Insert(const pair<K, V>& kv){Hash hf;Node* ret = Find(kv.first);if (ret != nullptr){return false;}else{if (_n == _bucket.size()){//扩容vector<Node*> newbucket;size_t newsize = _bucket.size() * 2;newbucket.resize(newsize);for (size_t i = 0; i < _bucket.size(); i++){Node* cur = _bucket[i];while (cur){Node* next = cur->_next;size_t index = hf(cur->_kv.first) % newbucket.size();cur->_next = newbucket[index];newbucket[index] = cur;cur = next;}_bucket[i] = nullptr;}_bucket.swap(newbucket);}size_t index = hf(kv.first) % _bucket.size();Node* newnode = new Node(kv);newnode->_next = _bucket[index];_bucket[index] = newnode;_n++;return true;}}

3、【哈希表的查找】

在哈希表中查找数据的步骤如下：

1. 先判断哈希表的大小是否为0，若为0则查找失败。
2. 通过哈希函数计算出对应的哈希地址。
3. 通过哈希地址找到对应的哈希桶中的单链表，遍历单链表进行查找即可。

Node* Find(const K& key){Hash hf;if (_bucket.size() == 0){return nullptr;}size_t index = hf(key) % _bucket.size();Node* cur = _bucket[index];while (cur){if (cur->_kv.first == key){return cur;}cur = cur->_next;}return nullptr;}

4、【哈希桶的删除】

在哈希表中删除数据的步骤如下：

1. 通过哈希函数计算出对应的哈希桶编号。
2. 遍历对应的哈希桶，寻找待删除结点。
3. 若找到了待删除结点，则将该结点从单链表中移除并释放。
4. 删除结点后，将哈希表中的有效元素个数减一。

注意： 不要先调用查找函数判断待删除结点是否存在，这样做如果待删除不在哈希表中那还好，但如果待删除结点在哈希表，那我们还需要重新在哈希表中找到该结点并删除，还不如一开始就直接在哈希表中找，找到了就删除。

bool Erase(const K& key){Hash hf;Node* ret = Find(key);if (ret == nullptr){return false;}else{size_t index = hf(key) % _bucket.size();Node* cur = _bucket[index];Node* prev = nullptr;while (cur){if (cur->_kv.first == key){if (prev == nullptr){_bucket[index] = cur->_next;}else{prev->_next = cur->_next;}delete cur;_n--;return true;}prev = cur;cur = cur->_next;}return false;}}

5、【完整代码】

HashBucket.hpp:

#include <iostream>
#include <vector>
using namespace std;template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};// 11:46继续
//HashFunc<string>
template<>
struct HashFunc<string>
{size_t operator()(const string& key){// BKDRsize_t hash = 0;for (auto e : key){hash *= 31;hash += e;}cout << key << ":" << hash << endl;return hash;}
};
template<class K,class V>
struct Hash_Node
{pair<K, V> _kv;Hash_Node<K, V>* _next;Hash_Node(const pair<K, V>& kv):_kv(kv),_next(nullptr){ }
};
template<class K, class V, class Hash = HashFunc<K>>
class HashBucket
{public:typedef  Hash_Node<K, V>  Node;HashBucket(){_bucket.resize(10);}~HashBucket(){for (size_t i = 0; i < _bucket.size(); i++){Node* cur = _bucket[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_bucket[i] = nullptr;}}Node* Find(const K& key){Hash hf;if (_bucket.size() == 0){return nullptr;}size_t index = hf(key) % _bucket.size();Node* cur = _bucket[index];while (cur){if (cur->_kv.first == key){return cur;}cur = cur->_next;}return nullptr;}bool Insert(const pair<K, V>& kv){Hash hf;Node* ret = Find(kv.first);if (ret != nullptr){return false;}else{if (_n == _bucket.size()){//扩容vector<Node*> newbucket;size_t newsize = _bucket.size() * 2;newbucket.resize(newsize);for (size_t i = 0; i < _bucket.size(); i++){Node* cur = _bucket[i];while (cur){Node* next = cur->_next;size_t index = hf(cur->_kv.first) % newbucket.size();cur->_next = newbucket[index];newbucket[index] = cur;cur = next;}_bucket[i] = nullptr;}_bucket.swap(newbucket);}size_t index = hf(kv.first) % _bucket.size();Node* newnode = new Node(kv);newnode->_next = _bucket[index];_bucket[index] = newnode;_n++;return true;}}bool Erase(const K& key){Hash hf;Node* ret = Find(key);if (ret == nullptr){return false;}else{size_t index = hf(key) % _bucket.size();Node* cur = _bucket[index];Node* prev = nullptr;while (cur){if (cur->_kv.first == key){if (prev == nullptr){_bucket[index] = cur->_next;}else{prev->_next = cur->_next;}delete cur;_n--;return true;}prev = cur;cur = cur->_next;}return false;}}void Print(){for (size_t i = 0; i < _bucket.size(); i++){Node* cur = _bucket[i];while (cur){ cout << cur->_kv.first << "->" << cur->_kv.second << " ";cur = cur->_next;}cout << endl;}}
private:vector<Node*> _bucket;size_t _n = 0;
};

三、【哈希的应用——布隆过滤器】

注：布隆过滤器的底层采用的是位图，按理说布隆过滤器应该是位图的应用，但是实际上由于位图采取的也是哈希结构的思想，而位图是作为C++中STL的一部分，所以这里布隆过隆器采用STL中的位图进行封装，并将其作为哈希的应用进行介绍，而至于位图见我的另一篇博客：【】。

3.1、【布隆过滤器的介绍】

1、【 布隆过滤器的提出】

首先让我们想一下如下的情景：

在注册账号，设置昵称的时候，为了保证每个用户昵称的唯一性，系统必须检测你输入的昵称是否被使用过，这本质就是一个key的模型，我们只需要判断这个昵称被用过，还是没被用过。我们一般会采用下面的两种方式进行判断。

方法一：用红黑树或哈希表将所有使用过的昵称存储起来，当需要判断一个昵称是否被用过时，直接判断该昵称是否在红黑树或哈希表中即可。但红黑树和哈希表最大的问题就是浪费空间，当昵称数量非常多的时候内存当中根本无法存储这些昵称
方法二：用位图将所有使用过的昵称存储起来，虽然位图只能存储整型数据，但我们可以通过一些哈希算法将字符串转换成整型，比如BKDR哈希算法。当需要判断一个昵称是否被用过时，直接判断位图中该昵称对应的比特位是否被设置即可。

位图虽然能够大大节省内存空间，但由于字符串的组合形式太多了，一个字符的取值有256种，而一个数字的取值只有10种，因此无论通过何种哈希算法将字符串转换成整型都不可避免会存在哈希冲突。

这里的哈希冲突就是不同的昵称最终被转换成了相同的整型，此时就可能会引发误判，即某个昵称明明没有被使用过，却被系统判定为已经使用过了，于是就出现了布隆过滤器。

2、【布隆过滤器的概念】

布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询。

这里我们知道，如果存在哈希冲突，那么就会出现误判，但是我们可以想一下，判断某个数据在位图中是否存在时，只有当该数据存在时才会出现误判，因为哈希冲突，可能是其他的数据但是哈希函数计算的结果与待判断数据计算结果相同，实际上在位图中存在的是其他的数据，但是如果是判断某个数据在位图中不存在，往往是更加准确的，因为不会受到哈希冲突的影响。

布隆过滤器其实就是位图的一个变形和延申，虽然无法避免存在哈希冲突，但我们可以想办法降低误判的概率。
当一个数据映射到位图中时，布隆过滤器会用多个哈希函数将其映射到多个比特位，当判断一个数据是否在位图当中时，需要分别根据这些哈希函数计算出对应的比特位，如果这些比特位都被设置为1则判定为该数据存在，否则则判定为该数据不存在。
布隆过滤器使用多个哈希函数进行映射，目的就在于降低哈希冲突的概率，一个哈希函数产生冲突的概率可能比较大，但多个哈希函数同时产生冲突的概率可就没那么大了。

这里举个例子：

假设布隆过滤器使用三个哈希函数进行映射，那么“张三”这个昵称被使用后位图中会有三个比特位会被置1，当有人要使用“李四”这个昵称时，就算前两个哈希函数计算出来的位置都产生了冲突，但由于第三个哈希函数计算出的比特位的值为0，此时系统就会判定“李四”这个昵称没有被使用过。

但随着位图中添加的数据不断增多，位图中1的个数也在不断增多，此时就会导致误判的概率增加。

比如“张三”和“李四”都添加到位图中后，当有人要使用“王五”这个昵称时，虽然“王五”计算出来的三个位置既不和“张三”完全一样，也不和“李四”完全一样，但“王五”计算出来的三个位置分别被“张三”和“李四”占用了，此时系统也会误判为“王五”这个昵称已经被使用过了。

3、【布隆过滤器的特点】

• 当布隆过滤器判断一个数据存在可能是不准确的，因为这个数据对应的比特位可能被其他一个数据或多个数据占用了。
• 当布隆过滤器判断一个数据不存在是准确的，因为如果该数据存在那么该数据对应的比特位都应该已经被设置为1了。

4、【误判率的控制】

那我们因该如何控制误判率呢？

很显然，过小的布隆过滤器很快所有的比特位都会被设置为1，此时布隆过滤器的误判率就会变得很高，因此布隆过滤器的长度会直接影响误判率，布隆过滤器的长度越长其误判率越小。
此外，哈希函数的个数也需要权衡，哈希函数的个数越多布隆过滤器中比特位被设置为1的速度越快，并且布隆过滤器的效率越低，但如果哈希函数的个数太少，也会导致误判率变高。

那应该如何选择哈希函数的个数和布隆过滤器的长度呢，有人通过计算后得出了以下关系式：

我们这里可以大概估算一下，如果使用3个哈希函数，即k的值为3，l n 2 ln2ln2的值我们取0.7，那么 m和 n  的关系大概是m = 4 × n 也就是布隆过滤器的长度应该是插入元素个数的4倍。

3.2、【布隆过滤器的实现】

1、【处理取模问题的三个哈希函数】

首先，布隆过滤器可以实现为一个模板类，因为插入布隆过滤器的元素不仅仅是字符串，也可以是其他类型的数据，只有调用者能够提供对应的哈希函数将该类型的数据转换成整型即可，但一般情况下布隆过滤器都是用来处理字符串的，所以这里可以将模板参数K的缺省类型设置为string。

布隆过滤器中的成员一般也就是一个位图，我们可以在布隆过滤器这里设置一个非类型模板参数N，用于让调用者指定位图的长度。

//布隆过滤器
template<size_t N, class K = string, class Hash1 = BKDRHash, class Hash2 = APHash, class Hash3 = DJBHash>
class BloomFilter
{
public://...
private:bitset<N> _bs;
};

实例化布隆过滤器时需要调用者提供三个哈希函数，由于布隆过滤器一般处理的是字符串类型的数据，因此这里我们可以默认提供几个将字符串转换成整型的哈希函数。

• 这里选取将字符串转换成整型的哈希函数，是经过测试后综合评分最高的BKDRHash、APHash和DJBHash，这三种哈希算法在多种场景下产生哈希冲突的概率是最小的。
• 此时本来这三种哈希函数单独使用时产生冲突的概率就比较小，现在要让它们同时产生冲突概率就更小了。

struct BKDRHash
{size_t operator()(const string& s){size_t value = 0;for (auto ch : s){value = value * 131 + ch;}return value;}
};
struct APHash
{size_t operator()(const string& s){size_t value = 0;for (size_t i = 0; i < s.size(); i++){if ((i & 1) == 0){value ^= ((value << 7) ^ s[i] ^ (value >> 3));}else{value ^= (~((value << 11) ^ s[i] ^ (value >> 5)));}}return value;}
};
struct DJBHash
{size_t operator()(const string& s){if (s.empty())return 0;size_t value = 5381;for (auto ch : s){value += (value << 5) + ch;}return value;}
};

2、【布隆过滤器的插入】

布隆过滤器当中需要提供一个Set接口，用于插入元素到布隆过滤器当中。插入元素时，需要通过三个哈希函数分别计算出该元素对应的三个比特位，然后将位图中的这三个比特位设置为1即可。

void Set(const K& key)
{//计算出key对应的三个位size_t i1 = Hash1()(key) % N;size_t i2 = Hash2()(key) % N;size_t i3 = Hash3()(key) % N;//设置位图中的这三个位_bs.set(i1);_bs.set(i2);_bs.set(i3);
}

3、【布隆过滤器的查找】

布隆过滤器当中还需要提供一个Test接口，用于检测某个元素是否在布隆过滤器当中。检测时，需要通过三个哈希函数分别计算出该元素对应的三个比特位，然后判断位图中的这三个比特位是否被设置为1。

• 只要这三个比特位当中有一个比特位未被设置则说明该元素一定不存在。
• 如果这三个比特位全部被设置，则返回true表示该元素存在（可能存在误判）。

bool Test(const K& key)
{//依次判断key对应的三个位是否被设置size_t i1 = Hash1()(key) % N;if (_bs.test(i1) == false){return false; //key一定不存在}size_t i2 = Hash2()(key) % N;if (_bs.test(i2) == false){return false; //key一定不存在}size_t i3 = Hash3()(key) % N;if (_bs.test(i3) == false){return false; //key一定不存在}return true; //key对应的三个位都被设置，key存在（可能误判）
}

4、【布隆过滤器的删除】

布隆过滤器一般不支持删除操作，原因如下：

• 因为布隆过滤器判断一个元素存在时可能存在误判，因此无法保证要删除的元素确实在布隆过滤器当中，此时将位图中对应的比特位清0会影响其他元素。
• 此外，就算要删除的元素确实在布隆过滤器当中，也可能该元素映射的多个比特位当中有些比特位是与其他元素共用的，此时将这些比特位清0也会影响其他元素。

但是也不是说布隆过滤器根本不能支持删除操作，要让布隆过滤器支持删除，必须要做到以下两点：

1、保证要删除的元素在布隆过滤器当中。比如刚才的呢称例子当中，如果通过调用Test函数得知要删除的昵称可能存在布隆过滤器当中后，可以进一步遍历存储昵称的文件，确认该昵称是否真正存在。

2、保证删除后不会影响到其他元素。可以为位图中的每一个比特位设置一个对应的计数值，当插入元素映射到该比特位时将该比特位的计数值++，当删除元素时将该元素对应比特位的计数值–即可。

可是布隆过滤器最终还是没有提供删除的接口，因为使用布隆过滤器本来就是要节省空间和提高效率的。在删除时需要遍历文件或磁盘中确认待删除元素确实存在，而文件IO和磁盘IO的速度相对内存来说是很慢的，并且为位图中的每个比特位额外设置一个计数器，就需要多用原位图几倍的存储空间，这个代价也是不小的。

3.3【布隆过滤器的应用】

我们来看一个题目：给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件的交集？给出近似算法。

题目要求给出近视算法，也就是允许存在一些误判，那么我们就可以用布隆过滤器。

• 先读取其中一个文件当中的query，将其全部映射到一个布隆过滤器当中。
• 然后读取另一个文件当中的query，依次判断每个query是否在布隆过滤器当中，如果在则是交集，不在则不是交集。

其次我们来看一下它的使用场景：使用布隆过滤器的前提是，布隆过滤器的误判不会对业务逻辑造成影响。

比如当我们首次访问某个网站时需要用手机号注册账号，而用户的各种数据实际都是存储在数据库当中的，也就是磁盘上面。

• 当我们用手机号注册账号时，系统就需要判断你填入的手机号是否已经注册过，如果注册过则会提示用户注册失败。
• 当我们用手机号注册账号时，系统就需要判断你填入的手机号是否已经注册过，如果注册过则会提示用户注册失败。
• 但这种情况下系统不可能直接去遍历磁盘当中的用户数据，判断该手机号是否被注册过，因为磁盘IO是很慢的，这会降低用户的体验。
• 这种情况下就可以使用布隆过滤器，将所有注册过的手机号全部添加到布隆过滤器当中，当我们需要用手机号注册账号时，就可以直接去布隆过滤器当中进行查找。
• 如果在布隆过滤器中查找后发现该手机号不存在，则说明该手机号没有被注册过，此时就可以让用户进行注册，并且避免了磁盘IO。
• 如果在布隆过滤器中查找后发现该手机号存在，此时还需要进一步访问磁盘进行复核，确认该手机号是否真的被注册过，因为布隆过滤器在判断元素存在时可能会误判。

• 由于大部分情况下用户用一个手机号注册账号时，都是知道自己没有用该手机号注册过账号的，因此在布隆过滤器中查找后都是找不到的，此时就避免了进行磁盘IO。而只有布隆过滤器误判或用户忘记自己用该手机号注册过账号的情况下，才需要访问磁盘进行复核。

3.4【布隆过滤器的优缺点】

1、【布隆过滤器的优点】

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

2、【布隆过滤器的缺陷】

• 有误判率，即存在假阳性（False Position），即不能准确判断元素是否在集合中（补救方法：再自建一个白名单，存储可能会误判的数据）
• 不能获取元素本身。
• 一般情况下不能从布隆过滤器中删除元素。

四、【哈希切割】

哈希切割就是将一个大的事务，利用哈希的原理（通过哈希函数，将相同或者相近的数据切分到一组），将其分为若干个小事务。相同的数据都被分到同一个事务集合里。

我们看两个问题：

• 问题一：给一个超过100G大小的，存着许多IP地址的大文件, 设计算法找到出现次数最多的IP地址？

分析：

• 100GB大小的文件，无法放入内存。
• 找到出现次数最多的IP，需要准确统计，无法使用位图或者布隆过滤器，因为它判断存在的时候会出现误判，所以是不准确的。
• 统计次数，还是需要用到map或者是unordered_map。
• 将100GB的文件拆分成100个1GB大小的小文件，每个小文件进行统计。

• 一个个来统计次数，依次读取每个小文件，依次统计次数。
•  统计完一个，将出现最多次数的IP及次数保存，并且clear掉map，再统计下一个小文件。

这样也会带来许多问题，请继续向下看。

如果将这100GB的文件均分为100给1GB的小文件，统计会出现问题。

• 假设A0中出现次数最多的IP是“IP1”，出现最少次数的IP是“IP2"，那么这个小文件最终得到是”IP1“出现最多。
• A1小文件中，出现最多的是”IP2“，出现最少的是”IP1“，那么这个小文件最终得到是”IP2“出现最多。
• 最终是A0中统计出来”IP1“的次数和A1中统计出来”IP2“的次数在比较。

这样最终比较时的数据具有片面性，因为在统计每个小文件时，会舍弃很多的数据，这些舍弃的数据再最终比较时并没有被考虑到。

但是如果我们在分小文件的时候，让相同的IP分到一个小文件中，这样统计出来的次数就不片面了。

这就需要我们用到哈希切分的办法，我们可以通过哈希函数，将100GB文件中的所有IP都转换成整数，然后模100，得到多少就进入标号为多少的小文件中。

• 哈希切分时：相同的IP经过哈希函数处理得到的整数必然是相同的，所以也必然会被分到同一个小文件中。
• 虽然会有哈希碰撞的情况，产生碰撞的IP都会在一个小文件中，而不会被分到其他小文件。

经过哈希切分后，每个小文件中统计出现次数最多的IP就是这100GB文件中该IP出现的总次数。最后再从每个小文件中出现次数最多的IP中比较出最终出现次数最多的IP。

但是此时又存在问题，哈希切分并不是均分，也就意味着每个小文件中的IP个数不一样，有的多有的少。如果某个小文件的大小超出1GB怎么办？

有两种超出1GB的情况：

• 这个小文件中冲突的IP很多，都是不同的IP，大多数是不重复的，此时无法使用map来统计——需要换一个哈希函数递归切分这个小文件。
• 这个小文件中冲突的IP很多，都是相同的IP，大多数是重复的，此时仍然可以用map来统计——直接统计。

无论是哪种情况，我们先都直接用map去统计，如果是第二种情况，内存就够用，map可以进行统计，而且不会报错。

如果是第一种情况，map就会因为内存不够而插入失败，相当于new节点失败，就会抛异常，此时我们只需要捕获这个异常，然后换一个哈希函数递归切分这个小文件即可。

下面看第二个问题：

• 问题二：给两个文件，分别有100亿个字符串，我们只有1G内存，如何找到两个文件交集？给出精确算法。

分析：

• 这个问题和布隆过滤器应用中的问题一样，只是需要给出精确的算法，所以肯定不能使用布隆过滤器，还是需要map来统计。
• 1GB的内存，无法存放下100亿个字符串，所以需要哈希切分。

假设平均每个字符串的大小是50B，那么100亿个字符串就是500GB，所以需要将这500GB哈希切分成1000份，每个小文件才能在内存中进行准确的次数统计。

• 将文件A和文件B各自进行哈希切分为1000个小文件，每个小文件平均大小是0.5GB。
•  然后Ai和Bi去找交集，找1000次就找到了两个文件中的所有交集。
•  如果某个小文件太大，仍然使用上个问题的方法去处理。

那各个小文件之间又应该如何找交集呢？

经过切分后理论上每个小文件的平均大小是512M，因此我们可以将其中一个小文件加载到内存，并放到一个set容器中，再遍历另一个小文件当中的query，依次判断每个query是否在set容器中，如果在则是交集，不在则不是交集。
并且哈希切分并不是平均切分，有可能切出来的小文件中有一些小文件的大小仍然大于1G，此时如果与之对应的另一个小文件可以加载到内存，则可以选择将另一个小文件中的字符串加载到内存，因为我们只需要将两个小文件中的一个加载到内存中就行了。
但如果两个小文件的大小都大于1G，那我们可以考虑将这两个小文件再进行一次切分，将其切成更小的文件，方法与之前切分A文件和B文件的方法类似。

本质这里在进行哈希切分时，就是将这些小文件看作一个个的哈希桶，将大文件中的字符串通过哈希函数映射到这些哈希桶中，如果是相同的字符串，则会产生哈希冲突进入到同一个小文件中。

这里需要注意的是，每个小文件Ai和Bi都需要各自降重以后再找交集。

总结

本篇博客到这里就结束了，感谢你观看！

.................................................................................装满了明信片的铁盒里藏着一片玫瑰花瓣

                                                                                                       ————《上海一九四三》