【数据结构】 哈希表查找—哈希函数、哈希冲突

摘要
本文介绍了哈希表的基本概念及其应用。首先阐述了哈希表的特点及查找过程，并详细讨论了构建哈希表所涉及的关键技术。文章重点介绍了几种常用的构造哈希函数的方法，如除留余数法、直接定址法等，并探讨了处理冲突的有效策略，如开放定址法和链地址法。最后分析了哈希表的查找性能与装载因子的关系，并强调了合理选择处理冲突方法的重要性以提高查询效率。

目录

一、哈希表的定义

二、 常用的哈希函数

三、 处理冲突的方法

四、哈希表的查找和性能分析

💟 创作不易，不妨点赞 💚评论❤️收藏💙一下

一、哈希表的定义

1）查找总结

查找表的各种数据结构**（线性表、二叉排序树、平衡二叉树、B-树等）** 共同特点：

复制代码

*

记录在表中的位置和它的关键字之间不存在一个确定的关系。

复制代码

*

而通过关键字与关键字的之间的关系 ，确定在表中的关系。而不是因为关键字本身，确定在表中的关系

查找流程：针对给定值按照预设的排序规则在数据集中对各个关键字段进行对比分析的过程即为查找流程。

查找的效率：取决于和给定值 进行比较的关键字个数。

用以上方法表示的查找表，其平均查找长度都不为零。

不同的表示方法，其差别仅在于：关键字和给定值进行比较的顺序不同。

2）哈希函数

对于高频使用的查找表,我们追求ASL=0. 当且仅当key能够准确地定位到该表中时

唯一的策略是提前了解查询关键字在表中的位置。具体来说，在表中为每个位置设定与其对应的关键字之间的固定关联关系。

当进行查找操作时，在获取键值的过程中可以直接确定数据元素的地址，这种类型的查找结构被称为哈希表。

键通过哈希函数H映射至存储位置。
其中，
键（Key）：基本数据单位。
哈希函数（Hash Function）或散列算法（Hash Algorithm）：用于计算存储位置的数学变换。
存储位置由哈希值决定（Hash Address）。

哈希表中查找数据元素

63 --> h(63) = 63 % 11 = 8 ，哈希地址为8，从下标为8的存储单元中取出该数据元素即可。

3）哈希冲突

哈希函数是一个映象，即：将关键字的集合映射到某个地址集合上 。

实例：52 --> h(52) = 52 % 11 = 8 ，哈希地址也为8 ！！！

由于哈希函数是一个压缩映象 ，因此，在一般情况下，很容易产生“冲突”现象，

即：key1 ≠ key2，而 h(key1) = h(key2)

实际上，在必要时应尽力减少冲突的发生（无法完全避免）。因此，在构造这种特殊的查找表的过程中，在选择了具有较低冲突可能性的哈希函数之后；同时必须采用有效的处理冲突方法。

4）哈希表

通过设定的哈希函数H(key)及选定的处理冲突策略, 采用一种系统的方法将一组关键词映射至一个有限且地址连续的地址空间中, 并以该关键字在地址集中的映射结果作为相应数据元素在表中的存储位置, 这种数据结构通过哈希函数处理关键字以确定存储位置的方式构建, 我们称之为'哈希表'。

所以，构建哈希表需要解决以下两个问题：

复制代码

1.

如何构建哈希函数

复制代码

2.

如何解决冲突

二、 常用的哈希函数

多种方法可用于构造哈希函数，而其核心理念则是最大限度实现对关键字集合空间的均衡分配。

对数字的关键字常用的是以下构造方法：

复制代码

1.

除留余数法

复制代码

2.

平方取中法

复制代码

3.

直接定址法

复制代码

4.

折叠法

复制代码

5.

数字分析法

复制代码

6.

随机数法

若是非数字关键字，则需先对其进行数字化处理。

约定：

1. 哈希表长度：m

2. 哈希函数：H

3. H的作用：将关键字转换成[0, m-1]中的整数

1）除留余数法

采用一个略小于哈希表大小m的质数p对所有关键字进行处理，在计算时会得到余数值作为新的哈希地址

H(k) = k mod p, 其中p不超过m。
采用除留余数法时需要谨慎选择模数p，在特定情况下如果模数选择不当会导致大量冲突。

