开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【数据结构】哈希表查找—哈希函数、哈希冲突 -> 正文阅读

[数据结构与算法]【数据结构】哈希表查找—哈希函数、哈希冲突

一、哈希表的定义

1）查找总结

查找表的各种数据结构（线性表、二叉排序树、平衡二叉树、B-树等）共同特点：
- ?记录在表中的位置和它的关键字之间不存在一个确定的关系。
- 而通过关键字与关键字的之间的关系，确定在表中的关系。而不是因为关键字本身，确定在表中的关系
查找的过程：为给定值按某种顺序和记录集合中，各个关键字进行比较的一个过程。
查找的效率：取决于和给定值进行比较的关键字个数。

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

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

2）哈希函数

对于频繁使用的查找表，希望 ASL = 0. （因为key可以确定在表中的位置，ASL就为0）
只有一个办法：预先知道所查关键字在表中的位置。即记录在表中位置和其关键字之间存在一种确定的关系。
在查找时，直接通过关键字获得数据元素的存储位置，此类查找表就是哈希表。
key --> H(key) --> 存储位置
- key：关键字
- H ：散列函数或哈希(Hash)函数
- 存储位置：函数值（哈希地址）

哈希表中查找数据元素

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(key) = key % p , (p≤m)
- 使用除留余数法，选取合适的p很重要，若p选择不当，在某些选择关键字的方式下，会造成严重冲突。
哈希表长度与其最大素数

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

// 若 p = 9
对应的哈希函数取值：3、3、0、6、6、3
// 若 p = 7
对应的哈希函数取值：5、4、4、3、5、0

2）直接地址法

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

H (key) = a * key + b （a、b为常数）
此法仅适合于：地址集合的大小 == 关键字集合的大小。
此方法很少使用，因为关键字集合中的数据元素往往是离散的，而且关键字集合通常比哈希地址集合大。

3）数字分析法

对于关键字的位数比存储区域的地址码位数多的情况，可以采取对关键字的各位进行分析，丢掉分布不均匀的位，留下分布均匀的位作为哈希地址，这种方法称为数字分析法。

此方法仅适合于：能预先估计出全体关键字的每一位上各个数字出现的频度。

4）平方取中法

以关键字的平方值的中间几位作为存储地址。求“关键字的平方值”的目的是“扩大差别”，同时平方值的中间各位又能受到整个关键字中各位的影响。
此方法仅适合于：关键字中的每一位都有某些数字重复出现频度很高的现象。

5）折叠法

将关键字分割成若干部分，然后取它们的叠加和为哈希地址。
有两种叠加处理方法：
- 移位叠加：将分隔后的各部分最低位对齐，然后相加。
- 间界叠加：从一端向另一端沿分割界来回折叠后，然后对齐最后一位相加。

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

6）随机数法

设定哈希函数为：

H(key) = Random(key)，其中Random为伪随机函数
此方法用于对长度不等的关键字构造哈希函数。

7）总结

实际工作中，需要根据不同的情况采用不同的哈希函数。通常应考虑的因素有：
1. 计算哈希函数所需时间
2. 关键字的长度
3. 哈希表的大小
4. 关键字的分布情况
5. 记录的查询频度

三、处理冲突的方法

1）概述

实际造表时，采用何种构造哈希函数的方法，取决于建表的关键字集合的情况（包括关键字的范围和形态），总的原则是：使产生冲突的可能性降到尽可能的小。
处理冲突的实际含义是，为产生冲突的地址寻找下一个哈希地址。
1. 开放定址法
2. 链地址法
3. 公共溢出区法
4. 再哈希法

2）开放定址法

开放定址法处理冲突的基本思想是，当冲突发生时，形成一个地址序列，沿着这个序列逐个探测，直到找到一个“空”的开放地址，将发生冲突的关键字存放到该地址中。
开放定址法的一般形式：Hi = ( H(key) + di ) % m ，（i= 1,2,...,k (k≤m-1) ）
对增量di有三种取法：
1. 线性探测法：di = 1,2, ... , m-1 ，i为探测次数。依次探测下一个地址，直到有空的地址后插入。
2. 二次探测法：di = 12,-12,22,-22, ... ,q2,-q2 (q≤m/2) ，左右轮询探测至少一半的存储单元。
3. 双哈希函数探测法：Hi=( H(key) + i*RH(key) ) % m (i=1,2, ... , m-1) ，H(key)和RH(key)是两个哈希函数，m为哈希表长度，i为步长因子。使用第一个哈希函数计算哈希地址，如果产生冲突，再使用第二个函数以及步长因子探测空余的哈希地址。
实例：关键字集合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成功= Σ(索引号 × 索引个数) / 元素总数? ? ? ?

//找到索引为0的有几个，索引为1的都几个, ...

例如：ASL成功=(1×6 + 2×2 + 3) / 9 = 13/9

ASL失败=元素个数 / 表长

// 不算空表，找完1个仍没有找到,找完2个仍没有找到...

例如：ASL失败=(1×4 + 2 + 3) / 7 = 9 / 7

4）公共溢出区法

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

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

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

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

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

5）再哈希法

主要思想：当发生冲突时，再用另一个哈希函数来得到一个新的哈希地址，若再发生冲突，则再使用另一个函数，直至不发生冲突为止。

预先需要设置一个哈希函数的序列：

Hi = RHi(key) (i=1,2,...,k) , RHi 表示不同的哈希函数

不易产生聚集，但增加了计算的时间。

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

1）哈希表的查找

查找过程和造表过程一致。
假设采用开放地址法处理冲突，则查找过程为：
- 对于给定值K，计算哈希地址 i = H(K)
- 若r[i] = NULL ,则查找不成功
- 若r[i].key = K , 则查找成功
- 否则，求下一个地址 Hi ，直至 r[Hi] = NULL(不成功) 或 r[Hi].key = K (成功) 为止。

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

从查找过程得知，哈希表查找的平均查找长度实际上并不等于零。
决定哈希表查找的ASL的因素：
1. 选用的哈希函数
2. 选中的处理冲突的方法
3. 哈希表饱和的程度，装载因子α=n/m值的大小（n：哈希表的记录数，m：哈希表的长度）
一般情况下，可以认为选用的哈希函数为“均匀”的，则在讨论ASL时，可以不考虑它的因素。因此，哈希表的ASL是处理冲突方法和装载因子的函数。