C++——哈希讲解

发布时间：2023年12月24日

作者：几冬雪来

时间：2023年12月23日

内容：C++板块哈希讲解

前言：?

unordered系列关联式容器：?

前言：?

在前不久我们讲解了C++板块中的红黑树，而在红黑树这里还有它的封装等操作可以去学习，但是今天我们将讲解C++模板中的另一大重要的知识，也就是经常被程序员谈及的——哈希。

unordered系列关联式容器：?

在正式讲解C++的哈希知识之前，在这个地方需要我们了解一个新的容器，也就是——unordered系列关联式容器。

unordered这个单词在英语中意味着无序，并且unordered可以和map与set组合成unordered_map和unordered_set进行使用，且它们二者的底层都是哈希表。

虽然unordered_map与unordered_set的底层是哈希表，但是它们的使用方法和使用set与map一样，并没有什么明显的改变，但是它们还是有区别的。??

在这里最明显的区别就是，在map与set中它们的迭代器是双向迭代器，可以使用begin，end，rbegin以及rend。

但是与unordered组合的map和set并不是双向迭代器，从上图可以看出二者是单向迭代器。

同时从什么代码运行的结果来看，unordered_map与unordered_set的作用中并没有将插入的数据进行排序，也就是说unordered_map与unordered_set的排序是无序的。

但是二者虽然没有排序的功能，但是它们会进行去重操作。

对比起普通的map与set，unordered_map与unordered_set某些方面的性能高更加的优秀。

哈希的概念：

在我们学习哈希之前，要从一个数组中寻找一个数。在C语言刚开始的时候学习了暴力查找，再后来就是有序数组的二分查找，接下来就是C++中的搜索树，并且也了解了它们实现的理论。

而接下来的哈希，在C++中也可以被称为散列，它的做法是将存储的值跟存储的位置建立出一个对应关系，也就是二者存在着规则。??

要插入数据的时候按照规则去插入，要查找的时候也按照规则去查找。

直接定址法与除留余数法：

在这个地方我们根据上图有关哈希的概念，在插入存储数据这里创建了两种方法。

在上边这种的就是直接定址法，而下边的则是除留余数法。

这里的直接定址法可以达到每一个值都有一个唯一位置，但是也有一个缺点，那就是需要值的分布集中。

而除留余数法则是完全和直接定址法相反，它能适用的值的分布范围可以很分散，但是却。

类似上图，因为24与44余上20最后的结果都为4，因此这里就会导致两个值在同一个位置的情况，而这种情况在哈希中也被称为——哈希冲突。

而解决哈希冲突这里有两种方法。

闭散列：

首先第一种方法就是闭散列——开放定址法，如果当前位置被占用了，则按规则找到下一个位置（占用其他数据的位置）。?

当空间不足的时候就要对其进行扩容操作。

除留余数法：?

再接下来就是除留余数法，这种方法是闭散列的反面。?

在这里我们画了一个图来表达它们，在图中存在一个数组，它的空间大小为10，接下来就将要插入的值映射进去。

这个地方先走因此线性探测，这里如果要想插入一个44的值。此处将值44%10得到的结果是4，因此就先看4的这个位置，如果该位置有值就会产生哈希冲突，为了防止这个问题的发生就需要我们向后走，直到找到一个空位置将这个值插入进去。

如果想再插入一个值，这个值从某处开始走到最后都没了找到空节点，这里的操作并不是采用扩容操作来获取更多的位置。

在学习扩容的时候我们有讲解过，扩容是在数组在没有空间下进行的操作。但是如图，在1到9中存在的许多还未使用的空节点，如果这里我们要再插入的值为19或者29等等，一开始就是在最后一个节点处映射，但是该节点存在值会与要新插入的节点发生哈希冲突。

且编译器会直接帮我们解决没有空间插入的问题。

接下来就是查找的操作?

如上图要查找44这个值的位置，也是一开始从4这个位置开始映射后，如果4这个位置不是则往后直到找到那个值。

这里如果要查找的值为54，还是从4这个位置开始映射，接下来继续往后走，直到空位置则停下来。（并不是走一圈）?

