《C++进阶之STL》【哈希表】-EW帮帮网

【哈希表】目录

前言
------------概念介绍------------
- 1. 什么是哈希？
------------核心术语------------
一、哈希函数
二、负载因子
三、哈希冲突
四、冲突处理
------------基本操作------------
- 怎么解决键key不能取模的问题？
一、开放定址法
二、链地址法
- 哈希结构
- 扩容操作
------------代码实现------------

在这里插入图片描述

往期《C++初阶》回顾：

《C++初阶》目录导航

往期《C++进阶》回顾：
/------------ 继承多态 ------------/
【普通类/模板类的继承 + 父类&子类的转换 + 继承的作用域 + 子类的默认成员函数】
【final + 继承与友元 + 继承与静态成员 + 继承模型 + 继承和组合】
【多态：概念 + 实现 + 拓展 + 原理】
/------------ STL ------------/
【二叉搜索树】
【AVL树】
【红黑树】
【set/map 使用介绍】
【set/map 模拟实现】

前言

hi~ 小伙伴们大家好啊！٩(ˊᗜˋ*)و
今天是什么节来着……嗯~ o(￣▽￣)o，今天是公元二〇二五年九月十三日，星期六，上午太阳照常从地平线升起，鼠鼠也照常“偷吃”了两个包子(≧ڡ≦*)ゞ，一切都正常！

今天我们要习得的是难度为S级的 【哈希表】，小伙伴们你们准备好要爆炸了吗？
哦不对，是准备好脑袋瓜子“砰”一下了吗？☆ﾐ(o*ｕωｕ)ﾉｼ

其实单看 “哈希表” 本身，它更偏向数据结构的范畴。但鼠鼠还是把它放进 C++ 的学习内容里，原因很简单：因为我们学哈希表，终极目标就是亲手撸出 unordered_set / unordered_map
就像之前啃完“二叉搜索树 + AVL 树 + 红黑树”是为了搞定 set/map 一样，套路熟悉不？(ʘ‿ʘ✿)

理论铺垫已就位，接下来请系好安全带，一起冲进哈希表的“O(1) 宇宙”吧！♡(ӦｖӦ｡)

------------概念介绍------------

1. 什么是哈希？

哈希（Hash），也称为散列：是一种将任意长度的输入数据（通常称为 “键” 或 “关键字”）通过特定的数学算法（称为 “哈希函数”）映射为固定长度输出的技术。

这个输出值被称为 “哈希值”、“散列值” 或 “哈希码”。

哈希的核心目的是快速实现数据的查找、存储和比较，广泛应用于哈希表、密码学、数据校验等领域。

------------核心术语------------

一、哈希函数

哈希函数（Hash Function）：是哈希表（Hash Table）的核心组成部分，它的作用是将任意长度的输入数据（称为 “键” 或 “关键字”）映射到一个固定长度的输出值（称为 “哈希值” 或 “散列值”）

这个输出值通常用于确定该键在哈希表中的存储位置。

1. 哈希函数的核心特点是什么？

哈希函数的核心特点：

确定性：同一输入必须始终映射到同一个哈希值。

例如：输入字符串"apple"每次通过哈希函数计算，结果都应相同

压缩性：无论输入数据的长度如何，输出的哈希值长度是固定的。

例如：常用的 MD5 哈希函数会将任意输入映射为 128 位的哈希值，而哈希表中常用的哈希函数可能将键映射为0~n-1（n为哈希表长度）的整数

高效性：计算哈希值的过程应快速且易于实现，时间复杂度通常为 $O (1)$ 或 $O (k)$ （ $k$ 为输入数据的长度），避免成为哈希表操作的性能瓶颈。

2. 哈希函数的设计目标是什么？

哈希函数的设计目标：

均匀分布：理想情况下，哈希函数应将不同的键均匀地映射到哈希表的各个位置，避免大量键集中在少数位置（称为 “哈希冲突”）

均匀分布能保证哈希表的操作（插入、查找、删除）效率接近 $O (1)$

减少冲突：由于输入空间（可能的键）远大于输出空间（哈希表长度），哈希冲突无法完全避免，但好的哈希函数能最大限度降低冲突概率

3. 常见的哈希函数有哪些？

直接定址法

直接定址法：通过直接利用关键字本身或关键字的某个线性函数来确定哈希地址，从而实现关键字到存储位置的映射。

直接定址法是一种简单直观的哈希函数构造方法。

核心公式和基本原理：

直接定址法的哈希函数公式通常为：

H(key) = key 或 H(key) = a × key + b

key：是待映射的关键字。（需要存储的数据的标识）

a 和 b：是常数。（a ≠ 0，用于对关键字进行线性变换）

H(key)：是计算得到的哈希地址。（即：数据在哈希表中的存储位置）

优缺点与适用场景：

优点

简单高效：无需复杂计算，直接通过关键字映射地址，时间复杂度为 $O (1)$

无冲突：只要关键字不重复，计算出的哈希地址一定唯一（因为是线性映射，不存在不同关键字映射到同一地址的情况）

缺点

空间浪费大：如果关键字的范围很大（例如：key 是 1000 到 1000000 的整数），哈希表需要开辟对应范围的空间，但实际存储的关键字可能很少，导致大量空间闲置

关键字需为整数：若关键字是非整数（例如：字符串、浮点数），需先转换为整数才能使用，否则无法直接映射

场景

关键字的范围较小且连续（或分布集中）

关键字可以直接作为地址（或通过简单线性变换后作为地址）

直接定址法的实际使用案例：

存储学生的年龄（范围通常在 5-25 岁），可直接用 H(age) = age，哈希表大小只需 30 左右

存储月份（1-12 月），可用 H(month) = month，哈希表大小为 12 即可

除法散列法

除法散列法：核心逻辑是用关键字对一个整数取余，把大范围的关键字映射到哈希表的有效下标区间，以此确定存储位置。

除法散列法是哈希函数构造方法里的经典手段。

核心公式与基本原理：

除法散列法的哈希函数一般形式为：

H(key) = key % m

key：是待映射的关键字。（可以是整数、经转换后的字符串哈希值等）

m：是哈希表的大小。（通常是数组长度，决定了哈希地址的范围）

H(key)：是计算出的哈希地址。（即：关键字在哈希表中的存储下标）

本质：利用取余运算的 “截断” 特性，把任意整数 key 映射到 [0, m-1] 区间，让关键字适配哈希表的下标范围

关键特性与优缺点：

优点

实现简单：一行取余运算即可完成映射，编码成本极低

适用性广：只要能转成整数（或本身是整数）的关键字都能用，涵盖整数、字符串、自定义结构体（需先哈希转整数）

控制范围：通过调整 m 灵活控制哈希地址范围，适配不同内存、性能需求

缺点

冲突概率与m强相关：若m选得不好（比如：是关键字的公约数），会导致大量冲突

例如：关键字都是偶数、m=4，则哈希地址只能是 0,2，冲突概率飙升

依赖m的选取：m 若为合数（尤其是 2 的幂），易让哈希地址分布不均（比如：二进制低位相同的关键字会扎堆）

不适用于动态扩容：哈希表扩容后 m 改变，所有关键字需重新计算哈希地址，迁移成本高

优化：m 的选取原则

除法散列法的效果高度依赖 m 的选择，工程中常用以下策略优化：

优化策略一：选质数

优先选质数作为 m，能大幅降低冲突概率。原因是：质数的约数少，关键字取余后分布更均匀。

