数据结构-哈希表课件

哈希表什么是哈希表哈希函数的构造方法处理冲突的方法哈希表的查找哈希表的查找分析小结和作业课堂练习1A哈希表什么是哈希表哈希函数的构造方法处理冲突的方法哈希表的查A[0]A[1]A[2]A[3]A[4]A[5]A[6]A[7]A[8]A[9]A[10]例1:有一批考试成绩，统计各分数段的人数。对成绩Grade，执行：A[grade/10]++什么是哈希表2AA[0]A[1]A[2]A[3]A[4]A[5]A[6]A[例2:Ord(Char)=asc(char)–asc(‘a’)+1什么是哈希表01(A)345(E)9(I)……

268(H)4(D)19(S)22(V)018(R)7(G)1905(E)HADHASHAVHEHERHEREHIGHIS3A例2:Ord(Char)=asc(char)–asc(‘将1000个学生的信息存放在数组A[0]—A[999]中例3:为每年招收的1000名新生建立一张查找表，其关键字为学号，其值的范围为xx000~xx999(前两位为年份)。什么是哈希表number(substring(学号,3,3))4A将1000个学生的信息存放在数组A[0]—A[999]中例3建立查找表：给定关键字key计算f(key)数组下标查找表：使用数组存放n个关键字，数组的下标0n-1什么是哈希表查找时：给定关键字key计算f(key)数组下标5A建立查找表：查找表：什么是哈希表查找时：5A建立查找表：给定grade计算f(grade)数组下标例4：统计学生成绩各分数段的人数什么是哈希表查找时：给定grade计算f(grade)数组下标Hash函数：f(grade)=grade/106A建立查找表：例4：统计学生成绩各分数段的人数什么是什么是哈希表{Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Dei}例5：对于如下9个关键字设哈希函数f(key)=

(Ord(第一个字母)-Ord('A')+1)/27A什么是哈希表{Zhao,Qian,Sun,Li,Wu什么是哈希表字母ABCDEFGHIJKLM序号12345678910111213字母NOPQRSTUVWXYZ序号14151617181920212223242526ChenZhaoQianSunLiWuHanYeDei序号012345678910111213问题:若添加关键字Zhou,怎么办？8A什么是哈希表字母ABCDEFGHIJKLM序号1234567什么是哈希表由此可见，1)哈希(Hash)函数是一个映象，即：将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地址集合的大小不超出允许范围即可；2)对不同的关键字可能得到同一哈希地址，即：key1≠key2，而f(key1)=f(key2),因此，很容易产生“冲突”现象；9A什么是哈希表由此可见，1)哈希(Hash)函数是一个映什么是哈希表3)很难找到一个不产生冲突的哈希函数。一般情况下，只能选择恰当的哈希函数，使冲突尽可能少地产生。因此，在构造这种特殊的“查找表”时，除了需要选择一个“好”(尽可能少产生冲突)的哈希函数之外；还需要找到一种“处理冲突”的方法。10A什么是哈希表3)很难找到一个不产生冲突的哈希函数。一般情哈希表的定义根据设定的哈希函数H(key)和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集(区间)上，并以关键字在地址集中的“象”作为相应记录在表中的存储位置，如此构造所得的查找表称之为“哈希表”。这一过程称为哈希造表或者散列，所得的存储位置成为哈希地址或者散列地址。11A哈希表的定义根据设定的哈希函数H(key)和所选中的处理哈希函数的构造方法对数字的关键字可有下列构造方法:若是非数字关键字，则需先对其进行数字化处理。1.直接定址法3.平方取中法5.除留余数法4.折叠法6.随机数法2.数字分析法12A哈希函数的构造方法对数字的关键字可有下列构造方法:若是哈希函数为关键字的线性函数H(key)=key或者H(key)=akey+b1.直接定址法哈希函数的构造方法13A哈希函数为关键字的线性函数1.直接定址法哈希函数的构造方法哈希函数的构造方法2.数字分析法假设关键字集合中的每个关键字都是由s位数字组成(u1,u2,…,us)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。此方法仅适合于：

