8.5　散列查找

以上讨论的查找方法,由于数据元素的存储位置与关键字之间不存在确定的关系,因此在查找时,需要进行一系列对关键字的查找比较,即“查找算法”是建立在比较的基础上的,查找效率由进行比较一次后缩小的查找范围决定。理想的情况是依据关键字直接得到其对应的数据元素位置,即要求关键字与数据元素间存在一一对应关系,通过这个关系,能很快地由关键字得到对应的数据元素位置,从而提高查找的效率。

8.5.1　散列表与散列函数

散列表又称哈希表,是除了顺序表、链表和索引表之外的又一种存储数据的存储结构。其基本思想是在记录的存储地址和其关键字之间建立一个确定的对应关系,这样不经过比较,一次存取就能得到所查找的元素。散列函数是在记录的关键字与存储地址之间建立的一种对应关系。该函数是从关键字空间到存储地址空间的一种映象,其函数可写成以下形式。

addr（a_i）＝h（k_i）

其中,a_i是表中的一个元素,addr（a_i）是a_i的存储地址,k_i是a_i的关键字。

应用散列函数,由记录的关键字确定记录在表中的地址,并将记录放入此地址中,这样构成的表就是散列表。利用散列函数进行查找的过程就是散列查找,又称为哈希查找。

例如,有11个元素的关键字分别为18,27,1,20,22,6,10,13,41,15,25。选取关键字与元素位置间的函数如下。

h（k）＝k%11

通过这个函数对11个元素建立的查找表如图8－24所示。

图8－24　关键字与函数的对应关系

查找时,对给定值k通过这个函数计算出地址,再将k与该地址单元中元素的关键字进行比较,若相等则查找成功。

对于n个数据元素的集合,总能找到关键字与存储地址一一对应的函数。若最大关键字为m,则可以分配m个数据元素存放单元,选取函数h（k）＝k即可,但这样会造成存储空间的浪费,甚至不可能分配这么大的存储空间。通常关键字的集合比哈希地址的集合大得多,因此经过哈希函数变换后,可能将不同的关键字映射到同一个哈希地址上,这种现象称为冲突（collision）。冲突不可能避免,只能尽可能减少。所以,哈希方法需要解决以下两个问题。

（1）构造好的哈希函数,可以采用以下两种方法。

①所选函数应尽可能简单,以便提高转换速度。

②所选函数对关键字所计算出的地址,应在哈希地址集合中,并且应大致均匀分布,以减少空间的浪费。

（2）制定解决冲突的方案。

8.5.2　散列函数的构造方法

根据关键字的结构和分布不同,可构造出许多不同的散列函数,这里主要介绍几种常用的整数类型关键字的散列函数的构造方法。

1.直接定址法

直接定址法构造散列函数如下。

h（k）＝a·k＋b

其中,a、b为常数。

直接定址法即取关键字的某个线性函数值为哈希地址,这类函数是一一对应函数,不会产生冲突,但要求地址集合与关键字集合的大小相同,因此,对于较大的关键字集合不适用。

【例8－5】　关键字集合为{20,30,50,60,80,90},选取散列函数为h（k）＝k/10,则具体存放如图8－25所示。

图8－25　关键字存放地址

2.除留余数法

除留余数法构造散列函数如下。

h（k）＝k mod p

其中,p是一个整数。

除留余数法即取关键字除以p的余数作为哈希地址。使用除留余数法,选取合适的p很重要,若哈希表的表长为m,则要求p≤m,并且接近m或等于m。p一般选取质数,也可以是不包含小于20质因子的合数。

3.平方取中法

平方取中法即对关键字平方后,按哈希表大小,取中间的若干位作为哈希地址的方法。例如:

若存储区域可存100个记录,关键字为4731,则

4731×4731＝223 82361　　　　取地址82

若存储区域可存10000个记录,关键字为14625,则

则　14625×14625＝213 890625　　　　取地址8906

