《hash查找》由会员分享，可在线阅读，更多相关《hash查找（32页珍藏版）》请在金锄头文库上搜索。
1、8.3 hash(散列)查找前述的查找方法建立在 “比较” 的 基础上，查找的次数依赖于查找过程中进 行比较的次数。问题：能否不用比较就能直接计算出记录 的存储地址，从而找到所要的结点？解决方法：采用散列方法。8.3.1 hash函数和hash表一、hash表 根据设定的散列函数和相应解决冲突的方法为一 组结点建立的一张表，表中的结点的存储位置依赖于 设定的散列函数和处理冲突的方法。 二、基本思想：以结点的关键值k为自变量，通过一定的函数关系 h 计算出对应的函数值 h(k), 把这个值解释为 结点的存储地址（散列地址）， 将结点存入该地址 中去。设计1个hash函数，计算 Hash函数， 其
2、函数值恰好 是 key 在 hash 表中的地址hash(key)=i (0.m-1)地址keyinfo0123ikeym-1例8-1：hash查找示例。人口统计表。在右表中查找 1982年出生的人数。查找方法（1）：顺序查找 查找方法（2）：二分查找 查找方法（3）：hash 查找hash(key)=key-1949=1982-1949=33地址年份人数01949-11950-21951-31952-40。 1989 。592008-三、冲突的概念若对于不同的键值k1和k2,且k1 k2,但 hash(k1)=hash(k2)， 即具有相同的散列地址，这种现象称为冲突。称 k1、k2称为同义
3、词。例：key=3,15,20,24，m=5（表长）， hash(k)=k%5hash(15)=0hash(20)=0 产生冲突。四、表长m的选取参考：n / m 3 / 4m: hash表的表长，n: hash表中关键字个数。五、要解决的问题（1）如何选择一个好的散列函数（ 能将关键值均匀地分布在整个地址空间，使冲突机会尽量的少 ）（2）如何选定一个解决冲突的办法。8.3.2 hash函数的构造方法（1）直接定址法哈希函数为关键字的线性函数。hash(key) = key 或者 hash(key) = a key + b如例8-1所示，hash(key)=key-1949（2）数字分析法假设
4、关键字集合中的每个关键字都是由s位 数字组成(k1, k2, , kn)，分析关键字集中的全 体，并从中提取分布均匀的若干位或它们的组合 作为地址。参见教材 P278仅限于：能预先估计出全体关键字的每一位 上各种数字出现的频度。（3）平方取中法若关键字的每一位都有某些数字重复出现频度 很高的现象，则先求关键字的平方值，以通过“平方” 扩大差别，同时平方值的中间几位受到整个关键字中 各位的影响。例如：a=0100, 则 a2=0010000i =1100, 则 i2 =1210000j =1200, 则 j2 =1440000若超出范围时，可再取模（4）折叠法若关键字的位数比较长，则可将其分割成
5、几部分， 然后取它们的叠加和为哈希地址。两种处理方法：移位叠加和间界叠加例如关键字key：0-442-20586-45864 58644220 0224+) 04 +) 0410088 6092hash(key)=0088 hash(key)=6092(a) 移位叠加 (b)间界叠加（5）除留余数法选择一个适当的正整数 p，用p去除关键值， 取其余数作为散列地址，即：hash(key)=key%p pm (表长)关键问题是: 如何选取 p ?p 应为不大于m 的最大质数例：设表长m=8，16，32，64，128，1001则 p=7，13，31，61，127，1001（6）随机数法H(key)
6、= Random(key)采用何种构造哈希函数的方法取决于关键字 集合的情况(包括关键字的范围和形)，总的原则是使产生冲突的可能性降到尽可能 地小。构造hash函数需要考虑的因素（1）计算hash函数的效率； （2）关键字的长度（包括是否等长）； （3）hash表的大小； （4）关键字的分布情况； （5）记录的查找频率。8.3.3 冲突的处理一、链地址法将具有相同散列地址的记录都存储在同 一个线性链表中。例8-2以14,1,68,27,55,23,11,10,19,20,79,84为例, 构造hash表。 分析： n=12 n/m=3/4 , 所以 m=16 , 则 p=13hash(key)
7、=key % 13例8-2 以 14,1,68,27,55,23,11,10,19,20,79,84构造 hash表。 用链地址法解决冲突。分析： n=12 n/m=3/4 , 所以 m=16 , 则 p=13hash(key)=key % 13hash(14)=hash(1)=hash(27)=hash(79)=1hash(68)=hash(55)=3hash(19)=hash(84)=6hash(20)=7hash(23)=hash(10)=10hash(11)=11127 79hash(key)=key % 13 hash(14)=1 hash(1)=1 hash(68)=3 hash(
8、27)=1 hash(55)=3 hash(23)=10 hash(11)=11 hash(10)=10 hash(19)=6 hash(20)=7 hash(79)=1 hash(84)=61468192023110 1 2 3 4 5 6 7 8 9 10 11 12 13 558410ASL=（6*1+4*2+1*3+1*4）/12=21/12141079hash(key)=key % 17 (m=17)(p=17)hash(14)=14 hash(1)=1 hash(68)=0 hash(27)=10 hash(55)=4 hash(23)=6 hash(11)=11 hash(10)
9、=10 hash(19)=2 hash(20)=3 hash(79)=11 hash(84)=161681923110 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16558427ASL=（10*1+2*2）/12=14/1220二、开放定址法当冲突发生时，使用某种方法在散列表 中形成一个探查序列，沿着此序列逐个地址 去探查，直到找到一个开放的地址（空位 置），将发生冲突的键值放到该地址中。（1）线性探查法（2）二次探测法（3）再散列探查法。（1）线性探测法 对给定的关键值 k，若地址d (即h(k)=d)的单元发生冲突，则依次探查下述地址单元（设m为 表长）：d+
10、1,d+2,.,m-1, 0 ,1,d-1设增量函数为d(i)=1,2,3,m-1。i: 为探测次数。14681552720198479112310hash 表：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 比较次数：1 2 1 4 3 1 1 8 4 1 1 3ASL=(1*6+2*1+3*2+4*2+8*1)/12=30/12问题: (1)聚集问题(2)删除问题(3)排序问题例8-3 以14,1,68,27,55,23,11,10,19,20,79,84 , 构造 hash表。hash表长度为16, hash(key)=key % 13 。 用线性探测法解决冲
11、突。例8-4 以14,1,68,27,55,23,11,10,19,20,79,84 , 构造 hash表。hash表长度为17, hash(key)=key % 17 。 用线性探测法解决冲突。hash 表：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1468 1552720198479112310比较次数： 3 3ASL=(1*10+3*2)/12=16/12（2）二次探测法 对给定的关键值 k，若地址d (即h(k)=d)的单元发生冲突，则探查下述地址单元：d+1,d-1,d+4,d-4,d+9,d-9,设增量函数为d(i)=12,- 12 , 22,- 22 , k2,- k2 。(kkey!=K ) p=p-next;if (!p) return(NULL); /表中无关键字等于K的记录else if ( p-key=K ) return(p); /查找成功决定哈希表查找的ASL的因素：（1）选用的哈希函数; （2）选用的处理冲突的方法; （3）哈希表饱和的程度，装载因子=n/m 值的大小。一般情况下，可以认为选用的哈希函数 是“均匀”的，则在讨论ASL时，可以不考虑它 的因素。线性探测再散列随机探测再散列链地址法8.3.5 hash表的查找分析装填（负载）因子=表中填入的记录数 hash表的长度