反例：若 m=10（合数），关键字 10、20、30 都会映射到 0，冲突严重

正例：若 m=11（质数），上述关键字会映射到 0、9、8，分布更分散

优化策略二： 避免 m=2^k/10^X

若 M = 2^X，key % M 等价于 “保留 key 的最后 X 位二进制数”。此时，只要不同 key 的最后 X 位二进制数相同，哈希值就会冲突。

取M = 16（即2^4），计算63 % 16 和 31 % 16：

63 的二进制后 8 位是 00111111，取最后 4 位 1111 → 余数 15

31 的二进制后 8 位是 00011111，取最后 4 位 1111 → 余数 15

可见，看似无关的 63 和 31，因最后 4 位相同，哈希值冲突。

若 M = 10^X，key % M 等价于 “保留 key 的最后 X 位十进制数”。此时，只要不同 key 的最后 X 位十进制数相同，哈希值就会冲突。

取M = 100（即10^2），计算112 % 100 和 12312 % 100

两者最后 2 位都是 12 → 余数均为 12，哈希值冲突

优化策略三：结合关键字分布调整

若已知关键字的分布（如：都是奇数、或集中在某个区间），选 m 时尽量让余数覆盖更全。

关键字全是奇数，m 选奇数可避免 “余数全为奇数 / 偶数” 的极端情况。

乘法散列法

乘法散列法：

先将关键字 key 与一个在 (0, 1) 之间的常数 A 相乘，得到的结果会是一个小数

取这个小数的小数部分，再乘以哈希表的大小 m

最后对结果向下取整，就得到了哈希值

核心公式与基本原理：

乘法散列法的哈希函数公式可以表示为：

$\lfloor m \times (key \times A \bmod 1) \rfloor$

key：是要进行哈希计算的关键字。（它可以是整数、字符串等各种数据类型对于非整数类型，通常需要先通过其他方式将其转换为整数）

A：是一个常数。（取值范围在 (0, 1) 之间，并且通常是一个无理数，常见的取值如 $\frac{\sqrt{5}-1}{2}$ （黄金分割数，约等于 0.6180339887），这样能让哈希值分布得更均匀）

m：是哈希表的大小。（即：哈希值的范围是 [0, m - 1]）

$\bmod 1$ ：表示取小数部分。（例如： $\bmod 1$ 结果为 0.14）

$\lfloor \ \rfloor$ ：是向下取整符号。（例如： $\lfloor 3.9 \rfloor$ 结果为 3）

关键特性与优缺点：

优点

哈希值分布均匀：当常数 A 选择合适时，乘法散列法能让哈希值在哈希表中较为均匀地分布，减少哈希冲突的发生。这是因为乘法运算能充分打乱关键字的二进制位，使得不同关键字映射到相同哈希值的概率降低。

对哈希表大小要求灵活：不像除法散列法对哈希表大小 m 的取值有较多限制（如：尽量取质数等），乘法散列法对 m 的取值相对自由，m 可以是任意正整数。

计算效率较高：乘法散列法主要涉及乘法、取小数部分和取整操作，在现代计算机硬件上，这些操作都能高效执行。

缺点

常数 A 的选择有难度：虽然理论上常数 A 只要在 (0, 1) 之间且为无理数就能工作，但要找到一个能在实际应用中让哈希值分布最优的 A 并不容易，往往需要通过实验和对数据特征的了解来确定。

实现相对复杂：相较于简单的除法散列法，乘法散列法的计算步骤更多，实现代码也相对复杂一些。

使用乘法散列法计算哈希值步骤示例：

假设要对整数关键字 key = 12345 进行哈希计算，哈希表大小 m = 100，常数 A 取黄金分割数 $\frac{\sqrt{5}-1}{2}$ ，计算过程如下：

计算 key * A： $\frac{\sqrt{5}-1}{2} \approx 12345 * 0.6180339887 = 7625.08749$

取小数部分： $\bmod 1 = 0.08749$

乘以哈希表大小： $0.08749 * 100 = 8.749$

向下取整得到哈希值： $\lfloor 8.749 \rfloor = 8$

全域散列法

全域散列法：是一种随机化哈希技术，通过从精心设计的哈希函数族中随机选择哈希函数，确保即使对于最坏情况下的输入也能获得良好的平均性能。

基本概念：

在普通的哈希函数设计中，如果哈希函数选择不当，可能会出现一些极端情况

例如：对于给定的哈希函数，某些特定的关键字集合会导致大量的哈希冲突，使得哈希表退化为链表，操作时间复杂度从期望的 $O (1)$ 变为 $O (n)$

全域散列的核心思想是从一个哈希函数族中随机选择哈希函数，使得对于任意给定的关键字集合，哈希冲突的概率都被控制在一个较低的水平。

核心原理：

全域散列法基于一个哈希函数族 $\mathcal{H}$ ，这个函数族包含了多个不同的哈希函数。
在使用全域散列时，会从这个函数族中随机选择一个哈希函数 $h$ 来进行哈希操作。

从数学角度来说，对于任意两个不同的关键字 $x$ 和 $y$ ，哈希函数族 $\mathcal{H}$ 满足：

$\frac{|\{h \in \mathcal{H}: h(x) = h(y)\}|}{|\mathcal{H}|} \leq \frac{1}{m}$

$|\mathcal{H}|$ ：表示哈希函数族中哈希函数的个数

$m$ ：是哈希表的大小

也就是说，从哈希函数族中随机选取一个哈希函数，使得两个不同关键字哈希值相同（产生冲突）的概率不超过 $\frac{1}{m}$
这样就能保证在平均情况下，哈希冲突的数量是比较少的。

全域散列法的实现步骤：

定义哈希函数族：需要先定义一个哈希函数族。

以简单的整数关键字为例，假设关键字 $k$ 是一个整数，哈希表大小为 $m$ ，可以定义哈希函数族如下：

设 $p$ 是一个比任何关键字值都大的质数

对于每个 $\in \{1, 2, \cdots, p - 1\}$ 和 $\in \{0, 1, \cdots, p - 1\}$

定义哈希函数： $h_{a,b}(k) = ((ak + b) \bmod p) \bmod m$

所有这样的哈希函数构成了一个哈希函数族 $\mathcal{H}$

假设： $P = 17$ ， $M = 6$ ， $a = 3$ ， $b = 4$ ，则 $h_{34}(8) = ((3 \times 8 + 4) \% 17) \% 6 = 5$

随机选择哈希函数：

在构建哈希表时，从哈希函数族 $\mathcal{H}$ 中随机选择一个哈希函数 $h_{a,b}$ 来使用

可以通过生成随机数来确定参数 $a$ 和 $b$ 的值，从而确定具体的哈希函数

进行哈希操作：

使用选定的哈希函数对关键字进行哈希计算，将关键字映射到哈希表的相应位置

在插入、查找和删除操作中，都使用这个选定的哈希函数来确定关键字在哈希表中的位置

二、负载因子

1. 什么是负载因子？

负载因子（Load Factor）：是哈希表设计与性能分析中的核心概念，用于衡量哈希表的 “填充程度”，直接影响哈希冲突概率和内存利用率

负载因子的定义： 哈希表中已存储的元素数量 / 哈希表的总容量（桶的数量）

负载因子的计算公式： $\lambda = \frac{n}{m}$

n：是哈希表中当前存储的有效元素数量

m：是哈希表的总容量（即桶数组的长度，如：vector<Node*> 的大小）

2. 负载因子对哈希表的性能有什么影响？