能预先估计出全体关键字的每一位上各种数字出现的频度。14A哈希函数的构造方法2.数字分析法假设关键字集合中的每个关键哈希函数的构造方法有80个记录，关键字为8位十进制数，哈希地址为2位十进制数8134653281372242813874228130136781322817813389678136853781419355…..…..分析：只取8只取1只取3、4只取2、7、5数字分布近乎随机所以：取任意两位或两位与另两位的叠加作哈希地址15A哈希函数的构造方法有80个记录，关键字为8位十进制数，哈希地哈希函数的构造方法以关键字的平方值的中间几位作为存储地址。求“关键字的平方值”的目的是“扩大差别”，同时平方值的中间各位又能受到整个关键字中各位的影响。3.平方取中法此方法适合于:关键字中的每一位都有某些数字重复出现频度很高的现象。16A哈希函数的构造方法以关键字的平方值的中间几位作为存储地址。求哈希函数的构造方法4.折叠法将关键字分割成若干部分，然后取它们的叠加和为哈希地址。有两种叠加处理的方法：移位叠加和间界叠加。此方法适合于:关键字的数字位数特别多，而且关键字在每一位上的数字分布大致均匀的情况。17A哈希函数的构造方法4.折叠法将关键字分割成若干部分，然后取哈希函数的构造方法例关键字为：0442205864，哈希地址位数为4586442200410088H(key)=0088移位叠加5864022404

6092H(key)=6092间界叠加4.折叠法18A哈希函数的构造方法例关键字为：0442205864，哈希函数的构造方法5.除留余数法设定哈希函数为:

H(key)=keyMODp

其中，p≤m(表长)并且p应为不大于m的素数或是不含20以下的质因子19A哈希函数的构造方法5.除留余数法设定哈希函数为:19A哈希函数的构造方法给定一组关键字为:12,39,18,24,33,21若取p=9,则它们对应的哈希函数值将为:3,3,0,6,6,3为什么要对p加限制？可见，若p中含质因子3,则所有含质因子3的关键字均映射到“3的倍数”的地址上，从而增加了“冲突”的可能。20A哈希函数的构造方法给定一组关键字为:12,39,18,哈希函数的构造方法6.随机数法设定哈希函数为:H(key)=Random(key)其中Random为随机函数此方法通常用于对长度不等的关键字构造哈希函数。21A哈希函数的构造方法6.随机数法设定哈希函数为:此方法通常用哈希函数的构造方法实际构造哈希表时1.采用哪种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)2.总的原则是使产生冲突的可能性尽可能的小。3.如果哈希造表过程中产生冲突，应当如何处理这些冲突呢？22A哈希函数的构造方法实际构造哈希表时22A处理冲突的方法冲突：由关键字得到的哈希地址为j（0≤j≤n-1）的位置上已存有记录处理冲突：为产生冲突的地址寻找下一个空的哈希地址1.开放定址法2.再哈希法3.链地址法处理冲突方法4.建立一个公共溢出区23A处理冲突的方法冲突：由关键字得到的哈希地址为j（0≤j≤n-处理冲突的方法1.开放定址法为产生冲突的地址H(key)求得一个地址序列：H0,H1,H2,…,Hs1≤s≤m-1其中：H0=H(key)Hi=(H(key)+di)MODm

i=1,2,…,s

m为哈希表表长24A处理冲突的方法1.开放定址法为产生冲突的地址H(key)处理冲突的方法1.线性探测再散列法2.二次探测再散列法3.随机探测再散列法增量di的三种取法25A处理冲突的方法1.线性探测再散列法2.二次探测再散列法3处理冲突的方法1.开放定址法对增量di

的三种取法---①：1)线性探测再散列

di=ci

最简单的情况c=1

即

