【高阶数据结构】哈希（哈希表、哈希桶）

【高阶数据结构】哈希（哈希表、哈希桶）
⭐博客主页：️CS semi主页
⭐欢迎关注：点赞收藏+留言
⭐系列专栏：C++进阶
⭐代码仓库：C++进阶
家人们更新不易，你们的点赞和关注对我而言十分重要，友友们麻烦多多点赞＋关注，你们的支持是我创作最大的动力，欢迎友友们私信提问，家人们不要忘记点赞收藏＋关注哦！！！
哈希（哈希表、哈希桶）
一、哈希概念

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

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素，即搜索的时间复杂度为O(1)。

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

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

该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)。

二、哈希冲突

不同关键字通过相同哈希函数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

很简单的例子，我们下图所示的假如说数据信息中增加了一个45这个数，模10以后就变成了5，然后和原本的5产生了歧义，两个映射到同一位置上了，这就引起了哈希冲突/哈希碰撞。

三、哈希函数

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

哈希函数设计原则：
1. 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
2. 哈希函数计算出来的地址能均匀分布在整个空间中
3. 哈希函数应该比较简单
常见的哈希函数如下：
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)作为哈希地址。
  平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况
4. 折叠法
  折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。
  折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况
5. 随机数法
  选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数函数。
  通常应用于关键字长度不等时采用此法
6. 数学分析法
  设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。例如：
假设要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前7位都是相同的，那么我们可以选择后面的四位作为散列地址，如果这样的抽取工作还容易出现冲突，还可以对抽取出来的数字进行反转(如1234改成4321)、右环位移(如1234改成4123)、左环移位、前两数与后两数叠加(如1234改成12+34=46)等方法。

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

四、哈希冲突解决

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

1、闭散列–开放定址法

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

（1）线性探索

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

我们如下图，插入41这个数值，那么往后进行线性探索，找空位置坐下。

Hi = (H0 + i) % m（i=1,2,3……）

Hi：冲突元素通过线性探索所找的空位置。
H0：通过哈希函数对元素的关键码进行计算得到的位置。
m：哈希表的capacity

我们直接一眼就能看出问题所在点了，我们插入过多数据或者是重复插入取余以后一样的数据那岂不是线性探索次数很多并且可能出现容量不够的情况嘛？？我们用一个图来看一下：

我们如上图发现1000冲突了两次，101冲突了两次，40更是冲突了4次次，线性探索往后寻找的实在是太多了，所以：

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

负载因子=哈希表中有效数据个数/总的容量大小

上图进行扩容后的哈希冲突明显减少，但是我们大家会发现空间浪费了好多，这就是上述我们谈到的负载因子的问题，负载因子就需要做到保证在0.7-0.8这个范围当中。

总结一下：
线性探索的优点：很简单好理解。
线性探索的缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，很多不同的数据容易堆积在一起，需要往后寻找空位置，并且寻找空位置的时候需要多次比较，最后，负载因子的控制也是一个难点。

（2）二次探索

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

从算出来的位置往后+i个数

$H_i$ = ( $H_0$ + $i^2$ )% m（i=1,2,3……）

$H_0$ 是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置。
$m$ 是哈希表的大小。
$H i$ 是冲突元素通过二次探测后得到的存放位置

采用二次探测为产生哈希冲突的数据寻找下一个位置，相比线性探测而言，采用二次探测的哈希表中元素的分布会相对稀疏一些，不容易导致数据堆积。但对于10个空间来讲确实稀疏一点，但还是比较了很多次，我们拓展到20个空间来看一下：

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

2、开散列–链地址法

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

当然，开散列哈希桶同样可以进行扩容的，当所开的空间的每一个结点都已经挂了一个头结点，每一个头结点下面挂着不同的数，此时每一次插入新的值都会引起哈希冲突导致需要在下面挂新的数，这虽然是可以的，没什么问题，但哈希的性能得到了缩小，所以我们可以扩一下容，让后面新插入的值一些放到后面的数值桶中。

3、闭散区别

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

所以在我们实际生活中，采用开散列的哈希桶更加多，因为开散列的哈希桶负载因子可以很大，也就是可以容纳更多的值，而且在哈希桶的极端情况下（所有插入的数据全在一个桶中）也有方法解决：