哈希表长度与其最大素数

实例：一组关键字：12、39、18、24、33、21

2）直接地址法

取关键字的某个线性函数值 为哈希地址

H (key) = a * key + b （a、b为常数）

此法仅适合于：地址集合的大小 == 关键字集合的大小 。

该方法的采用频率较低；其原因在于，在关键字集合中的元素通常呈现离散特征；此外，在规模上，关键字集合往往超出哈希表的地址空间。

3）数字分析法

在处理的关键字长度超过存储区域地址码长度时（...），可以通过对关键字各部分进行详细分析来确定（...），舍弃那些在分布上不够均匀的部分（...），从而选择那些分布较为均匀的关键字部分作为哈希地址（...）。这种方法被称为数字分析法。

此方法仅适用于能够预估全部关键码在各位上的数字出现频率的情况。

4）平方取中法

采用平方后的关键部分（取其中一部分）来作为存储地址。其中关键数据经平方后得到的部分的主要目的是为了增大差异程度。这些部分还能够反映整个数据各部分的信息。

该方法只适用于：在该关键字的每一位上都呈现数字重复出现的频率较高情况。

5）折叠法

将关键字分割成若干部分 ，然后取它们的叠加和 为哈希地址。

有两种叠加处理方法：

移位叠加：将分隔后的各部分最低位对齐，然后相加。

间界叠加：从一端向另一端沿分割界来回折叠后，然后对齐最后一位相加。

此方法适合于：关键字的数字位数特别多。

6）随机数法

设定哈希函数为：

H(key) = Random(key)，其中Random为伪随机函数

此方法用于对长度不等的关键字构造哈希函数。

7）总结

在实际工作中，在不同情况下采用适当的哈希函数。通常要考虑的关键因素包括：

评估哈希函数计算所需时间

关键词长度参数

哈希表规模

关键词分布特征

记录访问频率情况

三、 处理冲突的方法

1）概述

在实际构建表格时，选择哈希函数的具体构造方法主要取决于关键字集合的特性和形态。其核心依据在于：通过优化设计使得哈希冲突的发生概率得到最大限度地降低。

处理冲突的实际含义是，为产生冲突的地址寻找下一个哈希地址 。

复制代码

1.

开放定址法

复制代码

2.

链地址法

复制代码

3.

公共溢出区法

复制代码

4.

再哈希法

2）开放定址法

开放定址法处理冲突的基本思想是：当关键词冲突时 ，生成一个探针序列，并依次尝试这些地址位置直至寻找到第一个未被占用的开放地址 ，从而将该关键字存入该位置中。

开放定址法的一般形式：Hi = ( H(key) + di ) % m ，（i= 1,2,...,k (k≤m-1) ）

对增量di有三种取法：

线性探测法：遵循di = 1,2, ..., m-1的规律进行存储位置检查，在首次找到可用存储单元后完成插入操作。

二次探测法：按照di = 1²,-1²,2²,-2²,...,q²,-q²（q≤m/2）的顺序进行正反交替检查，在至少一半的存储单元中寻找空闲位置。

双哈希函数探测法：通过Hi=( H(key) + iRH(key) ) % m（i=1,2, ..., m-1）计算候选存储地址序列，在发生冲突时采用第二个哈希函数Hi=( H(key) + iRH(key) ) % m继续寻找可用空间。

实例：关键字集合9个数据元素 {19,01,23,14,55,68,11,82,36}

实例1：线性探测法 *

在查询过程中，在某个关键词出现空指针异常时会返回失败状态。后续的关键词将通过探测确定其位置。

实例2：二次探测法 *

关键字6的比较次数

复制代码

  *

68 --> H( % 11) --> 2，占用，比较1次

复制代码

  *

68 --> H ( % 11 + 12 ) --> 3，占用，比较2次

复制代码

  *

68 --> H (% 11 - 12) --> 1，占用，比较3次

复制代码

  *

68 --> H (% 11 + 22) --> 6，未占用，比较4次

官架子11的比较次数

复制代码

  *

11 --> H( % 11) --> 0，占用，比较1次

复制代码

  *

11 --> H( % 11+ 12) --> 1，占用，比较2次

复制代码

  *

