数据结构-哈希表

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,哈希表,什么是哈希表,哈希函数的构造方法,处理冲突的方法,哈希表的查找,哈希表的查找分析,小结和作业,课堂练习,A0,A1A2A3A4A5A6A7A8A9A10,例,1:,有一批考试成绩，统计各分数段的人数。,对成绩,Grade,，执行：,A,grade/10+,什么是哈希表,例,2:,Ord(Char,)=,asc(char,),asc(a,)+1,什么是哈希表,0 1(A)3 4 5(E)9(I),26,8(H),4(D)19(S)22(V)0 18(R)7(G)19,0 5(E),HAD,HAS,HAV,HE,HER,HERE,HIG,HIS,将,1000,个学生的信息存放在数组,A0,A999,中,例,3:,为每年招收的,1000,名新生建立一张查找表，其关键字为学号，其值的范围为,xx000 xx999(,前两位为年份,),。,什么是哈希表,number(substring,(,学号,3,3),建立查找表：,给定关键字,key,计算,f(key,),数组下标,查找表：,使用数组存放,n,个关键字，数组的下标,0,n-1,什么是哈希表,查找时：,给定关键字,key,计算,f(key,),数组下标,建立查找表：,给定,grade,计算,f(grade,),数组下标,例,4,：统计学生成绩各分数段的人数,什么是哈希表,查找时：,给定,grade,计算,f(grade,),数组下标,Hash,函数：,f(grade,)=grade/10,什么是哈希表,Z,hao,Q,ian,S,un,L,i,W,u,C,hen,H,an,Y,e,D,ei,例,5,：对于如下,9,个关键字,设 哈希函数,f(key)=,(,Ord,(,第一个字母,)-,Ord(A,)+1)/2,什么是哈希表,字母,A,B,C,D,E,F,G,H,I,J,K,L,M,序号,1,2,3,4,5,6,7,8,9,10,11,12,13,字母,N,O,P,Q,R,S,T,U,V,W,X,Y,Z,序号,14,15,16,17,18,19,20,21,22,23,24,25,26,Chen,Zhao,Qian,Sun,Li,Wu,Han,Ye,Dei,序号,0 1 2 3 4 5 6 7 8 9 10 11 12 13,问题,:,若添加关键字,Zhou,怎么办？,什么是哈希表,由此可见，,1),哈希,(Hash),函数是一个映象，即：将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地址集合的大小不超出允许范围即可；,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,位数字组成,(u1,u2,us),，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。,此方法仅适合于：,能,预先估计出,全体关键字的,每一位,上,各种,数字出现的频度,。,哈希函数的构造方法,有,80,个记录，关键字为,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,8 1 3 6 8 5 3 7,8 1 4 1 9 3 5 5,.,.,分析：,只取,8,只取,1,只取,3,、,4,只取,2,、,7,、,5,数字分布近乎随机,所以：取任意两位或两位,与另两位的叠加作哈希地址,哈希函数的构造方法,以关键字的平方值的中间几位作为存储地址。求,“,关键字的平方值,”,的目的是,“,扩大差别,”,，同时平方值的中间各位又能受到整个关键字中各位的影响。,3.,平方取中法,此方法适合于,:,关键字中的每一位都有某些数字重复出现频度很高的现象。,哈希函数的构造方法,4.,折叠法,将关键字分割成若干部分，然后取它们的叠加和为哈希地址。有两种叠加处理的方法：移位叠加和间界叠加。,此方法适合于,:,关键字的数字位数特别多,，而且关键字在每一位上的数字分布大致均匀的情况。,哈希函数的构造方法,例 关键字为：,0442205864,，哈希地址位数为,4,5 8 6 4,4 2 2 0,0 4,1,0 0 8 8,H(key)=0088,移位叠加,5 8 6 4,0 2 2 4,0 4,6 0 9 2,H(key)=6092,间界叠加,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.,总的原则是使产生冲突的可能性尽可能的小。,3.,如果哈希造表过程中产生冲突，应当如何处理这些冲突呢？,处理冲突的方法,冲突,：,由,关键字得到的哈希地址为,j,（,0jn-1,）的位置上已存有记录,处理冲突：,为产生冲突的地址寻找下一个空的哈希地址,1.,开放定址法,2.,再哈希法,3.,链地址法,处理冲突方法,4.,建立一个公共溢出区,处理冲突的方法,1.,开放定址法,为产生冲突的地址,H(key,),求得一个地址序列：,H,0,H,1,H,2,Hs,1 sm-1,其中：,H,0,=,H(key,),H,i,=(,H(key,)+,d,i,)MOD m,i=1,2,s,m,为哈希表表长,处理冲突的方法,1.,线性探测再散列法,2.,二次探测再散列法,3.,随机探测再散列法,增量,d,i,的三种取法,处理冲突的方法,1.,开放定址法,对增量,d,i,的三种取法,-,：,1),线性探测再散列,d,i,=c,i,最简单的情况,c=1,即,d,i,=1,2,3,m-1,处理冲突的方法,例如,:,关键字集合,19,01,23,14,55,68,11,82,36,设定哈希函数,H(key)=key MOD 11(,表长,=11),采用,线性探测再散列,法来构造哈希表。,19,0 1 2 3 4 5 6 7 8 9 10,19,01,01,23,23,23,14,14,55,55,68,68,68,11,82,11,36,11,82,36,1 1 2 1 3 6 2 5 1,处理冲突的方法,1.,开放定址法,对增量,d,i,有三种取法,-,：,2),平方（二次）探测再散列,d,i,=1,2,-1,2,2,2,-2,2,处理冲突的方法,例如,:,关键字集合,19,01,23,14,55,68,11,82,36,19,0 1 2 3 4 5 6 7 8 9 10,19,01,01,23,23,23,14,14,55,55,68,68,68,11,82,11,36,11,82,36,36,设定哈希函数,H(key)=key MOD 11(,表长,=11),采用,二次探测再散列,法来构造哈希表。,1 1 2 1 2 1 4 1 3,处理冲突的方法,1.,开放定址法,对增量,d,i,有三种取法,-,：,3),随机探测再散列,d,i,是一组随机数列 或者,d,i,=iH2(key,)(,又称双散列函数探测,),处理冲突的方法,即：产生的,H,i,均不相同，且所产生的,m-1,个,H,i,值能覆盖哈希表中所有地址。,则要求：,注意：,增量,d,i,应具有,“,完备性,”,随机探测时的,m,和,d,i,没有公因子。,平方探测时的表长,m,必为形如,4j+3,的素数（如,:7,11,19,23,等）；,处理冲突的方法,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,1 1 1 1 2 1 1 2 2,处理冲突的方法,2.,再哈希法,H,i,=,RH,i,(,key,)i=1,2,3,，,k,RH,i,均是不同的哈希函数，在同义词产生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。,缺点：增加了计算时间。,处理冲突的方法,3.,链地址法,所有关键字为同义词的记录存储在同一线性链表中。,定义指针型向量,Chain,ChainHashm,;,凡是哈希地址为,i,的记录都插入到头指针为,ChainHashi,的链表中。,处理冲突的方法,例如,:,关键字集合,19,01,23,14,55,68,11,82,36,采用,链地址,法来构造哈希表。,哈希函数为,H(key)=key MOD 7,11,19,82,68,55,14,01,36,23,19,01,23,14,55,68,11,82,36,0,1,2,3,4,5,6,ASL=(61+22+31)/9=13/9,处理冲突的方法,4.,建立一个公共溢出区,哈希函数的值域,0,m-1,向量,HashTable0.m-1,为基本表，每个分量存放一个记录,向量,OverTable0.v,为溢出表,对于关键字和基本表,HashTable,中关键字为同义词的记录，只要发生冲突，都填入溢出表。,哈希表的查找算法,查找过程和造表过程一致。假设采用,开放定址,处理冲突，则,查找过程,为,:,1.,对于给定值,K,计算哈希地址,i=H(K),2.,若,ri=NULL,则查找不成功,3.,若,ri.key=K,则查找成功,4.,否则,“,求下一地址,H,i,”,，直至,rH,i,=NULL,(,查找不成功,),或,rH,i,.key,=K,(,查找成功,),为止。,哈希表的查找算法,int,hashsize,=997,.;,typedef,struct,ElemType,*,elem,;,int,count;/,当前数据元素个数,in