di=1,2,3,……m-126A处理冲突的方法1.开放定址法对增量di的三种取法--处理冲突的方法例如:关键字集合{19,01,23,14,55,68,11,82,36}设定哈希函数H(key)=keyMOD11(表长=11)采用线性探测再散列法来构造哈希表。19012345678910190101232323141455556868681182113611823611213625127A处理冲突的方法例如:关键字集合设定哈希函数H(key)处理冲突的方法1.开放定址法对增量di

有三种取法---②：2)平方（二次）探测再散列

di=12,-12,22,-22,…,28A处理冲突的方法1.开放定址法对增量di有三种取法--处理冲突的方法例如:关键字集合{19,01,23,14,55,68,11,82,36}19012345678910190101232323141455556868681182113611823636设定哈希函数H(key)=keyMOD11(表长=11)采用二次探测再散列法来构造哈希表。11212141329A处理冲突的方法例如:关键字集合190处理冲突的方法1.开放定址法对增量di

有三种取法---③：3)随机探测再散列

di是一组随机数列或者

di=i×H2(key)(又称双散列函数探测)30A处理冲突的方法1.开放定址法对增量di有三种取法--处理冲突的方法即：产生的Hi均不相同，且所产生的m-1个Hi值能覆盖哈希表中所有地址。则要求：注意：增量di

应具有“完备性”※

随机探测时的m

和di没有公因子。※

平方探测时的表长

m必为形如

4j+3