这里也有间接看出，如果我们的表里面的值太满的话，会导致它的效率变低。

而且这里又引出了另一个问题，那就是它的删除问题。

按照我们以前学习的知识，如果要将某一个位置的值删除，最后都不免都有置空的操作。但是在这个地方并不能使用这种操作来解决问题。

在上面查找的时候有提及，查找到空的话就停止查找。

这里如果将6这个值的位置删除后置空，接下来如果想要去找44这个值，依旧是从4这个地方开始映射，但是这个地方到6位置为空就停止查找了。?

状态标记：?

而且这里解决上面的删除可能会出现的问题，我们进行了一个状态标记的操作。

这里就是状态标记，如果要将6这个位置的值删除，但是这个地方并不是将它删除后置空，这里的做法是将它的状态标记改为DELETE。

如果在查找的过程中遇到DELETE的状态标记的话，这里不需要停止而是继续往下找。

开放定址法（线性探测）：?

在上面讲解的除留余数法，状态标记等操作，在这个地方被称为开放定址法或者线性探测。

而且在了解以上操作之后，接下来就是对线性探测的代码进行书写了。

创建：?

首先要正式书写插入，删除，查找等代码之前，这里需要先对其进行创建。

首先因为这里进行的操作是简单的插入，删除和查找数据，因此这里我们就可以使用vector来进行这些操作。?

接下来就是枚举除哈希的三种状态标记。

再接下来就是用一个KV模板构造出HashData中的要插入的数据和它的状态标志。

最后再使用一个KV模板来定义_table和初始化存储有效数据的个数。?

做好以上这些就能书写我们的插入操作了。

插入：

在经过上面的创建之后，接下来就是对插入代码的书写了。?

首先这里的插入函数的类型是bool类型，因为要插入的值不能被修改，因此在函数参数这里要使用const类型。?

这里首先就要计算出它的起始位置，这里要%的是表的size而不是capacity。

接下来就是判断，如果要插入的地方的状态标记是存在数据的话，这里就要让hashi进行++操作，走到下一个位置，再将hashi进行%size的要绕回去，也可以当hashi的大小等于size的时候进行置0操作。

如果它的状态标志不是存在的话，这里就将数据插入，并将状态标志改为存在，最后++有效数据的个数。

负载因子（载荷因子）：?

在什么我们书写了线性探测的基本的插入代码，但是这并不意味着插入的代码到这里就结束了。

在先前介绍除留余数法与闭散法的时候我们有说道过，对比闭散法，除留余数法的扩容情况有所不同，因为除留余数法要求它有足够的空间，里面的数据不能是满数据。

因此这里对哈希进行扩容就涉及到了负载因子。?

而这里的负载因子也有一套计算公式。

这里负载因子等于表中的元素个数除以散列表的长度。

这里表示的就是存入数据的个数占总空间的比例。

如果负载因子越大，那么冲突的概率就越大，但是它的空间利用率高，相反负载因子越小，冲突的概率也就会越小，空间利用率低。

而这里在负载因子到什么程度的情况下进行扩容也是一个问题。

在这个地方有规定，一般的编译器在负载因子到达70%~80%左右就需要进行扩容，这里JAVA有明确规定为75%。

扩容：?

在了解完了负载因子后，接下来就是对代码进行扩容操作。

以前学习C语言或者C++学习的时候经常会使用到扩容的操作。

在上面我们得知负载因子如果大于70%的话，这里就要进行扩容操作。

上面的代码首先在插入操作外进行初始化操作，先将它定义10个空间大小的位置出来。

接下来就是插入语句在一开始进行判断操作，在这里判断有效值的个数除于整个空间大小，它的负载因子有没有超过70%。

如果超过了，这里就将存放的空间扩大两倍，然后将原数据放进去。

但是操作到这一步还没有结束。、

可以看见，如果进行了扩容操作，空间大小从原本的10变为了20，这也就导致了映射的位置发生了改变。

这里如果原先要找111值的位置，映射的地方为111%10，最后的结果为1。但是因为扩容操作，这里映射的地方就从111%10变成了111%20，最后的结果为11，就要从后面开始找，最后导致找不到111这个值。

