6、8 哈希表及其查找★3◎4
哈希译自“haｓh\一词,也称为散列或杂凑。? 哈希表查找得基本思想就是:根据当前待查找数据得特征,以记录关键字为自变量,设计一个哈希函数,依该函数按关键码计算元素得存储位置,并按此存放;查找时,由同一个函数对给定值ｋｅy计算地址,将ｋｅy与地址单元中元素关键码进行比较,确定查找就是否成功。哈希方法中使用得转换函数称为哈希函数(杂凑函数),按这个思想构造得表称为哈希表(杂凑表)。? 对于n个数据元素得集合,总能找到关键码与存放地址一一对应得函数、若最大关键为m,可以分配m个数据元素存放单元,选取函数f(keｙ)=ｋey即可,但这样会造成存储空间得很大浪费,甚至不可能分配这么大得存储空间、通常关键码得集合比哈希地址集合大得多,因而经过哈希函数变换后,可能将不同得关键码映射到同一个哈希地址上,这种现象称为冲突(Cｏlｌｉsioｎ)。映射到同一哈希地址上得关键码称为同义词。可以说,冲突不可能避免,只能尽可能减少。所以,哈希方法需要解决以下两个问题:? (1)构造好得哈希函数? ① 所选函数尽可能简单,以便提高转换速度。? ② 所选函数对关键码计算出得地址,应在哈希地址集中大致均匀分布,以减少空间浪费。 (2)制定解决冲突得方案 1.常用得哈希函数 (1)直接定址法
即取关键码得某个线性函数值为哈希地址,这类函数就是一一对应函数,不会产生冲突,但要求地址集合与关键码集合大小相同,因此,对于较大得关键码集合不适用。如关键码集合为｛100,300,500,7０0,8０0,900｝,选取哈希函数为Hａ
sh(key)=ｋey／100,则存放如表6-3所示。
表6—3 直接定址法构造哈希表
地址 关键码 0 1 １ ２ ３ 4 5 6 ７ ８ ８00 9 900 (２)除留余数法
即取关键码除以p得余数作为哈希地址。使用除留余数法,选取合适得p很重要,若哈希表表长为m,则要求p≤m,且接近ｍ或等于ｍ。p一般选取质数,也可以就是不包含小于20质因子得合数、? (3)数字分析法
设关键码集合中,每个关键码均由ｍ位组成,每位上可能有r种不同得符号、? 数字分析法根据ｒ种不同得符号及在各位上得分布情况,选取某几位,组合成哈希地址。所选得位应就是各种符号在该位上出现得频率大致相同。
(4)平方取中法? 对关键码平方后,按哈希表大小,取中间得若干位作为哈希地址。? (5)折叠法(Ｆoｌｄinｇ)? 此方法将关键码自左到右分成位数相等得几部分,最后一部分位数可以短些,然后将这几部分叠加求与,并按哈希表表长,取后几位作为哈希地址。这种方法称为折叠法。? 有两种叠加方法:? ① 移位法-—将各部分得最后一位对齐相加。
② 间界叠加法—-从一端向另一端沿各部分分界来回折叠后,最后一位对齐相加。? 如对关键码为 key=25３46358705,设哈希表长为３位数,则可对关键码每3位一部分来分割。关键码分割为如下4组: 253 ４６3 5８７ 05 分别用上述方法计算哈希地址如图6—12所示、对于位数很多得关键码,且每一位上符号分布较均匀时,可采用此方法求得哈希地址。
２。处理冲突得方法? (1)开放定址法
所谓开放定址法,即由关键码得到得哈希地址一旦产生了冲突,也就就是说,该地址已经存放了数据元素。我们需要寻找下一个空得哈希地址,只要哈希表足够大,空得哈希地址总能找到,并将数据元素存入。常用得找空哈希地址方法有下列三种、? ① 线性探测法
其中,Hasｈ(kｅｙ)为哈希函数,m为哈希表长度, 为增量序列1,２,…,m-１,且 = ｉ 。
设关键码集为 ｛４７,７,29,1１,16,92,22,8,3},哈希表表长为11,Hａsh(ｋey)＝key ｍod 11,用线性探测法处理冲突,构造哈希表如表6-4所示。
表6—4 哈希表
11 22 ４7 9２ 1６ 3 7 29 8 0 △ ▲ △ △ 4７,7,１1,1６,92均就是由哈希函数得到得没有冲突得哈希地址,因而就是直接存入得。? Ｈash(29)=7,哈希地址上冲突,需寻找下一个空得哈希地址:
另外,22,8同样在哈希地址上有冲突,也就是由 找到空得哈希地址得;而Hash(3)=３,哈希地址上冲突,因为:
线性探测法可能使第i个哈希地址得同义词存入第i+1个哈希地址,这样本应存入第i+１个哈希地址得元素变成了第i+2个哈希地址得同义词……因此,可能出现很多元素在相邻得哈希地址上“堆积”起来,大大降低了查找效率。为此,可采用二次探测法,或再哈希函数探测法,以改善“堆积”问题。? ② 二次探测法
哈希的基本概念