上面的这种情况是全在一个桶子中，那么其查找效率非常地低，O（N），所以我们的做法是将这些值再进行根据红黑树的存储模式进行插入，而不是用链表的模式：

那么这样下来，尽管有10亿个数据我们遍历寻找这个值也都只需要30次！
所以我们在一些编译器中当哈希的一个桶中插入的数据过于多的时候，例如JAVA新的编译器中下面挂的超过8个就变成红黑树，小于等于8个则还是单链表。

五、哈希表的闭散列实现

 1、哈希表的结构

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

0、EMPTY : 该位置没有数据，为空。
1、EXITS ：该位置有数据，不为空。
2、DELETE ：该位置原本有值，但被删除，无值，为空。

（1）疑惑问题 – 为什么要是状态？为什么要三个状态？

所以衍生出一个问题：为什么要有这三种状态，不是直接判断空不空就行了吗，我们就给两种状态不就好了吗？

先解释用状态

提示一个点，我们假如说要在表中找一个元素是否存在呢？就比如我们下面的这个哈希表，我们假如说要找40这个元素的位置。

我们使用线性探索通过除留余数法求得元素40在该哈希表中的哈希地址是0。从0下标开始向后进行查找，若找到了40则说明存在，若找到的是个空位置，则这个表中没有40。

因为哈希的意义在于取余后发生哈希冲突后是往后找空位插入的！因为线性探测在为冲突元素寻找下一个位置时是依次往后寻找的，既然我们已经找到了一个空位置，那就说明这个空位置的后面不会再有从下标0位置开始冲突的元素了。

再比如我们现在要找80这个数，我们从0地址往后寻找，发现第5个空位置是空，我们当机立断判定80不存在，因为你无论怎么样，80和40都是从0地址往后进行找的，所以在找到第一个空位置的时候必定是不存在这个值的！

那么我们的状态又是啥？用0表示不存在，用1表示存在？这么一看似乎没啥问题，但是有一个很严重的问题，那么我插入的数本身就是1或者是0呢？这岂不是闹了很大的乌龙了吗？所以我们使用的是状态！

再解释有三个状态

接下来我们使用删除操作，删除了1000这个值，我们看一下此时哈希表是咋样的：

我们此时再来找40这个值到底存不存在，你现在告诉我只有俩状态是EMPTY和EXITS，那么我们根据取余法从0地址开始往后找，发现2这个位置是空位置，标记的是EMPTY，根据我们上面所讲的哈希表的结构是遇到空位置则直接判断不存在，那么不是闹了个大乌龙了吗，后面明明有40这个值的呀！所以我们这里引入DELETE按键，代表着之前存在，但被删，跳过这个坑位继续往后找。

这样一来，当我们在哈希表中查找元素的过程中，若当前位置的元素与待查找的元素不匹配，但是当前位置的状态是EXITS或是DELETE，那么我们都应该继续往后进行查找，而当我们插入元素的时候，可以将元素插入到状态为EMPTY或是DELETE的位置。

（2）状态和负载因子

所以，我们的状态为：
```
// 标记状态
enum State
{
	EMPTY, // 空
	EXITS, // 存在
	DELETE // 删除
};
1
2
3
4
5
6
7
```
哈希数据：
```
// HashData数据
template<class K, class V>
struct HashData
{
	pair<K, V> _kv;
	State _state = EMPTY;
};

1
2
3
4
5
6
7
8
```
哈希表：
```
// HashTable
template<class K, class V>
class HashTable
{
public:

private:
	vector<HashData<K, V>> _table; //哈希表
	size_t _n = 0; //哈希表中的有效元素个数(用来控制负载因子)
};
1
2
3
4
5
6
7
8
9
10
```
（3）前期工作
```
// 将kv.first强转成size_t
// 仿函数
template<class K>
struct DefaultHashTable
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};
1
2
3
4
5
6
7
8
9
10
```
2、哈希表的插入

插入有以下四个步骤：
1. 查看哈希表中是否存在该键值的键值对，若已存在则插入失败
2. 负载因子过大要对哈希表做调整
3. 将键值对插入哈希表
4. 哈希表中有效元素+1
调整哈希表

