数据结构与算法设计PPT (52).pdf

《数据结构与算法设计PPT (52).pdf》由会员分享，可在线阅读，更多相关《数据结构与算法设计PPT (52).pdf（16页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第10章 哈希表10.2 冲突的解决方法处理冲突的方法 假设按照哈希函数H0=H(Rec.key)位置发生了冲突，就为Rec对象另外查找一个空间位置存放。可以采用地址序列H1,H2,Hk（Hi）（i=0,1m-1）去查找空闲位置，直到找到不冲突的位置为止处理冲突的方法 闭散列法 开散列法 在哈希法闭散列法 又称为开放定址法 开放的含义是指不仅向哈希函数值等于H0的同义词开放，而是向哈希函数值不是H0的记录开放，以抢占的方式争取哈希地址 又有以下类型-线性探查法-二次方探查法-伪随机探查法-二次哈希法线性探查法(Linear Probing)当进行插入记录时，使用哈希函数计算位置：H0=hash

2、(key)一旦发生冲突，在表中顺次向后寻找“下一个”空闲位置Hi 的递推公式为：Hi=(Hi-1+1)%m，i=1,2,m-1即用以下的线性探查序列在表中寻找“下一个”空桶的桶号：H0+1,H0+2,H0+m-1,0,1,2,m-1亦可写成如下的公式：Hi=(H0+i)%m，i=1,2,m-1线性探查法例子 已知关键字序列5,20,22,11,9,10,24 用除留余数法构造哈希函数，线性探查法解决冲突问题，构造哈希表，并求查找成功和失败情况下的平均查找长度。哈希函数为H(key)=key%13查找成功ASL=(4*1+1*2+2*3)/7=1.71查找失败ASL=(6*1+3*2+6+5+4

3、+3)/13=2.3012345678910 11 1224 520 22911 102000102线性探查法例子 9、10、11不是同义词，抢占同一个地址的现象称之为聚集 聚集会产生多个对象连续存储的现象造成查找性能下降012345678910 11 1224 520 22911 102000102线性探查法例子 删除9这个元素怎么做？把第10个位置直接设置成会发生什么问题？设置一个删除标记012345678910 11 1224 520 22 11 102000102012345678910 11 1224 520 22 del 11 102000102二次方探查法(Linear Prob

4、ing)当进行插入记录时，使用哈希函数计算位置：H0=hash(key)一旦发生冲突，在表中顺次向后寻找“下一个”空闲位置Hi 的递推公式为：Hi=(H0+i2)%m,Hi=(H0-i2)%m,i=1,2,(m-1)有时也可以用Hi=(H0+i2)%m,i=1,2,(m-1)二次方探查法例子 已知关键字序列5,20,22,11,9,10,24 用除留余数法构造哈希函数，二次方探查法解决冲突问题，构造哈希表，并求查找成功和失败情况下的平均查找长度。哈希函数为H(key)=key%13解决冲突用+1,-1,+4,-4查找成功ASL=(4*1+2*2+1*3)/7=1.57查找失败ASL=(6*1+

5、3*2+4+3+2+1)/13=1.69012345678910 11 1210 520 22911 242000101伪随机数探查法(Linear Probing)当进行插入记录时，使用哈希函数计算位置：H0=hash(key)一旦发生冲突，在表中顺次向后寻找“下一个”空闲位置Hi 的递推公式为：Hi=(H0+Randi)%m,i=0,1，2,(m-1)其中Randi自己生成，尽量均匀分布在整个空间上二次哈希探查法(Linear Probing)当进行插入记录时，使用哈希函数计算位置：H0=hash(key)一旦发生冲突，在表中顺次向后寻找“下一个”空闲位置Hi 的递推公式为：Hi=(H0+

6、i*H1（key）)%m,i=1,2,(m-1)用第二个哈希函数决定探查的步长二次哈希探查法例子 已知关键字序列5,20,22,11,9,10,24 用除留余数法构造哈希函数，二次方探查法解决冲突问题，构造哈希表，并求查找成功和失败情况下的平均查找长度。哈希函数为H(key)=key%13H1(key)=7-(key%7).不能为0012345678910 11 12924 520 22 10 11 1100000开散列方法-链地址法 开散列方法首先对关键字集合用某一个哈希函数计算它们的存放位置。若设哈希表地址空间的所有位置是从0到m-1，则关键字集合中的所有关键字被划分为m个子集，具有相同地址的关键字归于同一子集。我们称同一子集中的关键字互为同义词。每一个子集称为一个桶。通常各个桶中的表项通过一个单链表链接起来，称之为同义词子表。所有桶号相同的表项都链接在同一个同义词子表中，各链表的表头结点组成一个向量。已知关键字序列5,20,22,11,9,10,24 用除留余数法构造哈希函数，链地址法解决冲突问题，构造哈希表，并求查找成功和失败情况下的平均查找长度。哈希函数为H(key)=key%13链地址法例子查找成功ASL=(5*1+2*2)/7=1.28查找失败ASL=(8*0+3*1+2*2)/13=0.54链地址法例子0123456789101112520924221011