同时这个操作也可能会导致一些原本冲突的不冲突，原先不冲突的冲突的情况。

而这里的解决这个问题的操作就是在扩容后，因为映射关系发生了改变，因此需要进行重新的映射，相当于将原来的值插入进去。

接下来就是代码的修改。

首先还是判断负载因子的百分之有没有超过70%。

如果超过了70%，这里开始先开一个原空间两倍大的空间，然后再定义一个KV函数，将它的空间大小定义为新空间的大小，也就是原空间的两倍。

接下来就是遍历旧表，使用for循环语句。如果旧表该处的值状态为存在，这里就需要将旧表中的值插入到新表中，如果这里的空间的状态为删除状态的话，我们也是不需要将其插入到新表中的。

插入数据到新表后，再对其进行映射操作，在映射结束后将新表和旧表进行交换即可。

查找：

增删查改在书写完了插入操作后，接下来就是对查找操作代码的书写。

同样的哈希的查找代码也是十分的简单。

这里就是查找数据的代码。

首先先进行映射操作，先映射位置。接下来就是判断如果该映射位置的状态标志不为空则进入循环。

再然后就是查找数据，这里要注意判断语句中一定要判断它的状态标记是存在才能执行代码。因为在什么说过我们删除数据并不是真的删除而是将它的状态标记改为删除，如果不判断的话可能会找到删除的位置。

如果找到了值则进行类型转换返回它的位置，如果还没找到且没到空则继续往下找，如果找到空位置还没找到的话这里就返回空。

删除：

在我们之前学习的一系列的搜索数的代码，无疑都是删除代码书写的难度要高于插入代码书写的难度。

但是在哈希这里，两种情况则相反了过来。

这里就是删除的代码，对比以往复杂的代码，哈希的删除操作只需要将状态标记进行修改即可。

首先定义一个变量来存放想删除的值，这里想查找的key值因为不能被修改，因此要加上const。

如果要删除的值存在则满足判断语句的要求进入判断语句，将要删除的值的状态标记改为DELETE，同时将数据的有效值减一，最后返回true。

这里如果找不到就直接返回false。

取模问题（%）：

在解决完了增删查之后，之后就是哈希中的一个重要的问题了，也就是key的取模问题。

也就是在代码中key不单单为正整数可以被_table.size()整模，key也可以是double类型，也可以是char类型等，而这些类型就不能被取模。

而这里的解决方法就是进行两次映射。

举一个例子，如果key是一个字符串这里第一次映射就要将这个字符串映射成整形，在这样的情况下进行第二次映射，将这个整形映射到存储位置。

这里的第一次映射就成为了我们要解决的问题。

这里要从其他不可被取模的类型转换为整形，在这个地方我们不能使用以往的方法。

在这个地方能采取的方式只有去使用仿函数。

而下来就需要我们去写出仿函数的代码。

在这里为哈希表增加一个模板参数，该模板参数是一个仿函数，仿函数提供的默认仿函数和我们输入的仿函数，系统默认的仿函数可以将一些常见的key的类型全部转化为整形。

类似上图，如果提供的K为int或者double类型则仿函数执行DefaultHashFunc将它们转换为整形，如果输入的K是string类型则执行下面的函数，返回字符串首个元素的ASCII值。

同时，因为函数模板中增添了一个模板参数，因此在下面插入时候定义新节点，插入中取模，又或者是查找时候进行的取模操作，它们的代码都需要进行改变。

类似插入节点处就是将它的模板类型中多书写应该模板参数，而且取模操作处需要用仿函数定义一个变量，而后使用它对K值进行第一次映射操作。

string冲突问题：

在上面我们解决了最基础的取模会出现的问题，而在这里我们将对上面的代码进行优化。

上面处理string转整形的方法是取这个字符串的首元素的ASCII码值，但是如果是采用这种解决方法的话，这就会导致因为映射规则单一取材太多而很容易发生冲突。

这里第一个解决方法就是将这个字符串的所有的ASCII码值加到一起，这样就能避免因为首元素的ASCII码值相同而带来的冲突。

