数据结构-哈希表

.,哈希表,什么是哈希表,哈希函数的构造方法,处理冲突的方法,哈希表的查找,哈希表的查找分析,小结和作业,课堂练习,.,A0A1A2A3A4A5A6A7A8A9A10,例1:有一批考试成绩，统计各分数段的人数。,对成绩Grade，执行：Agrade/10+,什么是哈希表,.,例2:Ord(Char)=asc(char)asc(a)+1,什么是哈希表,.,将1000个学生的信息存放在数组A0A999中,例3:为每年招收的1000名新生建立一张查找表，其关键字为学号，其值的范围为xx000xx999(前两位为年份)。,什么是哈希表,number(substring(学号,3,3),.,建立查找表：给定关键字key计算f(key)数组下标,查找表：使用数组存放n个关键字，数组的下标0n-1,什么是哈希表,查找时：给定关键字key计算f(key)数组下标,.,建立查找表：给定grade计算f(grade)数组下标,例4：统计学生成绩各分数段的人数,什么是哈希表,查找时：给定grade计算f(grade)数组下标,Hash函数：f(grade)=grade/10,.,什么是哈希表,Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Dei,例5：对于如下9个关键字,设哈希函数f(key)=(Ord(第一个字母)-Ord(A)+1)/2,.,什么是哈希表,Chen,Zhao,Qian,Sun,Li,Wu,Han,Ye,Dei,序号,问题:若添加关键字Zhou,怎么办？,.,什么是哈希表,由此可见，,1)哈希(Hash)函数是一个映象，即：将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地址集合的大小不超出允许范围即可；,2)对不同的关键字可能得到同一哈希地址，即：key1key2，而f(key1)=f(key2),因此，很容易产生“冲突”现象；,.,什么是哈希表,3)很难找到一个不产生冲突的哈希函数。一般情况下，只能选择恰当的哈希函数，使冲突尽可能少地产生。,因此，在构造这种特殊的“查找表”时，除了需要选择一个“好”(尽可能少产生冲突)的哈希函数之外；还需要找到一种“处理冲突”的方法。,.,哈希表的定义,根据设定的哈希函数H(key)和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集(区间)上，并以关键字在地址集中的“象”作为相应记录在表中的存储位置，如此构造所得的查找表称之为“哈希表”。,这一过程称为哈希造表或者散列，所得的存储位置成为哈希地址或者散列地址。,.,哈希函数的构造方法,对数字的关键字可有下列构造方法:,若是非数字关键字，则需先对其进行数字化处理。,1.直接定址法,3.平方取中法,5.除留余数法,4.折叠法,6.随机数法,2.数字分析法,.,哈希函数为关键字的线性函数H(key)=key或者H(key)=akey+b,1.直接定址法,哈希函数的构造方法,.,哈希函数的构造方法,2.数字分析法,假设关键字集合中的每个关键字都是由s位数字组成(u1,u2,us)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。,此方法仅适合于：能预先估计出全体关键字的每一位上各种数字出现的频度。,.,哈希函数的构造方法,有80个记录，关键字为8位十进制数，哈希地址为2位十进制数,分析：只取8只取1只取3、4只取2、7、5数字分布近乎随机所以：取任意两位或两位与另两位的叠加作哈希地址,.,哈希函数的构造方法,以关键字的平方值的中间几位作为存储地址。求“关键字的平方值”的目的是“扩大差别”，同时平方值的中间各位又能受到整个关键字中各位的影响。,3.平方取中法,此方法适合于:关键字中的每一位都有某些数字重复出现频度很高的现象。,.,哈希函数的构造方法,4.折叠法,将关键字分割成若干部分，然后取它们的叠加和为哈希地址。有两种叠加处理的方法：移位叠加和间界叠加。,此方法适合于:关键字的数字位数特别多，而且关键字在每一位上的数字分布大致均匀的情况。,.,哈希函数的构造方法,例关键字为：0442205864，哈希地址位数为4,5864,4220,04,10088,H(key)=0088,移位叠加,5864,0224,04,6092,H(key)=6092,间界叠加,4.折叠法,.,哈希函数的构造方法,5.除留余数法,设定哈希函数为:H(key)=keyMODp其中，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)求得一个地址序列：H0,H1,H2,Hs1sm-1其中：H0=H(key)Hi=(H(key)+di)MODmi=1,2,sm为哈希表表长,.,处理冲突的方法,1.线性探测再散列法,2.二次探测再散列法,3.随机探测再散列法,增量di的三种取法,.,处理冲突的方法,1.开放定址法,对增量di的三种取法-：,1)线性探测再散列di=ci最简单的情况c=1即di=1,2,3,m-1,.,处理冲突的方法,例如:关键字集合19,01,23,14,55,68,11,82,36,设定哈希函数H(key)=keyMOD11(表长=11),采用线性探测再散列法来构造哈希表。,19,19,01,01,23,23,23,14,14,55,55,68,68,68,11,82,11,36,11,82,36,112136251,.,处理冲突的方法,1.开放定址法,对增量di有三种取法-：,2)平方（二次）探测再散列di=12,-12,22,-22,.,处理冲突的方法,例如:关键字集合19,01,23,14,55,68,11,82,36,19,19,01,01,23,23,23,14,14,55,55,68,68,68,11,82,11,36,11,82,36,36,设定哈希函数H(key)=keyMOD11(表长=11),采用二次探测再散列法来构造哈希表。,112121413,.,处理冲突的方法,1.开放定址法,对增量di有三种取法-：,3)随机探测再散列di是一组随机数列或者di=iH2(key)(又称双散列函数探测),.,处理冲突的方法,即：产生的Hi均不相同，且所产生的m-1个Hi值能覆盖哈希表中所有地址。则要求：,注意：增量di应具有“完备性”,随机探测时的m和di没有公因子。,平方探测时的表长m必为形如4j+3的素数（如:7,11,19,23,等）；,.,处理冲突的方法,H2(key)是另设定的一个哈希函数，它的函数值应和m互为素数。,若m为素数，则H2(key)可以是1至m-1之间的任意数;,若m为2的幂次，则H2(key)应是1至m-1之间的任意奇数。,.,处理冲突的方法,例如，当m=11时，可设H2(key)=(3key)MOD10+1,19,01,23,14,55,68,11,82,36,111121122,.,处理冲突的方法,2.再哈希法,Hi=RHi(key)i=1,2,3,，k,RHi均是不同的哈希函数，在同义词产生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。,缺点：增加了计算时间。,.,处理冲突的方法,3.链地址法,所有关键字为同义词的记录存储在同一线性链表中。,定义指针型向量ChainChainHashm;,凡是哈希地址为i的记录都插入到头指针为ChainHashi的链表中。,.,处理冲突的方法,例如:关键字集合19,01,23,14,55,68,11,82,36,采用链地址法来构造哈希表。,哈希函数为H(key)=keyMOD7,19,01,23,14,55,68,11,82,36,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.否则“求下一地址Hi”，直至rHi=NULL(查找不成功)或rHi.key=K(查找成功)为止。,.,哈希表的查找算法,inthashsize=997,.;typedefstructElemType*elem;intcount;/当前数据元素个数intsizeindex;/为当前容量HashTable;#defineSUCCESS1#defineUNSUCCESS0#defineDUPLICATE-1,/-开放定址哈希表的存储结构-/,.,哈希表的查找算法,StatusSearchHash(HashTableH,KeyTypeK,int/求得哈希地址,while(H.elemp.key!=NULLKEY/求得下一探查地址p,if(EQ(K,H.elemp.key)returnSUCCESS;/查找成功，返回待查数据元素位置p,elsereturnUNSUCCESS;/查找不成功,.,哈希表的维护算法,StatusInsertHash(HashTable,if(SearchHash(H,e.key,p,c)=SUCCESS)returnDUPLICATE;/表中已有与e有相同关键字的元素,elseif(chashsizeH.sizeindex/2)/冲突次数c未达到上限，（阀值c可调）H.elemp=e;+H.count;returnOK;,elseRecreateHashTable(H);returnUNSUCCESS;/重建哈希表,.,哈希表的查找分析,从查找过程得知：,1、由于冲突的产生，哈希表的查找过程仍然是一个给定值和关键字进行比较的过程。,2、哈希表查找的平均查找长度实际上并不等于零。,.,哈希表的查找分析,1)选用的哈希函数;2)选用的处理冲突的方法;3）哈希表饱和的程度，装载因子=n/m值的大小（n记录数，m表的长度）,决定哈希表查找的ASL的因素：,.,哈希表的查找分析,一般情况下，可以认为选用的哈希函数是“均匀”的，则在讨论ASL时，可以不考虑它的因素。,因此，哈希表的ASL是处理冲突方法和装载因子的函数。,例如：前述例子,线性探测处理冲突时，ASL=,链地址法处理冲突时，ASL=,22/9,13/9,.,哈希表的查找分析,线性探测再散列,可以证明：查找成功时有下列结果：,随机探测再散列,链地址法,.,哈希表的查找分析,从以上结果可见，,哈希表的平均查找长度是的函数，而不是n的函数。,这说明，用哈希表构造查找表时，可以选