对哈希表性能的影响：

负载因子是哈希冲突概率和内存利用率的 “平衡器”，核心影响如下：

（1）负载因子越小 → 哈希冲突概率越低

当 $\lambda \to 0$ （如：哈希表很空），每个桶的平均元素数少，链表 / 探测链短，插入、查找、删除的时间复杂度接近 $O (1)$

但内存浪费严重（大量桶闲置），空间利用率低。

（2）负载因子越大 → 哈希冲突概率越高

当 $\lambda \to 1$ （如：哈希表快满），桶的平均元素数多，链表 / 探测链长，操作时间复杂度会退化到 $O (n)$ （极端情况哈希表退化为链表）

内存利用率高，但性能暴跌。

3. 负载因子超过阈值时会发什么？

负载因子驱动的扩容流程：

当负载因子超过阈值时，哈希表会触发扩容（Resize），流程如下：

新建更大的桶数组：新容量通常是原容量的 2 倍（或接近的质数，依实现而定）

重新映射所有元素：遍历旧哈希表的所有元素，用新哈希函数（或新容量重新取模）将元素插入新桶

释放旧内存：销毁旧桶数组，替换为新桶数组

三、哈希冲突

哈希冲突（Hash Collision）：是哈希表设计与实现中无法避免的核心问题，指不同的关键字通过哈希函数计算后，得到相同的哈希地址的情况。（即：映射到哈希表的同一个桶或位置）

定义：对于两个不同的关键字 $key_1 \neq key_2$ ，若它们的哈希值满足 $h(key_1) = h(key_2)$ ，则称这两个关键字发生了哈希冲突。

本质：哈希函数是 “多对一” 的映射（输入空间无限，输出空间有限），根据鸽巢原理，冲突必然存在。

产生冲突的因素：

1. 哈希函数的 “压缩映射” 特性

哈希函数将任意长度的输入（如：字符串、整数、对象）映射到固定长度的哈希值（如：size_t 类型）

再通过取模等操作映射到哈希表的桶索引

这种 “压缩” 必然导致不同输入映射到同一输出

2. 哈希表容量与关键字分布

若哈希表容量 m 过小，或关键字分布集中（如大量关键字的哈希值在同一区间），冲突概率会急剧上升

示例：哈希表容量 (m=10)，若所有关键字的哈希值取模后都为 5，则所有数据会冲突到第 5 个桶。

四、冲突处理

方法一：开放定址法

开放定址法（Open Addressing）：开放定址法是处理哈希冲突的一种系统化方法，所有元素都存储在哈希表数组本身中（而不是像链地址法那样使用额外的数据结），通过探测序列寻找可用的空槽位。

它的核心思路是：当发生哈希冲突时，按照预定的探测规则在哈希表中寻找下一个空闲位置来存储冲突的元素。

开放定址法的原理：

假设哈希表的大小为 m，哈希函数为 h(key)，当通过哈希函数计算出的地址 h(key) 已经被占用，即发生冲突时

开放定址法会使用一个探测序列 h_i(key)（i = 0, 1, 2,...）来寻找下一个空闲位置，直到找到可以插入的位置或者确定哈希表已满

探测序列的计算方式决定了开放定址法的具体类型

线性探测

线性探测（Linear Probing）：

探测公式：h_i(key) = (h(key) + i) % m ，其中 i = 0, 1, 2,...

也就是说，在发生冲突时，从冲突位置开始，依次探测下一个位置（如果到达表尾则回到表头）

示例：假设哈希表大小m = 10，哈希函数h(key) = key % 10，依次插入元素12、22、32

插入 12 时，h(12) = 12 % 10 = 2，位置 2 空闲，插入成功

插入 22 时，h(22) = 22 % 10 = 2，位置 2 已被占用，发生冲突

根据线性探测，h_1(22) = (2 + 1) % 10 = 3，位置 3 空闲，插入成功

插入 32 时，h(32) = 32 % 10 = 2，位置 2 被占用，发生冲突

h_1(32) = (2 + 1) % 10 = 3，位置 3 也被占用，继续探测

h_2(32) = (2 + 2) % 10 = 4，位置 4 空闲，插入成功

缺点：容易产生 “聚集”（或叫 “堆积”）现象。

即连续的若干个位置被占用，导致后续插入元素时需要探测多个位置，降低插入和查找效率。

在这里插入图片描述

二次探测

二次探测（Quadratic Probing）

探测公式：h_i(key) = (h(key) + c1 * i + c2 * i * i) % m

通常取 c1 = 0，c2 = 1，即 h_i(key) = (h(key) + i * i) % m

在发生冲突时，从发生冲突的位置开始，按照二次方的步长，向右进行跳跃式探测，直至找到下一个未存储数据的位置

若向右探测到哈希表尾，就回绕到哈希表头继续

示例：同样假设哈希表大小m = 10，哈希函数h(key) = key % 10，插入元素11和21

插入 11 时，h(11) = 11 % 10 = 1，位置 1 空闲，插入成功

插入 21 时，h(21) = 21 % 10 = 1，位置 1 已被占用，发生冲突

根据二次探测，h_1(21) = (1 + 1 * 1) % 10 = 2，位置 2 空闲，插入成功

优点：相较于线性探测，二次探测能减少聚集现象，使元素在哈希表中分布得更均匀。

缺点：不能探测到哈希表中的所有位置。

当 m 不满足某些条件（如：m 不是 4 的倍数加 1 时），可能会出现有的位置永远无法被探测到的情况

双重散列

双重哈希（Double Hashing）：

探测公式：h_i(key) = (h1(key) + i * h2(key)) % m

其中 h1(key) 是主哈希函数，h2(key) 是辅助哈希函数且 h2(key) 的值不能为 0

在发生冲突时，通过主哈希函数和辅助哈希函数共同计算探测位置

示例：假设h1(key) = key % 7，h2(key) = 1 + (key % 5)，哈希表大小m = 7，插入元素1和24

插入 10 时，h1(10) = 10 % 7 = 3，位置 3 空闲，插入成功

插入 24 时，h1(24) = 24 % 7 = 3，位置 3 已被占用，发生冲突

h2(24) = 1 + (24 % 5) = 1 + 4 = 5，根据双重哈希探测，h_1(24) = (3 + 1 * 5) % 7 = 1，位置 1 空闲，插入成功

优点：探测序列比较均匀，能有效减少聚集，性能表现较好。

在这里插入图片描述

双重哈希的核心逻辑：

当第一个哈希函数计算的位置发生冲突时

通过第二个哈希函数生成一个与 key 相关的偏移量，不断向后探测，直到找到哈希表中未被占用的位置

偏移量 $h_2(key)$ 的约束：

为保证探测能覆盖哈希表的所有位置， $h_2(key)$ 需满足两个条件：

$h_2(key) < M$ （偏移量不能超过哈希表大小）

$h_2(key)$ 与 $M$ 互质 $（$ 即：最大公约数 $gcd(h_2(key), M) = 1）$

$h_2(key)$ 的简单取值方法：

根据哈希表大小 M 的类型，有两种常用策略：

当 M 是 2 的整数次幂时：从 [0, M-1] 中任选一个奇数作为 $h_2(key)$

因为奇数与 2 的幂次互质，可保证探测覆盖所有位置

当 M 是质数时：直接计算： $h_2(key) = key \% (M - 1) + 1$

此方法可确保 $h_2(key)$ 与 $M$ 互质

互质的必要性（关键原理）:

若 $h_2(key)$ 与 M 不互质（即 $gcd(h_2(key)，M) = p > 1$ ），探测的位置会无法覆盖整个哈希表，导致部分空闲位置永远无法被找到。

哈希表大小 $M = 12$ ，初始冲突位置 hash0 = 1，偏移量 $h_2(key) = 3 （\gcd( 3，12) = 3 > 1）$

探测序列为： $\times 3) \% 12 = 4(1 + 2 \times 3) \% 12 = 7(1 + 3 \times 3) \% 12 = 10(1 + 4 \times 3) \% 12 = 1$ （循环）

可见，探测位置仅为 {1, 4, 7, 10}，共 $12/3 = 4$ 个位置，无法覆盖整个哈希表。

总结：双重哈希的价值

双重哈希通过两个哈希函数和互质约束，让探测序列更均匀地覆盖哈希表，避免了线性探测的 “聚集问题”。

相比其他探测方法（如：线性探测、二次探测），双重哈希的冲突解决效率更高，适合对性能要求严格的场景。

方法二：链地址法

链地址法（Separate Chaining）（也叫拉链法、哈希桶法 ）：是哈希表解决哈希冲突的经典方案之一。

它的核心思路是：用数组 + 链表（或其他动态结构）的组合，让冲突元素 “链” 在一起，既简单又高效。

链地址法的原理：

哈希表底层是一个数组（称为 “哈希桶数组” ），每个数组元素对应一个链表 / 动态结构（如：链表、红黑树、跳表）

插入元素时：

通过哈希函数计算 key 的哈希值，确定要放入数组的哪个 “桶”（即：数组索引）

若该桶对应的链表为空，直接插入

若已存在元素（发生冲突），就把新元素追加到链表末尾

查找/删除元素时：

先通过哈希函数找到对应桶

再遍历链表逐个匹配 key

在这里插入图片描述

优缺点分析：

优点

冲突处理简单：不管冲突多频繁，只需往链表追加，逻辑清晰易实现

空间灵活：链表是动态结构，负载因子（负载因子 = 元素数 / 桶数 ）可大于 1 ，空间利用率高

无聚集问题：每个桶的冲突是独立链表，不会像开放定址法那样 “连累” 其他桶

缺点

遍历开销：若某个桶的链表过长，查找 / 删除会退化为 O(n)（n 是链表长度）

额外空间：链表节点需要存储指针，有一定内存开销（但现代优化如：用数组模拟链表可缓解）

------------基本操作------------

怎么解决键key不能取模的问题？

通过上面的学习我们知道了使用哈希函数要把关键字映射到数组的对应位置上，通常来说，关键字是整数的话进行映射计算会更方便。

哈哈，没错要是关键字本身不是整数，是 string、Date 等类型时，无法直接对 key 进行取模操作的话，我们要怎么做呢？

没错那就得想办法把它转换成整数，但是这要怎么实现呢？

这时，我们需要为哈希表增加一个 仿函数（也叫哈希函数对象 ），该仿函数的作用是，把 key 转换成一个可用于取模的整数。

若 key 本身能较方便地转换为整数，且转换后不易引发哈希冲突，直接使用哈希表默认的仿函数参数即可

若 key 无法直接转换为整数，就需要我们自行实现一个仿函数，并传递给哈希表

实现这类仿函数的核心要求是：让 key 的每个部分（字符、字段等）都参与计算，尽可能保证不同 key 转换后的整数值互不相同。

由于 string 作为哈希表的 key 十分常见，我们可以针对性地对 string 类型做特化处理（即：专门为 string 设计更适配的哈希转换逻辑）

/*------------------任务：定义哈希表函数的“结构体模板”------------------*/
template <class K>
struct HashFunc
{
	//1.重载()运算符 ---> 作用：将K类型转化为size_t类型，用于计算哈希值
	size_t operator()(const K& key)
	{
		return (size_t)key;  //注意：默认为直接转换，适用于int、long等整数类型
	} 
};



/*------------------任务：定义哈希函数的“模板特化”------------------*/
template <>
struct HashFunc<string>
{
	//1.实现：“()运算符的重载” ---> 作用：将string类型的变量转化为哈希值
	size_t operator()(const string& s)
	{
		//1.定义size_t类型变量记录string类型的变量计算的哈希值
		size_t hash = 0;

		//2.使用范围for循环遍历字符串并用BKDR算法计算其哈希值
		for (auto it : s)
		{
			//2.1：先将字符的ASCII值累加到哈希值中
			hash += it;
			//2.2：再让哈希值乘以质数131（BKDR哈希算法认为：131可有效减少冲突）
			hash *= 131;
		}

		//3.返回最终计算的哈希值
		return hash;
	}
};

一、开放定址法

在实践里，开放定址法的表现不如接下来要讲的链地址法。

原因在于，开放定址法不管采用哪种冲突解决方式，都是占用哈希表自身的空间，这就使得各元素的存储始终存在相互影响的问题。

所以，对于开放定址法，我们简单选用线性探测的方式来实现即可。

哈希结构

/*------------任务：定义哈希表中节点的三种状态的“枚举”------------*/
enum State
{
	EXIST,  //存在状态
	EMPTY,  //空状态
	DELETE  //删除状态
};

/*------------任务：定义哈希表存储的数据结构的“结构体模板”------------*/
template <class K, class V>
struct HashData
{
	//1.存储键值对类型的数据
	//2.记录存储的节点的状态

	pair<K, V> _kv;
	State _state = EMPTY; //节点的状态默认为空
};



/*------------任务：使用“开放地址法 - 线性探测”实现哈希表------------*/
template <class K, class V, class Hash = HashFunc<K>>
class HashTable
{
private:
	/*------------------成员变量------------------*/

	//1.存储HashData类型数据的数组
	//2.记录哈希表中有效元素的变量 

	vector<HashData<K,V>> _tables;
	size_t _n;
    
public:
    //…………
    
};

删除操作

要注意的是，这里需要给每个存储值的位置添加一个状态标识，否则删除某些值后，会影响后续冲突值的查找。

举个例子，如下若删除 30 ，会导致查找 20 失败

但如果我们给每个位置设置 {EXIST, EMPTY, DELETE} 这样的状态标识，删除 30 时，就不用真正删除对应的值，而是把该位置状态改为 DELETE

如此一来，查找 20 时，只有遇到 EMPTY 状态才停止探测，就能顺利找到 20 了

在这里插入图片描述

扩容操作

我们将哈希表的负载因子控制在 0.7 ，当负载因子达到 0.7 后，就需要对哈希表进行扩容。

扩容时我们依旧按照 2 倍的方式扩容，但同时要保证哈希表的大小始终为质数。

然而，初始大小是质数，扩容 2 倍后往往就不再是质数了。该如何解决这个问题呢？

一种方案是 sgi 版本哈希表所用的方式，预先提供一个近似 2 倍递增的质数表，每次扩容时从质数表中选取合适的大小作为扩容后的哈希表大小。