因为0.7是个小数，所以我们将0.7乘以10，当该哈希表的负载因子大于0.7的时候，我们需要创建一个新表，这个新表的大小是原始表的大小的两倍，也就是简单的扩容，将原本哈希表中的数据根据新表的位置插入新表中的不同位置，最后将原始表和新表进行交换即可。

如何将键值对插入到哈希表中？

先通过哈希函数（取余算法）计算出对应的哈希地址，再看是否哈希冲突，如果哈希冲突，则从该哈希地址处往后找EMPTY或者DELETE的位置进行插入（注意，此时因为之前已经调用Find函数进行查找了确认这个值不在这个哈希表中），最后将该值插入到这个位置并将这个位置的状态改成EXITS。

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

代码如下：
```
	HashTable()
	{
		// 构造10个空间
		_table.resize(10);
	}

	bool Insert(const pair<K, V>& kv)
	{
		// 查看哈希表中是否存在该键值的键值对，若已存在则插入失败
		// 负载因子过大都需要对哈希表的大小进行调整
		// 将键值对插入哈希表
		// 哈希表中的有效元素个数加1

		// 1、判断哈希表中是否存在该键值的键值对
		HashData<K, V>* key_ = Find(kv.first); 
		// 利用Find函数的bool值来判断是否存在
		if (key_)
		{
			return false; // 键值已经存在了，返回false
		}

		// 2、负载因子过大需要调整 -- 即大于0.7
		if (_n * 10 / _table.size() >= 7)
		{
			// 增容
			// a.创建新的哈希表，并将新表开辟到原始表的两倍
			size_t newSize = _table.size() * 2;
			HashTable<K, V, HashFunc> NewHashTable;
			NewHashTable._table.resize(newSize);

			// b.将原始表数据迁移到新表
			for (size_t i = 0; i < _table.size(); i++)
			{
				if (_table[i]._state == EXITS)
				{
					NewHashTable.Insert(_table[i]._kv);
				}
			}
			//for (auto& e : _table)
			//{
			//	if (e._state == EXITS)
			//	{
			//		NewHashTable.Insert(e._kv);
			//	}
			//}
			// c.交换原始表和新表
			_table.swap(NewHashTable._table);
		}

		// 3、将键值对插入到哈希表
		// 线性探索方式
		// a.取余计算原始哈希地址
		HashFunc hf;
		size_t hashi = hf(kv.first) % _table.size();
		// b.当是DELETE或者是EMPTY即插入，EXIST即跳过
		while (_table[hashi]._state == EXITS)
		{
			++hashi;
			hashi %= _table.size();// 防止超出
		}
		// c.插入进去并将状态进行改变
		_table[hashi]._kv = kv;
		_table[hashi]._state = EXITS;
		// 3、哈希表中的有效元素个数加1
		++_n;

		return true;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
```
3、哈希表的查找

方法有两个步骤：
1. 通过哈希函数计算出哈希地址
2. 从哈希地址处开始，采用线性探测向后向后进行数据的查找，直到找到待查找的元素判定为查找成功，或找到一个状态为EMPTY的位置判定为查找失败。
注意：在查找过程中，必须找到位置状态为EXIST，并且key值匹配的元素，才算查找成功。若仅仅是key值匹配，但该位置当前状态为DELETE，则还需继续进行查找，因为该位置的元素已经被删除了。
```
	// 查找函数
	HashData<K, V>* Find(const K& key)
	{
		// 1通过哈希函数计算出对应的哈希地址。
		// 2从哈希地址处开始，采用线性探测向后进行数据的查找，
		// 直到找到待查找的元素判定为查找成功，或找到一个状态为EMPTY的位置判定为查找失败。
		HashFunc hf;
		size_t hashi = hf(key) % _table.size();
		while (_table[hashi]._state != EMPTY)
		{
			if (_table[hashi]._state == EXITS
				&& _table[hashi]._kv.first == key)
			{
				return (HashData<K, V>*)&_table[hashi];
			}
			++hashi;
			hashi %= _table.size();
		}

		// 没找到
		return nullptr;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
```
4、哈希表的删除