的素数（如:7,11,19,23,…等）；31A处理冲突的方法即：产生的Hi均不相同，且所产生的注意：增处理冲突的方法H2(key)是另设定的一个哈希函数，它的函数值应和m互为素数。若m为素数，则H2(key)可以是1至m-1之间的任意数;若m为2的幂次，则H2(key)应是1至m-1之间的任意奇数。32A处理冲突的方法H2(key)是另设定的一个哈希函数，它的处理冲突的方法例如，当m=11时，可设H2(key)=(3key)MOD10+119012314556811823611112112233A处理冲突的方法例如，当m=11时，190123145568处理冲突的方法2.再哈希法Hi=RHi(key)i=1,2,3,……，kRHi均是不同的哈希函数，在同义词产生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。缺点：增加了计算时间。34A处理冲突的方法2.再哈希法Hi=RHi(key)i=1处理冲突的方法3.链地址法所有关键字为同义词的记录存储在同一线性链表中。定义指针型向量ChainChainHash[m];凡是哈希地址为i的记录都插入到头指针为ChainHash[i]的链表中。35A处理冲突的方法3.链地址法所有关键字为同义词的记录存储在同处理冲突的方法例如:关键字集合{19,01,23,14,55,68,11,82,36}采用链地址法来构造哈希表。哈希函数为H(key)=keyMOD71119826855140136231901231455681182360123456ASL=(6×1+2×2+3×1)/9=13/936A处理冲突的方法例如:关键字集合采用链地址法来构造哈希表。处理冲突的方法4.建立一个公共溢出区哈希函数的值域[0,m-1]向量HashTable[0..m-1]为基本表，每个分量存放一个记录向量OverTable[0..v]为溢出表对于关键字和基本表HashTable中关键字为同义词的记录，只要发生冲突，都填入溢出表。37A处理冲突的方法4.建立一个公共溢出区哈希函数的值域[0,m哈希表的查找算法查找过程和造表过程一致。假设采用开放定址处理冲突，则查找过程为:

1.对于给定值K,计算哈希地址i=H(K)2.若r[i]=NULL则查找不成功3.若

r[i].key=K则查找成功4.否则“求下一地址Hi”，直至r[Hi]=NULL(查找不成功)或r[Hi].key=K(查找成功)为止。38A哈希表的查找算法查找过程和造表过程一致。假设采用开放定址处理哈希表的查找算法inthashsize[]={997,...};typedefstruct{ElemType*elem;

intcount;//当前数据元素个数

intsizeindex;//为当前容量}HashTable;#defineSUCCESS1#defineUNSUCCESS0#defineDUPLICATE-1//---开放定址哈希表的存储结构---//39A哈希表的查找算法inthashsize[]={99哈希表的查找算法StatusSearchHash(HashTableH,KeyTypeK,

int&p,int&c){//在开放定址哈希表H中查找关键码为K的记录}//SearchHashp=Hash(K);//求得哈希地址while(H.elem[p].key!=NULLKEY&&

!EQ(K,H.elem[p].key)）

collision(p,++c);//求得下一探查地址pif(EQ(K,H.elem[p].key))returnSUCCESS;//查找成功，返回待查数据元素位置pelsereturnUNSUCCESS;//查找不成功40A哈希表的查找算法StatusSearchHash(Has哈希表的维护算法StatusInsertHash(HashTable&H,Elemtypee){

}//InsertHashc=0;if(SearchHash(H,e.key,p,c)==SUCCESS)returnDUPLICATE;//表中已有与e有相同关键字的元素elseif(c<hashsize[H.sizeindex]/2){

//冲突次数c未达到上限，（阀值c可调） H.elem[p]=e;++H.count;returnOK;}

else{RecreateHashTable(H); returnUNSUCCESS;}//重建哈希表41A哈希表的维护算法StatusInsertHash(Has哈希表的查找分析从查找过程得知：1、由于冲突的产生，哈希表的查找过程仍然是一个给定值和关键字进行比较的过程。2、哈希表查找的平均查找长度实际上并不等于零。42A哈希表的查找分析从查找过程得知：1、由于冲突的产生，哈希表的哈希表的查找分析1)选用的哈希函数;2)选用的处理冲突的方法;3）哈希表饱和的程度，装载因子

α=n/m值的大小（n—记录数，m—表的长度）决定哈希表查找的ASL的因素：43A哈希表的查找分析1)选用的哈希函数;决定哈希表查找的AS哈希表的查找分析一般情况下，可以认为选用的哈希函数是“均匀”的，则在讨论ASL时，可以不考虑它的因素。因此，哈希表的ASL是处理冲突方法和装载因子的函数。例如：前述例子线性探测处理冲突时，ASL=链地址法处理冲突时，ASL=22/913/944A哈希表的查找分析一般情况下，可以认为选用的哈希函数是“均匀”哈希表的查找分析线性探测再散列可以证明：查找成功时有下列结果：随机探测再散列链地址法45A哈希表的查找分析线性探测再散列可以证明：查找成功时有下列结果哈希表的查找分析从以上结果可见，哈希表的平均查找长度是

的函数，而不是n的函数。这说明，用哈希表构造查找表时，可以选择一个适当的装填因子，使得平均查找长度限定在某个范围内。46A哈希表的查找分析从以上结果可见，哈希表的平均查找长度是哈希表的删除操作从哈希表中删除记录时，要作特殊处理，相应地，需要修改查找的算法。47A哈希表的删除操作从哈希表中删除记录时，要作特殊处理，相应地，小结和作业哈希表