4.折叠法

折叠法将关键字分割成位数相同的几部分,然后取这几部分的叠加和（舍去进位）作为散列地址。

折叠法包括移位叠加和间界叠加两种。

（1）移位叠加:将分割后的每一部分的最低位对齐,然后相加。

（2）间界叠加:从一端向另一端沿分割界来回折叠,然后对齐相加。

折叠法适用于关键字位数很多,并且每一位上的数字分布大致均匀的情况。

【例8－6】　关键字为0442205864,哈希地址位数为4,用折叠法求散列地址。

使用移位叠加法求其散列地址如图8－26所示,使用间界叠加法求其散列地址如图8－27所示。

图8－26　移位叠加法

图8－27　间界叠加法

4.数字分析法

数字分析法通过对关键字进行分析,取关键字的若干位或其组合作为散列地址。

数字分析法适用于关键字位数比哈希地址位数大,并且可能出现的关键字事先知道的情况。

【例8－7】　有80个记录,关键字为8位十进制数,散列地址为2位十进制数。

【分析】　例8－7的记录如图8－28所示。其中,第①位均是8,第②位均是1,第③位也只有3、4,第⑧位只有2、7、5,因此这几位不能用,余下四位数字分布近乎随机,可作为哈希地址选用。故可取④⑤⑥⑦位中的任意两位或两位与另两位的叠加作为哈希地址。

图8－28　数字分析法

8.5.3　冲突的处理方法

1.开放定址法

所谓开放定址法,即是由关键字得到的散列地址一旦产生了冲突,则形成一个探查序列,沿此序列逐个地址探查,直到找到一个空位置（开放的地址）,将发生的冲突记录到该地址中。也就是说,该地址若已经存放了数据元素,就去寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到,并将数据元素存入。即

h_i＝（h（k）＋d_i）mod m；i＝1,2,…,k（k≤m－1）

其中:h（k）——散列函数；

m——散列表表长；d_i——增量序列。

开放地址法处理冲突时主要分线性探测法、二次探测法和双散列函数探测法,下面分别进行介绍。

1）线性探测法

线性探测法的公式如下。

h_i＝（h（k）＋d_i）mod m　　　（1≤i＜m）

其中:h（k）为散列函数；m为散列表长度；d_i＝i　（i＝1,2,3,…,m－1）。

【例8－8】　关键字集为{47,7,29,11,16,92,22,8,3},散列表表长为11,h（k）＝k　mod 11。用线性探测法处理冲突,建表如图8－29所示。

图8－29　用线性探测法处理冲突的散列表

其中,47、7、11、16、92均是由散列函数得到的没有冲突的哈希地址而直接存入的。h（29）＝7,散列地址上冲突,需寻找下一个空的散列地址。由h₁＝（h（29）＋1）mod　11＝8,可知散列地址8为空,将29存入。

另外,22、8同样在哈希地址上有冲突,也是由H1寻找到空的散列地址的；而h（3）＝3,散列地址上冲突,则

（1）h₁＝（h（3）＋1）mod　11＝4　　仍然冲突。

（2）h₂＝（h（3）＋2）mod　11＝5　　仍然冲突。

（3）h₃＝（h（3）＋3）mod　11＝6　　找到空的散列地址,存入。

线性探测法可能使第i个散列地址的同义词存入第i＋1个散列地址,这样本应存入第i＋1个散列地址的元素变成了第i＋2个散列地址的同义词,依此类推,则有可能出现很多元素在相邻的散列地址上“堆积”起来,从而大大降低了查找效率。为此,可采用二次探测法,或者双散列函数探测法,以改善“堆积”问题。

2）二次探测法（平方探测法）

二次探测法的公式如下。

h_i＝（h（k）±d_i）mod　m

其中:h（k）为散列函数；m为散列表长度,m要求是某个4k＋3的质数（k是整数）；d_i为增量序列1²,－1²,2²,－2²,…,q²,－q²且q≤（m－1）。

