前言：上篇文章介绍了unordered_set和unordered_map序列关联式容器，它们之所以效率比较高，是因为其底层使用了哈希结构。，所以这篇文章我们就来详细讲解一下哈希表。有关unordered序列关联式容器的知识，请移步至这篇文章：unordered_map与unordered_set（系列关联式容器）
文章目录
- 1.哈希概念
- 2.哈希冲突/碰撞
- 3.哈希函数
- 4.解决哈希冲突
- 4.1闭散列（开放定址法）
- 4.1.1线性探测
- 4.1.2负载因子
- 4.1.3二次探测
- 4.2开散列（哈希桶,拉链法）
- 4.2.1开散列的概念
- 4.2.2开散列的规则与剖析
- 5.哈希表闭散列的实现
- 5.1闭散列的结构
- 5.2闭散列的插入
- 5.3闭散列的查找
- 5.4闭散列的删除
- 6.哈希表开散列的实现
- 6.1开散列的结构
- 6.2开散列的插入
- 6.3开散列的查找
- 6.4开散列的删除
- 7.如何解决string类型的哈希映射问题
1.哈希概念
顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过多次比较关键码，搜索效率取决于搜索过程中元素的比较次数，因此顺序结构中查找的时间复杂度为O(N)，平衡树中查找的时间复杂度为O(logN)。
而最理想的搜索方法是：可以不经过任何比较，一次直接从表中得到想要搜索的元素，即查找的时间复杂度为O(1)。
这种理想的搜索方法是存在的，如果构造一种存储结构，该结构能够通过某种函数使元素的存储位置与它的关键码之间建立一一映射的关系，那么在查找时就能通过该函数很快找到该元素。
当向该结构中：
- 插入元素
根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放。 - 搜索元素
对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功。
该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表或者称散列表(Hash Table)
以上都是一些晦涩难懂的学术语言，接下来我们用一个例子来解释什么是哈希。
例如：数据集合{1，7，6，4，5，9}；
哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小。若我们将该集合存储在capacity为10的哈希表中，则各元素存储位置对应如下：
用该方法进行搜索直接使用哈希函数就可以定位元素下标，不必进行多次关键码的比较，因此搜索的速度比较快，时间复杂度为O(1)。
2.哈希冲突/碰撞
不同关键字通过相同哈希函数计算出相同的哈希地址，这种现象称为哈希冲突或哈希碰撞，我们把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。
例如，在上述例子中，再将元素19插入，就会产生哈希冲突，因为元素19通过哈希函数得到的哈希地址与元素9相同，%10后都是下标为9的位置。
那么发生哈希冲突该如何处理呢？
3.哈希函数
引起哈希冲突的一个原因可能是：哈希函数设计不够合理。
哈希函数设计原则：
- 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
- 哈希函数计算出来的地址能均匀分布在整个空间中
- 哈希函数应该比较简单
- 注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突
常见的哈希函数:
1.直接定址法（常用）
取关键字的某个线性函数为散列地址：Hash（key）=A*key+B
优点：简单，均匀
缺点：需要事先知道关键字的分布情况，通常要求数据是整数，范围比较集中。
使用场景：适合查找比较小且连续的情况（范围集中）
2. 除留余数法(常用)
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数。
按照哈希函数：Hash(Key) = Key % p ( p <= m ) 将关键码转换成哈希地址。
优点：使用场景广泛，不受限制。
缺点：存在哈希冲突，需要解决哈希冲突，冲突多，效率会有所下降。
3.平方取中法(了解)
假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址；
再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址。
平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况
四、折叠法（了解）
折叠法是将关键字从左到右分割成位数相等的几部分（最后一部分位数可以短些），然后将这几部分叠加求和，并按哈希表表长，取后几位作为哈希地址。
使用场景：折叠法适合事先不需要知道关键字的分布，或关键字位数比较多的情况。
五、随机数法（了解）
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即 Hash(Key)=random(Key)，其中random为随机数函数。
使用场景：通常应用于关键字长度不等时。
六、数字分析法（了解）
设有n个d位数，每一位可能有r种不同的符号，这r中不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，而在某些位上分布不均匀，只有几种符号经常出现。此时，我们可根据哈希表的大小，选择其中各种符号分布均匀的若干位作为哈希地址。
假设要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前7位都是 相同的，那么我们可以选择后面的四位作为散列地址，如果这样的抽取工作还容易出现 冲突，还可以对抽取出来的数字进行反转(如1234改成4321)、右环位移(如1234改成4123)、左环移位、前两数与后两数叠加(如1234改成12+34=46)等方法。
使用场景：数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀的情况
4.解决哈希冲突
解决哈希冲突两种常见的方法是：闭散列和开散列
4.1闭散列（开放定址法）
闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置呢？有两种方法：线性探测和二次探测。
4.1.1线性探测
线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
哈希函数：hashi = key % tablesize;
举个栗子：我们用除留余数法将序列{1,4，5,6，7,44,9}插入到表长为10的哈希表中，当发生哈希冲突时我们采用闭散列的线性探测找到下一个空位置进行插入，插入过程如下：
4.1.2负载因子
随着哈希表中数据的增多，产生哈希冲突的可能性也会随着增加，比如最后在44进行插入的时候连续出现了四次哈希冲突。因此，哈希表当中引入了负载因子（载荷因子）。
α（负载因子）=填入表中的元素个数 / 散列表的长度
- 负载因子越大，冲突的概率越高，查找效率越低，空间利用率越高
- 负载因子越小，冲突的概率越低，查找效率越高，空间利用率越低
α是散列表装满程度的标志因子。由于表长是定值，a与“填入表中的元素个数”成正比，所以，a越大，表明填入表中的元素越多，产生冲突的可能性就越大，反之，α越小，标明填入表中的元素越少，产生冲突的可能性就越小。实际上，散列表的平均查找长度是载荷因子α的函数，只是不同处理冲突的方法有不同的函数。对于开放定址法，荷载因子是特别重要因素，应严格限制在0.7-0.8以下。超过0.8，查表时的CPU缓存不命中(cache missing）按照指数曲线上升，因此，一些采用开放定址法的hash库，如Java的系统库限制了荷载因子为0.75，超过此值将resize散列表。
总结：
线性探测优点：实现非常简单，
线性探测缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。那么如何缓解呢？下面我们引出二次探测。
4.1.3二次探测
线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为：start+i^2(加0，加1，加4，加9)。
相比线性探测而言，采用二次探测的哈希表中元素的分布会相对稀疏一些，不容易导致数据堆积。
4.2开散列（哈希桶,拉链法）
4.2.1开散列的概念
开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
例如，我们用除留余数法将序列{1, 4, 44, 5, 6, 7, 9}插入到表长为10的哈希表中，当发生哈希冲突时我们采用开散列的形式，将哈希地址相同的元素都链接到同一个哈希桶下，插入过程如下：
从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。
4.2.2开散列的规则与剖析
开散列的主要思想：数组+链表，以上图为例，假设哈希表表长为10，即数组可以存储10个元素，数组的每个空间就相当于一个桶，上述例子就有10个哈希桶。
哈希桶中装的是单链表，准确来讲，每个哈希桶中存储的是单链表头结点的地址，所以开散列解决哈希冲突方式是将冲突元素挂到桶中的单链表中。
- 开散列负载因子的要求:
闭散列的开放定址法，建议控制在[0.0, 0.7]之间。
开散列的哈希桶，负载因子可以超过1，一般建议控制在[0.0, 1.0]之间。
哈希桶的极端情况：所有元素全部产生冲突，最终都放到了同一个哈希桶中，此时该哈希表增删查改的效率就退化成了O(N)。
解决方法：将这个桶中的元素，由单链表结构改为红黑树结构，并将红黑树的根结点存储在哈希表中。在这种情况下，如果有十亿个元素全部冲突到一个哈希桶中，我们也只需要在这个哈希桶中查找30次左右，这就是所谓的“桶里种树”。
5.哈希表闭散列的实现
5.1闭散列的结构
定义数据的存储结构：这里将其命名为HashData：
//枚举数据的三种状态：存在，删除，空
enum State
{
EMPTY,
EXIST,
DELETE
};
//哈希表每个位置存储的数据结构
template<class K, class V>
struct HashData
{
pair<K, V> _kv;
State _state = EMPTY; //默认状态为空
};
定义哈希表结构：哈希表的底层是一个线性数组，所以我们的成员变量有vector<HashData<K, V>> _tables,同时我们也要设置一个变量为_n,用于记录哈希表中的有效元素个数，这是用来计算哈希表的负载因子，当负载因子过大，就需要进行扩容。
//哈希表
template<class K, class V>
class HashTable
{
public:
//...
private:
vector<HashData<K, V>> _tables; //哈希表
size_t _n = 0; //哈希表中的有效元素个数
};
5.2闭散列的插入
步骤：
- 复用查找函数，查看哈希表中是否已存在该数据，若存在则插入失败。
- 计算负载因子，若超过0.7，就对哈希表的大小进行调整。
- 将数据插入哈希表。
如何对哈希表的大小进行调整？
- 若哈希表的大小为0（初始状态），就将哈希表的大小先扩到10。（resize）
- 若哈希表的负载因子大于0.7，则新创建一个哈希表，采用二倍扩容的方式，再遍历旧表，将原哈希表的数据插入到新的哈希表中。最后交换新旧哈希表。旧表在程序结束值，vector会自动调用其析构函数将其空间释放，所以不用担心这块的内存泄漏。
注意：将旧表的数据插入到新哈希表，不是单纯的照搬旧表的元素所在的位置进行插入，而是需要根据新的哈希表的大小重新计算每个数据在新表的位置，然后再进行插入。这里可以复用哈希表的插入函数。
在闭散列中，若出现哈希冲突，则从映射的哈希地址处开始，线性探测向后寻找状态为EMPTY或DELETE的位置，所以循环条件为_tables[index]._state == EXIST,当为EMPTY或DELETE就可以跳出循环，进行数据插入了。
bool Insert(const pair<K, V> kv)
{
//插入前先查找一番，如果数据存在就不插入了(哈希表不允许键值冗余)
HashData<K, V>* ret = Find(kv.first);
if (ret)
{
return false;
}
//引入负载因子，超过0.7就扩容
if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7)
{
//哈希表若大小为0，一开始就开10个空间
//若负载因子达到0.7,就二倍扩容
size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
//_tables.resize(newsize);//err.不能在原表上进行扩容，会造成数据覆盖
HashTable<K, V> newht;//定义一个新的哈希表
newht._tables.resize(newsize);//扩容
//将旧表的数据转移到新表有两种方法：
//遍历旧表，重新映射到新表
for (auto& data : _tables)
{
//法二：复用插入函数：如果旧表的数据存在，就插入到新表
if (data._state == EXIST)
{
newht.Insert(data._kv);
}
//法一
//if (data._state == EXIST)
//{
// //重新算在新表的位置
// size_t hashi = data.first % newtables.size();
// //线性探测
// size_t i = 1;
// size_t index = hashi;
// //当前位置存在数据时，就需要线性探测后面的位置
// while (newtables[index]._state == EXIST)
// {
// index = hashi + i;//在原位置上加i,二次探测的话+i*i
// index %= newtables.size();
// ++i;
// }
// newtables[index]._kv = kv;
// newtables[index]._state = EXIST;
//}
}
_tables.swap(newht._tables);//交换新旧表
}
//除留余数法:计算映射的哈希地址
size_t hashi = kv.first%_tables.size();
//线性探测
size_t i = 1;
size_t index = hashi;
//当前位置存在数据时，就需要线性探测下面的位置
while (_tables[index]._state == EXIST)
{
index = hashi + i;//在原位置上加i,二次探测的话+i*i
index %= _tables.size();
++i;
}
//找到空位置或者删除状态插入数据，并把状态置为EXIST
_tables[index]._kv = kv;
_tables[index]._state = EXIST;
_n++;
return true;
}
5.3闭散列的查找
步骤：
- 先判断哈希表的大小是否为0，若为0则查找失败。
- 通过哈希函数计算出对应的哈希地址。
- 从哈希地址处开始，采用线性探测向后向后进行数据的查找，直到找到待查找的元素判定为查找成功，或找到一个状态为EMPTY的位置判定为查找失败。
注意：查找成功的条件一定是该元素和key值匹配，并且状态为EXIST，若key值匹配，但是为DELETE状态，还需要继续向后线性探测，因为DELETE表明该元素已经删除了。
HashData<K, V>* Find(const K& key)
{
if (_tables.size() == 0) //哈希表大小为0，查找失败,防止除0错误
{
return nullptr;
}
//我要找key，我就要先映射key在哈希表中所在的位置
size_t hashi = key % _tables.size();
size_t i = 1;
size_t index = hashi;
while (_tables[index]._state != EMPTY)
{
if (_tables[index]._kv.first == key && _tables[index]._state == EXIST)
{
return &_tables[index];
}
index = hashi + i;
index = index % _tables.size();
++i;
//找了一圈没找到，可能当前哈希表全是存在+删除的情况
//找不到就跳出循环
if (index == hashi)
{
break;
}
}
return nullptr;
}
5.4闭散列的删除
删除哈希表中的元素非常简单，我们只需要进行伪删除即可，也就是将待删除元素所在位置的状态设置为DELETE。
//删除函数
bool Erase(const K& key)
{
//1、查看哈希表中是否存数据
HashData<K, V>* ret = Find(key);
if (ret)
{
//2、若存在，则将该键值对所在位置的状态改为DELETE
ret->_state = DELETE;
//3、哈希表中的有效元素个数减一
_n--;
return true;
}
return false;
}
6.哈希表开散列的实现
6.1开散列的结构
定义数据的存储结构：
//每个哈希桶中存储数据的结构
template<class K, class V>
struct HashNode
{
pair<K, V> _kv;
HashNode<K, V>* _next;//存储下一个结点的地址
//构造函数
HashNode(const pair<K, V>& kv)
:_kv(kv)
, _next(nullptr)//一开始初始化为空
{}
};
定义哈希表结构：利用了vector存储单链表头结点的地址，定义了_n记录有效元素个数（用于计算负载因子）。开散列不需要我们手动实现一个构造函数，因为系统会自动调vector的构造函数。
注意：开散列需要实现析构函数：程序结束时，vector会自动释放_tables中存储的结点，但是！！！，并不会自动释放挂在头结点下面的结点（单链表），所以我们要自己实现一个析构函数，取释放单链表所用的空间。
template <class K, class V>
class HashTable
{
typedef HashNode<K, V> Node;
public:
//析构函数
~HashTable()
{
//遍历哈希表“横向”
for (auto& cur : _tables)
{
//“纵向”遍历哈希桶
//如果cur为空就说明当前位置没有结点了
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
cur = nullptr;
}
}
//...
private:
vector<Node*> _tables;//存储数据的类型是Node*哦
size_t _n;//依然要考虑负载因子扩容的问题,_n(表示存储的有效数据)
};
6.2开散列的插入
步骤：
- 查看哈希表中是否已经存在这个数据，若存在则插入失败。
- 判断是否需要调整哈希表的大小，若为0，则扩容到10。若负载因子为1，则进行二倍扩容。
- 将数据插入哈希表。（这里采用的是头插，这样就不用再遍历一遍链表，插入到尾部了）
特别注意：遍历原表，将原表数据插入到新哈希表的过程中，不要通过复用插入函数，因为复用插入函数的过程中，我们需要创建相同数据的结点插入到新哈希表中，并且还要释放原表的数据。实际上，我们只需要遍历原表的每个哈希桶，通过哈希函数找到对应数据，然后将原数据挪动到新表中即可，这样就不用再进行结点的创建与释放了。（可以直接挪动原表数据的方法是：利用引用&）
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))
{
return false;
}
//当负载因子为1时，对哈希表进行扩容
if (_n == _tables.size())
{
size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
vector<Node*> newtable(newsize, nullptr);
//将原表的数据【挪动】到新表中，注意不是重新new结点，重新插入一遍
//遍历每个桶所存储的链表的头结点
for (auto& cur : _tables)
{
//遍历某个桶中的单链表
while (cur)
{
Node* next = cur->_next;
size_t hashi = cur->_kv.first%newtable.size();
//头插
cur->_next = newtable[hashi];
newtable[hashi] = cur;
cur = next;
}
}
_tables.swap(newtable);
}
//头插
size_t hashi = kv.first%_tables.size();
Node* newnode = new Node(kv);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return true;
}
6.3开散列的查找
//查找函数
Node* Find(const K& key)
{
if (_table.size() == 0) //哈希表大小为0，查找失败,也防止了%0错误
{
return nullptr;
}
size_t index = key % _table.size(); //通过哈希函数计算出对应的哈希桶编号index（除数不能是capacity）
//遍历下标为index的哈希桶
Node* cur = _table[index];
while (cur) //直到将该桶遍历完为止
{
if (cur->_kv.first == key) //key值匹配，则查找成功
{
return cur;
}
cur = cur->_next;
}
return nullptr; //直到该桶全部遍历完毕还没有找到目标元素，查找失败
}
6.4开散列的删除
步骤：
- 通过哈希函数计算出对应的哈希桶下标。
- 遍历对应的哈希桶，寻找待删除结点。
- 若找到了待删除结点，则将该结点从单链表中移除并释放。（注意：分为头删和其它位置的删除）
bool Erase(const K& key)
{
//1、通过哈希函数计算出对应的哈希桶编号index（除数不能是capacity）
size_t index = key % _table.size();
//2、在下标为index的哈希桶中寻找待删除结点
Node* prev = nullptr;
Node* cur = _table[index];
while (cur)
{
if (cur->_kv.first == key) //key值匹配，找到要删除的结点
{
if (prev == nullptr) //头删
{
//直接将头结点置为该删除结点的下一个结点
_table[index] = cur->_next;
}
else //待删除结点不是哈希桶的第一个结点
{
prev->_next = cur->_next; //将该结点从哈希桶中移除
}
delete cur; //释放该结点
_n--;
return true;
}
prev = cur;
cur = cur->_next;
}
return false; //直到该桶全部遍历完毕还没有找到待删除元素，删除失败
}
7.如何解决string类型的哈希映射问题
在上面的讲述中，我们都是以在哈希表中存储整数为例，那如果我们要让字符串作为键值key，映射到哈希表中进行存储，该怎么实现呢？
取字符串的首字符（ASCII码）进行映射可以吗？类似这样：
size_t hashi = cur->_kv.first[0] % newtables.size();
答案是：不可以。因为若我们取字符串的首元素计算哈希地址，这种代码满足了字符串作键值的情况，那么整数怎么办呢？我们要同时考虑到整型和字符串，这也是泛型编程的思想。并且这种解决方法，是将字符串的首元素映射到哈希表中，会存在大量的哈希冲突，非常不建议。
解决方法：将字符串转换成整型。哈希映射的关键思想就是取模，所以键值key需要能被取模，一般来说，哈希的键值key都是整型或字符串，因此我们这里利用了仿函数的特性，将键值key转换成size_t类型。如果key是string类型就会去调用HashFunc<string这个仿函数，如果是其它类型就会去调用默认的仿函数，将key值转换成无符号整数类型。
template<class K>
//将key键值转换成整型——仿函数
struct HashFunc
{
size_t operator()(const K& key)
{
return key;
}
};
//string类型转换成整型——模板特化
template<>
struct HashFunc<string>
{
//BKDR
size_t operator()(const string& s)
{
//不能将字符串每个字符的ASCII码值求和作为hashi，
//因为“abc”，“acb”...求和后的ASCII总值是一样的，哈希冲突的概率也比较高
//for (auto& ch : key)
//{
// hash += ch;
//}
size_t hashi = 0;
for (auto& ch : s)
{
hashi = hashi * 31 + ch;也可以乘131,1313,13131,131313
}
return hashi;
}
};
使用方法：
size_t hashi = hash(key) % _tables.size();
若想更深入的了解字符串哈希函数，可以看大佬的博客：各种字符串哈希函数