1．哈希原理2．哈希函数的构造方法3．处理冲突的方法4．哈希表的查找及分析作业：9.19，9.20，9.2148A小结和作业哈希表1．哈希原理2．哈希函数的构造方法3．课堂练习设有一组关键字{11，54，36，89，51，47，38，59，63，94，15}，采用哈希函数：H(key)=key%13。采用开放地址法的线性探测再散列方法解决冲突，试在0～15的散列地址空间中对该关键字序列构造哈希表。49A课堂练习设有一组关键字{11，54，36，89，51，47，哈希表什么是哈希表哈希函数的构造方法处理冲突的方法哈希表的查找哈希表的查找分析小结和作业课堂练习50A哈希表什么是哈希表哈希函数的构造方法处理冲突的方法哈希表的查A[0]A[1]A[2]A[3]A[4]A[5]A[6]A[7]A[8]A[9]A[10]例1:有一批考试成绩，统计各分数段的人数。对成绩Grade，执行：A[grade/10]++什么是哈希表51AA[0]A[1]A[2]A[3]A[4]A[5]A[6]A[例2:Ord(Char)=asc(char)–asc(‘a’)+1什么是哈希表01(A)345(E)9(I)……

268(H)4(D)19(S)22(V)018(R)7(G)1905(E)HADHASHAVHEHERHEREHIGHIS52A例2:Ord(Char)=asc(char)–asc(‘将1000个学生的信息存放在数组A[0]—A[999]中例3:为每年招收的1000名新生建立一张查找表，其关键字为学号，其值的范围为xx000~xx999(前两位为年份)。什么是哈希表number(substring(学号,3,3))53A将1000个学生的信息存放在数组A[0]—A[999]中例3建立查找表：给定关键字key计算f(key)数组下标查找表：使用数组存放n个关键字，数组的下标0n-1什么是哈希表查找时：给定关键字key计算f(key)数组下标54A建立查找表：查找表：什么是哈希表查找时：5A建立查找表：给定grade计算f(grade)数组下标例4：统计学生成绩各分数段的人数什么是哈希表查找时：给定grade计算f(grade)数组下标Hash函数：f(grade)=grade/1055A建立查找表：例4：统计学生成绩各分数段的人数什么是什么是哈希表{Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Dei}例5：对于如下9个关键字设哈希函数f(key)=

(Ord(第一个字母)-Ord('A')+1)/256A什么是哈希表{Zhao,Qian,Sun,Li,Wu什么是哈希表字母ABCDEFGHIJKLM序号12345678910111213字母NOPQRSTUVWXYZ序号14151617181920212223242526ChenZhaoQianSunLiWuHanYeDei序号012345678910111213问题:若添加关键字Zhou,怎么办？57A什么是哈希表字母ABCDEFGHIJKLM序号1234567什么是哈希表由此可见，1)哈希(Hash)函数是一个映象，即：将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地址集合的大小不超出允许范围即可；2)对不同的关键字可能得到同一哈希地址，即：key1≠key2，而f(key1)=f(key2),因此，很容易产生“冲突”现象；58A什么是哈希表由此可见，1)哈希(Hash)函数是一个映什么是哈希表3)很难找到一个不产生冲突的哈希函数。一般情况下，只能选择恰当的哈希函数，使冲突尽可能少地产生。因此，在构造这种特殊的“查找表”时，除了需要选择一个“好”(尽可能少产生冲突)的哈希函数之外；还需要找到一种“处理冲突”的方法。59A什么是哈希表3)很难找到一个不产生冲突的哈希函数。一般情哈希表的定义根据设定的哈希函数H(key)和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集(区间)上，并以关键字在地址集中的“象”作为相应记录在表中的存储位置，如此构造所得的查找表称之为“哈希表”。这一过程称为哈希造表或者散列，所得的存储位置成为哈希地址或者散列地址。60A哈希表的定义根据设定的哈希函数H(key)和所选中的处理哈希函数的构造方法对数字的关键字可有下列构造方法:若是非数字关键字，则需先对其进行数字化处理。1.直接定址法3.平方取中法5.除留余数法4.折叠法6.随机数法2.数字分析法61A哈希函数的构造方法对数字的关键字可有下列构造方法:若是哈希函数为关键字的线性函数H(key)=key或者H(key)=akey+b1.直接定址法哈希函数的构造方法62A哈希函数为关键字的线性函数1.直接定址法哈希函数的构造方法哈希函数的构造方法2.数字分析法假设关键字集合中的每个关键字都是由s位数字组成(u1,u2,…,us)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。此方法仅适合于：

