【数据结构】哈希表与哈希桶

👀樊梓慕：个人主页

🎥个人专栏：《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》《C++》《Linux》《算法》

🌝每一个不曾起舞的日子，都是对生命的辜负

前言

1.概念

2.哈希冲突

3.解决哈希冲突

3.1闭散列

3.2开散列（哈希桶）

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删除

前言

本篇文章我们共同学习哈希结构，哈希结构追求更极致的搜索效率。

之前学习的结构中搜索的效率取决于搜索过程中元素的比较次数，因此顺序结构中查找的时间复杂度为O(N)，平衡树中查找的时间复杂度为树的高度O(logN)。

那我们能不能构建一种数据结构，让搜索效率达到O(1)呢。

如果构造一种存储结构，该结构能够通过某种函数使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时就能通过该函数很快找到该元素进而达到O(1)的查找效率。

接下来就让我们共同学习哈希结构。

欢迎大家📂收藏📂以便未来做题时可以快速找到思路，巧妙的方法可以事半功倍。

=========================================================================

GITEE相关代码：🌟樊飞 (fanfei_c) - Gitee.com🌟

=========================================================================

1.概念

哈希结构的本质就是利用了『映射关系』。

向该结构当中插入和搜索元素的过程如下：

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

该方式即为哈希（散列）方法，哈希方法中使用的转换函数称为哈希（散列）函数，构造出来的结构称为哈希表（散列表）。

例如，集合{1, 7, 6, 4, 5, 9}

哈希函数设置为：hash( key ) = key % capacity ，其中capacity为存储元素底层空间的总大小。

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

2.哈希冲突

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

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

hash( 11 ) = 11 % 10 = 1。

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

哈希函数设计原则：

哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有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种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。例如：

假设要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前7位都是相同的，那么我们可以选择后面的四位作为哈希地址。

如果这样的抽取方式还容易出现冲突，还可以对抽取出来的数字进行反转（如1234改成4321）、右环位移（如1234改成4123）、左环位移（如1234改成2341）、前两数与后两数叠加（如1234改成12+34=46）等操作。

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

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

3.解决哈希冲突

3.1闭散列

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

1. 线性探测

如图，现在需要插入元素44，先通过哈希函数计算哈希地址，hashAddr为4，因此44理论上应该插在该位置，但是该位置已经放了值为4的元素，即发生哈希冲突。

线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

插入

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

删除

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

因此线性探测采用标记的伪删除法来删除一个元素。

// 哈希表每个空间给个标记
// EMPTY此位置空， EXIST此位置已经有元素， DELETE元素已经删除
enum State{EMPTY, EXIST, DELETE};

我们将数据插入到有限的空间，那么空间中的元素越多，插入元素时产生冲突的概率也就越大，冲突多次后插入哈希表的元素，在查找时的效率必然也会降低。介于此，哈希表当中引入了负载因子（载荷因子）。

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

虽然负载因子越小，冲突概率就会变低，查找效率会变高，但是负载因子越小，也就意味着空间的利用率越低，此时大量的空间实际上都被浪费了。对于闭散列（开放定址法）来说，负载因子是特别重要的因素，一般控制在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：表的大小。

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

研究表明：当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。

采用二次探测为产生哈希冲突的数据寻找下一个位置，相比线性探测而言，采用二次探测的哈希表中元素的分布会相对稀疏一些，不容易导致数据堆积，但也因此，闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。

3.2开散列（哈希桶）

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

这样看来，对于开散列来说，不同哈希值的元素之间不会互相干扰。

并且哈希桶的负载因子可以更大，空间利用率高。

极端情况：所有元素的哈希值均相同，最终都放到了同一个哈希桶中，此时该哈希表增删查改的效率就退化成了O(N)，对于这种情况，有这样一种解决方案：『桶中种树』。

为了避免出现这种极端情况，当桶当中的元素个数超过一定长度，有些地方就会选择将该桶中的单链表结构换成红黑树结构。

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

4.模拟实现

4.1闭散列的模拟实现

4.1.1哈希表结构设计

前面在讲解线性探测的部分时，提到过我们不能直接删除哈希表中的元素，而是采用伪标记的删除法，这里我们展开讲解一下：

闭散列又称开放定址法，当两个元素的哈希值冲突时我们采用线性探测的方式来解决冲突。

那么查找某个元素时，如何判断可以找到还是找不到？

根据线性探测的思想，明显是当遇到空时，就证明找不到了。

可当我们要删除某个元素时，如果直接删除，他所在的位置变成空值，那将来在查找『因为它而产生的哈希冲突后移的元素』时，可能会受到该位置为空的影响，提前结束查找操作。

所以这里不能简单的直接删除，并且也不能用某个具体的值代表空值，这样会导致哈希表存储不了这个值，所以最有效的方式就是给每个元素设置一个状态。

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

//枚举：标识每个位置的状态
enum State
{EMPTY,EXIST,DELETE
};//哈希表每个位置存储的结构
template<class K, class V>
struct HashData
{pair<K, V> _kv;State _state = EMPTY; //状态
};

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

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

4.1.2插入

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

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

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

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

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

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

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

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

//插入函数
bool Insert(const pair<K, V>& kv)
{//1、查看哈希表中是否存在该键值的键值对HashData<K, V>* ret = Find(kv.first);if (ret) //哈希表中已经存在该键值的键值对（不允许数据冗余）{return false; //插入失败}if _n * 10 / _table.size() >= 7) //负载因子大于0.7需要增容{//增容//a、创建一个新的哈希表，新哈希表的大小设置为原哈希表的2倍HashTable<K, V> newHT;newHT._table.resize(2 * _table.size());//b、将原哈希表当中的数据插入到新哈希表for (auto& e : _table){if (e._state == EXIST){newHT.Insert(e._kv);}}//c、vector的交换函数swap交换这两个哈希表_table.swap(newHT._table);}//3、将键值对插入哈希表//a、通过哈希函数计算哈希地址size_t hashi= kv.first%_table.size(); //除数不能是capacity//b、找到一个状态为EMPTY或DELETE的位置while (_table[hashi]._state == EXIST){++hashi;hashi %= _table.size(); //防止下标超出哈希表范围}//c、将数据插入该位置，并将该位置的状态设置为EXIST_table[hashi]._kv = kv;_table[hashi]._state = EXIST;//4、哈希表中的有效元素个数加一_n++;return true;
}

4.1.3删除

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

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

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

注意：虽然删除元素时没有将该位置的数据清0，只是将该元素所在状态设为了DELETE，但是并不会造成空间的浪费，因为我们在插入数据时是可以将数据覆盖到状态为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;
}

4.2哈希桶的模拟实现

4.2.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){}
};

注意：哈希桶的结构设计中不需要状态字，因为不同哈希值的元素不会互相影响。

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

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