/*------------------任务：实现“获取下一个 >=n 的质数的函数”---> “用于哈希表扩容”------------------*/
inline unsigned long _stl_next_prime(unsigned long n)
{
	//1.指定素数表的大小
	static const int __stl_num_primes = 28;

	//2.定义素数表覆盖常见哈希表大小
	static const unsigned long _stl_prime_list[__stl_num_primes] =   //注意：这里的素数表的类型是unsigned long 类型
	{
		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
	};

	//3.使用二分查找找到第一个 >=n 的素数
	//3.1：使用一个指针指向素数表中的“第一个素数”
	const unsigned long* first = _stl_prime_list;
	
	//3.1：使用一个指针指向素数表中的“最后一素数的下一位置”
	const unsigned long* last = _stl_prime_list + __stl_num_primes;

	//3.3：使用lower_bound()接口函数求出第一个 >=n 的素数
	const unsigned long* pos = lower_bound(first, last, n);
	
	//3.4：适合作为哈希表容量的质数
	return pos == last ? *(last - 1) : *pos;

	/*
	*  说明遍历完质数表，所有预定义的质数都比 n 小
	*  此时返回最大的质数 *(last - 1)，因为 last 是数组末尾的下一个位置，last - 1 指向最后一个有效质数 
	*/
}

二、链地址法

在开放定址法里，所有元素都会直接存放在哈希表中。

而链地址法不同，数据不再直接存储于哈希表，哈希表的每个位置存的是一个指针。

当没有数据映射到该位置时，指针为空

若有多个数据映射到同一位置，就把这些冲突数据链成链表，挂在哈希表对应位置下。

链地址法也常被叫做拉链法或者哈希桶

哈希结构

/*------------------任务：定义“哈希表节点的结构体模板”------------------*/
template<class K, class V>
struct HashNode
{
	/*------------------成员变量------------------*/

	//1.存储的键值对
	//2.下一个节点的指针

	pair<K, V> _kv;
	HashNode<K, V>* _next;

	/*------------------成员函数------------------*/
	//1.实现：哈希桶节点的“构造函数”
	HashNode(const pair<K, V>& kv)
		:_kv(kv)
		, _next(nullptr)
	{
	}
};


/*------------------任务：定义“哈希表的类模板”------------------*/
template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
private:
	/*------------------成员变量------------------*/

	//1.存储Node*类型数据的数组
	//2.记录哈希表中有效元素的变量 

	vector<HashNode<K, V>*> _tables;
	size_t _n;
    
public:
    
};

扩容操作

开放定址法的负载因子必须小于 1 ，链地址法的负载因子则没有限制，可大于 1 。

负载因子越小，哈希冲突的概率越低，空间利用率也越低

负载因子越大，哈希冲突的概率越高，空间利用率也越高

STL 中的最大负载因子基本控制在 1 ，一旦大于 1 就会触发扩容，我们后续实现也采用这种方式。

------------代码实现------------

头文件

哈希表：HashTable.h

#pragma once

//包含需要使用的头文件
#include <iostream>
#include <vector>
using namespace std;

/*------------------任务：定义哈希表函数的“通用类模板”------------------*/
template <class K>
struct HashFunc
{
	//1.重载()运算符 ---> 作用：将K类型转化为size_t类型，用于计算哈希值
	size_t operator()(const K& key)
	{
		return (size_t)key;  //注意：默认为直接转换，适用于int、long等整数类型
	} 
};



/*------------------任务：定义哈希函数的“模板特化”------------------*/
template <>
struct HashFunc<string>
{
	//1.实现：“()运算符的重载” ---> 作用：将string类型的变量转化为哈希值
	size_t operator()(const string& s)
	{
		//1.定义size_t类型变量记录string类型的变量计算的哈希值
		size_t hash = 0;

		//2.使用范围for循环遍历字符串并用BKDR算法计算其哈希值
		for (auto it : s)
		{
			//2.1：先将字符的ASCII值累加到哈希值中
			hash += it;
			//2.2：再让哈希值乘以质数131（BKDR哈希算法认为：131可有效减少冲突）
			hash *= 131;
		}

		//3.返回最终计算的哈希值
		return hash;
	}
};


/*------------------任务：实现“获取下一个 >=n 的质数的函数”---> “用于哈希表扩容”------------------*/
inline unsigned long _stl_next_prime(unsigned long n)
{
	//1.指定素数表的大小
	static const int __stl_num_primes = 28;

	//2.定义素数表覆盖常见哈希表大小
	static const unsigned long _stl_prime_list[__stl_num_primes] =   //注意：这里的素数表的类型是unsigned long 类型
	{
		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
	};

	//3.使用二分查找找到第一个 >=n 的素数
	//3.1：使用一个指针指向素数表中的“第一个素数”
	const unsigned long* first = _stl_prime_list;
	
	//3.1：使用一个指针指向素数表中的“最后一素数的下一位置”
	const unsigned long* last = _stl_prime_list + __stl_num_primes;

	//3.3：使用lower_bound()接口函数求出第一个 >=n 的素数
	const unsigned long* pos = lower_bound(first, last, n);
	
	//3.4：适合作为哈希表容量的质数
	return pos == last ? *(last - 1) : *pos;

	/*
	*  说明遍历完质数表，所有预定义的质数都比 n 小
	*  此时返回最大的质数 *(last - 1)，因为 last 是数组末尾的下一个位置，last - 1 指向最后一个有效质数 
	*/
}

开放定址法：open_address.h

#pragma once

#include "HashTable.h"

namespace open_address
{
	/*------------任务：定义哈希表中节点的三种状态的“枚举”------------*/
	enum State
	{
		EXIST,  //存在状态
		EMPTY,  //空状态
		DELETE  //删除状态
	};

	/*------------任务：定义哈希表存储的数据结构的“结构体模板”------------*/
	template <class K, class V>
	struct HashData
	{
		//1.存储键值对类型的数据
		//2.记录存储的节点的状态

		pair<K, V> _kv;
		State _state = EMPTY; //节点的状态默认为空
	};



	/*------------任务：使用“开放地址法 - 线性探测”实现哈希表------------*/
	template <class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
	private:
		/*------------------成员变量------------------*/

		//1.存储HashData类型数据的数组
		//2.记录哈希表中有效元素的变量 

		vector<HashData<K,V>> _tables;
		size_t _n;


		/*注意现在的结构的形式是：
		*    1.哈希表
		*		1.1：成员变量：容器vector
		*				1.1.1：键值对_kv
		*				1.1.2：枚举：_state
		*			               1.1.2.1：存在
		*						   1.1.2.2：空
		*						   1.1.2.2：删除
		*       1.2：成员变量：变量_n
		*/



		/*------------------成员变量------------------*/
	public:
		/*------------------成员变量（公有）------------------*/
		//1.实现：“哈希表的构造函数”
		HashTable()
			:_tables(_stl_next_prime(0))
			, _n(0)
		{
		}


		//2.实现：“查找操作” ----> 查找键对应的数据，找到返回指针，未找到返回nullptr
		HashData<K, V>* Find(const K& key)  //注意：传入“键”返回“哈希表存储元素的指针”
		{
			/*--------------第一步：计算初始哈希位置--------------*/

			//1.实例化哈希函数对象
			Hash hash;

			//2.计算哈希值 + 对其取模计算初始位置
			size_t hash_0 = hash(key) % _tables.size(); ///注意：这里相当于调用时vector的接口函数size()

			//3.定义变量记录当前的探测位置
			size_t hash_i = hash_0;

			//4.定义探测步长计数器
			size_t i = 1;


			/*--------------第二步：线性探测循环--------------*/

			while (_tables[hash_i]._state != EMPTY) //注意：遇到EMPTY标记时停止（EMPTY表示无数据，DELETE需继续）
			{
				//1.如果当前位置为EXIST且键匹配 ---> 找到了键为key的元素，返回该位置的指针 
				if (_tables[hash_i]._state == EXIST && _tables[hash_i]._kv.first == key)
				{
					return &_tables[hash_i];
				}


				//2.进行线性探测计算下一个位置
				hash_i = (hash_0 + i) % _tables.size();  //注意：取模防止越界

				//3.探测步长自增
				++i;
			}
			/*--------------第三步：--------------*/

			//“如果这个位置的状态为空 + 遇到EMPTY仍未找到” ---> 说明哈希表中并不存在键为key的元素
			return nullptr;
		}