能预先估计出全体关键字的每一位上各种数字出现的频度。63A哈希函数的构造方法2.数字分析法假设关键字集合中的每个关键哈希函数的构造方法有80个记录，关键字为8位十进制数，哈希地址为2位十进制数8134653281372242813874228130136781322817813389678136853781419355…..…..分析：只取8只取1只取3、4只取2、7、5数字分布近乎随机所以：取任意两位或两位与另两位的叠加作哈希地址64A哈希函数的构造方法有80个记录，关键字为8位十进制数，哈希地哈希函数的构造方法以关键字的平方值的中间几位作为存储地址。求“关键字的平方值”的目的是“扩大差别”，同时平方值的中间各位又能受到整个关键字中各位的影响。3.平方取中法此方法适合于:关键字中的每一位都有某些数字重复出现频度很高的现象。65A哈希函数的构造方法以关键字的平方值的中间几位作为存储地址。求哈希函数的构造方法4.折叠法将关键字分割成若干部分，然后取它们的叠加和为哈希地址。有两种叠加处理的方法：移位叠加和间界叠加。此方法适合于:关键字的数字位数特别多，而且关键字在每一位上的数字分布大致均匀的情况。66A哈希函数的构造方法4.折叠法将关键字分割成若干部分，然后取哈希函数的构造方法例关键字为：0442205864，哈希地址位数为4586442200410088H(key)=0088移位叠加5864022404

6092H(key)=6092间界叠加4.折叠法67A哈希函数的构造方法例关键字为：0442205864，哈希函数的构造方法5.除留余数法设定哈希函数为:

H(key)=keyMODp

其中，p≤m(表长)并且p应为不大于m的素数或是不含20以下的质因子68A哈希函数的构造方法5.除留余数法设定哈希函数为:19A哈希函数的构造方法给定一组关键字为:12,39,18,24,33,21若取p=9,则它们对应的哈希函数值将为:3,3,0,6,6,3为什么要对p加限制？可见，若p中含质因子3,则所有含质因子3的关键字均映射到“3的倍数”的地址上，从而增加了“冲突”的可能。69A哈希函数的构造方法给定一组关键字为:12,39,18,哈希函数的构造方法6.随机数法设定哈希函数为:H(key)=Random(key)其中Random为随机函数此方法通常用于对长度不等的关键字构造哈希函数。70A哈希函数的构造方法6.随机数法设定哈希函数为:此方法通常用哈希函数的构造方法实际构造哈希表时1.采用哪种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)2.总的原则是使产生冲突的可能性尽可能的小。3.如果哈希造表过程中产生冲突，应当如何处理这些冲突呢？71A哈希函数的构造方法实际构造哈希表时22A处理冲突的方法冲突：由关键字得到的哈希地址为j（0≤j≤n-1）的位置上已存有记录处理冲突：为产生冲突的地址寻找下一个空的哈希地址1.开放定址法2.再哈希法3.链地址法处理冲突方法4.建立一个公共溢出区72A处理冲突的方法冲突：由关键字得到的哈希地址为j（0≤j≤n-处理冲突的方法1.开放定址法为产生冲突的地址H(key)求得一个地址序列：H0,H1,H2,…,Hs1≤s≤m-1其中：H0=H(key)Hi=(H(key)+di)MODm

i=1,2,…,s

m为哈希表表长73A处理冲突的方法1.开放定址法为产生冲突的地址H(key)处理冲突的方法1.线性探测再散列法2.二次探测再散列法3.随机探测再散列法增量di的三种取法74A处理冲突的方法1.线性探测再散列法2.二次探测再散列法3处理冲突的方法1.开放定址法对增量di

的三种取法---①：1)线性探测再散列

di=ci

最简单的情况c=1

即

di=1,2,3,……m-175A处理冲突的方法1.开放定址法对增量di的三种取法--处理冲突的方法例如:关键字集合{19,01,23,14,55,68,11,82,36}设定哈希函数H(key)=keyMOD11(表长=11)采用线性探测再散列法来构造哈希表。19012345678910190101232323141455556868681182113611823611213625176A处理冲突的方法例如:关键字集合设定哈希函数H(key)处理冲突的方法1.开放定址法对增量di