但是同样的这种解决方法也不是很合适，虽然它对比起取首元素的ASCII码值冲突确实减少了很多。

就像图中如果是以前的代码就会因为s1与s2因为首元素相同，它们的ASCII码值也相同的缘故而发生冲突。

这里将所有的ASCII码值加起来则会避免这个问题，但是这种方法也有另一个弊端。

就如图中我们后面的两个函数，它们的首元素的ASCII码值不相同，按照原来的取模方法，这个地方二者是不会发生冲突的。

但是就是因为它们的ASCII相加起来的值是一样而产生了冲突。

要在这种情况下进一步的减少冲突，这里就要说到字符串的哈希算法。

这里的做法依旧是把ASCII值相加起来，只不过每次相加之前，上一个ASCII值就需要乘上131。

这里每次加上ch之前，就将上一个哈希的值乘上131，从展示窗口来看，s1与s2映射出来的整形值依旧不同，同时“az”与“za”两个字符串的结果也是不一样的。

并且此处也不用担心字符串过长导致最后得出来的整形过长的问题，这里编译器在运行的过程中会帮助我们进行截断操作。

哈希桶：

在上面我们讲解了一种处理哈希冲突的方法，也就是开放定址法。

这种开放定址法虽然好用，但是它有一个很明显的缺点，那就是它占用了其他数据的空间，冲突会相互影响到。

例如图中在5这个位置发生冲突，会影响4的查找同时也会影响到后面值的插入。

这是因为开放定址法始终还是在内部找空间，也就是占其他数据的空间。

而为了让数据不互相占用其他数据的空间，这里就研究出来了一种方法，这种方法叫做拉链法，同时它也就一个更熟悉的叫法——哈希桶。

这个地方的做法就是将我们的数组定义为指针数组，使冲突的数据外部消化。

例如图中就是制作了一个链表，就像这里一开始插入1处的值为11，我们就可以将它链接在1这个位置的，接下来要再插入一个值为111的话，因为该处的状态标志在插入11的时候已经被修改为了存在，因此这里我们就只需要将111链接到11的后面即可。

创建：

在介绍完了哈希桶的具体做法之后，接下来就是对其代码的书写。

与开放定址法一样，一开始我们还是要将它的基础部分都写出来。

与开放定址法不同，因为哈希桶是一个指针数组，因此在参数实例化处实例化处应该指针与构造出来的KV函数。

接下来再在下一个模板中使用vector定义一个Node*的_table同时也定义出一个整形来计算存储的有效的个数。

插入：

在接下来就是插入操作，这里的插入操作相比较于开放地址法要简单许多。

首先在这里先借用HashTable来对_table申请10个空间，并将它们都置为空。

这里的插入操作为头插，首先还是定义一个整形来接收映射出来的整形值。?

接下来用Node*指针定义一个新的节点，而节点里面则是我们要插入的kv。下来就是进行指针节点的链接。

最后将存储的有效值进行++操作，并返回true。

而这里的节点的链接我们就画一个图出来表示。

这里我们将新创建的节点的next指向原指针数组的_table的某个位置。

接下来将这个要新插入的节点给赋值为该指针节点的头节点即可（如图），这里就是我们哈希桶的头插操作。

扩容（概念）：

接下来就是讲解哈希桶的扩容操作，按照我们对哈希桶的描述，哈希桶就是一个指针数组，每插入一个值就将这个值映射到它的整形位置后，进行头插操作，与之前的值进行链接操作。

这里相比较于开放定址法的每一个值都对应每一个地址不一样，如果不进行扩容是会导致哈希表和负载因子判断，哈希表的容量是会满的。

按道理指针数组完成上面的操作完全不需要扩容，每创建一个指针就将其链接即可。

这里其实可以进行扩容也可以不进行扩容，首先因为节点连接的缘故，即使在哈希表中10个位置都存在值的情况下我们依旧可以继续插入操作。

但是如果只有10个位置，如上图，如果插入100个值的话，平均每个位置就是10个节点链接，同理如果插入10000个值，那么平均每个位置插入的节点的数量为1000。

