【哈希表】目录
往期《C++初阶》回顾：《C++初阶》目录导航 往期《C++进阶》回顾：【普通类/模板类的继承 + 父类&子类的转换 + 继承的作用域 + 子类的默认成员函数】 【final + 继承与友元 + 继承与静态成员 + 继承模型 + 继承和组合】 【多态：概念 + 实现 + 拓展 + 原理】 【二叉搜索树】 【AVL树】 【红黑树】 【set/map 使用介绍】 【set/map 模拟实现】 前言 hi~ 小伙伴们大家好啊！٩(ˊᗜˋ*)و 今天我们要习得的是难度为S级的 【哈希表】 ，小伙伴们你们准备好要爆炸了吗？ ------------概念介绍------------ 1. 什么是哈希？ 哈希（Hash） 散列：是一种将任意长度的输入数据（通常称为 “键” 或 “关键字”）通过特定的数学算法（称为 “哈希函数”）映射为固定长度输出的技术。这个输出值被称为 “哈希值”、“散列值” 或 “哈希码”。哈希的核心目的是快速实现数据的查找、存储和比较 ，广泛应用于哈希表、密码学、数据校验等领域。------------核心术语------------ 一、哈希函数 哈希函数（Hash Function）将任意长度的输入数据 （称为 “键” 或 “关键字”）映射 到一个固定长度的输出值 （称为 “哈希值” 或 “散列值”）这个输出值通常用于确定该键在哈希表中的存储位置。1. 哈希函数的核心特点是什么？ 哈希函数的核心特点： 确定性 ：同一输入必须始终映射到同一个哈希值。例如 ：输入字符串"apple"每次通过哈希函数计算，结果都应相同压缩性 ：无论输入数据的长度如何，输出的哈希值长度是固定的。例如 ：常用的 MD5 哈希函数会将任意输入映射为 128 位的哈希值，而哈希表中常用的哈希函数可能将键映射为0~n-1（n为哈希表长度）的整数高效性 ：计算哈希值的过程应快速且易于实现，时间复杂度通常为 O ( 1 ) O(1) O(1)或 O ( k ) O(k) O(k)（ k k k为输入数据的长度），避免成为哈希表操作的性能瓶颈。2. 哈希函数的设计目标是什么？ 哈希函数的设计目标： 均匀分布 ：理想情况下，哈希函数应将不同的键均匀地映射到哈希表的各个位置，避免大量键集中在少数位置（称为 “哈希冲突”）均匀分布能保证哈希表的操作（插入、查找、删除）效率接近 O ( 1 ) O(1) O(1)减少冲突 ：由于输入空间（可能的键）远大于输出空间（哈希表长度），哈希冲突无法完全避免，但好的哈希函数能最大限度降低冲突概率3. 常见的哈希函数有哪些？ 直接定址法 直接定址法 关键字本身或关键字的某个线性函数来确定哈希地址，从而实现关键字到存储位置的映射。直接定址法是一种简单直观的哈希函数构造方法。核心公式和基本原理： H(key) = key 或 H(key) = a × key + bkey：是待映射的关键字。（需要存储的数据的标识）a 和 b：是常数。（a ≠ 0，用于对关键字进行线性变换）H(key)：是计算得到的哈希地址。（即：数据在哈希表中的存储位置）优缺点与适用场景： 优点 简单高效无冲突缺点 空间浪费大例如 ：key 是 1000 到 1000000 的整数），哈希表需要开辟对应范围的空间，但实际存储的关键字可能很少，导致大量空间闲置关键字需为整数例如 ：字符串、浮点数），需先转换为整数才能使用，否则无法直接映射场景 关键字的范围较小且连续（或分布集中）关键字可以直接作为地址（或通过简单线性变换后作为地址）直接定址法的实际使用案例： H(age) = age，哈希表大小只需 30 左右存储月份（1-12 月），可用 H(month) = month，哈希表大小为 12 即可除法散列法 除法散列法 用关键字对一个整数取余，把大范围的关键字映射到哈希表的有效下标区间，以此确定存储位置。除法散列法是哈希函数构造方法里的经典手段。核心公式与基本原理： H(key) = key % mkey：是待映射的关键字。（可以是整数、经转换后的字符串哈希值等）m：是哈希表的大小。（通常是数组长度，决定了哈希地址的范围）H(key)：是计算出的哈希地址。（即：关键字在哈希表中的存储下标）本质 ：利用取余运算的 “截断” 特性，把任意整数 key 映射到 [0, m-1] 区间，让关键字适配哈希表的下标范围关键特性与优缺点： 实现简单适用性广控制范围缺点 冲突概率与m强相关例如 ：关键字都是偶数、m=4，则哈希地址只能是 0,2，冲突概率飙升依赖m的选取不适用于动态扩容优化：m 的选取原则 高度依赖 m 的选择 ，工程中常用以下策略优化：优化策略一：选质数 m=10（合数），关键字 10、20、30 都会映射到 0，冲突严重正例：若 m=11（质数），上述关键字会映射到 0、9、8，分布更分散优化策略二： 避免 m=2^k/10^X 只要不同 key 的最后 X 位二进制数相同 ，哈希值就会冲突。取M = 16（即2^4），计算63 % 16 和 31 % 16：63 的二进制后 8 位是 00111111，取最后 4 位 1111 → 余数 1531 的二进制后 8 位是 00011111，取最后 4 位 1111 → 余数 15可见，看似无关的 63 和 31，因最后 4 位相同，哈希值冲突。只要不同 key 的最后 X 位十进制数相同 ，哈希值就会冲突。取M = 100（即10^2），计算112 % 100 和 12312 % 100两者最后 2 位都是 12 → 余数均为 12，哈希值冲突优化策略三：结合关键字分布调整 m 选奇数可避免 “余数全为奇数 / 偶数” 的极端情况。乘法散列法 乘法散列法key 与一个在 (0, 1) 之间的常数 A 相乘，得到的结果会是一个小数取这个小数的小数部分，再乘以哈希表的大小 m最后对结果向下取整，就得到了哈希值核心公式与基本原理： key：是要进行哈希计算的关键字。（它可以是整数、字符串等各种数据类型对于非整数类型，通常需要先通过其他方式将其转换为整数）A：是一个常数。（取值范围在 (0, 1) 之间，并且通常是一个无理数 ，常见的取值如 5 − 1 2 \frac{\sqrt{5}-1}{2} 25−1（黄金分割数，约等于 0.6180339887），这样能让哈希值分布得更均匀）m：是哈希表的大小。（即：哈希值的范围是 [0, m - 1]）m o d 1 \bmod 1 mod1：表示取小数部分。（例如： 3.14 m o d 1 3.14 \bmod 1 3.14mod1 结果为 0.14）⌊ ⌋ \lfloor \ \rfloor ⌊ ⌋：是向下取整符号。（例如： ⌊ 3.9 ⌋ \lfloor 3.9 \rfloor ⌊3.9⌋ 结果为 3）关键特性与优缺点： 哈希值分布均匀 A 选择合适时，乘法散列法能让哈希值在哈希表中较为均匀地分布，减少哈希冲突的发生。这是因为乘法运算能充分打乱关键字的二进制位，使得不同关键字映射到相同哈希值的概率降低。对哈希表大小要求灵活 m 的取值有较多限制（如：尽量取质数等），乘法散列法对 m 的取值相对自由，m 可以是任意正整数。计算效率较高缺点 常数 A 的选择有难度 A 只要在 (0, 1) 之间且为无理数就能工作，但要找到一个能在实际应用中让哈希值分布最优的 A 并不容易，往往需要通过实验和对数据特征的了解来确定。实现相对复杂使用乘法散列法计算哈希值步骤示例： key = 12345 进行哈希计算，哈希表大小 m = 100，常数 A 取黄金分割数 5 − 1 2 \frac{\sqrt{5}-1}{2} 25−1 ，计算过程如下：计算 key * A取小数部分乘以哈希表大小向下取整得到哈希值全域散列法 全域散列法随机化哈希技术 ，通过从精心设计的哈希函数族中随机选择哈希函数，确保即使对于最坏情况下的输入也能获得良好的平均性能。基本概念： 例如 ：对于给定的哈希函数，某些特定的关键字集合会导致大量的哈希冲突，使得哈希表退化为链表，操作时间复杂度从期望的 O ( 1 ) O(1) O(1) 变为 O ( n ) O(n) O(n)核心原理： 全域散列法的实现步骤： 定义哈希函数族 ：需要先定义一个哈希函数族。以简单的整数关键字为例，假设关键字 k k k 是一个整数，哈希表大小为 m m m，可以定义哈希函数族如下：所有这样的哈希函数构成了一个哈希函数族 H \mathcal{H} H假设 ： P = 17 P=17 P=17， M = 6 M=6 M=6， a = 3 a=3 a=3， b = 4 b=4 b=4，则 h 34 ( 8 ) = ( ( 3 × 8 + 4 ) % 17 ) % 6 = 5 h_{34}(8) = ((3 \times 8 + 4) \% 17) \% 6 = 5 h34(8)=((3×8+4)%17)%6=5设 p p p 是一个比任何关键字值都大的质数对于每个 a ∈ { 1 , 2 , ⋯ , p − 1 } a \in \{1, 2, \cdots, p - 1\} a∈{1,2,⋯,p−1} 和 b ∈ { 0 , 1 , ⋯ , p − 1 } b \in \{0, 1, \cdots, p - 1\} b∈{0,1,⋯,p−1}定义哈希函数： h a , b ( k ) = ( ( a k + b ) m o d p ) m o d m h_{a,b}(k) = ((ak + b) \bmod p) \bmod m ha,b(k)=((ak+b)modp)modm随机选择哈希函数 ：在构建哈希表时，从哈希函数族 H \mathcal{H} H 中随机选择一个哈希函数 h a , b h_{a,b} ha,b 来使用可以通过生成随机数来确定参数 a a a 和 b b b 的值，从而确定具体的哈希函数进行哈希操作 ：使用选定的哈希函数对关键字进行哈希计算，将关键字映射到哈希表的相应位置在插入、查找和删除操作中，都使用这个选定的哈希函数来确定关键字在哈希表中的位置二、负载因子 1. 什么是负载因子？ 负载因子（Load Factor） 哈希冲突概率和内存利用率负载因子的定义 ：哈希表中已存储的元素数量 / 哈希表的总容量（桶的数量） ： λ = n m \lambda = \frac{n}{m} λ=mnn：是哈希表中当前存储的有效元素数量m：是哈希表的总容量（即桶数组的长度，如：vector<Node*> 的大小）2. 负载因子对哈希表的性能有什么影响？ 对哈希表性能的影响： 哈希冲突概率 和内存利用率 的 “平衡器”，核心影响如下：插入、查找、删除的时间复杂度接近 O ( 1 ) O(1) O(1) 但内存浪费严重（大量桶闲置），空间利用率低。操作时间复杂度会退化到 O ( n ) O(n) O(n) （极端情况哈希表退化为链表）内存利用率高，但性能暴跌。3. 负载因子超过阈值时会发什么？ 负载因子驱动的扩容流程： 扩容（Resize） ，流程如下：新建更大的桶数组 ：新容量通常是原容量的 2 倍（或接近的质数，依实现而定）重新映射所有元素 ：遍历旧哈希表的所有元素，用新哈希函数（或新容量重新取模）将元素插入新桶释放旧内存 ：销毁旧桶数组，替换为新桶数组三、哈希冲突 哈希冲突（Hash Collision）不同的关键字通过哈希函数计算后，得到相同的哈希地址 的情况。（即：映射到哈希表的同一个桶或位置）定义 ：对于两个不同的关键字 k e y 1 ≠ k e y 2 key_1 \neq key_2 key1=key2，若它们的哈希值满足 h ( k e y 1 ) = h ( k e y 2 ) h(key_1) = h(key_2) h(key1)=h(key2)，则称这两个关键字发生了哈希冲突。本质 ：哈希函数是 “多对一” 的映射（输入空间无限，输出空间有限），根据鸽巢原理，冲突必然存在。产生冲突的因素： 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 ( k e y ) h_2(key) h2(key) 的约束： 互质 （ （ （即 ：最大公约数 gcd ( h 2 ( k e y ) , M ) = 1 ） \gcd(h_2(key), M) = 1） gcd(h2(key),M)=1）h 2 ( k e y ) h_2(key) h2(key) 的简单取值方法： 当 M 是 2 的整数次幂时 [0, M-1] 中任选一个奇数 作为 h 2 ( k e y ) h_2(key) h2(key)因为奇数与 2 的幂次互质，可保证探测覆盖所有位置当 M 是质数时互质的必要性（关键原理）: 无法覆盖整个哈希表 ，导致部分空闲位置永远无法被找到。哈希表大小 M = 12 M = 12 M=12，初始冲突位置 hash0 = 1，偏移量 h 2 ( k e y ) = 3 （ gcd ( 3 ， 12 ) = 3 > 1 ） h_2(key) = 3 （\gcd( 3，12) = 3 > 1） h2(key)=3（gcd(3，12)=3>1）探测序列为： （ 1 + 1 × 3 ) % 12 = 4 ( 1 + 2 × 3 ) % 12 = 7 ( 1 + 3 × 3 ) % 12 = 10 ( 1 + 4 × 3 ) % 12 = 1 （1 + 1 \times 3) \% 12 = 4(1 + 2 \times 3) \% 12 = 7(1 + 3 \times 3) \% 12 = 10(1 + 4 \times 3) \% 12 = 1 （1+1×3)%12=4(1+2×3)%12=7(1+3×3)%12=10(1+4×3)%12=1（循环）可见，探测位置仅为 {1, 4, 7, 10}，共 12 / 3 = 4 12 / 3 = 4 12/3=4 个位置，无法覆盖整个哈希表。总结：双重哈希的价值 两个哈希函数 和互质约束 ，让探测序列更均匀地覆盖哈希表，避免了线性探测的 “聚集问题”。相比其他探测方法（如：线性探测、二次探测），双重哈希的冲突解决效率更高，适合对性能要求严格的场景。方法二：链地址法 链地址法（Separate Chaining） 拉链法、哈希桶法 ）：是哈希表解决哈希冲突的经典方案之一。它的核心思路是：用数组 + 链表（或其他动态结构）的组合，让冲突元素 “链” 在一起 ，既简单又高效。链地址法的原理： 数组 （称为 “哈希桶数组” ），每个数组元素对应一个链表 / 动态结构 （如：链表、红黑树、跳表 ）插入元素时 ：通过哈希函数计算 key 的哈希值，确定要放入数组的哪个 “桶”（即：数组索引 ）若该桶对应的链表为空，直接插入若已存在元素（发生冲突 ），就把新元素追加到链表末尾查找/删除元素时 ：先通过哈希函数找到对应桶再遍历链表逐个匹配 key优缺点分析： 冲突处理简单空间灵活 负载因子 = 元素数 / 桶数 ）可大于 1 ，空间利用率高无聚集问题缺点 遍历开销 O(n)（n 是链表长度 ）额外空间------------基本操作------------ 怎么解决键key不能取模的问题？ 通过上面的学习我们知道了使用哈希函数要把关键字映射到数组的对应位置上，通常来说，关键字是整数的话进行映射计算会更方便。哈哈，没错要是关键字本身不是整数， 是 string、Date 等类型时，无法直接对 key 进行取模操作的话，我们要怎么做呢？ 仿函数 哈希函数对象 ），该仿函数的作用是，把 key 转换成一个可用于取模的整数。若 key 本身能较方便地转换为整数 ，且转换后不易引发哈希冲突，直接使用哈希表默认的仿函数参数即可若 key 无法直接转换为整数 ，就需要我们自行实现一个仿函数，并传递给哈希表 由于 string 作为哈希表的 key 十分常见，我们可以针对性地对 string 类型做特化处理 （即：专门为 string 设计更适配的哈希转换逻辑 ） /*------------------任务：定义哈希表函数的“结构体模板”------------------*/template<classK>structHashFunc{//1.重载()运算符 ---> 作用：将K类型转化为size_t类型，用于计算哈希值 size_t operator()(const K& key){return(size_t)key;//注意：默认为直接转换，适用于int、long等整数类型}};/*------------------任务：定义哈希函数的“模板特化”------------------*/template<>structHashFunc<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;}};一、开放定址法 在实践里，开放定址法的表现不如接下来要讲的链地址法。 哈希结构 /*------------任务：定义哈希表中节点的三种状态的“枚举”------------*/enumState{ EXIST,//存在状态 EMPTY,//空状态 DELETE //删除状态};/*------------任务：定义哈希表存储的数据结构的“结构体模板”------------*/template<classK,classV>structHashData{//1.存储键值对类型的数据//2.记录存储的节点的状态 pair<K, V> _kv; State _state = EMPTY;//节点的状态默认为空};/*------------任务：使用“开放地址法 - 线性探测”实现哈希表------------*/template<classK,classV,classHash= HashFunc<K>>classHashTable{private:/*------------------成员变量------------------*///1.存储HashData类型数据的数组//2.记录哈希表中有效元素的变量 vector<HashData<K,V>> _tables; size_t _n;public://…………};删除操作 要注意的是，这里需要给每个存储值的位置添加一个状态标识，否则删除某些值后，会影响后续冲突值的查找。举个例子，如下若删除 30 ，会导致查找 20 失败但如果我们给每个位置设置 {EXIST, EMPTY, DELETE} 这样的状态标识，删除 30 时，就不用真正删除对应的值，而是把该位置状态改为 DELETEEMPTY 状态才停止探测，就能顺利找到 20 了 扩容操作 我们将哈希表的负载因子控制在 0.7 ，当负载因子达到 0.7 后，就需要对哈希表进行扩容。然而，初始大小是质数，扩容 2 倍后往往就不再是质数了。该如何解决这个问题呢？ /*------------------任务：实现“获取下一个 >=n 的质数的函数”---> “用于哈希表扩容”------------------*/inlineunsignedlong_stl_next_prime(unsignedlong n){//1.指定素数表的大小staticconstint __stl_num_primes =28;//2.定义素数表覆盖常见哈希表大小staticconstunsignedlong _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：使用一个指针指向素数表中的“第一个素数”constunsignedlong* first = _stl_prime_list;//3.1：使用一个指针指向素数表中的“最后一素数的下一位置”constunsignedlong* last = _stl_prime_list + __stl_num_primes;//3.3：使用lower_bound()接口函数求出第一个 >=n 的素数constunsignedlong* pos =lower_bound(first, last, n);//3.4：适合作为哈希表容量的质数return pos == last ?*(last -1):*pos;/* * 说明遍历完质数表，所有预定义的质数都比 n 小 * 此时返回最大的质数 *(last - 1)，因为 last 是数组末尾的下一个位置，last - 1 指向最后一个有效质数 */}二、链地址法 在开放定址法里，所有元素都会直接存放在哈希表中。链地址法也常被叫做拉链法或者哈希桶 哈希结构 /*------------------任务：定义“哈希表节点的结构体模板”------------------*/template<classK,classV>structHashNode{/*------------------成员变量------------------*///1.存储的键值对//2.下一个节点的指针 pair<K, V> _kv; HashNode<K, V>* _next;/*------------------成员函数------------------*///1.实现：哈希桶节点的“构造函数”HashNode(const pair<K, V>& kv):_kv(kv),_next(nullptr){}};/*------------------任务：定义“哈希表的类模板”------------------*/template<classK,classV,classHash= HashFunc<K>>classHashTable{private:/*------------------成员变量------------------*///1.存储Node*类型数据的数组//2.记录哈希表中有效元素的变量 vector<HashNode<K, V>*> _tables; size_t _n;public:};扩容操作 开放定址法的负载因子必须小于 1 ，链地址法的负载因子则没有限制，可大于 1 。负载因子越小，哈希冲突的概率越低，空间利用率也越低负载因子越大，哈希冲突的概率越高，空间利用率也越高 ------------代码实现------------ 头文件 哈希表：HashTable.h #pragmaonce//包含需要使用的头文件#include<iostream>#include<vector>usingnamespace std;/*------------------任务：定义哈希表函数的“通用类模板”------------------*/template<classK>structHashFunc{//1.重载()运算符 ---> 作用：将K类型转化为size_t类型，用于计算哈希值 size_t operator()(const K& key){return(size_t)key;//注意：默认为直接转换，适用于int、long等整数类型}};/*------------------任务：定义哈希函数的“模板特化”------------------*/template<>structHashFunc<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 的质数的函数”---> “用于哈希表扩容”------------------*/inlineunsignedlong_stl_next_prime(unsignedlong n){//1.指定素数表的大小staticconstint __stl_num_primes =28;//2.定义素数表覆盖常见哈希表大小staticconstunsignedlong _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：使用一个指针指向素数表中的“第一个素数”constunsignedlong* first = _stl_prime_list;//3.1：使用一个指针指向素数表中的“最后一素数的下一位置”constunsignedlong* last = _stl_prime_list + __stl_num_primes;//3.3：使用lower_bound()接口函数求出第一个 >=n 的素数constunsignedlong* pos =lower_bound(first, last, n);//3.4：适合作为哈希表容量的质数return pos == last ?*(last -1):*pos;/* * 说明遍历完质数表，所有预定义的质数都比 n 小 * 此时返回最大的质数 *(last - 1)，因为 last 是数组末尾的下一个位置，last - 1 指向最后一个有效质数 */}开放定址法：open_address.h #pragmaonce#include"HashTable.h"namespace open_address {/*------------任务：定义哈希表中节点的三种状态的“枚举”------------*/enumState{ EXIST,//存在状态 EMPTY,//空状态 DELETE //删除状态};/*------------任务：定义哈希表存储的数据结构的“结构体模板”------------*/template<classK,classV>structHashData{//1.存储键值对类型的数据//2.记录存储的节点的状态 pair<K, V> _kv; State _state = EMPTY;//节点的状态默认为空};/*------------任务：使用“开放地址法 - 线性探测”实现哈希表------------*/template<classK,classV,classHash= HashFunc<K>>classHashTable{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的元素returnnullptr;}//3.实现：“删除操作” ---> 删除键对应的数据，成功返回true，未找到返回falseboolErase(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即可returntrue;}//情况2：未找到键未key的元素else{returnfalse;}/* 注意事项：删除键为key的元素为什么是：“将这个元素的状态设置为删除状态”呢？ * * 核心逻辑：不直接清除数据，而是标记为DELETE状态 * 原因：开放定址法中，直接删除会破坏哈希冲突形成的探测链 * 例如：若删除中间元素，后续元素的查找可能提前终止 */}//4.实现：“插入操作”---> 插入键值对，成功返回true，键已存在返回falseboolInsert(const pair<K, V>& kv){/*----------------第一步：查重判断----------------*///1.使用Find()函数先检查键kv.first是否已经存在if(Find(kv.first)){returnfalse;// 当键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即可returntrue;}};}链地址法：hash_bucket.h #pragmaonce#include"HashTable.h"//任务8：使用“链地址法”实现哈希表namespace hash_bucket {/*------------------任务：定义“哈希表节点的结构体模板”------------------*/template<classK,classV>structHashNode{/*------------------成员变量------------------*///1.存储的键值对//2.下一个节点的指针 pair<K, V> _kv; HashNode<K, V>* _next;/*------------------成员函数------------------*///1.实现：哈希桶节点的“构造函数”HashNode(const pair<K, V>& kv):_kv(kv),_next(nullptr){}};/*------------------任务：定义“哈希表的类模板”------------------*/template<classK,classV,classHash= HashFunc<K>>classHashTable{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> ---> Nodetypedef 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 检查当前节点的键是否匹配目标 keyif(current->_kv.first == key){return current;}//4.2 若不匹配，移动到链表的下一个节点else{ current = current->_next;}}//5. 遍历完链表后仍未找到匹配的键，返回 nullptrreturnnullptr;}//4.实现：“删除操作”---> 根据键删除哈希表中的节点，成功返回 true，失败返回 falseboolErase(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：删除成功returntrue;}//5.未找到目标节点，继续遍历//5.1：当前节点的前驱节点指向当前节点 prev = curr;//5.2：当前节点指向下一个节点的位置 curr = curr->_next;}//6.遍历结束仍未找到目标节点，删除失败returnfalse;}//5.实现：“插入操作”---> 插入键值对，成功返回true，键已存在返回falseboolInsert(const pair<K, V>& kv){/*----------------第一步：查重判断----------------*///1.使用Find()函数判断键kv.first是否已经存在if(Find(kv.first)){returnfalse;// 当键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 =newNode(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即可returntrue;}};}测试文件：Test.cpp #include"HashTable.h"#include"open_address.h"#include"hash_bucket.h"#include<string>#include<iostream>usingnamespace std;// 辅助函数：打印测试结果voidprintTestResult(const string& testName,bool result){ cout <<(result ?"[PASS] ":"[FAIL] ")<< testName << endl;}/*-----------------------测试：开放寻址法哈希表-----------------------*/voidtest_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;}/*-----------------------测试：链地址法哈希表-----------------------*/voidtest_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;}//自定义日期结构体 ---> 用于测试复杂类型的哈希structDate{/*-------------------成员变量-------------------*/int _year;int _month;int _day;/*-------------------成员函数-------------------*///1.实现：日期类的“构造函数”Date(int year =1,int month =1,int day =1):_year(year),_month(month),_day(day){}//2.实现：“自定义相等比较”（哈希表需要判断键是否相等）booloperator==(const Date& d)const{return _year == d._year && _month == d._month && _day == d._day;}};//自定义日期的哈希函数（模仿BKDR算法）structDateHashFunc{//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;}};voidtest01(){/*---------------测试：字符串作为键的哈希表---------------*/ hash_bucket::HashTable<string, string> ht1;constchar* a1[]={"abcd","sort","insert"};for(auto& it : a1){ ht1.Insert({ it, it });// 键值均为字符串}/*---------------测试：负数作为键的哈希表（需保证哈希函数处理负数）---------------*/ hash_bucket::HashTable<int,int> ht2;constint 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});}intmain(){test_open_address();test_hash_bucket();test01();return0;}运行结果
