【高阶数据结构】哈希表详解

举报
YIN_尹 发表于 2023/12/23 21:11:06 2023/12/23
【摘要】 @[TOC]前言<font color = black>上一篇文章我们学习了STL中unordered系列容器的使用，并且提到，unordered系列容器的效率之所以比较高（尤其是查找），是因为它底层使用了哈希结构，即哈希表。那这篇文章，我们就来学习一下哈希表1. 哈希的概念<font color = black>顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个...

@[TOC]

前言

<font color = black>上一篇文章我们学习了STL中unordered系列容器的使用，并且提到，unordered系列容器的效率之所以比较高（尤其是查找），是因为它底层使用了哈希结构，即哈希表。

那这篇文章，我们就来学习一下哈希表

1. 哈希的概念

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

理想的搜索方法：

<font color = "#000066">可以不经过任何比较，一次直接从表中得到要搜索的元素。 如果构造一种存储结构，<font color = red>通过某种函数(一般称为哈希函数hashFunc)使元素的存储位置与它的关键码之间能够建立一 一映射的关系，那么在查找时通过该函数可以很快找到该元素

当向该结构中：

插入元素

<font color = blue>根据待插入元素的关键码，以此函数（即上面提到的哈希函数）计算出该元素的存储位置并按此位置进行存放

搜索元素

<font color = blue>对元素的关键码进行同样的函数计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功

<font color = "#000066">该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)

举个栗子：

<font color = black>待插入数据集合{1，7，6，4，5，9} 哈希函数设置为：hash(key) = key % capacity（ capacity为存储元素底层空间总的大小） 假设表的capacity为10，那插入之后就是这样的 在这里插入图片描述 那查找的时候我们直接通过函数获取下标位置查找即可 用该方法进行搜索不必进行多次关键码的比较，元素的存储位置与它的关键码之间能够建立一 一映射的关系，那么在查找时通过该函数可以很快找到该元素，因此搜索的速度比较快

但是，按照上述哈希方式，向集合中插入元素44，会出现什么问题？

<font color = black>44%10结果也是4，但是之前4这个元素已经存在下标为4的位置了！

那这种现象我们把它叫做哈希冲突。

2. 哈希冲突

对于两个数据元素的关键字$k_i$和 $k_j$(i != j)，有$k_i$ != $k_j$，但有：Hash($k_i$) == Hash($k_j$)，即：

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

那引起哈希冲突的一个原因可能是：

<font color = "#000066">哈希函数设计不够合理

那下面我们来介绍一下哈希函数。

3. 哈希函数

哈希函数（Hash Function）在哈希表中起着关键的作用。它接收键作为输入，并计算出一个索引或哈希码，用于确定键在哈希表中的位置。

哈希函数设计原则：

  1. <font color = "#000066">哈希函数的定义域必须包括需要存储的全部关键码，如果散列表允许有m个地址时，其值域必须在0到m-1之间

  2. <font color = "#000066">哈希函数计算出来的地址能均匀分布在整个空间中

  3. <font color = "#000066">哈希函数应该比较简单

那常见的哈希函数都有哪些呢？

3.1 直接定址法（常用）

第一种哈希函数——直接定址法：

<font color = blue>取关键字的某个线性函数为散列地址（通常是键值直接映射）：Hash（Key）= A*Key + B 优点：简单高效 缺点：适用场景有限 使用场景：适合于键值比较均匀、分布比较集中的情况

我们之前文章里讲过一道题：

<font color = black>在这里插入图片描述 就这个，这道题其实就用了哈希的思想

我们来复习一下。

当时讲的思路是这样的：

<font color = black>字符串中字符的范围就是【a,z】，那我们就可以创建一个大小为26的整型数组，然后用一个相对映射去统计每个字母的出现次数，a就映射到下标为0的位置，b就映射到下标为1的位置，依次类推。 那怎么让这些字母映射到对应的位置呢？ 减去’a’得到的值是不是就是它们映射的位置啊，然后遍历字符串，每个字母映射的值是几，就让下标为几的元素++，初值全为0，这样遍历过后每个字母出现的次数就统计出来了。（下标0的元素的值就是a出现的次数，1位置就是b出现的次数…） 但是现在有一个问题，那就是出现一次的字母可能不止一个，我们怎么判断那个是第一个只出现一次的字母呢？ 🆗，这里我们不要去遍历统计次数的数组，还是从前往后去遍历字符串，然后看哪个字母的次数是1，第一个是1的就是第一个只出现一次的字母。 在这里插入图片描述 这是我们当时写的代码。 <font color = "#000066">大家看这不就是运用了哈希的思想嘛——使元素的存储位置与它的关键码之间能够建立一 一映射的关系。 这里用的哈希函数就是一种直接定址法嘛，哈希函数就是key-'a'

当然现在我们学了unordered系列的容器就可以这样写了：

<font color = black>在这里插入图片描述 统计次数用unorder_map就行了。

但是，我们上面提到，直接定址法只适用于键值比较均匀、分布比较集中的情况：

<font color = black>比如这种情况 在这里插入图片描述 如果我们选择用键值直接映射（直接定址法：Hash（Key）=key），当前这几个值的话开这10个空间就够了，但是如果是这样一组值呢？ 4，5，12，33，55，1555，2333 难道我们要开2333个空间吗？ 可以是可以的，但是不就太浪费了嘛。

所以呢，除了直接定址法，还提供了一些其它的哈希函数

3.2 除留余数法--(常用)

