数据结构散列表

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,7.3 散列表的查找技术,7.3 散列表的查找技术,顺序查找、折半查找等。,这些查找技术都是通过一系列的给定值与关键码的比较，查找效率依赖于查找过程中进行的给定值与关键码的比较次数。,查找操作要完成什么任务？,待查值,k,确定,k,在存储结构中的位置,我们学过哪些查找技术？这些查找技术的共性？,在存储位置和关键码之间建立一个确定的对应关系,能否不用比较，通过关键码直接确定存储位置？,概 述,散列的基本思想：,在记录的存储地址和它的关键码之间建立一个确定的对应关系。这样，不经过比较，一次读取就能得到所查元素的查找方法。,7.3 散列表的查找技术,关键码集合,k,i,r,i,H,(,k,i,),H,散列表：,采用散列技术将记录存储在一块,连续,的存储空间中，,这块连续的存储空间,称为散列表。,概 述,7.3 散列表的查找技术,关键码集合,k,i,r,i,H,(,k,i,),H,散列表,数组,散列函数：,将关键码映射为散列表中适当存,储位置的函数。,概 述,7.3 散列表的查找技术,散列表,关键码集合,k,i,r,i,H,(,k,i,),H,散列函数,数组,散列地址：,由散列函数,所得的存储位置,。,概 述,7.3 散列表的查找技术,散列表,关键码集合,k,i,r,i,H,(,k,i,),H,散列函数,散列地址,下标,数组,例子,一组数：12，37，52，43，84，99,散列函数为:H(k)=k%11,散列表,：长度为11,0,1,2,3,4,5,6,7,8,9,10,12,37,52,43,84,99,概 述,7.3 散列表的查找技术,散列技术仅仅是一种查找技术吗？,散列既是一种查找技术，也是一种存储技术。,散列只是通过记录的关键码定位该记录，没有完整地表达记录之间的逻辑关系，所以，散列主要是,面向查找,的存储结构。,散列是一种,完整的存储结构,吗？,散列技术的关键问题：,散列函数的设计。如何设计一个简单、均匀、存储利用率高的散列函数。,冲突的处理。如何采取合适的处理冲突方法来解决冲突。,7.3 散列表的查找技术,概 述,冲突：,对于两个不同关键码,k,i,k,j,，有,H,(,k,i,),H,(,k,j,),，即两个不同的记录,需要存放在同一个存储位置,k,i,和,k,j,相对于,H,称做,同义词,。,7.3 散列表的查找技术,概 述,r,i,关键码集合,k,i,H,(,k,i,),k,j,H,(,k,j,),散列函数,7.3 散列表的查找技术,设计散列函数一般应遵循以下原则：,计算,简单,。散列函数不应该有很大的计算量，否则会降低查找效率。,函数值即散列地址分布,均匀,。函数值要尽量均匀散布在地址空间，这样才能保证存储空间的有效利用并减少冲突。,1、散列函数,直接定址法,散列函数是关键码的线性函数,，,即：,H,(,key,)=,a,key,+,b,（,a,，,b,为常数）,例：关键码集合为10,30,50,70,80,90，选取的散列函数为,H,(,key,),=,key,/10，,则散列表,为：,0 1 2 3 4 5 6 7 8 9,10,30,50,70,80,90,适用情况？,事先知道关键码，关键码集合不是很大且连续性较好。,7.3 散列表的查找技术,散列函数为：,H,(,key,),=,key,mod,p,7.3 散列表的查找技术,2、散列函数,除留余数法,如何选取合适的,p,，产生较少同义词？,一般情况下，选,p,为小于或等于表长（最好接近表长）的最小素数。,适用情况？,除留余数法是一种最简单、也是最常用的构造散列函数的方法，并且不要求事先知道关键码的分布。,根据关键码在各个位上的分布情况，选取分布比较,均匀,的若干位组,成散列地址。,例：关键码为8位十进制数，散列地址为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,7.3 散列表的查找技术,3、散列函数,数字分析法,适用情况:,能预先估计出全部关键码的每一位上各种数字出现的频度，不同的关键码集合需要重新分析。,7.3 散列表的查找技术,3、散列函数,数字分析法,对关键码平方后，按散列表大小，取中间的若干位作为散列地址（,平方,后,截取,）。,7.3 散列表的查找技术,4、散列函数,平方取中法,事先不知道关键码的分布且关键码的位数不是很大。,适用情况:,例：散列地址为2位，则关键码123的散列地址为：,(1234),2,152,27,56,将关键码从左到右分割成位数相等的几部分，将这几部分叠加求和，取后几位作为散列地址。,7.3 散列表的查找技术,5、散列函数,折叠法,例：设关键码为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,间界叠加,适用情况:,关键码位数很多，事先不知道关键码的分布。,1、处理冲突的方法,开放定址法,由关键码得到的散列地址一旦产生了冲突，就去寻找,下一个空,的散列地址，并将记录存入。,如何寻找下一个空的散列地址?,7.3 散列表的查找技术,（1）线性探测法,（2）二次探测法,（3）随机探测法,（1）线性探测法,当发生冲突时，从冲突位置的下一个位置起，依次寻找空的散列地,址。,对于键值,key,，设,H,(,key,),=,d,，闭散列表的长度为,m,，则发生冲突时，寻找下一个散列地址的公式为：,H,i,=,(,H,(,key,),d,i,),%,m,（,d,i,=1,，,2,，,m,-,1,）,7.3 散列表的查找技术,用开放定址法处理冲突得到的散列表叫,闭散列表,。,例：关键码集合为 47,7,29,11,16,92,22,8,3，散列表表长为11，散列函,数为,H,(,key,),=,key,mod 11,，用线性探测法处理冲突，则构造的散列表为：,0 1 2 3 4 5 6 7 8 9,47,7,29,11,16,92,29,22,22,8,8,3,3,3,3,堆积：,在处理冲突的过程中出现的,非同义词,之间对,同一个散列地址争夺的现象,。,7.3 散列表的查找技术,（1）线性探测法,用线性探测法构造的散列表中查找算法伪代码,1.计算散列地址j;,2.若htj=k，则查找成功，返回记录在散列表中的下标；,否则,3.若htj为空或将散列表探测一遍，则查找失败，转4；,否则，j指向下一单元，转2；,4.若整个散列表探测一遍，则表满，抛出溢出异常；,否则，将待查值插入；,7.3 散列表的查找技术,int HashSearch1(int ht,int m,int k),int j=k%m;,if(htj=k),return j;/没有发生冲突，比较一次查找成功,int i=(j+1)%m;,while(i!=j),if(hti=k)return i;/发生冲突,if(hti=0)break;,i=(i+1)%m;/向后探测一个位置,if(i=j)throw 溢出;,else,hti=k;return i;,7.3 散列表的查找技术,在线性探测法构造的散列表中查找算法C+描述,（2）二次探测法,当发生冲突时，寻找下一个散列地址的公式为：,H,i,=,(,H,(,key,),d,i,),%,m,（,d,i,=1,2,，,1,2,，,2,2,，,2,2,，,q,2,，,q,2,且,q,m,/2,）,7.3 散列表的查找技术,0 1 2 3 4 5 6 7 8 9,47,7,29,11,16,92,29,22,22,8,8,3,3,3,例：关键码集合为 47,7,29,11,16,92,22,8,3，散列表表长为11，散列函,数为,H,(,key,),=,key,mod 11,，用二次探测法处理冲突，则散列表为：,（2）二次探测法,7.3 散列表的查找技术,（3）随机探测法,当发生冲突时，下一个散列地址的位移量是一个随机数列，即,寻找下一个散列地址的公式,为：,H,i,=,(,H,(,key,),+,d,i,),%,m,（,d,i,是一个随机数列，,i,=1，2，,m,-,1）,7.3 散列表的查找技术,计算机中产生随机数的方法通常采用线性同余法，,其中，,d,称为随机种子。当,b,、,c,和,m,的值确定后，给定一个随机种子，产生确定的随机数序列。,0,=,d,a,=,+,=,-,1,2,L,mod,),(,1,n,m,c,ba,a,n,n,基本思想,：将所有散列地址相同的记录，即所有同义词的记录存储在一个单链表中（称为同义词子表），在散列表中存储的是所有同义词子,表的头指针。,用拉链法处理冲突构造的散列表叫做,开散列表,。,设,n,个记录存储在长度为,m,的散列表中，则同义词子表的平均长度为,n,/,m,。,7.3 散列表的查找技术,2、处理冲突的方法,拉链法（链地址法）,例：关键码集合 47,7,29,11,16,92,22,8,3，散列函数为,H,(,key,),=,key,mod 11,，用拉链法处理冲突，构造的开散列表为：,7.3 散列表的查找技术,0,1,2,3,4,5,6,7,8,9,10,11,22,47,3,92,16,7 ,29,8 ,在拉链法构造的散列表查找算法伪代码,1.计算散列地址j；,2.在第j个同义词子表中顺序查找；,3.若查找成功，则返回结点的地址；,否则，将待查记录插在第j个同义词子表的表头。,7.3 散列表的查找技术,Node*HashSearch2,(,Node*ht,int m,int k,),j=H,(,k,),;,p=htj;,while,(,p&p,-,data!=k,),p=p,-,next;,if,(,p,-,data=k,),return p;,else,q=new Node;q,-,data=k;,q,-,next=htj;,htj=q;,7.3 散列表的查找技术,在拉链法构造的散列表查找算法C+描述,基本思想,：散列表包含,基本表,和,溢出表,两部分（通常溢出表和基本表的大小相同），将发生冲突的记录存储在溢出表中。查找时，对给定值通过散列函数计算散列地址，先与,基本表,的相应单元进,行比较，若相等，则查找成功；否则，再到,溢出表,中进行顺序查找。,7.3 散列表的查找技术,3、处理冲突的方法,公共溢出区,例：关键码集合 47,7,29,11,16,92,22,8,3，散列函数为,H,(,key,),=,key,mod 11,，用公共溢出区法处理冲突，构造的散列表为：,7.3 散列表的查找技术,0,1,2,3,4,5,6,7,8,9,10,基本表 溢出表,11,47,92,16,7,8,0,1,2,3,4,5,6,7,8,9,10,29,22,3,散列查找的性能分析,由于冲突的存在，产生冲突后的查找仍然是给定值与关键码进行比较的过程。,在查找过程中，关键码的比较次数取决于产生冲突的概率。,而影响冲突产生的因素有：,（1）散列函数是否均匀,（2）处理冲突的方法,（3）散列表的装载因子,=表中填入的记录数/表的长度,7.3 散列表的查找技术,查找成功时,查找不成功时,线性探测法,二次探测法,拉链法,ASL,处理冲突方法,几种不同处理冲突方法的平均查找长度,7.3 散列表的查找技术,开散列表与闭散列表的比较,7.3 散列表的查找技术,不产生,产生,有,没有,堆积现象,结构开销,插入/删除,查找效率,开,散,列,表,闭,散,列,表,效率高,效率低,效率高,效率低,估计容量,不需要,需要,