这样不扩容的，我们就无法去保障它的效率，后面的删除和查找操作都会受到它的影响。

而要实现这里的操作函数要运用到负载因子。

负载因子（哈希桶版本）：

这里要对哈希桶进行扩容还是要运用到负载因子，但是因为扩容的概念不同，因此它们的扩容的负载因子也有所不同。

在开放定址法处需要扩容的条件是负载因子大于70%，而在这里哈希桶负载因子可以进一步扩大，扩大到负载因子为1的时候才需要扩容。

同时因为有扩容操作的进行，原先冲突的值可能不冲突了，原先不冲突的值可能冲突了。

扩容（操作）：?

在了解完了一系列操作之后，接下来就是对其扩容代码的书写。

上图就是扩容的代码。

首先就是判断负载因子，如果负载因子为1（100%）的话，这里首先要创建一个新表，新表的空间是原本的二倍，然后将其置空。

接下来使用循环语句取原表的第一个值，如果原表的值不为空则进入while循环，在循环中先用一个节点保存第一个值的下一个节点的位置。

接下来就是取模，确定该值在新表中映射的位置，接下来就是进行头插操作，头插结束后把一开始保存第一个值的下一个节点的位置置为要判断的节点，依次循环，直到该节点的下一个节点为空停止循环。

接下来要做的就是将原表置空，然后让原表和新表进行交换。

查找：

接下来在插入数据后就是要从哈希表中查找出我们想要的数据。

这里就是我们的查找操作，先用要查找的值进行映射，找到它的映射位置。

接下来确定该位置的首个节点，并以它为条件进行循环语句，如果在该位置的节点没有找到我们想要的值，这里就走它的下一个节点。

如果最后找到空都没找到，这里就返回空。

同时因为查找的代码的出现，这里我们要将开放定址法与哈希桶的插入位置都加上查找的判断，如果要插入的数据在原哈希表中可以查找得到，那么这里就不被允许插入，这里就返回false。??

删除：?

增加和查找的代码都书写完了，接下来就轮到哈希桶的删除操作了。

因为在书写哈希表的时候我们使用的是vector，也就是单向链表，这也就意味着在删除该节点的时候要先保留上个节点，并且与要删除节点的下一个节点相链接。

同时这个地方也要处理在不同位置进行删除时，可能会存在不同的操作。

这里要进行分类讨论，如果要删除的值cur前面存在节点的话，这里就让上一个节点连接要删除节点的下一个节点即可。

但是如果要删除的节点的前一个位置为空，这里就证明了该节点为第一个值，这个地方要做的就是将该节点删除也就是头删操作，用该节点的下一个节点做第一个值。

在这个地方又因为是单向链表的缘故，我们不能去附用查找的代码去查找要删除的值的位置。

这里就是我们删除的代码，第一步还是要进行映射操作，映射出来要删除的值的位置。

接下来就是创建一个节点用来保存要删除的节点的上一个节点的位置，然后将这个新节点置空。

接下来就是判断，如果这个地方prev等于空的时候找到要删除的值，这里就证明要删除的值是该位置的第一个值，这里就进行头删操作。

如果在开头位置没找到要删除的节点的话，这里就让prev和cur一起向下走，此时prev不为空的时候找到要删除的值，就让prev的下一个位置链接要删除节点cur的下一个位置。

到最后都要将删除的节点delete。?

处理string冲突问题：?

同样的哈希桶在这里也需要处理K为string，也就是为字符串的情况。

这里我们就直接调用开放定址法解决哈希冲突的代码来给予哈希桶使用即可。

这里也是同样的做法，在函数的模板参数中增加一个HashFunc，而后每次要进行映射之前用HasahFunc定义一个hf，每次进行取模之前先进行一次防止string或者其他类型冲突的映射。

析构：?

同时要注意这里哈希桶与开放定址法不同的地方就在于哈希桶没有自动析构的操作。

在这个地方哈希桶的析构函数需要我们自己去书写。

代码：?

哈希.h?

#pragma once
#include<vector>
#include<string>

using namespace std;
using std::pair;
using std::vector;


template<class K>
struct DefaultHashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