伪删除，不用将数据真正删除，而只需要将数据的状态改为DELETE即可。
1. 查看哈希表中是否存在该键值的键值对，若不存在则删除失败
2. 若存在，则将该键值对所在位置的状态改为DELETE即可
3. 哈希表中的有效元素个数减1
注意此处我们并没有将这个数据完全删除掉，而是将这个数据的状态改成DELETE，实际上的数据并没有删除掉，但我们要插入数据的时候是可以将新插入的数据覆盖这个老的数据。
```
	// 删除
	bool Erase(const K& key)
	{
		// 1查看哈希表中是否存在该键值的键值对，若不存在则删除失败
		// 2若存在，则将该键值对所在位置的状态改为DELETE即可
		// 3哈希表中的有效元素个数减一
		HashData<K, V>* key_ = Find(key);
		if (key_)
		{
			key_->_state = DELETE;
			--_n;
			return true;
		}
		return false;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
```
六、哈希表的开散列实现（哈希桶）

1、哈希表的结构

开散列的哈希表中，哈希表的每一个存储位置的指针类型都是相同的，简而言之也就是单链表的头结点，当然，该节点类型除了存储所给的数据之外，同样还需要存储一个next结点指针指向下一个结点。
```
	template<class K, class V>
	struct HashNode
	{
		HashNode(const pair<K, V>& kv)
			:_kv(kv)
			,_next(nullptr)
		{}

		pair<K, V> _kv;
		HashNode<K, V>* _next;
	};
1
2
3
4
5
6
7
8
9
10
11
```
我们还记得之前我们的闭散列中，我们是需要为每一个哈希表的位置设置一个状态（即EXITS,EMPTY,DELETE），但开散列的哈希表就不需要，因为是每一个哈希表的位置都存放着插入的头结点，并且下面也许可能连着插入的新结点，在开散列的哈希表中，我们将哈希地址相同的元素都放到了同一个哈希桶中，并不需要经过探测寻找所谓的“下一个位置”。

那么需不需要增容呢？答案是当然需要增容了，因为当我们的哈希桶中是可以往下存数据的，也就是一个链表存储，当然当负载因子过大的时候，几乎占满整个哈希表的时候，那么此时就负载因子过大，每一次新增加的数几乎都哈希冲突了，需要往后变量链表进行尾插，操作还是很复杂的，所以还不如扩个容，让负载因子变的小一点，没那么大，就能够使整个哈希桶的效率变的更好，何乐而不为呢？
```
	//哈希表
	template<class K, class V>
	class HashTable
	{
		typedef HashNode<K, V> Node;
	public:

	private:
		vector<Node*> _table; //哈希表
		size_t _n = 0; //哈希表中的有效元素个数
	};
1
2
3
4
5
6
7
8
9
10
11
```
2、前期准备
```
	// 将kv.first强转成size_t
	// 仿函数
	template<class K>
	struct DefaultHashTable
	{
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};

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

		pair<K, V> _kv;
		HashNode<K, V>* _next;
	};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
```
3、哈希表（桶）的插入

我们哈希表（桶）的插入主要有以下四个步骤：
1. 查看哈希表中是否存在该键值的键值对，若已存在则插入失败
2. 判断是否需要调整负载因子，若负载因子过大都需要对哈希表的大小进行调整
3. 将键值对插入哈希表
4. 哈希表中的有效元素个数加1
因为负载因子已经到1了，所以需要扩容来调整负载因子，我们思路为扩容至两倍，需要遍历初始哈希表，进行顺手牵羊，将原哈希表中的结点的数据直接迁到新表中，再将新表和旧表一交换即可，这样避免了我们释放旧表结点的过程，更加方便快捷。那么我们进行扩容后看一下插入的元素的分布：

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

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

下面是个扩容的例子，因为如果要10个位置都挂满然后操作需要步骤太多，所以我们用7个结点来进行模拟。

