哈希的基本概念.doc

6、8 哈希表及其查找34 哈希译自“hah一词,也称为散列或杂凑。哈希表查找得基本思想就是:根据当前待查找数据得特征,以记录关键字为自变量,设计一个哈希函数,依该函数按关键码计算元素得存储位置,并按此存放;查找时,由同一个函数对给定值y计算地址,将y与地址单元中元素关键码进行比较,确定查找就是否成功。哈希方法中使用得转换函数称为哈希函数(杂凑函数),按这个思想构造得表称为哈希表(杂凑表)。 对于n个数据元素得集合,总能找到关键码与存放地址一一对应得函数、若最大关键为m,可以分配m个数据元素存放单元,选取函数f(ke)=ey即可,但这样会造成存储空间得很大浪费,甚至不可能分配这么大得存储空间、通常关键码得集合比哈希地址集合大得多,因而经过哈希函数变换后,可能将不同得关键码映射到同一个哈希地址上,这种现象称为冲突(Clsio)。映射到同一哈希地址上得关键码称为同义词。可以说,冲突不可能避免,只能尽可能减少。所以,哈希方法需要解决以下两个问题: (1)构造好得哈希函数 所选函数尽可能简单,以便提高转换速度。 所选函数对关键码计算出得地址,应在哈希地址集中大致均匀分布,以减少空间浪费。 (2)制定解决冲突得方案1.常用得哈希函数(1)直接定址法 即取关键码得某个线性函数值为哈希地址,这类函数就是一一对应函数,不会产生冲突,但要求地址集合与关键码集合大小相同,因此,对于较大得关键码集合不适用。如关键码集合为100,300,500,70,80,900,选取哈希函数为Hsh(key)=ey100,则存放如表6-3所示。表63直接定址法构造哈希表地址014569关键码00900 ()除留余数法即取关键码除以p得余数作为哈希地址。使用除留余数法,选取合适得p很重要,若哈希表表长为m,则要求pm,且接近或等于。p一般选取质数,也可以就是不包含小于20质因子得合数、 (3)数字分析法 设关键码集合中,每个关键码均由位组成,每位上可能有r种不同得符号、数字分析法根据种不同得符号及在各位上得分布情况,选取某几位,组合成哈希地址。所选得位应就是各种符号在该位上出现得频率大致相同。 (4)平方取中法对关键码平方后,按哈希表大小,取中间得若干位作为哈希地址。 (5)折叠法(oin) 此方法将关键码自左到右分成位数相等得几部分,最后一部分位数可以短些,然后将这几部分叠加求与,并按哈希表表长,取后几位作为哈希地址。这种方法称为折叠法。有两种叠加方法: 移位法-将各部分得最后一位对齐相加。 间界叠加法-从一端向另一端沿各部分分界来回折叠后,最后一位对齐相加。 如对关键码为 key=2546358705,设哈希表长为位数,则可对关键码每3位一部分来分割。关键码分割为如下4组: 253 3 5 05 分别用上述方法计算哈希地址如图612所示、对于位数很多得关键码,且每一位上符号分布较均匀时,可采用此方法求得哈希地址。 。处理冲突得方法 (1)开放定址法 所谓开放定址法,即由关键码得到得哈希地址一旦产生了冲突,也就就是说,该地址已经存放了数据元素。我们需要寻找下一个空得哈希地址,只要哈希表足够大,空得哈希地址总能找到,并将数据元素存入。常用得找空哈希地址方法有下列三种、 线性探测法 其中,Has(k)为哈希函数,m为哈希表长度, 为增量序列1,m-,且 = 。 设关键码集为 ,29,1,16,92,22,8,3,哈希表表长为11,Hsh(ey)keyod 11,用线性探测法处理冲突,构造哈希表如表6-4所示。表64 哈希表0112279137298 4,7,1,1,92均就是由哈希函数得到得没有冲突得哈希地址,因而就是直接存入得。 ash(29)=7,哈希地址上冲突,需寻找下一个空得哈希地址: 另外,22,8同样在哈希地址上有冲突,也就是由找到空得哈希地址得;而Hash(3)=,哈希地址上冲突,因为: 线性探测法可能使第i个哈希地址得同义词存入第i+1个哈希地址,这样本应存入第i+个哈希地址得元素变成了第i+2个哈希地址得同义词因此,可能出现很多元素在相邻得哈希地址上“堆积”起来,大大降低了查找效率。为此,可采用二次探测法,或再哈希函数探测法,以改善“堆积”问题。 二次探测法 其中,Hash(key)为哈希函数,m为哈希表长度, 为增量序列,-12,22,-2,q,-q且 仍对前面例子得关键码序列4,29,11,1,92,22,3,用二次探测法处理冲突,构造哈希表如表65所示。表6-5 二次探测法构造哈希表112292729 与关键码寻找空得哈希地址只有3这个关键码不同,Has()=,哈希地址上冲突,由 H(Hash()1)%1=2,找到空得哈希地址,存入、 再哈希法 其中,s(y),eH(key)就是两个哈希函数,为哈希表长度。 再哈希法,先用第一个函数Hash(key)对关键码计算哈希地址,一旦产生地址冲突,再用第二个函数ReHah(key)确定移动得步长因子,最后,通过步长因子序列由探测函数寻找空得哈希地址、 比如,Has(key)a时产生地址冲突,就计算eHash(ey)b,则探测得地址序列为: (2)链地址法 又称拉链法,设哈希函数得到得哈希地址域在区间,m1上,以每个哈希地址作为一个指针,指向一个链,即分配指针数组: lType er;建立m个空链表,由哈希函数对关键码转换后,映射到同一哈希地址得同义词均加入epri指向得链表中。 对关键码序列为 7,7,29,11,16,2,8,0,7,89,94,21,哈希函数为Hsh(key)=ke mod 1,用拉链法处理冲突,建表如图13所示。 (3)建立一个公共溢出区设哈希函数产生得哈希地址集为0,m,则分配两个表:一个基本表lmTypeas_tbl;每个单元只能存放一个元素。 一个溢出表ElmTypove_k;只要关键码对应得哈希地址在基本表上产生冲突,则所有这样得元素一律存入该表中。查找时,对给定值k通过哈希函数计算出哈希地址i,先与基本表得base_tbl单元比较,若相等,查找成功;否则,再到溢出表中进行查找。 .哈希表得查找分析 哈希表得查找过程基本上与造表过程相同。一些关键码可通过哈希函数转换得地址直接找到,另一些关键码在哈希函数得到得地址上产生了冲突,需要按处理冲突得方法进行查找。在介绍得三种处理冲突得方法中,产生冲突后得查找仍然就是给定值与关键码进行比较得过程。所以,对哈希表查找效率得量度,依然用平均查找长度来衡量。 查找过程中,关键码得比较次数取决于产生冲突得多少。如果产生得冲突少,查找效率就高,如果产生得冲突多,查找效率就低、因此,影响产生冲突多少得因素,也就就是影响查找效率得因素。影响产生冲突多少有以下三个因素: 哈希函数就是否均匀; 处理冲突得方法; 哈希表得装填因子。分析这三个因素,尽管哈希函数得“好坏”直接影响冲突产生得频度,但一般情况下,我们总认为所选得哈希函数就是“均匀得”。因此,可不考虑哈希函数对平均查找长度得影响。就是哈希表装满程度得标志因子。由于表长就是定值,与“填入表中得元素个数”成正比,所以,越大,填入表中得元素较多,产生冲突得可能性就越大;越小,填入表中得元素较少,产生冲突得可能性就越小。 实际上,哈希表得平均查找长度就是装填因子得函数,只就是不同处理冲突得方法有不同得函数。表6为几种不同处理冲突方法得平均查找长度、表 几种不同处理冲突方法得平均查找长度处理冲突得方法平均查找长度查找成功时查找不成功时线性探测法二次探测法与再哈希法链地址法 哈希方法存取速度快、节省空间,静态查找、动态查找均适用,但由于存取就是随机得,因此,不便于顺序查找。