11 --> H( % 11- 12) --> -1 --> -1+11 --> 10，未占用，比较3次

实例3：双哈希函数探测法 *

关键字23比较次数

复制代码

  *

23 --> H( % 11) --> 1, 占用，比较1次

复制代码

  *

23 --> (H(23) + H2(23) ) % 11 --> (1 + 69 %10 + 1) % 11 --> 11 % 11 --> 0，未占用，比较2次

关键字36比较次数

复制代码

  *

36 --> H(36) --> 3 , 占用，比较1次

复制代码

  *

36 --> (H(36) + H2(36) ) % 11 --> (3 + 9) % 11 --> 1，占用，比较2次

复制代码

  *

36 --> (H(36) + 2×H2(36) ) % 11 --> (3 + 18) % 11 --> 10，未占用，比较3次

3）链地址法

链地址法：将所有哈希地址相同的记录都链接在同一链表中 。

例如：关键字序列{19,01,23,14,55,68,11,82,36}，哈希函数设为 H(key) = key MOD 7

该算法的成功率为所有样本特征值与其对应频次乘积之和与总样本数量之比。
//为了统计不同特征值出现次数的情况
比如，在具体应用中：
ASL的成功率为（特征值1出现次数 × 特征值权重系数之和）加上（特征值2出现次数 × 特征值权重系数之和）加上... ，然后除以总样本数量。
类似地，在具体案例中：
ASL的失败率为未命中目标样本数量与总样本数量之比。
//为了确保至少存在一个有效数据项
比如，在实际操作中：
当模型运行时，
如果所有预测结果都未命中真实标签，则认为模型表现为空；
否则，
计算未命中目标数目与总样本数目之间的比率作为模型性能评估指标。

4）公共溢出区法

基本思想是：除基本的存储区（称为基本表）之外，另建一个公共溢出区（称为溢出表）

当不发生冲突时，数据元素可存入基本表中；

当发生冲突时，不管哈希地址是什么，数据元素都存入溢出表。

查找时，对给定值K通过哈希函数计算出哈希地址i，先与基本表对应的存储单元相比较，若相等，则查询成功；否则，再到溢出表中查找。

适用于，冲突的数据很少 的情况

5）再哈希法

主要思想：在出现冲突时采用另一种哈希函数计算新的哈希地址 ，如果仍然存在碰撞现象，则继续采用后续的哈希函数进行计算操作直至达到设定的最大次数k次。
预先设定一组不同的哈希函数序列：
Hi = RHi(key) (i=1,2,...,k)，其中RHi表示一系列互不相同的哈希函数。
这种方法虽然能够有效减少数据碰撞的可能性但会增加计算过程的时间开销。

四、哈希表的查找和性能分析

1）哈希表的查找

查找过程和造表过程一致。

假设采用开放地址法处理冲突，则查找过程为：

通过哈希函数H计算给定值K对应的索引i。
若r[i]为空，则查找失败。
若r[i]中的键与K匹配，则查找成功。
依次检查后续地址Hi，在遍历过程中检测到目标键或空单元格时停止搜索。

2）哈希表查找的性能分析

从查找过程得知，哈希表查找的平均查找长度实际上并不等于零。

决定哈希表查找的ASL的因素：

采用的哈希函数

选定的冲突处理方法

哈希表饱和程度及装载因子α=n/m值的具体数值（其中n表示哈希表中的记录数，m表示哈希表的长度）

通常情况下，在评估哈希表性能时（即讨论ASL的情况下），我们假设所选择使用的哈希函数遵循均匀分布特性，并不考虑其相关因素的影响。因此，在这种设定下，哈希表的平均查找长度（ASL）主要取决于解决冲突策略和装载因子这两个关键参数。

从以上结果可见：

哈希表的平均查找长度是α的函数，而不是n的函数。

这一现象表明，在构建查询表时设置适当的装填因子α以控制平均查找长度不超过某个范围。其独特之处在于这是哈希表所特有的特点。

写到最后

四季轮换，已经数不清凋零了多少， 愿我们往后能向心而行，一路招摇胜！

🐋** 你的支持认可是我创作的动力**

💟创作不易，不妨 点赞💚评论❤️收藏💙一下

😘**** 感谢大佬们的支持，欢迎各位前来不吝赐教