什么是除留余数法呢？ 其实最开始给大家介绍的那个例子里面的哈希函数就是除留余数法。

除留余数法的概念：

<font color = blue>设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m)，将关键码转换成哈希地址

举个例子：

<font color = black>比如有这样一组值：1 2 5 1333 2447 如果用直接定址法的话，搞一个绝对映射，那就需要开好多个空间。 但是如果用除留余数法的话，那我们可以只开10个空间，p取10 那存储结果就是这样的 在这里插入图片描述 这样虽然key值得分布很不均匀，但是我们也能耗费比较小的空间把他们存起来。

但是，有没有什么问题呢？

<font color = black>如果我再加几个值，比如122，255，347，12 在这里插入图片描述 这是是不是会出现一个问题，就是我们上面提到的哈希冲突/哈希碰撞

那问题来了，对于哈希冲突，我们如何解决呢？

<font color = "#000066">哈希冲突的解决是我们下面要重点讲解的一个问题。 不过，在讲解之前，还有几个哈希函数需要我们了解一下，下面几个不常用，所以我们了解即可

3.3 平方取中法--(了解)

<font color = "#000066">假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址；再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址 平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况

3.4 折叠法--(了解)

<font color = "#000066">折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址（因为散列低地址不能超过表长）。 折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况

3.5 随机数法--(了解)

<font color = "#000066">选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key)，其中random为随机数函数。 通常应用于关键字长度不等时采用此法

3.6 数学分析法--(了解)

举个例子供大家了解一下：

<font color = black>有学生的生日数据如下： 年.月.日 75.10.03 75.11.23 76.03.02 76.07.12 75.04.21 76.02.15 ... 经分析，第一位，第二位，第三位重复的可能性大，取这三位造成冲突的机会增加，所以尽量不取前三位，取后三位比较好。

注意：

<font color = blue>哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突。

所以接下来我们就来讲一下如何处理哈希冲突。

4. 哈希冲突的解决方法及不同方法对应的哈希表实现

<font color = blue>解决哈希冲突两种常见的方法是：闭散列和开散列

4.1 闭散列（开放定址法）

闭散列：

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

那如何寻找下一个空位置呢？

线性探测

线性探测：

<font color = blue>从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止，将新插入的值放到该空位置。 即$H_i$ = ($H_0$ + $i$ )% m，i=1,2,3,4... $H_0$是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小，$H_i$是向后探测的位置 <font color = black>为什么加完i还要模m呢，因为一直加的话可能会超过表长，这时就要回到开头往后进行探测了

比如上面我们举例的那种情况：

<font color = black>在这里插入图片描述 现在我要插入122，那根据哈希函数122%10定位到下标为2的位置，但是这个位置已经被占用了，怎么办？ 向后进行线性探测，找下一个空位置，所以122就会放到下标4这个位置 在这里插入图片描述 那后续的插入如果发生冲突也是如此 当然如果插入满了的话肯定要涉及到扩容的问题，这个我们后面会说。

那大家觉得线性探测这样搞好不好啊，我们来简单分析一下：

<font color = "#000066">线性探测优点：实现非常简单， 线性探测缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”（我向后探测放到后面的空位置就占用了别的位置，其它key定位到这个位置也需要再向后探测），即：冲突值占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较（从冲突位置可能要向后查找多次），导致搜索效率降低。 可以认为闭散列本质是就是一种零和游戏

那如何缓解呢？

二次探测（平方探测法）

二次探测的产生呢能够在一定程度上缓解上面的问题：

<font color = "#000066">二次探测找下一个空位置的方法为： $H_i$ = ($H_0$ + $i^2$ )% m 或者：$H_i$ = ($H_0$ - $i^2$ )% m 其中：i = 1,2,3…， $H_0$是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小，$H_i$是向后探测的位置

那我们看到：

<font color = black>二次探测它在向后探测的过程中使用了二次增量（第一次冲突+$1^2$，第二次+$2^2$，第三次+$3^2$...），而不是线性增量，这样在寻找下一个可用槽位时，可以跳过一些位置，从而减少关键字在哈希表中的聚集程度，提高散列效果。

4.2 闭散列哈希表实现

闭散列的插入

<font color = black>那我们接下来一起来探讨一下，以闭散列线性探测的方式处理哈希冲突（哈希函数我们以除留余数法为例），具体如何进行插入删除，并带大家实现一下相关的代码

我们先来分析一下插入：

<font color = "#000066">那思路是很清晰的，也比较简单：

  1. <font color = blue>首先通过哈希函数获取待插入元素在哈希表中的位置

  2. <font color = blue>然后如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素 在这里插入图片描述 <font color = black>这里前面几个值插入都没有冲突，直接根据哈希函数获得的位置插入即可，44插入发生冲突，进行线性探测，探测到下一个空位置8进行插入。

闭散列的删除

然后我们分析一下删除：

大家想一下要删除一个值的时候怎么做？

<font color = "#000066">比如这样的场景： 在这里插入图片描述 我们能看出来现在是存在一些冲突的。 假设我们现在要删除33，怎么做？ 那首先我们还是根据哈希函数确定它的映射，33%10结果是3，但是3这个位置现在不是存的33，那这能证明33不存在吗？ 不能，因为他有可能发生了冲突在后面存着呢，所以如果第一次没找到的话就要线性探测继续往后找（找到这个过程和你如何存是对应着的），那这里我们往后一个位置就找到了。

那找到了，如何删除呢？