仍对例8－8采用二次探测法处理冲突,建表如图8－30所示。

图8－30　用二次探测法处理冲突的散列表

对关键字寻找空的哈希地址只有3这个关键字与上例不同,则可代入公式计算分析。

由h（3）＝3,哈希地址上冲突,则有

（1）h₁＝（h（3）＋12）mod　11＝4　　仍然冲突。

（2）h₂＝（h（3）－12）mod　11＝2　　找到空的哈希地址,存入。

3）双散列函数探测法

h_i＝（h（k）＋i＊rh（k））mod　m　（i＝1,2,…,m－1）

其中:h（k）、rh（k）是两个散列函数,m为散列表长度。

双散列函数探测法处理冲突,先用第一个函数h₁（k）对关键字计算散列地址,一旦产生地址冲突,再用第二个函数rh（k）确定移动的步长因子,最后,通过步长因子序列由探测函数寻找空的散列地址。

例如,当h（k）＝a时产生地址冲突,就计算rh（k）＝b,则探测的地址序列为:

h₁＝（a＋b）mod　m

h₂＝（a＋2b）mod　m

┇

h（m－1）＝（a＋（m－1）b）mod　m

2.拉链法（链地址法）

设哈希函数得到的散列地址域在区间[0,m－1]上,以每个散列地址作为一个指针,指向一个链,即分配指针数组ElemType＊eptr[m],从而建立m个空链表,由哈希函数对关键字转换后,映射到同一散列地址i的同义词均加入到＊eptr[i]指向的链表中。

【例8－9】　关键字序列如下。

47,　7,　29,　22,　27,　92,　33,　8,　3,　51,　37,　78,　94,　21

则散列函数为:

h（k）＝k　mod　11

用拉链法处理冲突,建表如图8－31所示。

图8－31　用拉链法处理冲突的散列表

3.建立一个公共溢出区

设哈希函数产生的哈希地址集为[0,m－1],则分配如下两个表。

（1）基本表ElemType　base＿tbl[m],其中每个单元只能存放一个元素。

（2）溢出表ElemType　over＿tbl[k],其中只要关键字对应的哈希地址在基本表上产生冲突,则所有这样的元素一律存入该表中。

查找时,对给定值x通过哈希函数计算出哈希地址i,先与基本表的base＿tbl[i]单元比较。若二者相等,查找成功；否则,再到溢出表中进行查找。

【例8－10】　已知一组关键字（19,14,23,1,68,20,84,27,55,11,10,79）,其散列函数为h（k）＝k　mod　13,散列表长为m＝16,设每个记录的查找概率相等,选择其中一种方法来处理冲突。先用线性探测法再用散列处理冲突,建表如下,即

h_i＝（h（k）＋d_i）mod　m

则有

（1）h（19）＝6

（2）h（14）＝1

（3）h（23）＝10

（4）h（1）＝1　　　冲突,h₁＝（1＋1）mod　16＝2

（5）h（68）＝2

（6）h（20）＝7

（7）h（84）＝6　　 冲突,h₁＝（6＋1）mod　16＝7

　　　　　　　　　　冲突,h2＝（6＋2）mod　16＝8

（8）h（27）＝1　　 冲突,h₁＝（1＋1）mod　16＝2

　　　　　　　　　　冲突,h2＝（1＋2）mod　16＝3

　　　　　　　　　　冲突,h3＝（1＋3）mod　16＝4

（9）h（55）＝3　　 冲突,h₁＝（3＋1）mod　16＝4　

　　　　　　　　　　冲突,h2＝（3＋2）mod　16＝5

（10）h（11）＝11

（11）h（10）＝10　 冲突,h₁＝（10＋1）mod　16＝11

　　　　　　　　　　冲突,h2＝（10＋2）mod　16＝12

