数9-查B

数据结构2004--12--289.3哈希(Hash)表和哈希法9.3.1哈希表(散列表)、同义词、冲突根据设定的哈希函数H(k)和处理冲突的方法，将一组关键字映象到一个有限的地址区间上，并以关键字在地址区间中的映象作为记录在表中的存储位置，这种表称为哈希表或散列表，所得存储位置称为哈希地址或散列地址。设K1和K2为关键字,若K1≠K2,H(K1)=H(K2),则称K1,K2为同义词,K2与K1为发生了冲突例设H(k)=k%17k1=5k2=22∵H(5)=5%17=5H(22)=22%17=5H(5)=H(22)=5∴5和22是同义词,5和22发生冲突9.3.2构造哈希函数的方法1.直接定址法取关键字或关键字的某个线性函数值为哈希地址H(key)=keyH(key)=a.key+b110.5212.6311.0420.8......150...序号(地址)年龄人数(万)1234150哈希函数是H(key)=key=地址H(年龄）=年龄key例1人口统计表例2学生成绩表200041刘大海男8075200042王伟男9083200043吴晓英女8288200044王伟女8090....................................1234nkey序号(地址)学号姓名性别数学外语H(key)=key-200040=地址H(学号)=学号-200040例3标识符表ABCCATDATFOXYABZOO1234562526序号标识符(key)H(key)=key的第一个字母在字母表中的序号key=ABCCADDATFOXYABZOOH(key)=134625262.除留余数法设哈希表HT[0..m-1]的表长为m，哈希地址为key除以p所的的余数：H(key)=keyMODp//PASCAL语言H(key)=key%p//C语言其中：MOD,%为取模或求余p=m，p为接近m的质数(素数),如：3,5,7,11,13,17,19,23,29,31,37......或不包含小于20的质因子的合数，如：713(=23*31)012.....129例2设m=256,取p=251,H(key)=key%251012.....255例1设m=130,取p=127,H(key)=key%127例设哈希表的地址范围为0～20,哈希函数为H(K)=K%19输入关键字序列：39,22,21,37,36,38,19,解决冲突的方法为线性探测再散列(哈希),构造哈希表HT[0..20]。38392122193637关键字KH(K)=K%193939%19=12222%19=32121%19=23737%19=183636%19=173838%19=01919%19=019与38冲突,再与39,21,22冲突,存入HT[4]01234517181920序号keyother_itemHT[0..20]例设哈希表的地址范围为0～20,哈希函数为H(K)=K%19输入关键字序列：39,22,21,37,36,38,19,解决冲突的方法为线性探测再散列(哈希),构造哈希表HT[0..20]。38392122195536371756再输入17,56,5517%19=1717与36冲突,再与37冲突,存入HT[19]。56%19=1856与37冲突,再与17冲突,存入HT[20]。55%19=1755与36,37,17,56冲突,再与38,39,21,22,19冲突,存入HT[5]。01234517181920HT[0..20]序号key对于H(k)=k%19，所有的19a+b为同义词,0≤b≤19如：5,24,43,62,81,.....3.平方取中法----取关键字平方后的中间某几位为哈希地址,即：H(k)=取k2的中间某几位数字例.设哈希表为HT[0..99],哈希函数为：H(K)=取k2的中间2位数,输入关键字序列：39,21,6,36,38,13,用线性探测再散列法解决冲突,构造HT[0..99]。Kk2H(K)391521522104414460036033612962938144444130169166133621383903162944455299序号keyother_itemHT[0..20]4.折叠法将关键字分割成位数相同的几部分,然后取这几部分的叠加和作为哈希地址。(1)边界折叠法设表地址范围为0～999k1=056439527650+439+725=1814H(k1)=814k2=123486790321+486+097=907H(k2)=907k3=300600007003+600+700=1303H(k2)=30330060000705643952712348679001303814907999HT[0..999]序号key4.折叠法将关键字分割成位数相同的几部分,然后取这几部分的叠加和作为哈希地址。(2)移位折叠法(移位法)设表地址范围为0～999k1=056439527056+439+527=1022H(k1)=022k2=123486790123+486+790=1399H(k2)=399k3=300600007300+600+007=907H(k2)=9070564395271234867903006000070122399907999HT[0..999]序号key5.数字分析法设哈希表中可能出现的关键字都是事先知道的,则可取关键字的若干分布均匀的位组成哈希地址。kH(k)902406820690443184319013458145904432843290617986799053243524901345690200679044313904432690532439061791145206431432524679HT[0..999]↑↑↑6.随机数法H(key)=random(key)random(key)为产生伪随机数的函数7.灵活构造哈希函数例.设哈希表为HT[0..40],哈希函数为：H(K)=取k2的中间2位数*40/99将00～99之内的地址压缩到00～40之内，设关键字序列是：39,21,6,36,38,13,用线性探测再散列法解决冲突。6132138397701361718213740序号keyotherKk2H(K)39152152*40/99=2121044144*40/99=176003603*40/99=177592992*40/99=3738144444*40/99=1713016916*40/99=6HT[0..40]9.3.3解决冲突的方法1.开放地址法(开式寻址法)假定对记录Ri,Rj，H(Ki)=H(Kj)=q,Ri已存入HT[0..m-1]中的HT[q]中，则Rj存入HT中的某个空位上。依次在地址q+1,q+2,...,m-1,0,1,...,q-1中寻找一个空位，叫做线性探测再散列。(1)线性探测再散列HT[0..m-1]01q-1qq+1m-1RjRi课堂练习：设H(k)=k的首字母在字母表中的序号,用线性探测再散列法解决冲突,依次用下列关键字,造哈希表HT[0..28]kH(k)A1DEC4ZMN26DAB4ZE26ANT1YY25ZOO26CAD3YES25ZY26LL12DE40123456121325262728HT[0..28]12345678910111213例设H(k)=k的首字母在字母表中的序号，用线性探测再散列法解决冲突，依次用下列关键字，造哈希表HT[0..28]。YESAANTCADDECDABZYDELLYYZMNZEZ00kH(k)A1DEC4ZMN26DAB4ZE26ANT1YY25ZOO26CAD3YES25ZY26LL12DE4012345671225262728HT[0..28]12345678910111213(2)二次探测再散列假定对记录Ri,Rj，H(Ki)=H(Kj)=q,Ri已存入HT[0..m-1]中的HT[q]中,若依次在地址q+12,q-12,q+22,q-22,...,q+i2,q-i2,...中寻找一个空位，叫做二次探测再散列。例设记录X和A为同义词，散列地址为50,二次探测再散列的地址序列为：51,49,54,46,59,41,66,......HT[0..99]GECABDF03441464950515459667599XXXXXXXXHT[0..99]GECABDFX034414649505154596675992.链地址法将关键字为同义的所有记录存入同一链表中。例设H(k)=k的首字母在字母表中的序号,用下列关键字造哈希表HT[1..26]kH(k)A1DEC4ZMN26DAB4ZE26ANT1YY25ZOO26CAD3YES25ZY26LL12DE412345678910111213∧∧∧∧HT[1..26]ZEZOOZYZMN∧DEYESYY∧CAD∧ANTA∧DABDEC∧LL∧1234122526头指针2.链地址法将关键字为同义的所有记录存入同一链表中。例设H(k)=k的首字母在字母表中的序号,用下列关键字造哈希表HT[1..26]HT[1..26]ZOOZEZMNZY∧DECYYYES∧CAD∧AANT∧DABDE∧LL∧∧∧∧∧1234122526kH(k)A1DEC4ZMN26DAB4ZE26ANT1YY25ZOO26CAD3YES25ZY26LL12DE412345678910111213头指针3.建立公共溢出区将发生冲突的所有记录存入一个公共溢出表OT[0..v]中。例设H(k)=k的首字母在字母表中的序号,用下列关键字生成基本表HT[1..26]和溢出表OT[0..50]ACADDECLLYYZMNHT[1..26]1234122526DABZEANTZOOYESZYDEOT[0..50]123456750kH(k)A1DEC4ZMN26DAB4ZE26ANT1YY25ZOO26CAD3YES25ZY26LL12DE412345678910111213基本表溢出表4.再哈希法发生冲突时，使用下一个哈希函数计算哈希地址：j1=H1(K)；j2=H2(K)；j3=H3(K)；......9.3.4哈希表的查找及其分析∧∧∧∧ZEZOOZYZMN∧DEYESYY∧CAD∧ANTA∧DABDEC∧LL∧例1假定每个记录的查找概率相等，查找成功时的平均查找长度：ASL=(1+2+1+1+2+3+1+1+2+1+2+3+4)/13=24/13≈1.851234122526HT[1..26]例2假定每个记录的查找概率相等，查找成功时的平均查找长度.关键字KH(K)比较次数A11ANT12CAD31DEC41DAB42ZY2610DE44LL121YY251ZMN261ZE262Z00263YES255合计34ASL=34/13≈2.62YESAANTCADDECDABZYDELLYYZMNZEZ00HT[0..28]01234567121325262728序号关键字练习题1.顺序查找1000个记录的顺序表,当使用监视哨时,若查找成功,比较关键字的次数最少是多少？最多是多少？假定每个记录的查找概率相同,求查找成功时的平均查找长度ASL。2.折半查找22个记录的有序表,若查找成功,比较关键字的次数最少是多少？最多是多少？假定每个记录的查找概率相同,求查找成功时的ASL；画出对应的判定树。3.对长度为800的表采用分块查找,最理想的块长是多少？假定每个记录的查找概率相同,试求查找成功时的ASL。4.试按表(13,06,04,12,20,05,02,26)中元素的排列次序,生成一棵二叉排序树:(1)画出二叉排序树；(2)对该树进行中序遍历,写出中序遍历序列；(3)假定每个结点的查找概率相等,求查找成功时的ASL。5.设哈希(Hash)函数为:H(k)=k%14,其中k为关键字,%为取模运算，用线性探测再散列法处理冲突,在地址范围为0～15的散列区中,试用关键字序列(1