数据结构 第九章 动态查找

单击以编辑,母版标题样式,单击以编辑母版文本样式,第二级,第三级,第四级,第五级,*,一、哈希表是什么？,二、,哈希函数的构造方法,三、,处理冲突的方法,四、,哈希表的查找,五、,哈希表的删除操作,六、,哈希表也可用来构造静态查找表,9.3 哈 希 表,以上两节讨论的表示查找表的各种,结构,的共同,特点,：,记录在表中的,位置,和它的,关键字,之间,不存在,一个确定的关系，,一、,哈希表是什么？,查找的过程,为,给定值,依次和关键字集合中各个,关键字,进行,比较,，,查找的效率,取决于和给定值,进行比较,的关键字,个数,。,用这类方法表示的查找表，,其平均查找长度都不为零。,不同的表示方法，其,差别仅在于：,关键字和给定值进行比较的顺序不同。,只有一个办法：预先知道所查关键字在表中的位置，,对于频繁使用的查找表，希望,ASL = 0。,即，要求：,记录在表中位置和其关键字之间存在一种确定的关系,。,若,以下标为000 999 的顺序表,表示之。,例如：,为每年招收的 1000 名新生建立一张查找表，其关键字为学号，其值的范围为,xx000 xx999 (,前两位为年份)。,则查找过程可以简单进行：取给定值（学号）的后三位，,不需要经过比较,便可直接从顺序表中找到待查关键字。,但是，对于,动态查找表,而言，,因此在一般情况下，需在关键字与记录在表中的存储位置之间建立一个函数关系，,以,f(key),作为关键字为,key,的记录在表中的位置,，,通常,称,这个函数,f(key),为哈希函数。,1) 表长不确定；,2) 在设计查找表时，只知道关键字所属,范围，而不知道确切的关键字。,Z,hao,Q,ian,S,un,L,i,W,u,C,hen,H,an,Y,e,D,ai,例如：,对于如下 9 个关键字,设 哈希函数,f(key) =,(,Ord,(,第一个字母) -,Ord,(A)+1)/2,Chen,Zhao,Qian,Sun,Li,Wu,Han,Ye,Dai,问题:,若添加关键字,Zhou,怎么办？,能否找到,另一个哈希函数？,1),哈希函数是一个,映象,，即：,将关键字的集合映射到某个地址集合上,，,它的设置很,灵活,，只要这个,地址集,合的大小,不超出允许范围,即可；,从这个例子可见：,2),由于哈希函数是一个,压缩映象,，因此，在一般情况下，很容易产生,“冲突”,现象，即：,key1,key2,，,而,f(key1) = f(key2)。,3),很难,找到一个不,产生冲突的哈希函数。,一般情况下，,只能选择恰当的哈希函数，使冲突尽可能少地产生。,因此，在构造这种特殊的,“,查找表,”,时，除了需要选择一个,“,好,”,(,尽可能少产生冲,突),的哈希函数之外；还需要找到,一种,“,处理冲突,”,的,方法,。,哈希表的定义：,根据设定的,哈希函数,H(key),和所选中的,处理冲突的方法,，将一组关键字,映象到,一个有限的、地址连续的地址集 (区间) 上，并以关键字在地址集中的,“,象,”,作为相应记录在表中的,存储位置,，如此构造所得的查找表称之为,“,哈希表,”,。,二、,构造哈希函数的方法,对,数字,的关键字可有下列构造方法：,若是,非数字关键字,，则,需先,对其,进行数字化处理,。,1.,直接定址法,3. 平方取中法,5.,除留余数法,4.,折叠法,6.,随机数法,2.,数字分析法,哈希函数为关键字的线性函数,H(key) = key,或者,H(key) = a,key + b,1.,直接定址法,此法仅适合于：,地址集合的大小 = = 关键字集合的大小,此方法仅适合于：,能,预先估计出,全体关键字的,每一位上,各种,数字出现的频度,。,2.,数字分析法,假设关键字集合中的每个关键字都是由,s,位数字组成 (,u,1, u,2, , u,s,)，,分析关键字集中的全体， 并,从中提取分布均匀的若干位,或,它们的组合,作为地址。,以,关键字的平方值的中间几位,作为存储地址。求,“,关键字的平方值,”,的目的是,“,扩大差别,”,，同时平方值的中间各位又能受到整个关键字中各位的影响。,3. 平方取中法,此方法适合于:,关键字中的每一位都有某些数字重复出现频度很高的现象。,将关键字分割成若干部分，然后取它们的叠加和为哈希地址。,有两种叠加处理的方法：,移位叠加,和,间界叠加,。,4.,折叠法,此方法适合于:,关键字的数字位数特别多。,5.,除留余数法,设定哈希函数为:,H(key) = key MOD p,其中,，,pm,(,表长),并且,p,应为不大于,m,的素数,或是,不含,20,以下的质因子,给定一组关键字为：,12, 39, 18, 24, 33, 21,，,若取,p=9,则他们对应的哈希函数值将为：,3, 3, 0, 6, 6, 3,例如：,为什么要对,p,加限制？,可见，若,p,中含质因子 3，,则所有含质因子 3 的关键字均映射到,“,3 的倍数,”,的地址上,，从而增加了,“,冲突,”,的可能。,6.,随机数法,设定哈希函数为:,H(key) = Random(key),其中，,Random,为伪随机函数,通常，此方法用于对长度不等的关键字构造哈希函数。,实际造表时，,采用何种,构造哈希函数的,方法,取决于建表的关键字集合的情况(包括关键字的范围和形态)，总,的,原则,是,使产生冲突的可能性降到尽可能地小,。,三、,处理冲突的方法,“,处理冲突,”,的实际含义是：,为产生冲突的地址,寻找下一个,哈希地址。,1.,开放定址法,2.,链地址法,为产生冲突的地址,H(key),求得一个,地址序列,：,H,0, H,1, H,2,H,s,1 sm-1,其中：,H,0,= H(key),H,i,= ( H(key) +,d,i,) MOD m,i=1, 2, , s,1.,开放定址法,对增量,d,i,有三种取法：,1,),线性探测再散列,d,i,= c,i,最简单的情况,c=1,2,),平方探测再散列,d,i,= 1,2, -1,2, 2,2, -2,2,3,),随机探测再散列,d,i,是一组,伪随机数列,或者,d,i,=i,H,2,(key),(,又称双散列函数探测),即：产生的,H,i,均不相同，且所产生的,s(m-1),个,H,i,值能,覆盖,哈希表中所有地址。则要求：,注意：,增量,d,i,应具有“完备性”,随机探测时的,m,和,d,i,没有公因子。,平方探测时的表长,m,必为形如,4,j+3,的素数（如: 7, 11, 19, 23, 等）；,例如:,关键字集合,19, 01, 23, 14, 55, 68, 11, 82, 36 ,设定,哈希函数,H(key) = key,MOD,11,(,表长=11 ),19,01,23,14,55,68,19,01,23,14,68,若采用,线性探测再散列,处理冲突,若采用,二次探测再散列,处理冲突,11,82,36,55,11,82,36,1 1 2 1 3 6 2 5 1,H,2,(key),是另设定的一个哈希函数，它的函数值应和,m,互为素数,。,若,m,为素数，则,H,2,(key),可以是,1,至,m-1,之间的,任意数,；,若,m,为 2 的幂次，则,H,2,(key),应是,1,至,m-1,之间的,任意奇数,。,例如，当,m=11,时，可设,H,2,(key)=(3 key) MOD 10+1,19,01,23,14,55,68,11,82,36,2 1 1 1 2 1 2 1 3,将所有哈希地址相同的记录,都链接在同一链表中。,2.,链地址法,0,1,2,3,4,5,6,14,01,36,19,82,23,11,68,55,ASL=(61+22+3)/9=13/9,例如:同前例的关键字，哈希函数为,H(key)=key MOD 7,查找过程和造表过程一致。假设采用开放定址处理冲突，则,查找过程,为：,四、,哈希表的查找,对于,给定值,K,，,计算,哈希地址,i = H(K),若,ri = NULL,则查找不成功,若,ri.key = K,则查找成功,否则,“,求下一地址,Hi,”,，,直至,rHi = NULL,(,查找不成功),或,rHi.key = K,(,查找成功) 为止。,int,hashsize, = 997, . ;,typedef struct,ElemType,*,elem,;,int,count;,/,当前数据元素个数,int,sizeindex,;,/,hashsize,sizeindex,为当前容量,HashTable,;,#define,SUCCESS 1,#define,UNSUCCESS 0,#define,DUPLICATE -1,/-,开放定址哈希表,的存储结构 -,Status,SearchHash,(,HashTable,H,KeyType,K,int,&,p,int,&,c),/,在开放定址哈希表,H,中查找关键码为,K,的记录, /,SearchHash,p = Hash(K);,/,求得哈希地址,while,(,H.,elem,p.key,!=,NULLKEY,&,!,EQ(K, H.,elem,p.key),）,collision(p, +c);,/,求得下一探查地址,p,if,(EQ(K, H.,elem,p.key),return,SUCCESS;,/,查找成功，返回待查数据元素位置,p,else return,UNSUCCESS;,/,查找不成功,Status,InsertHash,(,HashTable,&,H,Elemtype,e),/,InsertHash,c = 0;,if,(,HashSearch,( H, e.key, p, c ) = SUCCESS ),return,DUPLICATE;,/,表中已有与,e,有相同关键字的元素,else,H.,elem,p = e;,+,H.count;,return,OK;,/,查找不成功时，返回,p,为插入位置,else,RecreateHashTable,(H);,/,重建哈希表,if,( c ,hashsize,H.,sizeindex,/2 ),/,冲突次数,c,未达到上限，（阀值,c,可调）,1,),选用的,哈希函数,；,2,),选用的,处理冲突的方法,；,3,),哈希表饱和的程度，,装载因子,=n/m,值的,大小,（,n,记录数，,m,表的长度）,决定哈希表查找的,ASL,的因素,：,哈希表查找的分析:,从查找过程得知，哈希表查找的平均查找长度,实际上并不等于零,。,一般情况下，可以认为选用的哈希函数是“均匀”的，则在讨论,ASL,时，可以不考虑它的因素。,因此，哈希表的,ASL,是,处理冲突方法,和,装载因子,的函数。,例如：前述例子,线性探测处理冲突时，,ASL =,双散列探测处理冲突时，,ASL =,链地址法处理冲突时，,ASL =,22,/9,14,/9,13,/9,线性探测再散列,链地址法,随机探测再散列,可以证明：,查找成功,时有下列结果：,从以上结果可见：,哈希表的平均查找长度是,的函数,，而不是,n,的函数。,这说明，用哈希表构造查找表时，可以选择一个适当的装填因子, ，使得,平均查找长度限定在某个范围内,。, 这是哈希表所特有的特点。,从哈希表中删除记录时，要作,特殊处理,，相应地，需要修改查找的算法。,五、哈希表的删除操作,六、哈希表也可以用来构造静态查找表,并且，,对静态查找表，有时可以,找到不发生冲突的哈希函数。即，此时的,哈希表的,ASL=0,称此类哈希函数为,理想,（,perfect）,的哈希函数,。,1.,顺序表,和,有序表,的查找方法及其平均查找长度的计算方法。,2.,熟练掌握,二叉排序树,的构造和查找方法。,本章学习要点,3.,理解,B-,树,、,B,+,树和键树,的,特点以及它们的建树和查找的过程。,4.,熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别。,5.,掌握按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。,