（12）h（79）＝1　　冲突,h₁＝（1＋1）mod　16＝2

　　　　　　　　　　冲突,h2＝（1＋2）mod　16＝3

　　　　　　　　　　冲突,h3＝（1＋3）mod　16＝4

　　　　　　　　　　冲突,h4＝（1＋4）mod　16＝5

　　　　　　　　　　冲突,h5＝（1＋5）mod　16＝6

　　　　　　　　　　冲突,h6＝（1＋6）mod　16＝7

　　　　　　　　　　冲突,h7＝（1＋7）mod　16＝8

　　　　　　　　　　冲突,h8＝（1＋8）mod　16＝9

ASL＝（1×6＋2＋3×3＋4＋9）/12＝2.5

8.5.4　散列查找的性能分析

按理论分析,散列查找的时间复杂度应为O（1）,因此其ASL＝1,但由于冲突的存在,其平均查找长度将会比1大。下面分析几种散列查找方法的平均查找长度。首先引入装填因子的概念,所谓装填因子是指散列表中存入的元素个数n与哈希表的大小m的比值,即

装填因子α＝n/m

其中,当α越小时,发生冲突的可能性也越小；α越大时（最大为1）,发生冲突的可能性越大。

1.线性探查法的查找性能分析

由于线性探查法解决冲突是线性地查找空闲位置,平均查找长度与表的大小m无关,只与所选取的哈希函数h、装填因子α的值及该处理方法有关,这时的成功的平均查找长度为:

例如,给定关键字序列如下,散列函数为h（k）＝k%13,用线性探测法建立如下散列表。

19,14,23,1,68,20,84,27,55,11,10,79

分析每个关键字如下。

19%13＝6；84%13＝6；14%13＝1；27%13＝1；

23%13＝10；55%13＝3；1%13＝1；11%13＝11；

68%13＝3；10%13＝10；20%13＝7；79%13＝1。

故可求得

ASL成功＝（1＋1＋1＋2＋1＋1＋3＋4＋3＋1＋3＋9）/12＝30/12

ASL失败＝（1＋13＋12＋11＋10＋9＋8＋7＋6＋5＋4＋3＋2＋1）/12＝92/12

2.链地址法的查找性能分析

由于拉链法查找就是在单链表上查找,查找单链表中第一个结点的比较次数为1,第二个结点比较次数为2,依此类推。故其平均查找长度为ASL＝1＋α/2。

使用拉链法分析上例中的关键字序列,则可建立如图8－32所示的散列表,并且ASL值计算如下。

图8－32　用拉链法建立散列表

ASL成功＝（1×6＋2×4＋3＋4）/12＝21/12 ASL失败＝（4＋2×3＋1＋1）/13＝12/13

从上述分析中可知:散列表的查找性能主要取决于以下三个方面。

（1）散列函数的选择。散列函数选择得当,就可使散列地址尽可能均匀地分布在散列地址空间上,从而减少冲突发生,提高查找效率。

（2）冲突解决策略。冲突策略的好坏将直接减少或增加冲突发生的可能性。

（3）装填因子。一般α与冲突发生的可能性成正比,但α也不能太小,否则会造成大量存储空间的浪费,所以要兼顾存储空间与冲突这两个方面,通常将α控制在0.6到0.9之间。

本章小结

1.顺序查找对表无任何要求,既可以是顺序表,也可以是链表,既适合无序表,也适合于有序表。顺序查找的成功平均查找长度为,故时间复杂度为O（n）。

2.二分查找仅适用于有序的顺序表,它的平均查找长度为log₂（n＋1）－1,故时间复杂度为O（log₂n）。

3.分块查找是一种特殊的索引查找,其索引表中的索引值与主表中每个元素的关键字具有相同的数据类型。

4.散列查找是通过构造散列函数来计算关键字的存储地址的一种查找方法,按理论分析,不需要用到比较,其时间复杂度为O（1）。