考研帮 > 数学 > 每日一练

6.8 哈希表及其查找★3◎4

6.8 哈希表及其查找★3◎4

  哈希译自“hash”一词,也称为散列或杂凑。
  哈希表查找的基本思想是:根据当前待查找数据的特征,以记录关键字为自变量,设计一个哈希函数,依该函数按关键码计算元素的存储位置,并按此存放;查找时,由同一个函数对给定值key计算地址,将key与地址单元中元素关键码进行比较,确定查找是否成功。哈希方法中使用的转换函数称为哈希函数(杂凑函数),按这个思想构造的表称为哈希表(杂凑表)。
  对于n个数据元素的集合,总能找到关键码与存放地址一一对应的函数。若最大关键为m,可以分配m个数据元素存放单元,选取函数f(key)=key即可,但这样会造成存储空间的很大浪费,甚至不可能分配这么大的存储空间。通常关键码的集合比哈希地址集合大得多,因而经过哈希函数变换后,可能将不同的关键码映射到同一个哈希地址上,这种现象称为冲突(Collision)。映射到同一哈希地址上的关键码称为同义词。可以说,冲突不可能避免,只能尽可能减少。所以,哈希方法需要解决以下两个问题:
  (1)构造好的哈希函数
  ① 所选函数尽可能简单,以便提高转换速度。
  ② 所选函数对关键码计算出的地址,应在哈希地址集中大致均匀分布,以减少空间浪费。
  (2)制定解决冲突的方案
  1.常用的哈希函数
  (1)直接定址法

  即取关键码的某个线性函数值为哈希地址,这类函数是一一对应函数,不会产生冲突,但要求地址集合与关键码集合大小相同,因此,对于较大的关键码集合不适用。如关键码集合为{100,300,500,700,800,900},选取哈希函数为Hash(key)=key/100,则存放如表6-3所示。

表6-3 直接定址法构造哈希表

地址

0

1

2

3

4

5

6

7

8

9

关键码

 

100

 

300

 

500

 

700

800

900

  (2)除留余数法

  即取关键码除以p的余数作为哈希地址。使用除留余数法,选取合适的p很重要,若哈希表表长为m,则要求p≤m,且接近m或等于m。p一般选取质数,也可以是不包含小于20质因子的合数。
  (3)数字分析法
  设关键码集合中,每个关键码均由m位组成,每位上可能有r种不同的符号。
  数字分析法根据r种不同的符号及在各位上的分布情况,选取某几位,组合成哈希地址。所选的位应是各种符号在该位上出现的频率大致相同。
  (4)平方取中法
  对关键码平方后,按哈希表大小,取中间的若干位作为哈希地址。
  (5)折叠法(Folding)
  此方法将关键码自左到右分成位数相等的几部分,最后一部分位数可以短些,然后将这几部分叠加求和,并按哈希表表长,取后几位作为哈希地址。这种方法称为折叠法。
  有两种叠加方法:
  ① 移位法——将各部分的最后一位对齐相加。
  ② 间界叠加法——从一端向另一端沿各部分分界来回折叠后,最后一位对齐相加。
  如对关键码为 key=25346358705,设哈希表长为3位数,则可对关键码每3位一部分来分割。关键码分割为如下4组: 253 463 587 05
  分别用上述方法计算哈希地址如图6-12所示。对于位数很多的关键码,且每一位上符号分布较均匀时,可采用此方法求得哈希地址。

  2.处理冲突的方法
  (1)开放定址法
  所谓开放定址法,即由关键码得到的哈希地址一旦产生了冲突,也就是说,该地址已经存放了数据元素。我们需要寻找下一个空的哈希地址,只要哈希表足够大,空的哈希地址总能找到,并将数据元素存入。常用的找空哈希地址方法有下列三种。
  ① 线性探测法

  其中,Hash(key)为哈希函数,m为哈希表长度, 为增量序列1,2,…,m-1,且 = i 。
  设关键码集为 {47,7,29,11,16,92,22,8,3},哈希表表长为11,Hash(key)=key mod 11,用线性探测法处理冲突,构造哈希表如表6-4所示。

表6-4 哈希表

0

1

2

3

4

5

6

7

8

9

10

11

22

 

47

92

16

3

7

29