<font color = black>把后面的值移动覆盖吗？ 那这样效率就太低了。 那做一个标识吗？ 比如删除一个值之后把它置成0或者-1表示这个位置为空（那最开始可以把所有位置初始化成0或-1表示全空）。 好像也不好，如果你要存的就是0或-1呢。

另外如果这样处理的话，会影响到查找。

<font color = black>大家想一下查找一个值的话什么时候结束？ 其实分为两种情况，如果不冲突的话，其实一下直接就找到了，因为不冲突的话他就直接存到哈希函数确定的那个映射位置了。 如果冲突的话，就往后探测嘛，我们这里是线性探测，那就继续往后找，那往后找的话找到了好说，找不到的话，什么时候结束呢？ 走到哈希表结尾吗？ 那这样如果表比较长就太慢了，效率太低了。当然其实也不需要走到表尾。 大家看 在这里插入图片描述 比如这种情况，我们现在查找13 那首先定位到下标3这个位置，但是不是，所以要往后探测，一直走到5这个空位置，还是没有找到，大家想，还有必要往后查找吗？ 我们查找的时候是按照对应的探测方法去查找的，所以我们往后查找的值一定是对应位置的冲突值，如果走到一个探测位置为空了，那就说明从这个位置开始以及后面都没有其它冲突值了，后面即使还有值它们对应的散列地址都跟你查找的这个不是一个值了，所以也没必要再往后查找了。 就我们当前这个情况，查找13的散列地址是3，但是那个空位置后面其它非空值的散列地址都不是3了。

那我们再过回来，上面那样删除如何就影响查找了呢？

<font color = black>回到上面删除的场景——删除33 在这里插入图片描述 删除之后是这样的 那然后我想查找13，大家看，现在能查找到吗？ 按照我们上面的分析，正常查找到空就结束了，现在查找13的话散列地址是3，从下标3的位置开始，走到空并没有找到，因为要查找的13在空位置的后面。 但是这里13是真的不存在吗，我们看到并不是。

所以上面的删除方法是不行的，那如何搞呢？

<font color = blue>🆗，我们这里采用标记的伪删除法删除一个元素

伪删除法

那具体怎么做呢？

我们给每个位置增加一个状态：

<font color = "#000066">状态有三种取值——空、存在、删除 空不用解释，存在就是当前这个位置有值，删除就是这个位置存过值，但是现在被删除了。 这样我们进行相应的操作之后去该这个状态就行了（当然初始状态就应该全为空）

结构定义

那接下来我们就来实现一下代码，这里我们以KV模型为例

首先我们定义一下大致的结构：

<font color = black>在这里插入图片描述

然后哈希表的底层结构呢一般就使用数组，那我们用vector就可以了，也很方便

<font color = "#000066">那用vector的话需要我们增加一个变量来记录哈希表中的数据个数。 那大家可能会疑问用vector的话vector.size()不就是数据个数嘛。 注意我们这里的插入不像vector的正常插入那样，从前往后连续插入，我们是按照得到的散列地址去插入的，vector的size不一定就是我们真实插入数据的size，而且我们哈希表删除只是把状态置为删除，也不会影响vector的size。 这里大家要区分一下。 在这里插入图片描述

插入函数insert实现

那然后我们来写一下插入——Insert

<font color = black>在这里插入图片描述 首先第一个问题，我们这里用vector实现哈希表，那我们除留余数法模的这个值应该是size还是capacity？ <font color = "#000066">🆗，这里不能去%capacity，要去%size才可以。 为什么呢？ 因为如果%capacity的，得到的那个散列值是可能会大于size的。 那我们之前也模拟实现过vector，要知道vector在进行插入操作的时候是会检查插入的那个位置是否在start和finish之间的 在这里插入图片描述 包括它对方括号的重载也会检查插入位置的下标是否小于size的。 所以如果这里%capacity的话有可能会越界，当然如果出现这种情况vector里面直接就报断言错误了。

那我们写一下插入的具体代码：

<font color = black>那就按照我们上面分析的逻辑走就行了 在这里插入图片描述 大家自己看一看理解一下

那大家有没有发现什么问题啊就上面插入的实现？

<font color = black>🆗，刚开始的时候size为0啊，那这里是不是就是除0错误了。 那除了size为0的情况我们还要考虑什么问题？ 我们不断的插入，是不是要考虑在合适的时候进行扩容啊？ 另外size是不是会发生变化啊，size一变这个映射关系是不是也就随之改变了？

那不着急，下面这些问题我们都会一一处理

载荷因子/负载因子

思考：哈希表什么情况下进行扩容？如何扩容？

<font color = black>对于哈希表来说，它的扩容不是等到当前表插入满了才去扩容。 而是去衡量哈希表的装满程度，如果当前表里面插入的元素已经比较多了，那这时再去插入新元素，发生冲突的可能性就比较大了，那冲突值就会增多，冲突值越多，那哈希表查找的效率就越低了。 所以当哈希表的装满程度已经比较大的时候，即使还没满，这个时候就要扩容了。

扩容

所以，这里引入了载荷因子来衡量一个哈希表的装满程度来判断要不要进行扩容：

