静态查找表动态查找表哈希表课件

n静态查找表静态查找表n动态查找表动态查找表n哈希表哈希表(Hash)(Hash)静态查找表第九章 查找1问题引入问题引入 前面的查找方法是基于前面的查找方法是基于前面的查找方法是基于前面的查找方法是基于比较比较比较比较的的的的 数组存储可以实现用下标立即取得数组存储可以实现用下标立即取得数组存储可以实现用下标立即取得数组存储可以实现用下标立即取得目标数据目标数据目标数据目标数据现实问题中，经常遇到按给定的值进行快速查找（查询）现实问题中，经常遇到按给定的值进行快速查找（查询）现实问题中，经常遇到按给定的值进行快速查找（查询）现实问题中，经常遇到按给定的值进行快速查找（查询）的事例。的事例。的事例。的事例。例如，使用文件名查找活动文件，程序语言的关键例如，使用文件名查找活动文件，程序语言的关键例如，使用文件名查找活动文件，程序语言的关键例如，使用文件名查找活动文件，程序语言的关键字查找。字查找。字查找。字查找。按内容查找，不用比较，立即取得所查找记录。按内容查找，不用比较，立即取得所查找记录。按内容查找，不用比较，立即取得所查找记录。按内容查找，不用比较，立即取得所查找记录。需要考虑需要考虑需要考虑需要考虑 记录存放位置和用以标识它的关键码记录存放位置和用以标识它的关键码记录存放位置和用以标识它的关键码记录存放位置和用以标识它的关键码 之间的对之间的对之间的对之间的对应关系，从而选择适当的数据结构，很方便地根据记录的关应关系，从而选择适当的数据结构，很方便地根据记录的关应关系，从而选择适当的数据结构，很方便地根据记录的关应关系，从而选择适当的数据结构，很方便地根据记录的关键码检索到对应记录的信息。键码检索到对应记录的信息。键码检索到对应记录的信息。键码检索到对应记录的信息。问题引入 前面的查找方法是基于比较的29.3.1 9.3.1 哈希表(Hash)nHashHash表又称散列表。表又称散列表。nHashHash函数函数 为记录存放位置和数据项为记录存放位置和数据项(关键码关键码)凑凑一个对应关系。一个对应关系。即：记录的存储位置即：记录的存储位置loc=h(key)loc=h(key)n实现立即查找实现立即查找9.3.1 哈希表(Hash)Hash表又称散列表。3哈希哈希(Hash)(Hash)表表如：如：hash函数函数h(key)=keymod10,记录集合为记录集合为No.NameClass5Zhangc112Liuc24Wangc110Lic311则则Hash表为表为10Lic312Liuc24Wangc15Zhangc301234567lockey哈希(Hash)表如：hash函数h(key)=key 4C+的保留字的保留字C+的保留字59.3.2 9.3.2 哈希函数的构造方法哈希函数的构造方法n直接定址法直接定址法 n数字分析法数字分析法n平方取中法平方取中法n折叠法折叠法n除留余数法除留余数法 n随机数法随机数法 9.3.2 哈希函数的构造方法直接定址法 6构造哈希函数时的几点要求：构造哈希函数时的几点要求：构造哈希函数时的几点要求：构造哈希函数时的几点要求：n n 哈希函数的定义域必须包括需要存储的全部关哈希函数的定义域必须包括需要存储的全部关哈希函数的定义域必须包括需要存储的全部关哈希函数的定义域必须包括需要存储的全部关 键码，如果哈希表允许有键码，如果哈希表允许有键码，如果哈希表允许有键码，如果哈希表允许有 m m 个地址时个地址时个地址时个地址时,其值域其值域其值域其值域 必须在必须在必须在必须在00到到到到 mm-1 1之间。之间。之间。之间。n n 哈希函数计算出来的地址应能均匀分布在整个哈希函数计算出来的地址应能均匀分布在整个哈希函数计算出来的地址应能均匀分布在整个哈希函数计算出来的地址应能均匀分布在整个 地址空间中：若地址空间中：若地址空间中：若地址空间中：若 key key 是从关键码集合中随机抽是从关键码集合中随机抽是从关键码集合中随机抽是从关键码集合中随机抽 取的一个关键码，哈希函数应能以同等概率取取的一个关键码，哈希函数应能以同等概率取取的一个关键码，哈希函数应能以同等概率取取的一个关键码，哈希函数应能以同等概率取00到到到到 mm-1 1中的每一个值。中的每一个值。中的每一个值。中的每一个值。n n 哈希函数应是简单的，能在较短的时间内计算哈希函数应是简单的，能在较短的时间内计算哈希函数应是简单的，能在较短的时间内计算哈希函数应是简单的，能在较短的时间内计算 出结果。出结果。出结果。出结果。哈希函数哈希函数构造哈希函数时的几点要求：哈希函数7例如：有一个从例如：有一个从1到到100岁的人口数字统计表，其中，年龄作为关键岁的人口数字统计表，其中，年龄作为关键字，哈希函数取关键字自身。字，哈希函数取关键字自身。地址地址0102.252627.100年龄年龄12.252627.人数人数30002000.1050.、直接定址法、直接定址法例如：有一个从1到100岁的人口数字统计表，其中，年龄作为关8、数字分析法、数字分析法有学生的生日数据如下：有学生的生日数据如下：年年.月月.日日75.10.0375.11.2376.03.0276.07.1275.04.2176.02.15.经分析经分析,第一位，第二位，第三位重复的可能性第一位，第二位，第三位重复的可能性大，取这三位造成冲突的机会增加，所以尽量不大，取这三位造成冲突的机会增加，所以尽量不取前三位，取后三位比较好。取前三位，取后三位比较好。、数字分析法有学生的生日数据如下：93平方取中法平方取中法取关键字平方后的中间几位为哈希函数地址。这是一种比较常用的哈希函数构造方法，但在选定哈希函数时不一定知道关键字的全部信息，取其中哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，因此，可以使用随机分布的关键字得到哈希函数地址。如图中，随机给出一些关键字，并取平方后的第2到4位为函数地址。3平方取中法如图中，随机给出一些关键字，并取平方后的第2到10将关键字分割成位数相同的几部分（最后一部分的位数可以不同）将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址，这方法称，然后取这几部分的叠加和（舍去进位）作为哈希地址，这方法称为为折叠法折叠法折叠法折叠法。例如：每一种西文图书都有一个国际标准图书编号，它是一个例如：每一种西文图书都有一个国际标准图书编号，它是一个10位位的十进制数字，若要以它作关键字建立一个哈希表，当馆藏书种类的十进制数字，若要以它作关键字建立一个哈希表，当馆藏书种类不到不到10,000时，可采用此法构造一个四位数的哈希函数。如果一本时，可采用此法构造一个四位数的哈希函数。如果一本书的编号为书的编号为0-442-20586-4,则：则：5864586442200224+)04+)04-100886092H(key)=0088H(key)=6092(a)移位叠加(b)间界叠加 将关键字分割成位数相同的几部分（最后一部分的位数可115.5.除留余数法除留余数法设计哈希表中允许的地址数设计哈希表中允许的地址数,取一个接近于所需大取一个接近于所需大小小 m m 的质数的质数 p p,利用以下公式把关键码转换成哈希利用以下公式把关键码转换成哈希地址。哈希函数为：地址。哈希函数为：hash hash(keykey)=)=keykey%p p其中其中,“%”,“%”是整数除法取余的运算。是整数除法取余的运算。例：有一个关键码例：有一个关键码 keykey=962148=962148，取质数，取质数 p p=23=23。哈希函数哈希函数 hash hash(key key)=)=key key%p p。则哈希地址为。则哈希地址为hashhash(962148)=962148%23=12(962148)=962148%23=12。5.除留余数法12、随机数法、随机数法选择一个随机函数，取关键字的随机函数值为它的哈希地选择一个随机函数，取关键字的随机函数值为它的哈希地址，即址，即H(key)=random(key),其中其中random为随机函数。通常用于关键字长度不等时采用为随机函数。通常用于关键字长度不等时采用此法。此法。、随机数法选择一个随机函数，取关键字的随机函数值为它的哈13哈希哈希(Hash)(Hash)表表n使使用用哈哈希希方方法法进进行行搜搜索索不不必必进进行行多多次次关关键键码码的的比比较较，搜搜索索速度比较快。速度比较快。n哈哈希希函函数数是是一一个个压压缩缩映映象象函函数数。关关键键码码取取值值范范围围比比哈哈希希表表地地址址集集合合大大得得多多。因因此此很很可可能能经经过过哈哈希希函函数数的的计计算算，把把不不同同的的关关键键码码映映射射到到同同一一个个哈哈希希地地址址上上，这这就就产产生生了了冲冲突突 (Collision)(Collision)。n例：一个班的同学有人在同一天过生日的机会是多大？例：一个班的同学有人在同一天过生日的机会是多大？哈希(Hash)表使用哈希方法进行搜索不必进行多次关键码的比14 既然冲突很难避免。所以对于哈希方法，既然冲突很难避免。所以对于哈希方法，需要讨论以下两个重要问题：需要讨论以下两个重要问题：u 对于给定的一个关键码集合，选择一个计对于给定的一个关键码集合，选择一个计算简单且地址分布比较均匀的算简单且地址分布比较均匀的哈希函数哈希函数，避，避免或尽量减少冲突；免或尽量减少冲突；u 拟订解决冲突的方案。拟订解决冲突的方案。两个努力方向两个努力方向 既然冲突很难避免。所以对于哈希方法，需要讨论以下15 解决冲突的方法又称为溢出处理技术。解决冲突的方法又称为溢出处理技术。开放地址法开放地址法链地址法链地址法再哈希法再哈希法公共溢出区公共溢出区9.3.3 冲突处理方法冲突处理方法 解决冲突的方法又称为溢出处理技术。9.3.3 冲突16开放地址法开放地址法n若设哈希表中的编址为若设哈希表中的编址为 0 0 到到 m m-1-1，当要加入一，当要加入一个项个项 R R2 2时时,用它的关键码用它的关键码 R R2 2.keykey，通过哈希函，通过哈希函数数 hash hash(R R2 2.key key)的计算，得到它的存放地的计算，得到它的存放地址号址号 j j，但是在存放时发现这个位置已经被另，但是在存放时发现这个位置已经被另一个一个R R1 1 占据了。这时发生了冲突，必须处理溢占据了。这时发生了冲突，必须处理溢出。为此，必须把出。为此，必须把 R R2 2 存放到表中存放到表中“下一个下一个”空空位中。如果表未被装满，则在允许的范围内必位中。如果表未被装满，则在允许的范围内必定还有空位。定还有空位。开放地址法若设哈希表中的编址为 0 到 m-1，当要加入一个17(1)(1)线性探查法线性探查法(Linear Probing)(Linear Probing)n需要搜索或加入一个表项时，使用哈希函数计算号：需要搜索或加入一个表项时，使用哈希函数计算号：H H0 0=hashhash(key key)n一旦发生冲突，在表中顺次向后寻找一旦发生冲突，在表中顺次向后寻找“下一个下一个”空空 H Hi i 的公的公式为：式为：H Hi i=(=(H H0 0 +i i)%)%m m，i i=1,2,=1,2,m m-1-1 亦可写成亦可写成 H Hi i =(=(H Hi i-1-1+1)%+1)%m m，i i=1,2,=1,2,m m-1-1 (1)线性探查法(Linear Probing)需要搜索18 线性探查法线性探查法 例例n假假设设给给出出一一组组表表项项，它它们们的的关关键键码码为为 Burke,Burke,Ekers,Ekers,Broad,Broad,Blum,Blum,Attlee,Attlee,AltonAlton,Hecht,Hecht,EderlyEderly。采采用的哈希函数是：取其第一个字母在字母表中的位置。用的哈希函数是：取其第一个字母在字母表中的位置。HashHash(x x)=)=ord ord(x x)-)-ord ord(A A)/ordord()()是求字符内码的函数是求字符内码的函数n这样，可得这样，可得 Hash Hash(Burke)=1 (Burke)=1 HashHash(Ekers)=4(Ekers)=4 HashHash(Broad)=1 (Broad)=1 HashHash(Hecht)=7 (Hecht)=7 HashHash(Attlee)=0 (Attlee)=0 HashHash(Blum)=1(Blum)=1 线性探查法 例假设给出一组表项，它们的关键码为 Bur19 n又设哈希表为又设哈希表为HTHT2626，m m=26=26。采用线性探查法处。采用线性探查法处理溢出，则上述关键码在哈希表中哈希位置如图所理溢出，则上述关键码在哈希表中哈希位置如图所示。括号内的数字表示找到空位时的比较次数。示。括号内的数字表示找到空位时的比较次数。0123401234AttleeBurkeBroadEkersBlumHecht5678956789(1)(1)(2)(1)(1)(1)(2)(1)(1)(1)又设哈希表为HT26，m=26。采用线性探查法处理20 n又设哈希表为又设哈希表为HTHT2626，m m=26=26。采用线性探查法处。采用线性探查法处理溢出，则上述关键码在哈希表中哈希位置如图所理溢出，则上述关键码在哈希表中哈希位置如图所示。括号内的数字表示找到空位时的比较次数。示。括号内的数字表示找到空位时的比较次数。0123401234AttleeBurkeBroadEkersBlumHecht5678956789(1)(1)(2)(1)(1)(1)(2)(1)(1)(1)又设哈希表为HT26，m=26。采用线性探查法处理21 n又设哈希表为又设哈希表为HTHT2626，m m=26=26。采用线性探查法处。采用线性探查法处理溢出，则上述关键码在哈希表中哈希位置如图所理溢出，则上述关键码在哈希表中哈希位置如图所示。括号内的数字表示找到空位时的比较次数。示。括号内的数字表示找到空位时的比较次数。0123401234AttleeBurkeBroadEkersBlumHecht5678956789(1)(1)(2)(1)(1)(1)(2)(1)(1)(1)又设哈希表为HT26，m=26。采用线性探查法处理22 n又设哈希表为又设哈希表为HTHT2626，m m=26=26。采用线性探查法处。采用线性探查法处理溢出，则上述关键码在哈希表中哈希位置如图所理溢出，则上述关键码在哈希表中哈希位置如图所示。括号内的数字表示找到空位时的比较次数。示。括号内的数字表示找到空位时的比较次数。0123401234AttleeBurkeBroadEkersBlumHecht5678956789(1)(1)(2)(3)(1)(1)(1)(2)(3)(1)(1)(1)又设哈希表为HT26，m=26。采用线性探查法处理23n当发生冲突时当发生冲突时,探查下一个位置。当循环探查下一个位置。当循环 m m-1-1次后次后就会回到开始探查时的位置就会回到开始探查时的位置,说明待查关键码不在说明待查关键码不在表内表内,而且表已满而且表已满,不能再插入新关键码。不能再插入新关键码。n有聚集现象有聚集现象当发生冲突时,探查下一个位置。当循环 m-1次后就会回到开24(2)(2)二次探查法二次探查法(quadratic probing)(quadratic probing)n为改善聚集现象，减少为完成搜索所需的平均探查次为改善聚集现象，减少为完成搜索所需的平均探查次数，可使用二次探查法。数，可使用二次探查法。n通过某一个哈希函数对表项的关键码通过某一个哈希函数对表项的关键码 x x 进行计算，得进行计算，得到地址号，它是一个非负整数。到地址号，它是一个非负整数。H H0 0=hashhash(x x)n二次探查法在表中寻找二次探查法在表中寻找“下一个下一个”空位空位的公式为：的公式为：H Hi i =(=(H H0 0 i i 2 2)%)%m m,i i=1,2,(=1,2,(m m-1)/2-1)/2n式中的式中的 m m 是表的大小，它应是一个值为是表的大小，它应是一个值为 4 4k k+3+3 的质数，的质数，其中其中k k是一个整数。这样的质数如是一个整数。这样的质数如 3,7,11,19,23,3,7,11,19,23,31,43,59,127,251,503,1019,31,43,59,127,251,503,1019,。(2)二次探查法(quadratic probing)为25(2)(2)二次探查法二次探查法(quadratic probing)(quadratic probing)n快速计算方法快速计算方法np=1p=1n H Hi i =(=(H Hi i-1-1 p)%p)%m m,p=p+2,p=p+2,i i=1,2,(=1,2,(m m-1)/21)/2(2)二次探查法(quadratic probing)快26二次探查法二次探查法 例例n n示示示示例例例例：给给给给出出出出一一一一组组组组关关关关键键键键码码码码 Burke,Burke,Ekers,Ekers,Broad,Broad,Blum,Attlee,Alton,Hecht,EderlyBlum,Attlee,Alton,Hecht,Ederly。散散散散列列列列函函函函数数数数为为为为：HashHash(x x)（ord ord(x x)ord ord(A A)）2323 用它计算可得用它计算可得用它计算可得用它计算可得 Hash Hash(Burke)=1(Burke)=1HashHash(Ekers)=4(Ekers)=4 Hash Hash(Broad)=1(Broad)=1HashHash(Blum)=1(Blum)=1 Hash Hash(Attlee)=0(Attlee)=0HashHash(Hecht)=7(Hecht)=7 Hash Hash(Alton)=0(Alton)=0HashHash(Ederly)=4(Ederly)=4二次探查法 例示例：给出一组关键码 Burke,Ek27n若设表的长度为若设表的长度为TableSize TableSize=23=23，则利用二次，则利用二次探查法所得到的哈希结果如图所示。探查法所得到的哈希结果如图所示。012345BlumBurkeBroadEkersEderlyHecht67891011AltonAttlee(3)(1)(2)(1)(2)(1)171819202122(5)(3)利用二次探查法处理溢出利用二次探查法处理溢出若设表的长度为TableSize=23，则利用二次探查法28练习，h(key)=keymod11,现在哈希表如下:新记录关键字为38,其位置应为38mod11=5.有冲突！应插入到哪里?60 17 2901234567891060 17 29 38012345678910线性探测.平方探测.3860 17 2901234567891038练习，h(key)=key mod 11,现在哈希表如下29链地址法链地址法n首首先先对对关关键键码码集集合合用用某某一一个个哈哈希希函函数数计计算算它它们们的的存存放位置。放位置。n若若设设哈哈希希表表地地址址空空间间的的所所有有位位置置是是从从0 0到到m m-1-1，则则关关键键码码集集合合中中的的所所有有关关键键码码被被划划分分为为m m个个子子集集，具具有有相相同同地地址址的的关关键键码码归归于于同同一一子子集集。称称同同一一子子集集中中的的关关键码互为同义词。键码互为同义词。n通通常常同同义义词词表表项项通通过过一一个个单单链链表表链链接接起起来来，称称之之为为同义词子表。各链表的表头结点组成一个向量。同义词子表。各链表的表头结点组成一个向量。链地址法首先对关键码集合用某一个哈希函数计算它们的存放位置。30n采用链地址法处理溢出，采用链地址法处理溢出，关键码为关键码为 Burke,Burke,Ekers,Broad,Blum,Attlee,Alton,Hecht,Ekers,Broad,Blum,Attlee,Alton,Hecht,EderlyEderly。哈希函数与前面相同，。哈希函数与前面相同，则哈希表为：则哈希表为：采用链地址法处理溢出，关键码为 Burke,Ekers,31 n通通常常，每每个个同同义义词词子子表表都都很很短短，设设有有n n 个个关关键键码码通通过过某某一一个个哈哈希希函函数数，存存放放到到哈哈希希表表中中的的 m m 个个桶桶中中。那那么么每每一一个个桶桶中中的的同同义义词词子子表表的的平平均均长长度度为为 n n /m m。这这样样，以以搜搜索索平平均均长长度度为为 n n /m m 的的同同义义词词子子表表代代替替了了搜搜索索长长度度为为 n n 的的顺顺序序表表，搜搜索速度快得多。索速度快得多。通常，每个同义词子表都很短，设有n 个关键码通过某一个哈希32n再哈希法n公共溢出区再哈希法33其他问题其他问题n在在利利用用哈哈希希表表进进行行各各种种处处理理之之前前，必必须须首首先先将将哈哈希希表表中中原原有有的的内内容容清清掉掉。只只需需将将表表中中所所有有表表项项的的infoinfo域域置置为为EmptyEmpty即可。即可。n哈哈希希表表存存放放的的表表项项不不应应有有重重复复的的关关键键码码。在在插插入入新新表表项项时时，如果发现表中已经有关键码相同的表项，则不再插入。如果发现表中已经有关键码相同的表项，则不再插入。n一一般般不不能能真真正正删删除除表表中中已已有有表表项项。删删除除表表项项会会影影响响其其它它表表项项的的搜搜索索。若若把把关关键键码码为为BroadBroad的的表表项项真真正正删删除除，把把它它所所在在位位置置的的infoinfo域域置置为为EmptyEmpty，以以后后在在搜搜索索关关键键码码为为BlumBlum和和AltonAlton的的表表项项时时就就查查不不下下去去，从从而而会会错错误误地地判判断断表表中中没没有有关键码为关键码为BlumBlum和和AltonAlton的表项。的表项。其他问题在利用哈希表进行各种处理之前，必须首先将哈希表中原有34n若想删除一个表项，只能给它做一个删除标若想删除一个表项，只能给它做一个删除标记记deleteddeleted，进行逻辑删除，不能把它真正，进行逻辑删除，不能把它真正删去。删去。n逻辑删除的副作用逻辑删除的副作用是：在执行多次删除后，是：在执行多次删除后，表面上看起来哈希表很满，实际上有许多位表面上看起来哈希表很满，实际上有许多位置没有利用。置没有利用。若想删除一个表项，只能给它做一个删除标记deleted，进行35n哈希表分析哈希表分析 n哈哈希希表表是是一一种种直直接接计计算算记记录录存存放放地地址址的的方方法法，它在关键码与存储位置之间直接建立了映象。它在关键码与存储位置之间直接建立了映象。n当当选选择择的的哈哈希希函函数数能能够够得得到到均均匀匀的的地地址址分分布布时时，在搜索过程中可以不做多次探查。在搜索过程中可以不做多次探查。哈希表分析 36n若设若设 是哈希表的装填因子：是哈希表的装填因子：n用地址分布均匀的哈希函数用地址分布均匀的哈希函数HashHash()()计算地址。计算地址。nS Sn n 是搜索一个随机选择的关键码是搜索一个随机选择的关键码 x xi i (1(1 i i n n)所所需的关键码比较次数的期望值需的关键码比较次数的期望值nU Un n 是在长度为是在长度为 m m 的哈希表中的哈希表中 n n 个地址已有记录的个地址已有记录的情况下，装入第情况下，装入第 n n+1+1 项所需执行的关键码比较次数项所需执行的关键码比较次数期望值期望值。n前者是搜索成功时的平均搜索长度，后者是搜索不前者是搜索成功时的平均搜索长度，后者是搜索不成功时的平均搜索长度。成功时的平均搜索长度。算法分析算法分析若设 是哈希表的装填因子：算法分析37n当装填因子当装填因子 较高时，选择的哈希函数不同，哈希较高时，选择的哈希函数不同，哈希表的搜索性能差别很大。表的搜索性能差别很大。n对哈希表技术进行的实验评估表明，它具对哈希表技术进行的实验评估表明，它具有很好的有很好的平均性能平均性能，优于一些传统的技术，如平衡树优于一些传统的技术，如平衡树。n但哈希表但哈希表在最坏情况下性能很不好在最坏情况下性能很不好。如果对一。如果对一 个个有有 n n 个关键码的哈希表执行一次搜索或插入操作，个关键码的哈希表执行一次搜索或插入操作，最坏情况下需要最坏情况下需要 O(O(n n)的时间。的时间。当装填因子 较高时，选择的哈希函数不同，哈希表的搜索性能38n用不同的方法处理冲突时哈希表的平均搜索长度如表用不同的方法处理冲突时哈希表的平均搜索长度如表所示。所示。各种方法处理冲突的平均搜索长度各种方法处理冲突的平均搜索长度用不同的方法处理冲突时哈希表的平均搜索长度如表所示。各种方法39n哈哈希希表表的的装装填填因因子子 表表明明了了表表中中的的装装满满程程度度。越越大大，说说明明表表越越满满，再再插插入入新新元元素素时时发发生生冲冲突突的的可可能性就越大。能性就越大。n哈哈希希表表的的搜搜索索性性能能，即即平平均均搜搜索索长长度度依依赖赖于于哈哈希希表的装填因子，不直接依赖于表的装填因子，不直接依赖于 n n 或或 m m。n不不论论表表的的长长度度有有多多大大，我我们们总总能能选选择择一一个个合合适适的的装填因子，以把平均搜索长度限制在一定范围内。装填因子，以把平均搜索长度限制在一定范围内。n复杂度复杂度O(1)O(1)哈希表的装填因子 表明了表中的装满程度。越大，说明表越满40理论分析结果理论分析结果理论分析结果41实际测试结果实际测试结果实际测试结果42完美的哈希函数完美的哈希函数完美的哈希函数43总结总结n哈希表n查找总结哈希表44作业作业n已知一关键字序列为87,25,310,08,132,68,95,187,123,70,63,47。设哈希函数为H(key)=key%13，采用链地址法处理冲突。画出最后存储的哈希表，计算该表查找成功时的平均查找长度。作业已知一关键字序列为87,25,310,08,132,645