代码如下：
```
		HashTable()
		{
			_table.resize(10, nullptr);
		}

		// 插入
		bool Insert(const pair<K, V>& kv)
		{
			// 1查看哈希表中是否存在该键值的键值对，若已存在则插入失败
			// 2判断是否需要调整负载因子，若负载因子过大都需要对哈希表的大小进行调整
			// 3将键值对插入哈希表
			// 4哈希表中的有效元素个数加一


			HashFunc hf;
			// 1、查看键值对，调用Find函数
			Node* key_ = Find(kv.first);
			if (key_) // 如果key_是存在的则插入不了
			{
				return false; // 插入不了
			}

			// 2、判断负载因子，负载因子是1的时候进行增容
			if (_n == _table.size()) // 整个哈希表都已经满了
			{
				// 增容
				// a.创建一个新表，将原本容量扩展到原始表的两倍
				int HashiNewSize = _table.size() * 2;
				vector<Node*> NewHashiTable;
				NewHashiTable.resize(HashiNewSize, nullptr);

				// b.遍历旧表，顺手牵羊，将原始表数据逐个头插到新表中
				for (size_t i = 0; i < _table.size(); ++i)
				{
					if (_table[i]) // 这个桶中的有数据/链表存在
					{
						Node* cur = _table[i]; // 记录头结点
						while (cur)
						{
							Node* next = cur->_next; // 记录下一个结点
							size_t hashi = hf(kv.first) % _table.size(); // 记录一下新表的位置
							// 头插到新表中
							cur->_next = _table[hashi];
							_table[hashi] = cur;

							cur = next; // 哈希这个桶的下一个结点
						}
						_table[i] = nullptr;
					}
				}
				// c.交换两个表
				_table.swap(NewHashiTable);
			}

			// 3、将键值对插入到哈希表中
			size_t hashii = hf(kv.first) % _table.size();
			Node* newnode = new Node(kv);
			// 头插法
			newnode->_next = _table[hashii];
			_table[hashii] = newnode;

			// 4、将_n++
			++_n;
			return true;
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
```
4、哈希表（桶）的查找
1. 通过哈希函数计算出对应的哈希地址
2. 通过哈希地址找到对应的哈希桶中的单链表，遍历单链表进行查找即可
```
		// 查找
		HashNode<K, V>* Find(const K& key)
		{
			//1通过哈希函数计算出对应的哈希地址
			//2通过哈希地址找到对应的哈希桶中的单链表，遍历单链表进行查找即可
			HashFunc hf;
			size_t hashi = hf(key) % _table.size();

			Node* cur = _table[hashi]; // 刚好到哈希桶的位置
			while (cur)
			{
				// 找到匹配的了
				if (cur->_kv.first == key)
				{
					return (HashNode<K, V>*)cur;
				}
				cur = cur->_next;
			}
			return nullptr;
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
```
5、哈希表（桶）的删除
1. 通过哈希函数计算出对应的哈希桶编号
2. 遍历对应的哈希桶，寻找待删除结点
3. 若找到了待删除结点，则将该结点从单链表中移除并释放
4. 删除结点后，将哈希表中的有效元素个数减1
```
		// 删除
		bool Erase(const K& key)
		{
			//1通过哈希函数计算出对应的哈希桶编号
			//2遍历对应的哈希桶，寻找待删除结点
			//3若找到了待删除结点，则将该结点从单链表中移除并释放
			//4删除结点后，将哈希表中的有效元素个数减一
			HashFunc hf;
			size_t hashi = hf(key) % _table.size();
			// prev用来记录前面一个结点，有可能是删除的是哈希桶第一个结点
			// cur记录的是当前结点，当然是要删除的结点
			Node* prev = nullptr;
			Node* cur = _table[hashi];

			while (cur) // 遍历到结尾
			{
				if (cur->_kv.first == key) // 刚好找到这个值
				{
					// 第一种情况：这个要删除的值刚好是哈希桶的头结点
					if (prev == nullptr)
					{
						_table[hashi] = cur->_next;
					}
					// 第二种情况：这个要删除的值不是哈希桶的头结点，而是下面挂的值
					else // (prev != nullptr)
					{
						prev->_next = cur->_next;
					}
					delete cur; // 删除cur结点
					_n--;
					return true;
				}
				prev = cur;
				cur = cur->_next;
			}
			return false;
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
```
6、哈希表（桶）的打印