		//3.实现：“删除操作” ---> 删除键对应的数据，成功返回true，未找到返回false
		bool Erase(const K& key)
		{
			//1.调用Find函数查找键key对应的目标的元素
			HashData<K, V>* ret = Find(key);  //注意：返回指向该元素的指针（存在）或nullptr（不存在）

			//2.判断是否找到的目标元素
			//情况1：找到了键为key的元素
			if (ret)
			{
				//1.将该元素的状态设置为DELETE（删除状态）
				ret->_state = DELETE;

				//2. 更新有效元素的数量
				--_n;

				//3.删除成功返回true即可
				return true;
			}

			//情况2：未找到键未key的元素
			else
			{
				return false;
			}

			/* 注意事项：删除键为key的元素为什么是：“将这个元素的状态设置为删除状态”呢？
			*
			*    核心逻辑：不直接清除数据，而是标记为DELETE状态
			*    原因：开放定址法中，直接删除会破坏哈希冲突形成的探测链
			*    例如：若删除中间元素，后续元素的查找可能提前终止
			*/
		}



		//4.实现：“插入操作”---> 插入键值对，成功返回true，键已存在返回false
		bool Insert(const pair<K, V>& kv)
		{
			/*----------------第一步：查重判断----------------*/
			//1.使用Find()函数先检查键kv.first是否已经存在
			if (Find(kv.first))
			{
				return false; // 当键kv.first已经存在时，插入失败
			}


			//1.进行扩容的判断：负载因子（_n/_tables.size()）≥0.7时扩容
			if (_n * 10 / _tables.size() >= 7)
			{
				/*----------------第二步：扩容操作----------------*/

				//2.创建新哈希表，容量为大于当前size的最小质数（减少哈希冲突）
				HashTable<K, V, Hash> newHt;
				newHt._tables.resize(_stl_next_prime(_tables.size() + 1));

				/*  注意事项：
				*
				*      newHt：是一个哈希表
				*	   _tables：是哈希表中的一个成员变量，本质上是vector；哈希表的另一个成员变量是_n，本质上是size_t类型的变量
				*      resize： 是vecotr容器中用来进行扩容的接口函数
				*/

				//3.遍历旧表，将所有EXIST状态的元素重新插入新表
				for (auto& htData : _tables)
				{
					if (htData._state == EXIST)
					{
						newHt.Insert(htData._kv);  // 注意：需重新计算哈希值（因表长改变，取模结果不同）
					}
				}

				//4.交换新旧哈希表：旧表.swap(新表)
				_tables.swap(newHt._tables);   //注意：当前表指向新表，旧表由newht接管（离开作用域时自动释放）
			}


			/*----------------第三步：初始位置----------------*/

			//1.实例化哈希函数对象
			Hash hashFunc;

			//2.计算哈希值 + 对其取模计算初始位置
			size_t hash_0 = hashFunc(kv.first) % _tables.size(); ///注意：这里相当于调用时vector的接口函数size()

			//3.定义变量记录当前的探测位置
			size_t hash_i = hash_0;

			//4.定义探测步长计数器
			size_t i = 1;


			/*----------------第四步：线性探测----------------*/

			//1.使用while循环第一个非EXIST位置（EMPTY或DELETE均可，EXIST需要继续寻找）
			while (_tables[hash_i]._state == EXIST)
			{
				//2.进行线性探测计算下一个位置
				hash_i = (hash_0 + i) % _tables.size();  //注意：取模防止越界，环形探测

				//3.探测步长自增
				++i;
			}

			/* 注意事项：“查找”和“插入”使用while进行线性探测的“循环判断条件不同”
			*      查找操作：while (_tables[hash_i]._state != EMPTY) ---> 查找的位置EXIST或DELETE需要继续寻找“键为key的元素”
			*
			*      插入操作：while (_tables[hashi]._state == EXIST) ---> 查找的位置EXIST需要继续寻找“空位置”
			*/


			/*----------------第五步：插入数据----------------*/

			//1.将键值对插入该位置
			_tables[hash_i]._kv = kv;

			//2.将该位置的设置为EXIST
			_tables[hash_i]._state = EXIST;

			//3.更新哈希表中有效元素的数量
			++_n;

			//4.插入成功返回true即可
			return true;

		}

	};
}

在这里插入图片描述

链地址法：hash_bucket.h

#pragma once

#include "HashTable.h"

//任务8：使用“链地址法”实现哈希表
namespace hash_bucket
{
	/*------------------任务：定义“哈希表节点的结构体模板”------------------*/
	template<class K, class V>
	struct HashNode
	{
		/*------------------成员变量------------------*/

		//1.存储的键值对
		//2.下一个节点的指针

		pair<K, V> _kv;
		HashNode<K, V>* _next;

		/*------------------成员函数------------------*/
		//1.实现：哈希桶节点的“构造函数”
		HashNode(const pair<K, V>& kv)
			:_kv(kv)
			, _next(nullptr)
		{
		}
	};


	/*------------------任务：定义“哈希表的类模板”------------------*/
	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
	private:
		/*------------------成员变量------------------*/

		//1.存储Node*类型数据的数组
		//2.记录哈希表中有效元素的变量 

		vector<HashNode<K, V>*> _tables;
		size_t _n;

		/*注意现在的结构的形式是：
		*    1.哈希表
		*      1.1：成员变量：容器vector
		*			   1.1.1：哈希表节点类型的指针：HashNode<K,V>*
		*					  1.1.1.1：键值对：_kv
		*					  1.1.1.2：下一个节点的指：_next
		*	   1.2：成员变量：变量_n
		*/

		/*------------------类型别名------------------*/

		//1.重命名哈希表节点的类型：HashNode<K,V> ---> Node
		typedef HashNode<K, V> Node;

	public:
		/*------------------成员函数------------------*/

		//1.实现：“哈希表的构造函数”
		HashTable()
			:_tables(_stl_next_prime(0)) //初始化为11个桶
			, _n(0)
		{
		}


		//2.实现：“哈希表的析构函数”
		~HashTable()
		{
			//1.遍历哈希表的每个桶（注：_tables 是存储桶头节点指针的容器）
			for (size_t i = 0; i < _tables.size(); ++i)
			{
				//2.获取当前桶的头节点指针，从第一个桶开始清理
				Node* current = _tables[i];

				//3.遍历当前桶对应的链表，逐个释放节点内存
				while (current)
				{
					//3.1：提前保存当前节点的下一个节点指针 ---> 防止删除当前节点后丢失链表连接
					Node* next = current->_next;

					//3.2：释放当前节点的内存（避免内存泄漏）
					delete current;

					//3.3：移动到下一个节点，继续清理
					current = next;
				}

				//4.将当前桶的头节点指针置空，确保析构后桶不会指向无效内存
				_tables[i] = nullptr;
			}
		}

