数据结构Ch哈希表-课件

9.3哈希表哈希表动态查找表动态查找表动态查找表动态查找表1哈希查找哈希查找哈希查找哈希查找也称为也称为也称为也称为散列查找散列查找散列查找散列查找它不同于前面介绍的几种查找方法。它不同于前面介绍的几种查找方法。它不同于前面介绍的几种查找方法。它不同于前面介绍的几种查找方法。上述方法都是把查找建立在上述方法都是把查找建立在上述方法都是把查找建立在上述方法都是把查找建立在比较比较比较比较的基础上，而哈希查找则的基础上，而哈希查找则的基础上，而哈希查找则的基础上，而哈希查找则是通过计算存储地址的方法进行查找的。是通过计算存储地址的方法进行查找的。是通过计算存储地址的方法进行查找的。是通过计算存储地址的方法进行查找的。29.3.1什么是哈希表什么是哈希表纵纵纵纵观观观观以以以以上上上上两两两两节节节节讨讨讨讨论论论论的的的的表表表表示示示示查查查查找找找找表表表表的的的的各各各各种种种种结结结结构构构构，有有有有一一一一个个个个共共共共同同同同点点点点：记记记记录录录录在在在在表表表表中中中中的的的的位位位位置置置置和和和和它它它它的的的的关关关关键键键键字字字字之之之之间间间间不不不不存存存存在在在在一一一一个个个个确确确确定定定定的的的的关关关关系系系系，因因因因此此此此，查查查查找找找找的的的的过过过过程程程程为为为为给给给给定定定定值值值值依依依依次次次次和和和和关关关关键键键键字字字字集集集集合合合合中中中中各各各各个个个个关关关关键键键键字字字字进进进进行行行行比比比比较较较较，查查查查找找找找的的的的效效效效率率率率取取取取决决决决于于于于和和和和给给给给定定定定值值值值进行比较的关键字个数。进行比较的关键字个数。进行比较的关键字个数。进行比较的关键字个数。因因因因此此此此，用用用用这这这这类类类类方方方方法法法法表表表表示示示示的的的的查查查查找找找找表表表表，其其其其平平平平均均均均查查查查找找找找长长长长度度度度ASLASL都都都都不不不不为为为为零零零零，不不不不同同同同表表表表示示示示方方方方法法法法的的的的差差差差别别别别仅仅仅仅在在在在于于于于：和和和和给给给给定定定定值值值值进进进进行行行行比比比比较的关键字的顺序不同。较的关键字的顺序不同。较的关键字的顺序不同。较的关键字的顺序不同。3对对对对于于于于频频频频繁繁繁繁使使使使用用用用的的的的查查查查找找找找表表表表，希希希希望望望望ASL=0ASL=0。即即即即不不不不需需需需要要要要从从从从“比比比比较较较较”的的的的结结结结果果果果来来来来确确确确定定定定查查查查找找找找成成成成功功功功，只只只只有有有有一一一一个个个个办办办办法法法法：预预预预先先先先知知知知道道道道所所所所查查查查关关关关键键键键字字字字在在在在表表表表中中中中的的的的位位位位置置置置，也也也也就就就就是是是是说说说说，记记记记录录录录在在在在表表表表中中中中位位位位置置置置和和和和其其其其关键字之间存在一种确定的关系。关键字之间存在一种确定的关系。关键字之间存在一种确定的关系。关键字之间存在一种确定的关系。4例如：例如：例如：例如：为每年招收的为每年招收的为每年招收的为每年招收的10001000名新生建立一张查找表，其关键字为名新生建立一张查找表，其关键字为名新生建立一张查找表，其关键字为名新生建立一张查找表，其关键字为xx000 xx999(xx000 xx999(前两位为年份前两位为年份前两位为年份前两位为年份)。则可以下标为。则可以下标为。则可以下标为。则可以下标为000999000999的的的的顺序表表示之。由于关键字和记录在表中的序号相同，则顺序表表示之。由于关键字和记录在表中的序号相同，则顺序表表示之。由于关键字和记录在表中的序号相同，则顺序表表示之。由于关键字和记录在表中的序号相同，则不需要经过比较即可确定待查关键字。不需要经过比较即可确定待查关键字。不需要经过比较即可确定待查关键字。不需要经过比较即可确定待查关键字。数据元素数据元素数据元素数据元素存储位置存储位置存储位置存储位置5但是，对于动态查找表而言，但是，对于动态查找表而言，但是，对于动态查找表而言，但是，对于动态查找表而言，1)1)表长不确定；表长不确定；表长不确定；表长不确定；2)2)在在在在设设设设计计计计查查查查找找找找表表表表时时时时，只只只只知知知知道道道道关关关关键键键键字字字字所所所所属属属属范范范范围围围围，而而而而不不不不知知知知道道道道确确确确切的关键字。切的关键字。切的关键字。切的关键字。因因因因此此此此，一一一一般般般般情情情情况况况况，需需需需建建建建立立立立一一一一个个个个函函函函数数数数关关关关系系系系，以以以以f(key)f(key)作作作作为为为为关关关关键键键键字字字字为为为为keykey的的的的记记记记录录录录在在在在表表表表中中中中的的的的位位位位置置置置，通通通通常常常常称称称称这这这这个个个个函函函函数数数数f(key)f(key)为为为为哈希函数哈希函数哈希函数哈希函数。注意：注意：注意：注意：这个函数并不一定是数学函数。这个函数并不一定是数学函数。这个函数并不一定是数学函数。这个函数并不一定是数学函数。6例如：例如：例如：例如：对于如下对于如下对于如下对于如下9 9个关键字个关键字个关键字个关键字Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,DeiZhao,Qian,Sun,Li,Wu,Chen,Han,Ye,DeiA AB BC CD DE EF FGGHH I IJ JKK L LMM1 12 23 34 45 56 67 78 89 91 10 01 11 11 12 21 13 3N NOOP PQQR RS ST TU UV VWW X XY YZ Z1 14 41 15 51 16 61 17 71 18 81 19 92 20 02 21 12 22 22 23 32 24 42 25 52 26 6 1313设设设设f(key)=f(key)=(Ord(Ord(第一个字母第一个字母第一个字母第一个字母)-Ord(A)+1)/2)-Ord(A)+1)/2 8 82 29 96 611111 14 412127哈希表：哈希表：哈希表：哈希表：ChenChenDeiDeiHanHanLiLiQianQianSunSunChenChenYeYeZhaoZhao1 12 23 34 45 56 67 78 89 91010111112121313.8从这个例子可见，从这个例子可见，从这个例子可见，从这个例子可见，哈哈哈哈希希希希函函函函数数数数是是是是一一一一个个个个映映映映象象象象，即即即即：将将将将关关关关键键键键字字字字的的的的集集集集合合合合映映映映射射射射到到到到某某某某个个个个地地地地址址址址集集集集合合合合上上上上，它它它它的的的的设设设设置置置置很很很很灵灵灵灵活活活活，只只只只要要要要这这这这个个个个地地地地址址址址集集集集合合合合的的的的大大大大小不超出允许范围即可小不超出允许范围即可小不超出允许范围即可小不超出允许范围即可;由由由由于于于于哈哈哈哈希希希希函函函函数数数数是是是是一一一一个个个个压压压压缩缩缩缩映映映映象象象象，因因因因此此此此，在在在在一一一一般般般般情情情情况况况况下下下下，很很很很容容容容易易易易产产产产生生生生“冲冲冲冲突突突突”现现现现象象象象，即即即即：key1key1 key2key2，而而而而 f(key1)f(key1)=f(key2)f(key2)。并并并并且且且且，改改改改进进进进哈哈哈哈希希希希函函函函数数数数只只只只能能能能减减减减少少少少冲冲冲冲突突突突，而而而而不不不不能能能能避避避避免冲突。免冲突。免冲突。免冲突。因因因因此此此此，在在在在设设设设计计计计哈哈哈哈希希希希函函函函数数数数时时时时，一一一一方方方方面面面面要要要要考考考考虑虑虑虑选选选选择择择择一一一一个个个个“好好好好”的的的的哈希函数哈希函数哈希函数哈希函数;另一方面要选择一种处理冲突的方法。另一方面要选择一种处理冲突的方法。另一方面要选择一种处理冲突的方法。另一方面要选择一种处理冲突的方法。9所所所所谓谓谓谓“好好好好”的的的的哈哈哈哈希希希希函函函函数数数数，指指指指的的的的是是是是，对对对对于于于于集集集集合合合合中中中中的的的的任任任任意意意意一一一一个个个个关关关关键键键键字字字字，经经经经哈哈哈哈希希希希函函函函数数数数“映映映映象象象象”到到到到地地地地址址址址集集集集合合合合中中中中任任任任何何何何一一一一个个个个地地地地址址址址的的的的概率是相同的。称这类哈希函数为概率是相同的。称这类哈希函数为概率是相同的。称这类哈希函数为概率是相同的。称这类哈希函数为“均匀的均匀的均匀的均匀的”哈希函数哈希函数哈希函数哈希函数。哈哈哈哈希希希希表表表表：根根根根据据据据设设设设定定定定的的的的哈哈哈哈希希希希函函函函数数数数H(key)H(key)和和和和所所所所选选选选中中中中的的的的处处处处理理理理冲冲冲冲突突突突的的的的方方方方法法法法，将将将将一一一一组组组组关关关关键键键键字字字字映映映映象象象象到到到到一一一一个个个个有有有有限限限限的的的的、地地地地址址址址连连连连续续续续的的的的地地地地址址址址集集集集(区区区区间间间间)上上上上，并并并并以以以以关关关关键键键键字字字字在在在在地地地地址址址址集集集集中中中中的的的的“象象象象”作作作作为为为为相相相相应记录在表中的存储位置，这种表被称为应记录在表中的存储位置，这种表被称为应记录在表中的存储位置，这种表被称为应记录在表中的存储位置，这种表被称为哈希表哈希表哈希表哈希表。所得存储位置称为所得存储位置称为哈希地址哈希地址(又称又称散列地址散列地址)。109.3.29.3.2哈希函数的构造方法哈希函数的构造方法哈希函数的构造方法哈希函数的构造方法 对对对对数数数数字字字字的的的的关关关关键键键键字字字字可可可可有有有有下下下下列列列列哈哈哈哈希希希希函函函函数数数数的的的的构构构构造造造造方方方方法法法法，若若若若是是是是非非非非数数数数字关键字，则需先对其进行数字化处理。字关键字，则需先对其进行数字化处理。字关键字，则需先对其进行数字化处理。字关键字，则需先对其进行数字化处理。111.1.直接定址法直接定址法直接定址法直接定址法哈希函数为关键字的线性函数哈希函数为关键字的线性函数哈希函数为关键字的线性函数哈希函数为关键字的线性函数H(key)=keyH(key)=key或者或者或者或者H(key)=aH(key)=a key+bkey+b如如如如：k1,k1,k2k2分分分分别别别别有有有有值值值值 1010、10001000；选选选选1010、10001000作作作作为为为为存存存存放放放放地地地地址。址。址。址。简单、不经济。简单、不经济。简单、不经济。简单、不经济。仅限于：地址集合的大小仅限于：地址集合的大小仅限于：地址集合的大小仅限于：地址集合的大小=关键字集合的大小关键字集合的大小关键字集合的大小关键字集合的大小自身函数自身函数自身函数自身函数122.2.数字分析法数字分析法数字分析法数字分析法假假假假设设设设关关关关键键键键字字字字集集集集合合合合中中中中的的的的每每每每个个个个关关关关键键键键字字字字都都都都是是是是由由由由s s位位位位数数数数字字字字组组组组成成成成(k(k1 1,k k2 2,k kn n)，分分分分析析析析关关关关键键键键字字字字集集集集中中中中的的的的全全全全体体体体，并并并并从从从从中中中中提提提提取取取取分分分分布布布布均均均均匀的若干位或它们的组合作为地址。匀的若干位或它们的组合作为地址。匀的若干位或它们的组合作为地址。匀的若干位或它们的组合作为地址。仅仅仅仅限限限限于于于于：能能能能预预预预先先先先估估估估计计计计出出出出全全全全体体体体关关关关键键键键字字字字的的的的每每每每一一一一位位位位上上上上各各各各种种种种数数数数字字字字出出出出现现现现的的的的频频频频度度度度，它它它它完完完完全全全全依依依依赖赖赖赖于于于于关关关关键键键键字字字字集集集集合合合合。如如如如果果果果换换换换一一一一个个个个关关关关键键键键字集合，选择哪几位要重新决定。字集合，选择哪几位要重新决定。字集合，选择哪几位要重新决定。字集合，选择哪几位要重新决定。133 3平方取中法平方取中法平方取中法平方取中法此此此此方方方方法法法法在在在在词词词词典典典典处处处处理理理理中中中中使使使使用用用用十十十十分分分分广广广广泛泛泛泛。它它它它先先先先计计计计算算算算构构构构成成成成关关关关键键键键码码码码的的的的标标标标识识识识符符符符的的的的内内内内码码码码的的的的平平平平方方方方，然然然然后后后后按按按按照照照照散散散散列列列列表表表表的的的的大大大大小小小小取取取取中中中中间间间间的若干位作为散列地址。的若干位作为散列地址。的若干位作为散列地址。的若干位作为散列地址。若若若若关关关关键键键键字字字字的的的的每每每每一一一一位位位位都都都都有有有有某某某某些些些些数数数数字字字字重重重重复复复复出出出出现现现现频频频频度度度度很很很很高高高高的的的的现现现现象象象象，则则则则先先先先求求求求关关关关键键键键字字字字的的的的平平平平方方方方值值值值，以以以以通通通通过过过过“平平平平方方方方”扩扩扩扩大大大大差差差差别别别别，同同同同时时时时平方值的中间几位受到整个关键字中各位的影响平方值的中间几位受到整个关键字中各位的影响平方值的中间几位受到整个关键字中各位的影响平方值的中间几位受到整个关键字中各位的影响;14设设设设标标标标识识识识符符符符可可可可以以以以用用用用一一一一个个个个计计计计算算算算机机机机字字字字长长长长的的的的内内内内码码码码表表表表示示示示。因因因因为为为为内内内内码码码码平平平平方方方方数数数数的的的的中中中中间间间间几几几几位位位位一一一一般般般般是是是是由由由由标标标标识识识识符符符符所所所所有有有有字字字字符符符符决决决决定定定定，所所所所以以以以对对对对不不不不同同同同的的的的标标标标识识识识符符符符计计计计算算算算出出出出的的的的散散散散列列列列地地地地址址址址大大大大多多多多不不不不相相相相同同同同，即即即即使使使使其其其其中中中中有些字符相同。有些字符相同。有些字符相同。有些字符相同。在在在在平平平平方方方方取取取取中中中中法法法法中中中中，一一一一般般般般取取取取散散散散列列列列地地地地址址址址为为为为 2 2的的的的某某某某次次次次幂幂幂幂。例例例例如如如如，若若若若散散散散列列列列地地地地址址址址总总总总数数数数取取取取为为为为 mm=2 2r r，则则则则对对对对内内内内码码码码的的的的平平平平方方方方数数数数取取取取中中中中间间间间的的的的 r r位位位位。如如如如果果果果 r r=3 3，所所所所取取取取得得得得的的的的散散散散列列列列地地地地址址址址参参参参看看看看下下下下图图图图的的的的最最最最右右右右一列。一列。一列。一列。15标识符标识符标识符标识符内码内码内码内码 内码的平方内码的平方内码的平方内码的平方散列地址散列地址散列地址散列地址A01A010101001001A101342A1013420420420 0042042A901442A90144234234203420342B02B024 4004004DMAX0415013021526DMAX0415013021526443443617100443617100443DMAX10415013034526447DMAX1041501303452644735235221514202151420 352352AMAX011501301354AMAX0115013013542362361710017100236236AMAX10115013034345424AMAX1011501303434542465265221514202151420 652652标识符的八进制内码表示及其平方值标识符的八进制内码表示及其平方值164.4.折叠法折叠法折叠法折叠法此此此此方方方方法法法法把把把把关关关关键键键键字字字字自自自自左左左左到到到到右右右右分分分分成成成成位位位位数数数数相相相相等等等等的的的的几几几几部部部部分分分分，每每每每一一一一部部部部分分分分的的的的位位位位数数数数应应应应与与与与散散散散列列列列表表表表地地地地址址址址位位位位数数数数相相相相同同同同，只只只只有有有有最最最最后后后后一一一一部部部部分分分分的的的的位位位位数数数数可可可可以以以以短短短短一一一一些些些些。把把把把这这这这些些些些部部部部分分分分的的的的数数数数据据据据叠叠叠叠加加加加起起起起来来来来，就就就就可可可可以以以以得到具有该关键字的记录的散列地址。得到具有该关键字的记录的散列地址。得到具有该关键字的记录的散列地址。得到具有该关键字的记录的散列地址。有两种叠加方法：有两种叠加方法：有两种叠加方法：有两种叠加方法：移位法移位法移位法移位法把各部分的最后一位对齐相加；把各部分的最后一位对齐相加；把各部分的最后一位对齐相加；把各部分的最后一位对齐相加；分分分分界界界界法法法法各各各各部部部部分分分分不不不不折折折折断断断断，沿沿沿沿各各各各部部部部分分分分的的的的分分分分界界界界来来来来回回回回折折折折叠叠叠叠，然然然然后后后后对齐相加，将相加的结果当做散列地址。对齐相加，将相加的结果当做散列地址。对齐相加，将相加的结果当做散列地址。对齐相加，将相加的结果当做散列地址。17示例：设给定的关键码为示例：设给定的关键码为示例：设给定的关键码为示例：设给定的关键码为key=23938587841key=23938587841，若存储空，若存储空，若存储空，若存储空间限定间限定间限定间限定33位位位位,则划分结果为每段则划分结果为每段则划分结果为每段则划分结果为每段33位位位位.上述关键码可划分上述关键码可划分上述关键码可划分上述关键码可划分为为为为4 4段：段：段：段：2392393853858788784141把超出地址位数的最高位删去把超出地址位数的最高位删去把超出地址位数的最高位删去把超出地址位数的最高位删去,仅保留最低的仅保留最低的仅保留最低的仅保留最低的3 3位，做为可位，做为可位，做为可位，做为可用的散列地址。用的散列地址。用的散列地址。用的散列地址。185.5.除留余数法除留余数法除留余数法除留余数法H(key)=keyMODppm(H(key)=keyMODppm(表长表长表长表长)最简单最常用的构造哈希函数的方法：最简单最常用的构造哈希函数的方法：最简单最常用的构造哈希函数的方法：最简单最常用的构造哈希函数的方法：关键问题是：如何选取关键问题是：如何选取关键问题是：如何选取关键问题是：如何选取p?p?pp应为不大于应为不大于应为不大于应为不大于mm的质数或是不含的质数或是不含的质数或是不含的质数或是不含2020以下的质因数的合数以下的质因数的合数以下的质因数的合数以下的质因数的合数不仅可以对关键字直接取模，也可在折叠、平方取中等运不仅可以对关键字直接取模，也可在折叠、平方取中等运不仅可以对关键字直接取模，也可在折叠、平方取中等运不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。算之后取模。算之后取模。算之后取模。19质数质数质数质数:在所有比在所有比在所有比在所有比1 1大的整数中，除了大的整数中，除了大的整数中，除了大的整数中，除了1 1和它本身以外，不再有别的和它本身以外，不再有别的和它本身以外，不再有别的和它本身以外，不再有别的约数，这种整数叫做质数，质数又叫做素数。约数，这种整数叫做质数，质数又叫做素数。约数，这种整数叫做质数，质数又叫做素数。约数，这种整数叫做质数，质数又叫做素数。合数合数合数合数:合数是除了合数是除了合数是除了合数是除了1 1和它本身还能被其他的正整数整除的正整数。和它本身还能被其他的正整数整除的正整数。和它本身还能被其他的正整数整除的正整数。和它本身还能被其他的正整数整除的正整数。除除除除2 2之外的偶数都是合数。之外的偶数都是合数。之外的偶数都是合数。之外的偶数都是合数。20例例例例：keykey=12,12,39,39,18,18,24,24,33,33,2121时时时时，若若若若取取取取 p=9,p=9,则则则则使使使使所所所所有有有有含含含含质质质质因因因因子子子子3 3的的的的关关关关键键键键字字字字均均均均映映映映射射射射到到到到地地地地址址址址0,0,3,3,6 6上上上上，从从从从而而而而增增增增加加加加了了了了“冲突冲突冲突冲突”的可能性的可能性的可能性的可能性21例：有一个关键字例：有一个关键字例：有一个关键字例：有一个关键字key=962148key=962148，散列表大小，散列表大小，散列表大小，散列表大小m=25m=25，取，取，取，取质数质数质数质数p=23p=23。散列函数。散列函数。散列函数。散列函数H(key)=key%pH(key)=key%p。则散列地址为。则散列地址为。则散列地址为。则散列地址为H(962148)=962148%23=12H(962148)=962148%23=12。需要注意的是，需要注意的是，需要注意的是，需要注意的是，使用上面的散列函数计算出来的地址范围是使用上面的散列函数计算出来的地址范围是使用上面的散列函数计算出来的地址范围是使用上面的散列函数计算出来的地址范围是0 0到到到到2222，因此，因此，因此，因此，从从从从2323到到到到2424这几个散列地址实际上在一开始是不可能用散列这几个散列地址实际上在一开始是不可能用散列这几个散列地址实际上在一开始是不可能用散列这几个散列地址实际上在一开始是不可能用散列函数计算出来的，只可能在处理溢出时达到这些地址。函数计算出来的，只可能在处理溢出时达到这些地址。函数计算出来的，只可能在处理溢出时达到这些地址。函数计算出来的，只可能在处理溢出时达到这些地址。1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1 10 01 11 11 12 21 13 31 14 41 15 51 16 61 17 71 18 81 19 92 20 02 21 12 22 22 23 32 24 42 25 522例例假假设设哈哈希希表表长长度度m=13,采采用用除除留留余余数数法法哈哈希希函函数数建建立立如如下下关键字集合的哈希表：关键字集合的哈希表：16,74,60,43,54,90,46,31,29,88,77。解解：n=11,m=13,除除留留余余数数法法的的哈哈希希函函数数为为f(k)=kmodp,p应为小于等于应为小于等于m的素数的素数,假设假设p取值取值13。则有：。则有：f(16)=3,f(74)=9,f(60)=8,f(43)=4,f(54)=2,f(90)=12,f(46)=7,f(31)=5,f(29)=3,f(88)=10,f(77)=12。注意：存在冲突。注意：存在冲突。236.6.随机数法随机数法随机数法随机数法H(key)=Random(key)H(key)=Random(key)适用于关键字长度不等适用于关键字长度不等适用于关键字长度不等适用于关键字长度不等 实实实实际际际际造造造造表表表表时时时时，采采采采用用用用何何何何种种种种构构构构造造造造哈哈哈哈希希希希函函函函数数数数的的的的方方方方法法法法取取取取决决决决于于于于建建建建表表表表的的的的关关关关键键键键字字字字集集集集合合合合的的的的情情情情况况况况(包包包包括括括括关关关关键键键键字字字字的的的的范范范范围围围围和和和和形形形形态态态态)，总总总总的的的的原原原原则是使产生冲突的可能性降到尽可能地小。则是使产生冲突的可能性降到尽可能地小。则是使产生冲突的可能性降到尽可能地小。则是使产生冲突的可能性降到尽可能地小。24实际造表时，考虑的因素：实际造表时，考虑的因素：实际造表时，考虑的因素：实际造表时，考虑的因素：计算哈希函数所需时间；计算哈希函数所需时间；计算哈希函数所需时间；计算哈希函数所需时间；关键字的长度；关键字的长度；关键字的长度；关键字的长度；哈希表的大小；哈希表的大小；哈希表的大小；哈希表的大小；关键字的分布情况；关键字的分布情况；关键字的分布情况；关键字的分布情况；记录的查找频率记录的查找频率记录的查找频率记录的查找频率259.3.3处理冲突的方法处理冲突的方法假假假假设设设设哈哈哈哈希希希希表表表表的的的的地地地地址址址址集集集集为为为为0(n-1)0(n-1)，冲冲冲冲突突突突是是是是指指指指由由由由关关关关键键键键字字字字得得得得到到到到的的的的哈哈哈哈希希希希地地地地址址址址为为为为j(0j(0 j jn-1n-1)的的的的位位位位置置置置上上上上已已已已存存存存在在在在记记记记录录录录，则则则则处处处处理理理理冲冲冲冲突突突突就是为该关键字的记录找到另一个就是为该关键字的记录找到另一个就是为该关键字的记录找到另一个就是为该关键字的记录找到另一个“空空空空”的哈希地址。的哈希地址。的哈希地址。的哈希地址。处理冲突的实际含义是：处理冲突的实际含义是：处理冲突的实际含义是：处理冲突的实际含义是：为产生冲突的地址寻找下一个哈希地址。为产生冲突的地址寻找下一个哈希地址。为产生冲突的地址寻找下一个哈希地址。为产生冲突的地址寻找下一个哈希地址。26在在在在处处处处理理理理冲冲冲冲突突突突的的的的过过过过程程程程中中中中可可可可能能能能得得得得到到到到一一一一个个个个地地地地址址址址序序序序列列列列HHi i(i=1(i=1，2 2，k k，h hi i00，n-1)n-1)。即即即即在在在在处处处处理理理理哈哈哈哈希希希希地地地地址址址址的的的的冲冲冲冲突突突突时时时时，若若若若得得得得到到到到的的的的另另另另外外外外一一一一个个个个哈哈哈哈希希希希地地地地址址址址HHi i任任任任然然然然发发发发生生生生冲冲冲冲突突突突，则则则则再再再再求求求求下下下下一一一一个个个个地地地地址址址址HH2 2，若若若若HH2 2任任任任然然然然冲冲冲冲突突突突，再再再再求求求求得得得得HH3 3。依依依依次次次次类类类类推推推推，直直直直至至至至HHk k不发生冲突为止，则不发生冲突为止，则不发生冲突为止，则不发生冲突为止，则HHk k为记录在表中的地址。为记录在表中的地址。为记录在表中的地址。为记录在表中的地址。27解决冲突的方法又称为解决冲突的方法又称为解决冲突的方法又称为解决冲突的方法又称为溢出处理技术溢出处理技术溢出处理技术溢出处理技术。因为任一种散列函。因为任一种散列函。因为任一种散列函。因为任一种散列函数也不能避免产生冲突，因此选择好的解决冲突溢出的数也不能避免产生冲突，因此选择好的解决冲突溢出的数也不能避免产生冲突，因此选择好的解决冲突溢出的数也不能避免产生冲突，因此选择好的解决冲突溢出的方法十分重要。方法十分重要。方法十分重要。方法十分重要。281.1.开放定址法开放定址法开放定址法开放定址法为产生冲突的地址为产生冲突的地址为产生冲突的地址为产生冲突的地址H(key)H(key)求得一个地址序列：求得一个地址序列：求得一个地址序列：求得一个地址序列：HH0 0,H,H1 1,H,H2 2,H,Hs s1sm-11sm-1其中：其中：其中：其中：HH0 0=H(key)=H(key)HHi i=(H(key)+d=(H(key)+di i)MODmi=1,2,s)MODmi=1,2,sn n增量增量增量增量 d di i 有三种取法：有三种取法：有三种取法：有三种取法：(1)(1)线性探测再散列：线性探测再散列：线性探测再散列：线性探测再散列：d di i=c=c i i。最简单的情况最简单的情况最简单的情况最简单的情况 c=1c=1(2)(2)平方探测再散列：平方探测再散列：平方探测再散列：平方探测再散列：d di i=1=12 2,-1,-12 2,2,22 2,-2,-22 2,(3)(3)随机探测再散列：随机探测再散列：随机探测再散列：随机探测再散列：d di i 是一组伪随机数列是一组伪随机数列是一组伪随机数列是一组伪随机数列29n n线线线线性性性性探探探探测测测测容容容容易易易易产产产产生生生生二二二二次次次次聚聚聚聚集集集集，一一一一次次次次聚聚聚聚集集集集的的的的产产产产生生生生主主主主要要要要取取取取决决决决于于于于哈哈哈哈希希希希函函函函数数数数，在在在在哈哈哈哈希希希希函函函函数数数数均均均均匀匀匀匀的的的的前前前前提提提提下下下下，可可可可以以以以认认认认为为为为没没没没有有有有一次聚集。一次聚集。一次聚集。一次聚集。30n n线线线线性性性性探探探探测测测测:假假假假定定定定采采采采用用用用的的的的HH函函函函数数数数为为为为：H(key)=H(key)=keyMOD11keyMOD11，关键字序列为：关键字序列为：关键字序列为：关键字序列为：1717、6060、2929、383831n n当散列当散列当散列当散列 3838时发生冲突，同时发生冲突，同时发生冲突，同时发生冲突，同 6060争夺第争夺第争夺第争夺第 5 5个单元个单元个单元个单元n n解决办法解决办法解决办法解决办法：探测下一个空单元，步长：探测下一个空单元，步长：探测下一个空单元，步长：探测下一个空单元，步长：1 1H(key)=(key+dH(key)=(key+di i)MOD11)MOD11，其中：其中：其中：其中：d di i 为为为为1 1、210210注意：可取其它步长，如注意：可取其它步长，如注意：可取其它步长，如注意：可取其它步长，如 3 3n n冲突：冲突：冲突：冲突：初级冲突：不同关键字值的结点得到同一个散列地址。初级冲突：不同关键字值的结点得到同一个散列地址。初级冲突：不同关键字值的结点得到同一个散列地址。初级冲突：不同关键字值的结点得到同一个散列地址。二次聚集：同不同散列地址的结点争夺同一个单元。二次聚集：同不同散列地址的结点争夺同一个单元。二次聚集：同不同散列地址的结点争夺同一个单元。二次聚集：同不同散列地址的结点争夺同一个单元。结果：冲突加剧，最坏时可能达到结果：冲突加剧，最坏时可能达到结果：冲突加剧，最坏时可能达到结果：冲突加剧，最坏时可能达到 OO（n n）级代价。级代价。级代价。级代价。32n n解决办法：解决办法：解决办法：解决办法：改变步长：选和改变步长：选和改变步长：选和改变步长：选和 mm互质的数作为步长，如互质的数作为步长，如互质的数作为步长，如互质的数作为步长，如3 3、5 5、77 如选步长为如选步长为如选步长为如选步长为5 5，用，用，用，用 H(key)=(key+5)MOD11H(key)=(key+5)MOD11H(key)=(key+52)MOD11H(key)=(key+52)MOD11H(key)=(key+53)MOD11H(key)=(key+53)MOD11等进行下一个空的单元，直到找到为止。等进行下一个空的单元，直到找到为止。等进行下一个空的单元，直到找到为止。等进行下一个空的单元，直到找到为止。随随随随机机机机地地地地改改改改变变变变步步步步长长长长，如如如如取取取取步步步步长长长长序序序序列列列列：2 2，7 7，4 4，3 3，6 6，1 1，5 5，如用如用如用如用 H(key)=(key+2)MOD11H(key)=(key+2)MOD11H(key)=(key+7)MOD11H(key)=(key+7)MOD11H(key)=(key+4)MOD11H(key)=(key+4)MOD11等进行探测下一个空的单元，直到找到为止。等进行探测下一个空的单元，直到找到为止。等进行探测下一个空的单元，直到找到为止。等进行探测下一个空的单元，直到找到为止。33例例1假设哈希表长度假设哈希表长度m=13,采用除留余数法哈希函数建立如下采用除留余数法哈希函数建立如下关键字集合的哈希表：关键字集合的哈希表：16,74,60,43,54,90,46,31,29,88,77。34对构造的哈希表采用线性探查法解决冲突。对构造的哈希表采用线性探查法解决冲突。解：解：h(16)=3,h(74)=9,h(60)=8,h(43)=4,h(54)=2,h(90)=12,h(46)=7,h(31)=5,h(29)=3 冲突冲突d0=3,d1=(3+1)mod13=4仍冲突仍冲突d2=(4+1)mod13=5仍冲突仍冲突d3=(5+1)mod13=6h(88)=10h(77)=12冲突冲突d0=12,d1=(12+1)mod13=035下标下标下标下标0 01 12 23 34 45 56 67 78 89 910101111 1212k k77775454161643433131292946466060 747488889090探查次数探查次数探查次数探查次数2 21 11 11 11 14 41 11 11 11 11 1哈希表哈希表ha0.12 建立的哈希表建立的哈希表ha0.12如下表所示。如下表所示。362.2.再哈希法再哈希法再哈希法再哈希法n n出出出出现现现现冲冲冲冲突突突突时时时时，采采采采用用用用多多多多个个个个哈哈哈哈希希希希函函函函数数数数计计计计算算算算散散散散列列列列地地地地址址址址，直直直直到到到到找找找找到到到到空空空空单单单单元元元元为为为为止止止止。或或或或者者者者用用用用另另另另一一一一个个个个哈哈哈哈希希希希函函函函数数数数作作作作为为为为步步步步长长长长进进进进行行行行探探探探测，找到下一个空单元。测，找到下一个空单元。测，找到下一个空单元。测，找到下一个空单元。如：如：如：如：H1(key)=keyMOD11H1(key)=keyMOD11 H2(key)=(key+RH(x)MOD11H2(key)=(key+RH(x)MOD11n n例例例例2 2：给出一组表项关键字给出一组表项关键字给出一组表项关键字给出一组表项关键字22,41,53,46,30,13,01,6722,41,53,46,30,13,01,67。散列函数为：散列函数为：散列函数为：散列函数为：H(x)H(x)(3x)%11(3x)%11。散列表为散列表为散列表为散列表为 HT0.10HT0.10，mm=11=11。因此，再散列函数为因此，再散列函数为因此，再散列函数为因此，再散列函数为 RH(x)=(7x)%10+1RH(x)=(7x)%10+1。HHi i=(H=(Hi-1i-1+(7x)%10+1)%11,i=1,2,+(7x)%10+1)%11,i=1,2,37HH0 0(22)=0H(22)=0H0 0(41)=2H(41)=2H0 0(53)=5H(53)=5H0 0(46)=6(46)=6HH0 0(30)=2(30)=2冲突冲突冲突冲突HH1 1=(2+1)=3=(2+1)=3HH0 0(13)=6(13)=6冲突冲突冲突冲突HH1 1=(6+2)=8=(6+2)=8HH0 0(01)=3(01)=3冲突冲突冲突冲突HH1 1=(3+8)=0H=(3+8)=0H2 2=(0+8)=8=(0+8)=8HH3 3=(8+8)=5H=(8+8)=5H4 4=(5+8)=2H=(5+8)=2H5 5=(2+8)=10=(2+8)=10HH0 0(67)=3(67)=3冲突冲突冲突冲突HH1 1=(3+10)=2H=(3+10)=2H2 2=(2+10)=1=(2+10)=1383.3.链地址法链地址法链地址法链地址法将将将将所所所所有有有有哈哈哈哈希希希希地地地地址址址址相相相相同同同同的的的的记记记记录录录录都都都都链链链链接接接接在在在在同同同同一一一一链链链链表表表表中中中中。链链链链地地地地址址址址肯定不会产生二次聚集。肯定不会产生二次聚集。肯定不会产生二次聚集。肯定不会产生二次聚集。39例例.对例对例1构造的哈希表采用拉链法解决冲突。构造的哈希表采用拉链法解决冲突。解：采用拉链法解决冲突建立的链表如下图所示。解：采用拉链法解决冲突建立的链表如下图所示。404.4.公共溢出区法：公共溢出区法：公共溢出区法：公共溢出区法：将发生冲突的结点都存放在一个公共溢出区内。将发生冲突的结点都存放在一个公共溢出区内。将发生冲突的结点都存放在一个公共溢出区内。将发生冲突的结点都存放在一个公共溢出区内。41四、哈希表的查找四、哈希表的查找四、哈希表的查找四、哈希表的查找查查查查找找找找过过过过程程程程和和和和造造造造表表表表过过过过程程程程一一一一致致致致。假假假假设设设设采采采采用用用用开开开开放放放放定定定定址址址址处处处处理理理理冲冲冲冲突突突突，则查找过程为则查找过程为则查找过程为则查找过程为:对于给定值对于给定值对于给定值对于给定值K,K,计算哈希地址计算哈希地址计算哈希地址计算哈希地址i=H(K)i=H(K)若若若若ri=NULLri=NULL则查找不成功则查找不成功则查找不成功则查找不成功若若若若ri.key=Kri.key=K则查找成功则查找成功则查找成功则查找成功否则否则否则否则 求下一地址求下一地址求下一地址求下一地址HiHi，直至，直至，直至，直至rHi=NULL(rHi=NULL(查找不成功查找不成功查找不成功查找不成功)或或或或rHi.key=K(rHi.key=K(查找成功查找成功查找成功查找成功)为止。为止。为止。为止。42n n 决定哈希表查找的决定哈希表查找的决定哈希表查找的决定哈希表查找的ASLASL的因素：的因素：的因素：的因素：(1)(1)选用的哈希函数选用的哈希函数选用的哈希函数选用的哈希函数;(2)(2)选用的处理冲突的方法选用的处理冲突的方法选用的处理冲突的方法选用的处理冲突的方法;(3)(3)哈希表饱和的程度，装载因子哈希表饱和的程度，装载因子哈希表饱和的程度，装载因子哈希表饱和的程度，装载因子值的大小值的大小值的大小值的大小装填因子装填因子装填因子装填因子=表中填入的记录数表中填入的记录数表中填入的记录数表中填入的记录数哈希表的长度哈希表的长度哈希表的长度哈希表的长度43