两个循环，大循环里套一个小循环。
```
		// 打印一下
		void Print()
		{
			// 大循环套小循环
			for (size_t i = 0; i < _table.size(); ++i)
			{
				printf("[%d]->", i);
				Node* cur = _table[i];
				// 小循环
				while (cur)
				{
					cout << cur->_kv.first << ":" << cur->_kv.second << "->";
					cur = cur->_next;
				}
				printf("NULL\n");
			}
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
```
7、哈希表中插入string类型的值

string类型的值我们还没有实现，所以我们使用重载struct使用一个特化模版即能解决这个问题，我们如下代码：

131是一个素数，也可以用其他一些素数代替，主要作用防止两个不同字符串计算得到的哈希值相等
```
	// 模版的特化（其他类型） 
	template<>
	struct DefaultHashTable<string>
	{
		size_t operator()(const string& str)
		{
			// BKDR
			size_t hash = 0;
			for (auto ch : str)
			{
				// 131是一个素数，也可以用其他一些素数代替，主要作用防止两个不同字符串计算得到的哈希值相等
				hash *= 131;
				hash += ch;
			}

			return hash;
		}
	};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
```
七、做个实验–为什么哈希表长度用素数更好

我们用合数和素数两个来说明一下：

10这个合数和11这个素数。
1. 10这个合数的因子：1 2 5 10
2. 11这个素数的因子：1 11
我们根据上面的因子选5个序列进行做实验：

数与数之间间隔1：
s1=:{1 2 3 4 5 6 7 8 9 10}

数与数之间间隔2：
s2={2 4 6 8 10 12 14 16 18 20}

数与数之间间隔5：
s3={5 10 15 20 25 30 35 40 45 50}

数与数之间间隔10：
s4={10 20 30 40 50 60 70 80 90 100}

数与数之间间隔11：
s5={11 22 33 44 55 66 77 88 99 101}

实验一：
将数与数间隔1的序列分别插入到表长为10和表长为11的哈希桶中：

实验二：
将数与数间隔2的序列分别插入到表长为10和表长为11的哈希桶中：

实验三：
将数与数间隔5的序列分别插入到表长为10和表长为11的哈希桶中：

实验四：
将数与数间隔10的序列分别插入到表长为10和表长为11的哈希桶中：

实验五：
将数与数间隔11的序列分别插入到表长为10和表长为11的哈希桶中：

得出结论：

1、大家都间隔为1的时候，不管表长是多少都是均匀分布的。
2、当数与数之间间隔的是哈希表的表长或者是哈希表表长的倍数的时候，必然会产生哈希冲突，从第二个数开始就发生哈希冲突。
3、每当数与数之间间隔表长的因子的间距的时候，产生哈希冲突的概率会变得很大，基本上没三个数就要发生1到2次哈希冲突。

我们发现，素数的因子最少，只有1和它本身！所以素数更加适合做表长！
相关阅读:
Redis（三）session共享
 chmod文档权限
 【仙逆】王林用计灭富二代，有长命锁也没用，藤化元一怒请一人出山
 Java之POI导出Excel(一)：单sheet
面试题53：vue数据的双向绑定原理（如何实现vue的双向绑定）
软件测试中功能测试流程
 lua_gettable 函数详解
 Flask 入门教程
 复杂环境下人形机器人自动导航项目复盘
 Spring Boot 实现跨域的 5 种方式，总有一种适合你，建议收藏
原文地址：https://blog.csdn.net/m0_70088010/article/details/133483476

哈希（哈希表、哈希桶）

一、哈希概念

二、哈希冲突

三、哈希函数

四、哈希冲突解决

1、闭散列–开放定址法

（1）线性探索

（2）二次探索

2、开散列–链地址法

3、闭散区别

五、哈希表的闭散列实现

1、哈希表的结构

（1）疑惑问题 – 为什么要是状态？为什么要三个状态？

先解释用状态

再解释有三个状态

（2）状态和负载因子

（3）前期工作

2、哈希表的插入

3、哈希表的查找

4、哈希表的删除

六、哈希表的开散列实现（哈希桶）

1、哈希表的结构

2、前期准备

3、哈希表（桶）的插入

4、哈希表（桶）的查找

5、哈希表（桶）的删除

6、哈希表（桶）的打印

7、哈希表中插入string类型的值

七、做个实验–为什么哈希表长度用素数更好