template<>
struct DefaultHashFunc<string>
{
	size_t operator()(const string& str)
	{
		size_t hash = 0;
		for (auto ch : str)
		{
			hash *= 131;
			hash += ch;
		}

		return hash;
	}
};

//开放定址法
namespace open_addr
{
	enum STATE
	{
		EXIST,
		EMPTY,
		DELETE
	};

	template<class K, class V>
	struct HashData
	{
		pair<K, V> _kv;
		STATE _state = EMPTY;
	};

	//struct StringHashFunc
	//{
	//	size_t operator()(const string& str)
	//	{
	//		return str[0]; 
	//	}
	//};


	template<class K, class V, class HashFunc = DefaultHashFunc<K>>
	class HashTable
	{
	public:
		HashTable()
		{
			_table.resize(10);
		}

		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
			{
				return false;  
			}
			if ((double)_n / _table.size() >= 0.7)
			{
				size_t newSize = _table.size() * 2;
				//遍历旧表，重新映射
				HashTable<K, V, HashFunc> newHT;
				newHT._table.resize(newSize);

				for (size_t i = 0; i < _table.size(); i++)
				{
					if (_table[i]._state == EXIST)
					{
						newHT.Insert(_table[i]._kv);
					}
				}

				_table.swap(newHT._table);
			}
			HashFunc hf;
			size_t hashi = hf(kv.first) % _table.size();
			while (_table[hashi]._state == EXIST)
			{
				++hashi;
				hashi %= _table.size();
			}

			_table[hashi]._kv = kv;
			_table[hashi]._state = EXIST;
			++_n;

			return true;
		}

		HashData<const K, V>* Find(const K& key)
		{
			HashFunc hf;
			size_t hashi = hf(key) % _table.size();
			while (_table[hashi]._state != EMPTY)
			{
				if (_table[hashi]._state == EXIST && _table[hashi]._kv.first == key)
				{
					return (HashData<const K, V>*) & _table[hashi];
				}

				++hashi;
				hashi %= _table.size();
			}

			return nullptr;
		}

		bool Erase(const K& key)
		{
			HashData<const K, V>* ret = Find(key);
			if (ret)
			{
				ret->_state = DELETE;
				--_n;

				return true;
			}
			return false;
		}

	private:
		vector<HashData<K, V>> _table;
		size_t _n = 0;//存储有效数据的个数
	};
}

//namespace hash_bucket
//{
//	template<class K,class V>
//	struct HashNode
//	{
//		pair<K, V> _kv;
//		HashNode<K, V>* _next;
//	};
//
//	template<class K,class V>
//	class HashTable
//	{
//		typedef	HashNode<K, V> Node;
//	public:
//		HashTable()
//		{
//			_table.reserve(10, nullptr);
//		}
//
//		bool Insert(const pair<K, V>& kv)
//		{
//			size_t hashi = kv.first % _table.size();
//			Node* newNode = new Node(kv);
//			newNode->_next = _table[hashi];
//			_table[hashi] = newNode;
//		}
//
//	private:
//		vector<Node*> _table;
//		size_t _n;
//	};
//}

//哈希桶
namespace hash_bucket
{
	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 HashFunc = DefaultHashFunc<K>>
	class HashTable
	{
		typedef HashNode<K, V> Node;
	public:
		HashTable()
		{
			_table.resize(10, nullptr);
		}

