一、哈希函数哈希函数Hash Function是哈希表Hash Table的核心组成部分它的作用是将任意长度的输入数据称为 “键” 或 “关键字”映射到一个固定长度的输出值称为 “哈希值” 或 “散列值”这个输出值通常用于确定该键在哈希表中的存储位置。1. 哈希函数的核心特点是什么哈希函数的核心特点确定性同一输入必须始终映射到同一个哈希值。例如输入字符串apple每次通过哈希函数计算结果都应相同压缩性无论输入数据的长度如何输出的哈希值长度是固定的。例如常用的 MD5 哈希函数会将任意输入映射为 128 位的哈希值而哈希表中常用的哈希函数可能将键映射为0~n-1n为哈希表长度的整数高效性计算哈希值的过程应快速且易于实现时间复杂度通常为O(1)或O(k)k为输入数据的长度避免成为哈希表操作的性能瓶颈。2. 哈希函数的设计目标是什么哈希函数的设计目标均匀分布理想情况下哈希函数应将不同的键均匀地映射到哈希表的各个位置避免大量键集中在少数位置称为 “哈希冲突”均匀分布能保证哈希表的操作插入、查找、删除效率接近O(1)减少冲突由于输入空间可能的键远大于输出空间哈希表长度哈希冲突无法完全避免但好的哈希函数能最大限度降低冲突概率3. 常见的哈希函数有哪些直接定址法直接定址法通过直接利用关键字本身或关键字的某个线性函数来确定哈希地址从而实现关键字到存储位置的映射。直接定址法是一种简单直观的哈希函数构造方法。核心公式和基本原理直接定址法的哈希函数公式通常为H(key) key或H(key) a × key bkey是待映射的关键字。需要存储的数据的标识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 % mkey是待映射的关键字。可以是整数、经转换后的字符串哈希值等m是哈希表的大小。通常是数组长度决定了哈希地址的范围H(key)是计算出的哈希地址。即关键字在哈希表中的存储下标本质利用取余运算的 “截断” 特性把任意整数key映射到[0, m-1]区间让关键字适配哈希表的下标范围关键特性与优缺点优点实现简单一行取余运算即可完成映射编码成本极低适用性广只要能转成整数或本身是整数的关键字都能用涵盖整数、字符串、自定义结构体需先哈希转整数控制范围通过调整 m 灵活控制哈希地址范围适配不同内存、性能需求缺点冲突概率与m强相关若m选得不好比如是关键字的公约数会导致大量冲突例如关键字都是偶数、m4则哈希地址只能是0,2冲突概率飙升依赖m的选取m 若为合数尤其是 2 的幂易让哈希地址分布不均比如二进制低位相同的关键字会扎堆不适用于动态扩容哈希表扩容后 m 改变所有关键字需重新计算哈希地址迁移成本高优化m 的选取原则除法散列法的效果高度依赖m的选择工程中常用以下策略优化优化策略一选质数优先选质数作为 m能大幅降低冲突概率。原因是质数的约数少关键字取余后分布更均匀。反例若m10合数关键字10、20、30都会映射到0冲突严重正例若m11质数上述关键字会映射到0、9、8分布更分散优化策略二避免 m2^k/10^X若 M 2^Xkey % M 等价于 “保留 key 的最后 X 位二进制数”。此时只要不同 key 的最后 X 位二进制数相同哈希值就会冲突。取M 16即2^4计算63 % 16 和 31 % 1663的二进制后 8 位是00111111取最后 4 位1111→ 余数1531的二进制后 8 位是00011111取最后 4 位1111→ 余数15可见看似无关的63和31因最后 4 位相同哈希值冲突。若 M 10^Xkey % M 等价于 “保留 key 的最后 X 位十进制数”。此时只要不同 key 的最后 X 位十进制数相同哈希值就会冲突。取M 100即10^2计算112 % 100 和 12312 % 100两者最后 2 位都是12→ 余数均为12哈希值冲突优化策略三结合关键字分布调整若已知关键字的分布如都是奇数、或集中在某个区间选 m 时尽量让余数覆盖更全。关键字全是奇数m选奇数可避免 “余数全为奇数 / 偶数” 的极端情况。乘法散列法乘法散列法先将关键字key与一个在(0, 1)之间的常数A相乘得到的结果会是一个小数取这个小数的小数部分再乘以哈希表的大小m最后对结果向下取整就得到了哈希值核心公式与基本原理乘法散列法的哈希函数公式可以表示为h(key)⌊m×(key×Amod1)⌋key是要进行哈希计算的关键字。它可以是整数、字符串等各种数据类型对于非整数类型通常需要先通过其他方式将其转换为整数A是一个常数。取值范围在(0, 1)之间并且通常是一个无理数 常见的取值如√5−12黄金分割数约等于 0.6180339887这样能让哈希值分布得更均匀m是哈希表的大小。即哈希值的范围是[0, m - 1]mod1表示取小数部分。例如3.14mod1结果为0.14⌊ ⌋是向下取整符号。例如⌊3.9⌋结果为3关键特性与优缺点优点哈希值分布均匀当常数A选择合适时乘法散列法能让哈希值在哈希表中较为均匀地分布减少哈希冲突的发生。这是因为乘法运算能充分打乱关键字的二进制位使得不同关键字映射到相同哈希值的概率降低。对哈希表大小要求灵活不像除法散列法对哈希表大小m的取值有较多限制如尽量取质数等乘法散列法对m的取值相对自由m可以是任意正整数。计算效率较高乘法散列法主要涉及乘法、取小数部分和取整操作在现代计算机硬件上这些操作都能高效执行。缺点常数 A 的选择有难度虽然理论上常数A只要在(0, 1)之间且为无理数就能工作但要找到一个能在实际应用中让哈希值分布最优的A并不容易往往需要通过实验和对数据特征的了解来确定。实现相对复杂相较于简单的除法散列法乘法散列法的计算步骤更多实现代码也相对复杂一些。使用乘法散列法计算哈希值步骤示例假设要对整数关键字key 12345进行哈希计算哈希表大小m 100常数A取黄金分割数√5−12计算过程如下计算 key * A12345∗√5−12≈12345∗0.61803398877625.08749取小数部分7625.08749mod10.08749乘以哈希表大小0.08749∗1008.749向下取整得到哈希值⌊8.749⌋8全域散列法全域散列法是一种随机化哈希技术通过从精心设计的哈希函数族中随机选择哈希函数确保即使对于最坏情况下的输入也能获得良好的平均性能。基本概念在普通的哈希函数设计中如果哈希函数选择不当可能会出现一些极端情况例如对于给定的哈希函数某些特定的关键字集合会导致大量的哈希冲突使得哈希表退化为链表操作时间复杂度从期望的O(1)变为O(n)全域散列的核心思想是从一个哈希函数族中随机选择哈希函数使得对于任意给定的关键字集合哈希冲突的概率都被控制在一个较低的水平。核心原理全域散列法基于一个哈希函数族H这个函数族包含了多个不同的哈希函数。 在使用全域散列时会从这个函数族中随机选择一个哈希函数h来进行哈希操作。 从数学角度来说对于任意两个不同的关键字x和y哈希函数族H满足|{h∈H:h(x)h(y)}||H|≤1m|H|表示哈希函数族中哈希函数的个数m是哈希表的大小也就是说从哈希函数族中随机选取一个哈希函数使得两个不同关键字哈希值相同产生冲突的概率不超过1m这样就能保证在平均情况下哈希冲突的数量是比较少的。全域散列法的实现步骤定义哈希函数族需要先定义一个哈希函数族。 以简单的整数关键字为例假设关键字k是一个整数哈希表大小为m可以定义哈希函数族如下设p是一个比任何关键字值都大的质数对于每个a∈{1,2,⋯,p−1}和b∈{0,1,⋯,p−1}定义哈希函数ha,b(k)((akb)modp)modm所有这样的哈希函数构成了一个哈希函数族H假设P17M6a3b4则h34(8)((3×84)%17)%65随机选择哈希函数在构建哈希表时从哈希函数族H中随机选择一个哈希函数ha,b来使用可以通过生成随机数来确定参数a和b的值从而确定具体的哈希函数进行哈希操作使用选定的哈希函数对关键字进行哈希计算将关键字映射到哈希表的相应位置在插入、查找和删除操作中都使用这个选定的哈希函数来确定关键字在哈希表中的位置二、负载因子1. 什么是负载因子负载因子Load Factor是哈希表设计与性能分析中的核心概念用于衡量哈希表的 “填充程度”直接影响哈希冲突概率和内存利用率负载因子的定义哈希表中已存储的元素数量 / 哈希表的总容量桶的数量负载因子的计算公式λnmn是哈希表中当前存储的有效元素数量m是哈希表的总容量即桶数组的长度如vectorNode*的大小2. 负载因子对哈希表的性能有什么影响对哈希表性能的影响负载因子是哈希冲突概率和内存利用率的 “平衡器”核心影响如下 1负载因子越小 → 哈希冲突概率越低当λ→0如哈希表很空每个桶的平均元素数少链表 / 探测链短插入、查找、删除的时间复杂度接近O(1)但内存浪费严重大量桶闲置空间利用率低。2负载因子越大 → 哈希冲突概率越高当λ→1如哈希表快满桶的平均元素数多链表 / 探测链长操作时间复杂度会退化到O(n)极端情况哈希表退化为链表内存利用率高但性能暴跌。3. 负载因子超过阈值时会发什么负载因子驱动的扩容流程当负载因子超过阈值时哈希表会触发扩容Resize流程如下新建更大的桶数组新容量通常是原容量的 2 倍或接近的质数依实现而定重新映射所有元素遍历旧哈希表的所有元素用新哈希函数或新容量重新取模将元素插入新桶释放旧内存销毁旧桶数组替换为新桶数组三、哈希冲突哈希冲突Hash Collision是哈希表设计与实现中无法避免的核心问题指不同的关键字通过哈希函数计算后得到相同的哈希地址的情况。即映射到哈希表的同一个桶或位置定义对于两个不同的关键字key1≠key2若它们的哈希值满足h(key1)h(key2)则称这两个关键字发生了哈希冲突。本质哈希函数是 “多对一” 的映射输入空间无限输出空间有限根据鸽巢原理冲突必然存在。产生冲突的因素1. 哈希函数的 “压缩映射” 特性哈希函数将任意长度的输入如字符串、整数、对象映射到固定长度的哈希值如size_t类型再通过取模等操作映射到哈希表的桶索引这种 “压缩” 必然导致不同输入映射到同一输出2. 哈希表容量与关键字分布若哈希表容量 m 过小或关键字分布集中如大量关键字的哈希值在同一区间冲突概率会急剧上升示例哈希表容量 (m10)若所有关键字的哈希值取模后都为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空闲插入成功