《第八章查找3.ppt》由会员分享,可在线阅读,更多相关《第八章查找3.ppt(27页珍藏版)》请在三一文库上搜索。
1、第八章 查找,线性表上的查找 二叉排序树 哈希表,8.3 哈希表,查找操作要完成什么任务? 我们学过哪些查找技术?这些查找技术的共性? 顺序查找、折半查找、二叉排序树查找等。 以上讨论的查找方法,由于记录的存储位置与关键字之间不存在确定的关系,因此查找时需要进行一系列对关键字的查找比较,即“查找算法”是建立在比较的基础上的,查找效率由比较一次缩小的查找范围决定。,能否不用比较,通过关键码直接确定存储位置? 依据关键字直接得到其对应的记录位置,即要求关键字与记录位置间存在一一对应关系,通过这个关系,能很快地由关键字得到对应的记录位置。,哈希函数(散列函数):在记录的关键字与记录的存储地址之间建立
2、的一种对应关系。,哈希函数是从关键字空间到存储地址空间的一种映象。 哈希函数可写成:addr(ai)=H(ki) ai是表中的一个元素 addr(ai)是ai的存储地址 ki是ai的关键字,以编号作关键字, 构造哈希函数:H(key)=key H(1)=1 H(2)=2,以地区别作关键字,取地区 名称第一个拼音字母的序号 作哈希函数:H(Beijing)=2 H(Shanghai)=19 H(Shenyang)=19,散列技术仅仅是一种查找技术吗? 散列既是一种查找技术,也是一种存储技术。 散列是一种完整的存储结构吗? 散列只是通过记录的关键码定位该记录,没有完整地表达记录之间的逻辑关系,所以
3、,散列主要是面向查找的存储结构。,散列技术适合于哪种类型的查找? 散列技术一般不适用于允许多个记录有同样关键码的情况。散列方法也不适用于范围查找,换言之,在散列表中,我们不可能找到最大或最小关键码的记录,也不可能找到在某一范围内的记录。, 散列函数的设计。如何设计一个简单、均匀、存储利用率 高的散列函数。 所选函数尽可能简单,以便提高转换速度。 所选函数对关键字计算出的地址,应在Hash地址集中大致均 匀分布,以尽量减少冲突。, 冲突的处理。如何采取合适的处理冲突方法来解决冲 突。 Hash函数。若Hash函数选择得当,就可使Hash地址尽可能均 匀地分布在Hash地址空间上,从而减少冲突的发
4、生;否则,若Hash 函数选择不当,就可能使Hash地址集中于某些区域,从而加大冲突 的发生。 处理冲突的方法。选择适当的Hash函数可以减少冲突,但不能 避免冲突,因此当冲突发生时,必须有较好的处理冲突的方法。 Hash表的装填因子。,散列技术的关键问题,哈希函数的构造,直接定址法,数据分析法,平方取中法,折叠法,除留取余法,1. 直接定址法,散列函数是关键码的线性函数,即:,H(key) = a key + b (a,b为常数),例如:有一个解放后出生人口调查表,每个记录包含年份、人数等 数据项,其中年分为关键字,则哈希函数可取为: H(key)=key +(-1948) 这样就可以方便地
5、存储和查找1948年后任意一年的记录。,练习:关键码集合为10, 30, 50, 70, 80, 90,选取的散列函数为H(key)=key/10,则散列表为:,10,30,50,70,80,90,特点: 直接定址法所得地址集合与关键字集合大小相等,不 会发生冲突。 实际中能用这种哈希函数的情况很少。,2. 数据分析法,根据关键码在各个位上的分布情况,选取分布比较均匀的若干位组成散列地址。,例 有80个记录,关键字为8位十进制数,哈希地址为2位十进制数。,分析: 只取8 只取1 只取3、4 只取2、7、5 数字分布近乎随机 所以:取任意两位或两位 与另两位的叠加作哈希地址,练习:关键码为8位十
6、进制数,散列地址为2位十进制数。,8 1 3 4 6 5 3 2 8 1 3 7 2 2 4 2 8 1 3 8 7 4 2 2 8 1 3 0 1 3 6 7 8 1 3 2 2 8 1 7 8 1 3 3 8 9 6 7, ,特点: 适于关键字位数比哈希地址位数大,且可能出现的关键字事先知道的情况。,3. 平方取中法,对关键码平方后,按散列表大小,取中间的若干位作为散列地址(平方后截取)。,例:散列地址为2位,则关键码1234的散列地址为:,(1234)21522756,特点: 适于事先不知道关键码的分布且关键码的位数不是很大。,4. 折叠法,将关键码从左到右分割成位数相等的几部分,将这几
7、部分叠加求和,取后几位作为散列地址。,种类 移位折叠法:将分割后的几部分低位对齐相加。 边界折叠法:从一端沿分割界来回折送,然后对齐相加。,例 关键字为 :0442205864,哈希地址位数为4,练习:设关键码为2 5 3 4 6 3 5 8 7 0 5,散列地址为三位。,2 5 3 4 6 3 5 8 7 + 0 5 1 3 0 8 移位折叠,2 5 3 3 6 4 5 8 7 + 5 0 1 2 5 4 边界折叠,特点: 适于关键字位数很多,且每一位上数字分布大致均匀情况。,5. 除留取余法,散列函数为:,H(key)=key mod p,例: p 21,特点 简单、常用,可与上述几种方法
8、结合使用。 p的选取很重要;p选的不好,容易产生同义词。,选取哈希函数,考虑以下因素: 计算哈希函数所需时间 关键字长度 哈希表长度(哈希地址范围) 关键字分布情况 记录的查找频率,发生冲突如何解决?,冲突的解决方法,开放地址法,链地址法,1. 开放地址法,方法:当冲突发生时,形成一个探查序列;沿此序列逐个地址探查,直到找到一个空位置(开放的地址),将发生冲突的记录放到该地址中,即Hi=(H(key)+Di)MOD m,i=1,2,k(km-1) 其中:H(key)哈希函数 m哈希表表长 Di增量序列,1. 开放地址法-线性探测法,在线性探测法中,D被定义为一个线性函数,如 D(i) = i这
9、相当于逐个探测每个单元以查找出一个空单 元时为止。,例 表长为11的哈希表中已填有关键字为17,60,29的记录,H(key)=key MOD 11,现有第4个记录,其关键字为38,将它填入表中,(1) H(38)=38 MOD 11=5 冲突 H1=(5+1) MOD 11=6 冲突 H2=(5+2) MOD 11=7 冲突 H3=(5+3) MOD 11=8 不冲突,38,1. 开放地址法-平方探测法,在平方探测法中,D被定义为一个二次函数,如 D(i) = i2。,例 表长为11的哈希表中已填有关键字为17,60,29的记录,H(key)=key MOD 11,现有第4个记录,其关键字为
10、38, 按平方探测法,将它填入表中。,(2) H(38)=38 MOD 11=5 冲突 H1=(5+1) MOD 11=6 冲突 H2=(5+2) MOD 11=9 不冲突,38,1. 开放地址法-双散列,双散列是以关键字的另一个关键字的散列值作为 增量。设有两个函数分别为h1和h2,则选择的 D(i) = I * h2(key)。即当地址i发生冲突时,探测的是 i + h2(key), i + 2h2(key), i + 3h2(key), 。,例 表长为11的哈希表中已填有关键字为17,60,29的记录,H(key)=key MOD 11,现有第4个记录,其关键字为38,按双散列方法,将它
11、填入表中。,(3) H(38)=38 MOD 11=5 冲突 令h2(key) = key % 9 + 1,则: h2(38)=38 % 9 + 1=3因此得到下一个探测地址为 5 + 3 = 8 不冲突,38,2. 链地址法,方法:将所有关键字为同义词的记录存储在一个单链 表中,并用一维数组存放头指针。,例 已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函数为:H(key)=key MOD 13, 用链地址法处理冲突。,哈希表的查找过程及其分析,哈希表的查找过程,哈希查找仍是一个给定值与关键字进行比较的过程。 哈希查找与给定值进行比较的关键字的个
12、数取决于: 哈希函数 处理冲突的方法 哈希表的填满因子 =表中填入的记录数/哈希表长度,哈希查找分析,例 已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函数为:H(key)=key MOD 13, 哈希表长为 n=16,设每个记录的查找概率相等。,(1) 用线性探测再散列处理冲突,即Hi=(H(key)+di) MOD m,H(55)=3 冲突,H1=(3+1)MOD13=4 冲突,H2=(3+2)MOD13=5,H(79)=1 冲突,H1=(1+1)MOD13=2 冲突,H2=(1+2)MOD13=3 冲突,H3=(1+3)MOD13=4 冲突,
13、H4=(1+4)MOD13=5 冲突,H5=(1+5)MOD13=6 冲突,H6=(1+6)MOD13=7 冲突,H7=(1+7)MOD13=8 冲突,H8=(1+8)MOD13=9,ASL=(1*6+2+3*3+4+9)/12=2.5,14,1,68,27,55,19,20,84,79,23,11,10,H(19)=6,H(14)=1,H(23)=10,H(1)=1 冲突,H1=(1+1) MOD13=2,H(68)=3,H(20)=7,H(84)=6 冲突,H1=(6+1)MOD13=7 冲突,H2=(6+2)MOD13=8,H(27)=1 冲突,H1=(1+1)MOD13=2 冲突,H2=(1+2)MOD13=3 冲突,H3=(1+3)MOD13=4,H(11)=11,H(10)=10 冲突,H1=(10+1)MOD13=11 冲突,H2=(10+2)MOD13=12,(2) 用链地址法处理冲突,ASL=(1*6+2*4+3+4)/12=1.75,关键字(19,14,23,1,68,20,84,27,55,11,10,79)。,几种不同处理冲突方法的平均查找长度,查找成功时,查找不成功时,ASL,处理冲突方法,
链接地址:https://www.31doc.com/p-2969105.html