		~HashTable()
		{
			for (size_t i = 0; i < _table.size(); i++)
			{
				Node* cur = _table[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_table[i] = nullptr;
			}
		}

		bool Insert(const pair<K, V>& kv)
		{
			HashFunc hf;
			if (Find(kv.first))
			{
				return false;
			}
			if (_n == _table.size())
			{
				size_t newSize = _table.size() * 2;
				vector<Node*> newTable;
				newTable.resize(newSize, nullptr);

				for (size_t i = 0; i < _table.size(); i++)
				{
					Node* cur = _table[i];
					while (cur)
					{
						Node* next = cur->_next;
						
						size_t hashi = hf(cur->_kv.first) % newSize;
						cur->_next = newTable[hashi];

						newTable[hashi] = cur;
						cur = next;
					}

					_table[i] = nullptr;
				}
				_table.swap(newTable);
			}

			size_t hashi = hf(kv.first) % _table.size();
			Node* newNode = new Node(kv);
			newNode->_next = _table[hashi];
			_table[hashi] = newNode;
			++_n;
			return true;
		}

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

		bool Erase(const K& key)
		{
			HashFunc hf;
			size_t hashi = hf(key) % _table.size();
			Node* prev = nullptr;
			Node* cur = _table[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (prev == nullptr)
					{
						_table[hashi] = cur->_next;
					} 
					else
					{
						prev->_next = cur->_next;
					}

					delete cur;
					return true;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}
		}

		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 = cur->_next;
				}
				printf("NULL\n");
			}
		}

	private:
		vector<Node*> _table;
		size_t _n;
	};
}

哈希.cpp

#include<iostream>
#include<unordered_map>
#include<unordered_set>
#include"哈希.h"

using namespace std;

//int main()
//{
//	unordered_set<int> us;
//	us.insert(3);
//	us.insert(1);
//	us.insert(4);
//	us.insert(5);
//	us.insert(8);
//	us.insert(5);
//
//	auto it = us.begin();
//	while (it != us.end())
//	{
//		cout << *it << " ";
//		++it;
//	}
//	cout << endl;
//
//	return 0;
//}

//int main()
//{
//	/*HashTable<int, int> ht;*/
//	HashTable<int, int> ht;
//	int a[] = { 1,111,4,7,15,25,44,9 };
//	for (auto e : a)
//	{
//		ht.Insert(make_pair(e, e));
//	}
//	/*HashTable<string, string> dict;
//	dict.Insert(make_pair("sort", "排序"));
//	dict.Insert(make_pair("left", "xxx"));
//	auto kv = dict.Find("left");
//	kv->first = "xx";
//	kv->second = "左边";*/
//	auto ret  = ht.Find(4);
//	//ret->_kv.first = 40;
//	ret->_kv.second = 400;
//	
//
//	return 0;
//}

//int main()
//{
//	/*HashTable<int, int> ht;*/
//	HashTable<string, string> ht;
//	ht.Insert(make_pair("sort", "排序"));
//	ht.Insert(make_pair("left", "xxx"));
//	/*HashTable<string, string> dict;
//	dict.Insert(make_pair("sort", "排序"));
//	dict.Insert(make_pair("left", "xxx"));
//	auto kv = dict.Find("left");
//	kv->first = "xx";
//	kv->second = "左边";*/
//	auto ret = ht.Find("left");
//	//ret->_kv.first = 40;
//	ret->_kv.second = "左边";
//
//	string s1("xxx");
//	string s2("xxx");
//
//	DefaultHashFunc<string> hf;
//	cout << hf(s1) << endl;
//	cout << hf(s2) << endl;
//
//
//	return 0;
//}

//int main()
//{
//	string s1("xxy");
//	string s2("xxx");
//
//	open_addr::DefaultHashFunc<string> hf;
//	cout << hf(s1) << endl;
//	cout << hf(s2) << endl;
//	cout << hf("az") << endl;
//	cout << hf("za") << endl;
//
//
//	return 0;
//}

int main()
{
	hash_bucket::HashTable<int, int> ht;
	int a[] = { 1,111,4,7,15,25,44,9 };
	for (auto e : a)
	{
		ht.Insert(make_pair(e, e));
	}

	ht.Insert(make_pair(24, 24));
	ht.Insert(make_pair(6, 6));
	ht.Insert(make_pair(12, 12));

	ht.Erase(4);
	ht.Erase(24);
	ht.Erase(44);


	ht.Print();

	return 0;
}

结尾：

到这里我们C++板块的一个重要的知识点就讲解完毕了，与红黑树和AVL树一样，哈希表在后面学习或者现实生活又或者考试中都会经常出现，想要更进一步的了解哈希，就需要对其进行更加深入的学习。最后希望这篇博客能带来帮助。

文章来源:https://blog.csdn.net/dongxue727504/article/details/134844687
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！