		//3.实现：“查找操作”---> 根据键查找对应的节点，找到返回节点指针，未找到返回 nullptr
		Node* Find(const K& key)
		{
			//1. 实例化哈希函数对象
			Hash hashFunc;
			/* 代码解释：
			*     1. 利用模板参数 Hash 生成哈希函数实例
			*     2. 若 K 是 int，使用默认的整数哈希；若 K 是 string，使用特化的字符串哈希
			*/

			//2. 计算键的哈希值并取模，得到对应的桶索引
			size_t hash_i = hashFunc(key) % _tables.size();
			/* 代码解释：
			*      1. hashFunc(key)：调用哈希函数，将键转换为 size_t 类型的哈希值
			*	   2. % _tables.size()：对哈希表的桶数量取模，确定节点应该落在哪个桶中
			*	   3.目的：将任意键映射到 [0, _tables.size()-1] 范围内的桶索引
			*/

			//3. 获取对应桶的头节点，开始遍历链表
			Node* current = _tables[hash_i]; //注意：_tables[hash_i] 是桶的头节点指针


			//4. 遍历当前桶对应的链表
			while (current) //注意：若 current 为 nullptr，说明桶为空，直接跳过循环
			{
				//4.1 检查当前节点的键是否匹配目标 key
				if (current->_kv.first == key)
				{
					return current;
				}
				
				//4.2 若不匹配，移动到链表的下一个节点
				else
				{
					current = current->_next;
				}
			}

			//5. 遍历完链表后仍未找到匹配的键，返回 nullptr
			return nullptr;
		}



		//4.实现：“删除操作”---> 根据键删除哈希表中的节点，成功返回 true，失败返回 false
		bool Erase(const K& key)
		{
			//1.计算键的哈希值，确定所在桶
			Hash hashFunc;
			size_t hash_i = hashFunc(key) % _tables.size();

			//2.定义一个指向桶的头节点的指针
			Node* curr = _tables[hash_i];
			//3.定义一个指向当前节点的前驱节点的指针
			Node* prev = nullptr;  //作用记录待删除节点的前驱节点

			//3.遍历当前桶的链表
			while (curr)
			{
				//4.找到目标节点
				if (curr->_kv.first == key)
				{
					//4.2：处理待删除节点
					if (prev == nullptr)
					{
						//情况1：待删除节点是桶的头节点
						_tables[hash_i] = curr->_next;
					}
					else
					{
						//情况2：待删除节点在链表中间或末尾
						prev->_next = curr->_next;
					}

					//4.3：释放节点内存
					delete curr;

					//4.4：有效元素数量减一
					--_n;

					//4.5：删除成功
					return true;
				}

				//5.未找到目标节点，继续遍历
				//5.1：当前节点的前驱节点指向当前节点
				prev = curr;
				//5.2：当前节点指向下一个节点的位置
				curr = curr->_next;
			}

			//6.遍历结束仍未找到目标节点，删除失败
			return false;
		}





		//5.实现：“插入操作”---> 插入键值对，成功返回true，键已存在返回false
		bool Insert(const pair<K, V>& kv)
		{
			/*----------------第一步：查重判断----------------*/
			//1.使用Find()函数判断键kv.first是否已经存在
			if (Find(kv.first))
			{
				return false; // 当键kv.first已经存在时，插入失败
			}

			/*----------------第二步：扩容操作----------------*/

			//1.进行扩容判断：负载因子（元素数/桶数）等于1时触发扩容
			if (_n == _tables.size()) //目的：避免哈希冲突过多导致链表过长，影响性能
			{
				/*
				//////////////////方法一：创建新哈希表对象并复用Insert函数//////////////////

				//2.创建新哈希表，容量为大于当前size的最小质数（减少哈希冲突）
				HashTable<K, V, Hash> newHt;
				newHt._tables.resize(_stl_next_prime(_tables.size() + 1));

				//3.使用for循环变量的旧表中的所有桶 ---> 将旧表中的所有节点重新插入到新表中
				for (size_t i = 0; i < _tables.size(); i++)
				{
					//4.定义一个指针指向当前桶存储的链表的头节点
					Node* current = _tables[i];

					//5.遍历链表 ---> 将遍历的到的每个节点节点进行插入
					while (current)
					{
						//5.1：将链表中的每个节点重新插入到新表中
						newht.Insert(cur->_kv);  // 复用Insert函数（会重新计算哈希值并查重）

						//5.2：指向当前节点的current指针向后移动一位
						cur = cur->_next;

					}
				}

				//6.交换新旧哈希表：旧表.swap(新表)
				_tables.swap(newHt._tables);   //注意：当前表指向新表，旧表由newht接管（离开作用域时自动释放）

				*/



				//////////////////方法二：直接操作数组进行节点迁移（优化版）//////////////////
				//2.创建新数组，容量为大于当前size的最小质数（减少哈希冲突）
				//vector<Node*> newVector(_stl_next_prime(_tables.size() + 1));
				vector<Node*> newVector(_tables.size() * 2);

				//3.使用for循环变量的旧表中的所有桶 ---> 将旧表中的所有节点重新插入到新表中
				for (size_t i = 0; i < _tables.size(); i++)
				{
					//4.定义一个指针指向当前节点的指针
					Node* current = _tables[i];

					//5.遍历链表 ---> 将遍历的到的每个节点节点进行插入
					while (current)
					{
						//6.定义一个指针指向当前节点的下一个节点的指针 ---> 暂存下一节点避免链表断裂
						Node* next = current->_next;

						//7.实例化哈希函数
						Hash hashFunc;  //创建哈希函数对象

						//8.重新计算“遍历到节点”在新表中的桶索引 ---> 因表长变化，哈希值需重新取模
						size_t hash_i = hashFunc(current->_kv.first) % newVector.size();


						//9.使用头插入法将当前节点插入新表对应桶的头部
						//第一步：新插入的节点的下一个节点 ---> 该节点的桶索引位置的链表头节点
						current->_next = newVector[hash_i];

						//第二步：将新插入的节点的指针赋值给其对应的桶
						newVector[hash_i] = current;

						//第三步：指向当前节点的current指针向后移动一位
						current = next;
					}

					//10.清空旧表的当前桶
					_tables[i] = nullptr;  //注意：当前桶在旧表中的哈希值是i，在新表中的哈希值是hash_i
				}
				//11.交换新旧哈希表：旧表.swap(新表)
				_tables.swap(newVector);   //注意：当前表指向新表，旧表由newht接管（离开作用域时自动释放）

			}

			/*----------------第三步：插入数据----------------*/

			//1.创建新节点
			Node* newNode = new Node(kv);

			//2.实例化哈希函数
			Hash hashFunc;

			//3.计算“新插入数据”的哈希值/桶索引
			size_t hash_i = hashFunc(kv.first) % _tables.size();

			//4.1：头插第一步：
			newNode->_next = _tables[hash_i];
			//4.2：头插第二步：
			_tables[hash_i] = newNode;

			//5.更新新表中有效元素的数量
			++_n;

			//6.插入成功返回true即可
			return true;
		}

	};
}

测试文件：Test.cpp

#include "HashTable.h" 
#include "open_address.h"
#include "hash_bucket.h"

#include <string>
#include <iostream>
using namespace std;

// 辅助函数：打印测试结果
void printTestResult(const string& testName, bool result)
{
    cout << (result ? "[PASS] " : "[FAIL] ") << testName << endl;
}