<font color = "#000066">散列表的载荷因子定义为： α =填入表中的元素个数/散列表的长度 α是散列表装满程度的标志因子。 α越大，表明填入表中的元素越多，产生冲突的可能性就越大； 反之，α越小，表明填入表中的元素越少，产生冲突的可能性就越小。 实际上，散列表的平均查找长度是载荷因子α的函数，只是不同处理冲突的方法有不同的函数。 对于开放定址法，荷载因子是特别重要因素，应严格限制在0.7-0.8以下。超过0.8，查表时的CPU缓存不命中(cache missing）按照指数曲线上升。 所以当负载因子超过规定值就要扩容。

那我们来完善一下上面的代码：

<font color = blue>我们这里可以取0.7为负载因子的最大值，大于等于这个值就扩容。 <font color = black>代码： 在这里插入图片描述 大家看这样可以了吗？还有其它问题吗？

大家翻上去看一下上面提到的几个问题处理完了吗？

<font color = black>是不是还没有啊，刚才的代码解决了扩容和size为0情况的处理。 但是还有一个问题： <font color = "#000066">就是我们使用resize扩容之后哈希表的size改变了，而我们用的哈希函数是除留余数法Hash(key) = key% size，那size变了，映射关系也就变了 扩容之后原来表里面已经插入的值，它现在新的散列地址如果还用之前的，可能就不对了。

所以这里的扩容操作：

<font color = "#000066">我们要这样做 不能在原表的基础上进行扩容，而是要重新去开一块空间，该空间的大小就是扩容之后的大小，然后在新表上面把旧表的元素重新进行散列定位和插入。 在这里插入图片描述

那我们来修改补充一下上面的代码：

<font color = black>在这里插入图片描述 然后红框这里其实就是还是走一个插入的逻辑，我们可以把下面之前写的插入的代码拷贝上来修改一下。 这样写当然是可以的，如果嫌这样冗余的话，也可以单独把插入的部分封装一个函数，需要的地方直接调用就行了。

但是这里我们介绍一个新玩法：

<font color = black>在这里插入图片描述 这样就可以很好的实现一个复用。

Insert测试

那插入写好了，我们来测试一下：

<font color = black>比如我们就拿前面的这组数组测试一下 在这里插入图片描述 插入之后我们看跟图上一样不一样 在这里插入图片描述 来通过监视窗口看一下 在这里插入图片描述 大家可以自己对比一下，是完全一致的。

然后我们再来针对扩容的情况测试一下：

<font color = black>我们的平衡因子设置的是0.7，而上面我们刚好已经插入7个值了（对应的size是10） 所以，按理说我们再去插入一个值就会去扩容了，我们来看一下 在这里插入图片描述 比如我们再插入一个15，插入之后是这样的 在这里插入图片描述 我们来看一下 在这里插入图片描述 没有问题。

查找函数Find实现

上面把插入写好了，find我们顺便直接写一下，因为下面删除也要先查找：

<font color = "#000066">那查找的话就按照对应的哈希函数确定散列地址就行了，然后如果有哈希冲突的话就按对应的探测方法往后查找就行了，找到了我们可以返回一下这个元素的指针，如果走到空还没找到就是没有这个值，返回空（如果表为空也没必要查找直接返回） <font color = black>写一下代码 在这里插入图片描述

那find写好之后的话，其实insert里面我们可以再加一个，如果到时候封装unordered_map/set的时候，它们可以去重嘛，所以：

<font color = black>在这里插入图片描述 insert之前可以判断一下，如果存在就不再插入了。

删除函数Erase实现

那我们再来看一下删除的实现

<font color = "#000066">那删除的逻辑呢我们上面已经讲过了，利用伪删除法，其实就是去改它的状态就行了。 那当然我们得先查找一下，确保这个值存在我们才能删除 <font color = black>🆗，来我们写一下 在这里插入图片描述

Find、Erase测试

然后查找删除我们一块测试一下

<font color = black>在这里插入图片描述 没什么问题。

bug解决

但是，现在我们上面写的代码在Find那里还有一个隐藏的bug，如果出现下面这种特殊情况就会有问题：

<font color = "#000066">那种情况呢？ 大多数情况下我们插入，只要负载因子达到设定值就会扩容。 但是不排除可能会出现这样的情况，就是我们插入了一些值之后，只要再插入一个值就会扩容，但是没有继续插入，而是删除了一些元素，删除一些之后又重新插入，这样没有引起扩容，但是导致了表中的状态只有删除和存在，而没有空的状态。 那此时我们的查找 在这里插入图片描述 就会陷入一个死循环（如果找不到的时候），因为这里这个while循环是遇到空才结束的

那如何解决呢？

<font color = black>也好办，加一个判断就行了 在这里插入图片描述 这样就可以了

那我们闭散列的实现差不多就到这里，当然我们这里是以线性探测为例实现，大家有兴趣可以自己写一下二次探测的版本。当然除了线性探测和二次探测也有其他的一些方法，大家有兴趣可以自行去了解。

闭散列的缺陷：

<font color = "#000066">空间利用率低、冲突频率高： 开放定址法容易产生冲突，特别是当哈希表的负载因子较大时，即哈希表的装满程度更高。这会导致性能下降，因为冲突的数量会增加，导致查找的效率降低。而一旦减小负载因子，又会导致频繁扩容，空间利用率低。 聚集问题： 开放定址法在处理冲突时，有时会出现聚集问题。聚集是指数据项在哈希表中被连续地存储在相邻的位置上，这样会导致冲突更加频繁，并且会造成某些位置的利用率低而其他位置的利用率高的情况。

所以，实际应用中，处理哈希冲突更常用的是下面的方法

4.3 开散列（拉链法）

开散列/拉链法的概念：

<font color = blue>开散列法又叫链地址法(拉链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。 在这里插入图片描述 在这里插入图片描述 从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素

4.4 开散列哈希表实现

那下面我们就用拉链法来重新实现一个哈希表。

结构定义

那我们来定义一下结构，还是以KV模型为例：

<font color = black>在这里插入图片描述 当然这里你直接用vector< list<K,V> >也可以，但是直接用list里面有些地方会不太好处理，所以这里里面的链接我们自己搞。

析构

<font color = "#000066">那由于我们这样实现vector里面存的是一个个的结点，这些结点可能指向空（链表为空，还没有插入值），但也可能指向一个链表（vector里面存的相当于链表的头指针嘛），因为这种实现我们的元素就是存在每个哈希桶（链表）里面的嘛

所以这里我们要写一下析构，因为里面的链表是涉及到资源管理的，vector的和我们用库里面的，不用管

<font color = black>在这里插入图片描述

插入函数insert实现

我们来实现一下insert

首先不考虑扩容，我们先写一下仅仅是插入的过程

<font color = "#000066">怎么插入呢？ 根据哈希函数算出元素的散列地址，将它链接到对应的单链表（哈希桶）上就行了 至于插入的方式，头插尾插都可以，这里我们选择头插，因为单链表的头插是比较方便的 在这里插入图片描述 代码： 在这里插入图片描述

扩容

然后我们来讨论一下扩容的问题：

<font color = "#000066">其实按理来说，我们这里如果不对表的大小或者说哈希表的长度进行扩容，也可以不断插入值，即使有冲突，那我们就一直往每个对应的链表后面链接就行了。 这样好像也没什么问题。 确实，但是如果我们插入的值比较多，而表的长度有限，那它每个链表里面的冲突值肯定会一直增多，那这样效率就会大打折扣。

所以这里依然使用负载因子来控制在合适的时机进行扩容：

<font color = "#000066">那对于这里的拉链法我们可以把负载因子设置成1。 那1的话就是哈希表里面所有的链表（哈希桶）里面插入的元素之和等于表的长度的时候，我们进行扩容。平均一点的话就是每个哈希桶里面都有一个元素。 这样是比较合适的，当然不一定非要设置成1。

那我们来把扩容的代码加上：

<font color = black>那我们这里还是先按扩容之后的size创建一个新表，然后把旧表的值依次重新插入（因为size改变了映射关系也会变），最后把哈希表和新表进行交换 和上面闭散列扩容的逻辑一下嘛 在这里插入图片描述 这样写没什么问题。

扩容优化

但是呢，我们可以进行一些优化：

<font color = "#000066">怎么优化呢？ 我们上面的写法，遍历旧表，依次把每个哈希桶里面的数据重新插入到新表newht里面，虽然我们遍历用了引用，但是它里面调inert的时候，在insert里面还是会拿旧表里面每个结点的_kv去重新开结点然后插入，最后还要一个一个结点释放旧表。 所以我这里想这样优化一下： 我想直接把旧表的结点直接拿下来插入到新表里面，这样即不用开新结点，最终交换之后也不用释放旧表的结点。 那这样的话我们就不去复用insert了，自己去搞

来实现一下：

<font color = black>我们取旧表结点重新进行散列头插到新表就行了在这里插入图片描述 就写好了

insert和扩容测试

然后我们来测试一下，insert和扩容一起测一下

<font color = black>先不扩容，用这个用例测试一下在这里插入图片描述 在这里插入图片描述 我们运行通过监视窗口看一下 在这里插入图片描述 大家看一下，没有问题，跟图上是一样的。

然后扩容的情况：

<font color = black>我们插入第11个值得时候就会扩容 在这里插入图片描述 我们来调试看一下在这里插入图片描述 大家可以自己画图对比一下，是没问题的。

查找函数Find实现

那我们再来写一下查找：

<font color = "#000066">那这里的查找就是根据散列地址去对应的链表里面查找就行了 在这里插入图片描述

然后insert里面也可以加一个这个：

<font color = black>在这里插入图片描述 key不允许重复。

删除函数Erase实现

接着写一下删除Erase：

<font color = "#000066">那删除的话也是先走查找的逻辑嘛，先根据散列地址去对应的链表里面找，找到了就进行删除（那这就是链表里面删除元素的操作了），找不到返回false即可 来写一下 在这里插入图片描述 看不太懂的可以看之前文章复习一下单链表的删除

Find、Erase测试

我们来测试一下查找和删除：

<font color = black>在这里插入图片描述 删除之前 在这里插入图片描述 删除之后 在这里插入图片描述 在这里插入图片描述 没问题

相比于开放定址等方法，拉链法无需在哈希表中预留额外的空间，只需在桶内分配链表节点即可。这样可以有效利用内存，空间利用率更高。

5. 思考：存储整型之外的其它类型元素

我们来思考一个问题：

<font color = black>我们上面用两种方式实现了哈希表（当然接口可能没有实现特别完整），但是我们上面的实现哈希表里面存的都是整型，而我们的哈希函数用整型进行计算刚好是比较好的（比如我们上面用的是除留余数法）。 但是如果是其它类型，要是浮点型或者char类型，还比较好处理，因为可以强转，但是，如果是除此之外的其它类型，比如string，或者其它的自定义类型，我们的程序还能很好的处理吗？

我们可以先来试一下，就用我们刚才实现的开散列的哈希表：

<font color = black>在这里插入图片描述 来运行一下 在这里插入图片描述 是不行的。 因为string类型是无法进行取模运算的。

那我们如何解决一下呢？

<font color = "#000066">🆗，我们可以用一个仿函数来解决。 这个仿函数的作用就是把key（无论是什么类型 ），转换成整型。

那我们来写一下：

<font color = black>如果是对于double，char这些能够隐式类型转换为整型的，那我们的仿函数这样写就行了 在这里插入图片描述 这样的话如果是这些可以隐式类型转换的类型用这个仿函数就可以转换成整型，因为这里的返回值是size_t（无符号整型）嘛，其实就是起了一个类型转换的作用。 当然我们这里可以把这个设置为缺省值 在这里插入图片描述 这样这些可以支持隐式类型转换的这些类型就默认支持了，对于这些类型我们就不用手动传了。 那使用仿函数的话，我们代码里面取模的地方就得改一下 在这里插入图片描述 下面还有我就不截图了

但是呢：

<font color = black>string这些自定义类型还是不支持啊，因为它们不能转换为整型。 <font color = "#000066">那这时候呢我们就可以针对具体的类型再去实现对应的仿函数，然后自己显式传第三个仿函数的参数。

比如，对于string类型我们来搞一下

<font color = black>首先下一个针对string的仿函数 至于在仿函数内部如何将string转换为整型，方法有很多种 比如 在这里插入图片描述 我们这里返回string第一个字符的ASCII码值。 在这里插入图片描述 那现在就可以了。 不过我们这种方法其实不太好，因为有可能是空串，另外这样只要key的第一个字符相等，那他们就会冲突。 所以，我们也可以考虑这样写 在这里插入图片描述 用所有字符ASCII值之和作为返回结果，这样冲突可能会少一点。 那对于其它自定义类型也是一样，大家可以根据实际情况自己写仿函数控制。

那这样的话我们猜想库里面肯定也要解决这种情况：

<font color = "#000066">在这里插入图片描述 我们看到库里面也是通过仿函数来解决这种问题的。 ps：下面那个Pred那个是用来控制比较两个键是否相等的。

但是我们会发现：

<font color = black>在这里插入图片描述 库里面的unordered_map，如果key是string的时候也不需要传仿函数，可以直接用。 因为string这个类型还是比较常用的，所以库里面直接默认就支持了。

那它是如何做到的呢？

<font color = "#000066">那其实很简单，做一个特化就行了嘛，这是我们模板那里学过的知识 在这里插入图片描述 那现在我们用string就也不用再手动传仿函数了 在这里插入图片描述

那上面把字符串所有的字符之和作为key去散列，在一定程度上可以减少冲突，但是避免不了这样的情况：

<font color = "#000066">即两个字符串是不相同的，但是它们的字符ASCII码值之和是相同的，比如两个字符串只是有些字符顺序不同。 如果这样情况比较多的话，还是会造成大量冲突。 在这里插入图片描述 前三个相同，后两个相同。

6. 字符串哈希

所以其实现在也有很多的字符串哈希函数来解决这个问题

<font color = black>常见的比如： 在这里插入图片描述 种类很多，大家有兴趣可以自行去了解。

那我们这里重点来了解一种：

<font color = "#000066">BKDR哈希： 在这里插入图片描述 也是去算字符串所有字符的ASCII码值之和，但是它每次都把前一个值乘一个数，这个数也可以取好多种值。

那我们把自己写的改造一下，比如我们乘31：

<font color = black>在这里插入图片描述 然后我们再来测一下这个 在这里插入图片描述 看看结果 在这里插入图片描述 大家看这次就没有重复值了。

当然字符串哈希也是在一定程度上减少冲突，也不能完全避免冲突（我们这里测试数据比较少）。

7. 哈希表性能测试分析

大家算一下再哈希表里面查找一个元素，时间复杂度是多少？

<font color = "#000066">对于哈希表的查找，如果我们考虑最坏的情况的话，是O(N)，即在插入的元素里面，大部分的值都冲突到一个位置，被放到同一个桶里面。 但是，这种最坏的情况几乎不会出现。 因为我们插入的过程还会不断扩容，而扩容的过程旧表的值重新散列到扩容之后的新表里面，它的冲突值是会不断减少的。 另外我们的负载因子也在控制嘛，像我们上面设置负载因子为1，平均情况就是每个哈希桶上面挂一个值再插入就要扩容了。 所以如果按平均情况的话哈希表的查找就是O(1)，这是很快的。

当然我们也可以通过程序来感受一下：

<font color = black>在这里插入图片描述 多搞一些随机值，插入到哈希表里面，然后我们可以观察一下插入这么多随机值以后，哈希表里面所有的哈希桶中高度最高是多少，如果它的高度能一直保存在一个比较低的水平，那它的效率就一定是很高的。 那我们来写一个求哈希桶最大高度的函数 在这里插入图片描述

然后我们来测试一下：

<font color = black>先来10万个数据 在这里插入图片描述 我们看到最长的哈希桶长度才是1，当然这里实际插入的值应该只有3万多个，因为rand产生的随机数有大量重复值。 所以我们可以这样在这里插入图片描述 这下重复值就少了 再测试在这里插入图片描述 这次最长是2 数据量再增大，100万！ 在这里插入图片描述 还是2。 这个效率还是非常好的，最长的哈希桶才为2，着查找起来是很快的。

那再问大家一个问题：如果现在就是出现了某种比较特殊、比较极端的场景，使得哈希表里面某些桶比较长，那我们可以如何解决呢？

<font color = "#000066">首先我们可能会想到缩小负载因子，这肯定能缓解一下。 然后这里有人提供这样一种思路： 就是如果真的出现了某个桶特别长，那针对这个桶我们可以不用链表，而改用挂红黑树去存储该桶里面的值。 即有的地方挂链表，有的地方链表比较长，就把里面的值放到红黑树里面挂上去（既有的位置挂链表，有的位置挂红黑树，可以借助联合体实现）。

8. 除留余数法最好模一个素数

<font color = "#000066">有些书上提出，用除留余数法的时候，模一个素数是比较好的。

那就有一个问题： 如何每次快速取一个类似两倍关系的素数？（作为每次扩容前后表的size）

<font color = "#000066">那其实SGI版本的STL里面就使用了这种方式，我们可以看一下他怎么搞的： 在这里插入图片描述 我们看到他其实就是给了一个现成的素数表，每次扩容就从这里面选取一个比当前size大的数作为下一次的容量（第一次取53）。 而且我们的哈希表去扩容，它是不可能扩到大于这里的最大值的，这个不用担心。

那我们可以就用它这个表，把我们实现的改造一下：

<font color = black>首先来一个这个函数在这里插入图片描述 作用就是你给我一个素数，我们从这里面找一个比你大的返回。 那我们代码里面扩容的size就可以这样获取： 在这里插入图片描述

这个大家了解一下即可。

9. 源码

9.1 HashTable.h

#pragma once
#include <stdbool.h>
​
namespace OpenAddress
{
    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:
        bool Insert(const pair<K, V>& kv)
        {
            if (Find(kv.first))
            {
                return false;
            }
​
            //先判断负载因子是否>=0.7，超过就扩容
            //if (_table.size() == 0 || (double)_n / (double)_table.size() >= 7)
            if (_table.size() == 0 || _n * 10 / _table.size() >= 7)
            {
                size_t newsize = _table.size() == 0 ? 10 : _table.size() * 2;
                //创建一个新哈希表
                HashTable<K, V> newht;
                newht._table.resize(newsize);
​
                for (auto& data : _table)
                {
                    if (data._state == EXIST)
                    {
                        //把旧表里面的元素重新映射插入到新表里面
                        newht.Insert(data._kv);
                    }
                }
                //将哈希表底层旧表的新哈希表进行交换
                _table.swap(newht._table);
            }
​
            size_t hashi = kv.first % _table.size();
​
            //判断是否发生冲突并进行线性探测
            size_t i = 1;
            size_t index = hashi;
            while (_table[index]._state == EXIST)
            {
                index = hashi + i;
                index %= _table.size();
                i++;
            }
​
            //在合适的位置进行插入
            _table[index]._kv = kv;
            _table[index]._state = EXIST;
            ++_n;
​
            return true;
        }
        HashData<K, V>* Find(const K& key)
        {
            if (_table.size() == 0)
            {
                return nullptr;
            }
            size_t hashi = key % _table.size();
​
            //判断是否发生冲突并进行线性探测寻找
            size_t i = 1;
            size_t index = hashi;
            while (_table[index]._state != EMPTY)
            {
                if (_table[index]._state == EXIST
                    && key == _table[index]._kv.first)
                {
                    return &_table[index];
                }
                index = hashi + i;
                index %= _table.size();
                i++;
​
                //如果index在向后探测的过程中没有找到且又回到了起始点，
                //就说明表中只有DELETE和EXIST，我们手动结束循环
                if (index == hashi)
                {
                    break;
                }
            }
            return nullptr;
        }
        bool Erase(const K& key)
        {
            HashData<K, V>* ret = Find(key);
            if (ret)
            {
                ret->_state = DELETE;
                --_n;
                return true;
            }
            else
            {
                return false;
            }
        }
    private:
        vector<HashData<K, V>> _table;
        size_t _n = 0;//记录哈希表中的有效数据个数
    };
​
    void test_hash1()
    {
        int arr[] = { 3,33,2,13,5,12,1002 };
        HashTable<int, int> ht;
        for (auto e : arr)
        {
            ht.Insert(make_pair(e, e));
        }
        ht.Insert(make_pair(15, 15));
​
        if (ht.Find(13))
        {
            cout << "存在" << endl;
        }
        else
        {
            cout << "不存在" << endl;
        }
​
        ht.Erase(13);
        if (ht.Find(13))
        {
            cout << "存在" << endl;
        }
        else
        {
            cout << "不存在" << endl;
        }
    }
}
​
//-----------------------------------------------------------------------------------------------------------------
namespace HashBucket
{
    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>
    struct keyToIntFunc
    {
        size_t operator()(const K& key)
        {
            return key;
        }
    };
​
    //对string类型进行特化
    template<>
    struct keyToIntFunc<string>
    {
        size_t operator()(const string& key)
        {
            size_t sum = 0;
            for (auto& e : key)
            {
                sum = sum * 31 + e;
            }
            return sum;
        }
    };
​
    template<class K, class V, class keyToInt = keyToIntFunc<K>>
    class HashTable
    {
        typedef HashNode<K, V> Node;
    public:
        ~HashTable()
        {
            for (auto& cur : _table)
            {
                while (cur)
                {
                    Node* next = cur->_next;
                    delete cur;
                    cur = next;
                }
                cur = nullptr;
            }
        }
​
        size_t GetNextPrime(size_t prime)
        {
            // SGI
            static const int __stl_num_primes = 28;
            static const unsigned long __stl_prime_list[__stl_num_primes] =
            {
                53, 97, 193, 389, 769,
                1543, 3079, 6151, 12289, 24593,
                49157, 98317, 196613, 393241, 786433,
                1572869, 3145739, 6291469, 12582917, 25165843,
                50331653, 100663319, 201326611, 402653189, 805306457,
                1610612741, 3221225473, 4294967291
            };
​
            size_t i = 0;
            for (; i < __stl_num_primes; ++i)
            {
                if (__stl_prime_list[i] > prime)
                    return __stl_prime_list[i];
            }
​
            return __stl_prime_list[i];
        }
​
        bool Insert(const pair<K, V>& kv)
        {
            if (Find(kv.first))
            {
                return false;
            }
​
            //负载因子==1进行扩容
            
            //复用insert
            /*if (_n == _table.size())
            {
                size_t newsize = _table.size() == 0 ? 10 : _table.size() * 2;
                HashTable<K, V> newht;
                newht.resize(newsize);
                for (auto& cur : _table)
                {
                    while (cur)
                    {
                        newht.insert(cur->_kv);
                        cur = cur->_next;
                    }
                }
                _table.swap(newht._table);
            }*/
​
            //自己搞
            if (_n == _table.size())
            {
                //size_t newsize = _table.size() == 0 ? 10 : _table.size() * 2;
                size_t newsize = GetNextPrime(_table.size());
​
                vector<Node*> newtable(newsize, nullptr);
                for (auto& cur : _table)
                {
                    while (cur)
                    {
                        Node* next = cur->_next;
                        size_t hashi = keyToInt()(cur->_kv.first) % newtable.size();
​
                        //把结点头插到新表
                        cur->_next = newtable[hashi];
                        newtable[hashi] = cur;
​
                        cur = next;
                    }
                }
                _table.swap(newtable);
            }
​
            //计算散列地址
            size_t hashi = keyToInt()(kv.first) % _table.size();
​
            //链到散列地址对应的单链表上（头插）
            Node* newNode = new Node(kv);
            newNode->_next = _table[hashi];
            _table[hashi] = newNode;
​
            ++_n;
            return true;
        }
​
        Node* Find(const K& key)
        {
            if (_table.size() == 0)
            {
                return nullptr;
            }
            size_t hashi = keyToInt()(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)
        {
            size_t hashi = keyToInt()(key) % _table.size();
            Node* prev = nullptr;
            Node* cur = _table[hashi];
​
            while (cur)
            {
                if (key == cur->_kv.first)
                {
                    //头删
                    if (prev == nullptr)
                    {
                        _table[hashi] = cur->_next;
                    }
                    //非头删
                    else
                    {
                        prev->_next = cur->_next;
                    }
                    delete cur;
                    return true;
                }
                else
                {
                    prev = cur;
                    cur = cur->_next;
                }
            }
            return false;
        }
​
        size_t MaxBucketSize()
        {
            size_t max = 0;
            for (auto& cur : _table)
            {
                size_t size = 0;
                while (cur)
                {
                    ++size;
                    cur = cur->_next;
                }
                if (size > max)
                {
                    max = size;
                }
            }
            return max;
        }
​
    private:
        vector<Node*> _table;
        size_t _n = 0;
    };
​
    void test_hash1()
    {
        int arr[] = { 1,4,5,6,7,9,44,13,24,37 };
        HashTable<int, int> ht;
        for (auto e : arr)
        {
            ht.Insert(make_pair(e, e));
        }
        ht.Insert(make_pair(99, 99));
​
        if (ht.Find(13))
        {
            cout << "存在" << endl;
        }
        else
        {
            cout << "不存在" << endl;
        }
​
        ht.Erase(13);
        ht.Erase(4);
​
        if (ht.Find(13))
        {
            cout << "存在" << endl;
        }
        else
        {
            cout << "不存在" << endl;
        }
    }   
​
    /*struct strToInt
    {
        size_t operator()(const string& key)
        {
            size_t sum = 0;
            for (auto& e : key)
            {
                sum = sum * 31 + e;
            }
            return sum;
        }
    };*/
​
    void test_hash2()
    {
        HashTable<string, string> ht;
        ht.Insert(make_pair("", "字符串"));
        ht.Insert(make_pair("left", "左边"));
        ht.Insert(make_pair("right", "右边"));
        ht.Insert(make_pair("count", "数量"));
​
        /*strToInt hashstr;
        cout << hashstr("abcd") << endl;
        cout << hashstr("bcda") << endl;
        cout << hashstr("aadd") << endl;
        cout << hashstr("eat") << endl;
        cout << hashstr("ate") << endl;*/
    }
​
    void test_hash3()
    {
        size_t N = 1000000;
        HashTable<int, int> ht;
        srand((unsigned int)time(nullptr));
        for (size_t i = 0; i < N; ++i)
        {
            size_t x = rand() + i;
            ht.Insert(make_pair(x, x));
        }
​
        cout << "最长哈希桶长度为：" << ht.MaxBucketSize() << endl;
    }
}

9.2 Test.cpp

#include "HashTable.h"
​
int main()
{
    //OpenAddress::test_hash1();
    HashBucket::test_hash3();
    return 0;
}

在这里插入图片描述

【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱： cloudbbs@huaweicloud.com
容器 数据结构
  • 点赞
  • 收藏
  • 关注作者

评论（0）

0/1000
抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认 取消

加入云驻计划，成为创作者

  • 华为云周边好礼
  • 免费体验产品
  • 特殊身份标识
  • 线下官方门票
  • 内部专家零距离
  • 与10000+优质创作者共同成长
立即加入