有三种取法---②：2)平方（二次）探测再散列

di=12,-12,22,-22,…,77A处理冲突的方法1.开放定址法对增量di有三种取法--处理冲突的方法例如:关键字集合{19,01,23,14,55,68,11,82,36}19012345678910190101232323141455556868681182113611823636设定哈希函数H(key)=keyMOD11(表长=11)采用二次探测再散列法来构造哈希表。11212141378A处理冲突的方法例如:关键字集合190处理冲突的方法1.开放定址法对增量di

有三种取法---③：3)随机探测再散列

di是一组随机数列或者

di=i×H2(key)(又称双散列函数探测)79A处理冲突的方法1.开放定址法对增量di有三种取法--处理冲突的方法即：产生的Hi均不相同，且所产生的m-1个Hi值能覆盖哈希表中所有地址。则要求：注意：增量di

应具有“完备性”※

随机探测时的m

和di没有公因子。※

平方探测时的表长

m必为形如

4j+3

的素数（如:7,11,19,23,…等）；80A处理冲突的方法即：产生的Hi均不相同，且所产生的注意：增处理冲突的方法H2(key)是另设定的一个哈希函数，它的函数值应和m互为素数。若m为素数，则H2(key)可以是1至m-1之间的任意数;若m为2的幂次，则H2(key)应是1至m-1之间的任意奇数。81A处理冲突的方法H2(key)是另设定的一个哈希函数，它的处理冲突的方法例如，当m=11时，可设H2(key)=(3key)MOD10+119012314556811823611112112282A处理冲突的方法例如，当m=11时，190123145568处理冲突的方法2.再哈希法Hi=RHi(key)i=1,2,3,……，kRHi均是不同的哈希函数，在同义词产生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。缺点：增加了计算时间。83A处理冲突的方法2.再哈希法Hi=RHi(key)i=1处理冲突的方法3.链地址法所有关键字为同义词的记录存储在同一线性链表中。定义指针型向量ChainChainHash[m];凡是哈希地址为i的记录都插入到头指针为ChainHash[i]的链表中。84A处理冲突的方法3.链地址法所有关键字为同义词的记录存储在同处理冲突的方法例如:关键字集合{19,01,23,14,55,68,11,82,36}采用链地址法来构造哈希表。哈希函数为H(key)=keyMOD71119826855140136231901231455681182360123456ASL=(6×1+2×2+3×1)/9=13/985A处理冲突的方法例如:关键字集合采用链地址法来构造哈希表。处理冲突的方法4.建立一个公共溢出区哈希函数的值域[0,m-1]向量HashTable[0..m-1]为基本表，每个分量存放一个记录向量OverTable[0..v]为溢出表对于关键字和基本表HashTable中关键字为同义词的记录，只要发生冲突，都填入溢出表。86A处理冲突的方法4.建立一个公共溢出区哈希函数的值域[0,m哈希表的查找算法查找过程和造表过程一致。假设采用开放定址处理冲突，则查找过程为:

1.对于给定值K,计算哈希地址i=H(K)2.若r[i]=NULL则查找不成功3.若

r[i].key=K则查找成功4.否则“求下一地址Hi”，直至r[Hi]=NULL(查找不成功)或r[Hi].key=K(查找成功)为止。87A哈希表的查找算法查找过程和造表过程一致。假设采用开放定址处理哈希表的查找算法inthashsize[]={997,...};typedefstruct{ElemType*elem;

intcount;//当前数据元素个数

intsizeindex;//为当前容量}HashTable;#defineSUCCESS1#defineUNSUCCESS0#defineDUPLICATE-1//---开放定址哈希表的存储结构---//88A哈希表的查找算法inthashsize[]={99哈希表的查找算法StatusSearchHash(HashTableH,KeyTypeK,