/*-----------------------测试：开放寻址法哈希表-----------------------*/
void test_open_address()
{
    cout << "\n===== 测试开放寻址法哈希表 =====" << endl;

    /*--------------------创建哈希表--------------------*/
    open_address::HashTable<int, string> ht;
    cout << "创建哈希表成功" << endl;


    /*--------------------插入测试--------------------*/
    cout << "\n--- 插入测试 ---" << endl;
    bool insert1 = ht.Insert({ 1, "A" });
    printTestResult("插入键1值A", insert1);

    bool insert2 = ht.Insert({ 1, "B" }); // 重复键
    printTestResult("插入重复键1值B（期望失败）", !insert2);

    bool insert3 = ht.Insert({ 2, "C" });
    printTestResult("插入键2值C", insert3);


    /*--------------------查找测试--------------------*/
    cout << "\n--- 查找测试 ---" << endl;
    auto node1 = ht.Find(1);
    printTestResult("查找键1", node1 != nullptr && node1->_kv.second == "A");

    auto node2 = ht.Find(2);
    printTestResult("查找键2", node2 != nullptr && node2->_kv.second == "C");

    auto node3 = ht.Find(3);
    printTestResult("查找不存在的键3", node3 == nullptr);


    /*--------------------删除测试--------------------*/
    cout << "\n--- 删除测试 ---" << endl;
    bool erase1 = ht.Erase(1);
    printTestResult("删除键1", erase1);

    bool erase2 = ht.Erase(1); // 重复删除
    printTestResult("重复删除键1（期望失败）", !erase2);

    bool erase3 = ht.Erase(3); // 删除不存在的键
    printTestResult("删除不存在的键3", !erase3);


    /*--------------------扩容测试--------------------*/
    cout << "\n--- 扩容测试 ---" << endl;
    cout << "开始插入大量数据以触发扩容..." << endl;
    for (int i = 3; i < 100; ++i)
    {
        ht.Insert({ i, to_string(i) });
    }
    cout << "插入完成，验证数据访问..." << endl;

    auto node99 = ht.Find(99);
    printTestResult("查找扩容后的键99", node99 != nullptr && node99->_kv.second == "99");

    cout << "开放寻址法哈希表测试完毕" << endl;
}



/*-----------------------测试：链地址法哈希表-----------------------*/
void test_hash_bucket()
{
    cout << "\n===== 测试链地址法哈希表 =====" << endl;


    /*--------------------创建哈希表--------------------*/
    hash_bucket::HashTable<string, int> ht;
    cout << "创建哈希表成功" << endl;


    /*--------------------插入测试--------------------*/
    cout << "\n--- 插入测试 ---" << endl;
    bool insert1 = ht.Insert({ "apple", 5 });
    printTestResult("插入键apple值5", insert1);

    bool insert2 = ht.Insert({ "apple", 10 }); // 重复键
    printTestResult("插入重复键apple值10（期望失败）", !insert2);

    bool insert3 = ht.Insert({ "banana", 8 });
    printTestResult("插入键banana值8", insert3);

    /*--------------------查找测试--------------------*/
    cout << "\n--- 查找测试 ---" << endl;
    auto node1 = ht.Find("apple");
    printTestResult("查找键apple", node1 != nullptr && node1->_kv.second == 5);

    auto node2 = ht.Find("banana");
    printTestResult("查找键banana", node2 != nullptr && node2->_kv.second == 8);

    auto node3 = ht.Find("orange");
    printTestResult("查找不存在的键orange", node3 == nullptr);

    /*--------------------删除测试--------------------*/
    cout << "\n--- 删除测试 ---" << endl;
    bool erase1 = ht.Erase("apple");
    printTestResult("删除键apple", erase1);

    bool erase2 = ht.Erase("apple"); // 重复删除
    printTestResult("重复删除键apple（期望失败）", !erase2);

    bool erase3 = ht.Erase("orange"); // 删除不存在的键
    printTestResult("删除不存在的键orange", !erase3);

    /*--------------------扩容测试--------------------*/
    cout << "\n--- 扩容测试 ---" << endl;
    cout << "开始插入大量数据以触发扩容..." << endl;
    for (int i = 0; i < 100; ++i)
    {
        string key = "key_" + to_string(i);
        ht.Insert({ key, i });
    }
    cout << "插入完成，验证数据访问..." << endl;

    auto node = ht.Find("key_99");
    printTestResult("查找扩容后的键key_99", node != nullptr && node->_kv.second == 99);

    cout << "链地址法哈希表测试完毕" << endl;
}


//自定义日期结构体 ---> 用于测试复杂类型的哈希
struct Date
{
    /*-------------------成员变量-------------------*/
    int _year;
    int _month;
    int _day;


    /*-------------------成员函数-------------------*/
    //1.实现：日期类的“构造函数”
    Date(int year = 1, int month = 1, int day = 1)
        :_year(year)
        , _month(month)
        , _day(day)
    {
    }

    //2.实现：“自定义相等比较”（哈希表需要判断键是否相等）
    bool operator==(const Date& d) const
    {
        return _year == d._year
            && _month == d._month
            && _day == d._day;
    }
};

//自定义日期的哈希函数（模仿BKDR算法）
struct DateHashFunc
{
    //1.实现：“运算符()的重载” ---> 作用：用于计算日期类对象的哈希值
    size_t operator()(const Date& d)
    {
        //1.定义size_t类型的变量记录日期类对象计算的哈希值
        size_t hash = 0;

        //2.分步哈希，减少冲突概率
        hash += d._year;
        hash *= 131;   // 乘以质数，增强离散性

        hash += d._month;
        hash *= 131;

        hash += d._day;
        hash *= 131;

        //3.返回最终计算的哈希值
        return hash;
    }
};


void test01()
{
    /*---------------测试：字符串作为键的哈希表---------------*/
    hash_bucket::HashTable<string, string> ht1;

    const char* a1[] = { "abcd", "sort", "insert" };
    for (auto& it : a1)
    {
        ht1.Insert({ it, it });  // 键值均为字符串
    }

    /*---------------测试：负数作为键的哈希表（需保证哈希函数处理负数）---------------*/
    hash_bucket::HashTable<int, int> ht2;

    const int a2[] = { -19,-30,5,36,13,20,21,12 };
    for (auto& it : a2)
    {
        ht2.Insert({ it, it });
    }


    /*---------------测试：日期结构体作为键（自定义“哈希函数”和“相等比较”）---------------*/
    hash_bucket::HashTable<Date, int, DateHashFunc> ht3;

    ht3.Insert({ { 2025, 6, 29 }, 1 });  // 插入日期键值对
    ht3.Insert({ { 2025, 6, 30 }, 1 });

}

int main()
{
    test_open_address();

    test_hash_bucket();

    test01();

    return 0;
}

运行结果

在这里插入图片描述

《C++进阶之STL》【哈希表】

【哈希表】目录

前言

------------概念介绍------------

1. 什么是哈希？

------------核心术语------------

一、哈希函数

1. 哈希函数的核心特点是什么？

2. 哈希函数的设计目标是什么？

3. 常见的哈希函数有哪些？

直接定址法

除法散列法

乘法散列法

全域散列法

二、负载因子

1. 什么是负载因子？

2. 负载因子对哈希表的性能有什么影响？

3. 负载因子超过阈值时会发什么？

三、哈希冲突

四、冲突处理

方法一：开放定址法

线性探测

二次探测

双重散列

方法二：链地址法

------------基本操作------------

怎么解决键key不能取模的问题？

一、开放定址法

哈希结构

删除操作

扩容操作

二、链地址法

哈希结构

扩容操作

------------代码实现------------

头文件

哈希表：HashTable.h

开放定址法：open_address.h

链地址法：hash_bucket.h

测试文件：Test.cpp

运行结果

网站公告

今日签到

热门文章

最新发布