8

 

         △                     ▲       △   △

  47,7,11,16,92均是由哈希函数得到的没有冲突的哈希地址,因而是直接存入的。
  Hash(29)=7,哈希地址上冲突,需寻找下一个空的哈希地址:

  

  另外,22,8同样在哈希地址上有冲突,也是由 找到空的哈希地址的;而Hash(3)=3,哈希地址上冲突,因为:

  

  线性探测法可能使第i个哈希地址的同义词存入第i+1个哈希地址,这样本应存入第i+1个哈希地址的元素变成了第i+2个哈希地址的同义词……因此,可能出现很多元素在相邻的哈希地址上“堆积”起来,大大降低了查找效率。为此,可采用二次探测法,或再哈希函数探测法,以改善“堆积”问题。
  ② 二次探测法

  其中,Hash(key)为哈希函数,m为哈希表长度, 为增量序列12,12,22,22,…,q2,q2且

  仍对前面例子的关键码序列{47,7,29,11,16,92,22,8,3},用二次探测法处理冲突,构造哈希表如表6-5所示。

表6-5 二次探测法构造哈希表

0

1

2

3

4

5

6

7

8

9

10

11

22

3

47

92

16

 

7

29

8

 

            △            ▲                                                                                               △            △

  与关键码寻找空的哈希地址只有3这个关键码不同,Hash(3)=3,哈希地址上冲突,由

  H2=(Hash(3)+12)%11=2,找到空的哈希地址,存入。
  ③ 再哈希法

  其中,Hash(key),ReHash(key)是两个哈希函数,m为哈希表长度。
  再哈希法,先用第一个函数Hash(key)对关键码计算哈希地址,一旦产生地址冲突,再用第二个函数ReHash(key)确定移动的步长因子,最后,通过步长因子序列由探测函数寻找空的哈希地址。
  比如,Hash(key)=a时产生地址冲突,就计算ReHash(key)=b,则探测的地址序列为:

  (2)链地址法
  又称拉链法,设哈希函数得到的哈希地址域在区间[0,m-1]上,以每个哈希地址作为一个指针,指向一个链,即分配指针数组:
  ElemType *eptr[m];
  建立m个空链表,由哈希函数对关键码转换后,映射到同一哈希地址i的同义词均加入*eptr[i]指向的链表中。
  对关键码序列为 {47,7,29,11,16,92,22,8,3,50,37,89,94,21},哈希函数为Hash(key)=key mod 11,用拉链法处理冲突,建表如图6-13所示。

  (3)建立一个公共溢出区
  设哈希函数产生的哈希地址集为[0,m-1],则分配两个表:
  一个基本表ElemType base_tbl[m];每个单元只能存放一个元素。
  一个溢出表ElemType over_tbl[k];只要关键码对应的哈希地址在基本表上产生冲突,则所有这样的元素一律存入该表中。查找时,对给定值kx通过哈希函数计算出哈希地址i,先与基本表的base_tbl[i]单元比较,若相等,查找成功;否则,再到溢出表中进行查找。
  3.哈希表的查找分析
  哈希表的查找过程基本上和造表过程相同。一些关键码可通过哈希函数转换的地址直接找到,另一些关键码在哈希函数得到的地址上产生了冲突,需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中,产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以,对哈希表查找效率的量度,依然用平均查找长度来衡量。
  查找过程中,关键码的比较次数取决于产生冲突的多少。如果产生的冲突少,查找效率就高,如果产生的冲突多,查找效率就低。因此,影响产生冲突多少的因素,也就是影响查找效率的因素。影响产生冲突多少有以下三个因素:
  ① 哈希函数是否均匀;
  ② 处理冲突的方法;
  ③ 哈希表的装填因子。
  分析这三个因素,尽管哈希函数的“好坏”直接影响冲突产生的频度,但一般情况下,我们总认为所选的哈希函数是“均匀的”。因此,可不考虑哈希函数对平均查找长度的影响。

  是哈希表装满程度的标志因子。由于表长是定值,α与“填入表中的元素个数”成正比,所以,α越大,填入表中的元素较多,产生冲突的可能性就越大;α越小,填入表中的元素较少,产生冲突的可能性就越小。
  实际上,哈希表的平均查找长度是装填因子α的函数,只是不同处理冲突的方法有不同的函数。表6-6为几种不同处理冲突方法的平均查找长度。

表6-6 几种不同处理冲突方法的平均查找长度

处理冲突的方法 平均查找长度
查找成功时 查找不成功时
线性探测法
二次探测法与再哈希法
链地址法

  哈希方法存取速度快、节省空间,静态查找、动态查找均适用,但由于存取是随机的,因此,不便于顺序查找。

关于"最后阶段,真题的正确打开方式_备考经验_考研帮"15名研友在考研帮APP发表了观点

扫我下载考研帮

考研帮地方站更多

你可能会关心:

来考研帮提升效率

× 关闭