《算法与数据结构散列结构课件》由会员分享，可在线阅读，更多相关《算法与数据结构散列结构课件（108页珍藏版）》请在金锄头文库上搜索。
1、第十章第十章 散散 列列 结结 构构1算法与数据结构散列结构枚举向量，这种向量中使用的下标不是整数，而是某枚举类型的实例。对枚举向量，查询的出发点是一个枚举值，要做就是由这个枚举值出发，确定有关数据元素的存储位置。2算法与数据结构散列结构作为查询出发点的值可能有各种不同情况，需要进一步研究有关的技术和方法。在集合与字典的一章里，已经讨论了一些结构和技术，那里使用的基本技术是关键码比较。3算法与数据结构散列结构散列结构与枚举向量有类似之处：这里采用的基本存储结构也是一个向量，要做的也是从关键码出发，直接确定数据元素的存储位置。但是散列结构更具一般性，原则上说它允许任意种类的关键码。4算法与数据结
2、构散列结构设计良好的散列结构可以具有非常高的操作效率，因此这种结构在计算机领域中应用广泛，是一种非常有效的存储和查询结构。5算法与数据结构散列结构下面将首先介绍散列结构的基本思想，然后重点讨论散列结构实现的两个基本要素：散列函数和“碰撞”的各种解决技术。本章的后面部分把散列结构作为集合和字典的重要实现技术，讨论这些方面的有关问题。6算法与数据结构散列结构10.1基本概念基本概念7算法与数据结构散列结构存储方式和检索方法：存储方式和检索方法：存储方式和检索方法：存储方式和检索方法： 散列函数散列函数散列函数散列函数关键码关键码关键码关键码 地址地址地址地址( (固定，连续空间固定，连续空间固定，
3、连续空间固定，连续空间) )8算法与数据结构散列结构“ “散列散列散列散列” ”一词的意思是进行某种随机的混合，有一词的意思是进行某种随机的混合，有一词的意思是进行某种随机的混合，有一词的意思是进行某种随机的混合，有的中文教科书或文献中把它称为的中文教科书或文献中把它称为的中文教科书或文献中把它称为的中文教科书或文献中把它称为“ “杂凑杂凑杂凑杂凑” ”，对应，对应，对应，对应的英文词是一样的的英文词是一样的的英文词是一样的的英文词是一样的hashhash。9算法与数据结构散列结构散列函数是一种数据转换函数，它的参数应该是某种查询的依据，一般称为“关键词”或“关键码”，而函数返回的是一个无符号
4、整数值，作为确定下标的依据。散列的基本想法就是构造一个对应关系，把每个关键码对应到一个整数（存储位置）。这样，如果需要存储与某个关键码相关的数据，就将它存到与关键码对应的存储位置里去；如果需要查询与某个关键码有关的信息，就到与这个关键码对应的位置中去找。10算法与数据结构散列结构“散列”（hash）一词的意思是进行某种混合性的变换，从关键码本身看，这种变换可能并没有很清楚的具体意义。散列这个词在有些中文教科书或文献中被译为“杂凑”，散列结构也被称为“散列表”、“杂凑表”，或者按照音译称为“哈希表”等。11算法与数据结构散列结构根据散列函数概念，可以定义一种新向量类，叫作simpleHashVe
5、ctor类（简单散列向量类）。这里把它定义为向量类Vector的一个子类。简单散列向量比普通向量多一个数据成分，那就是一个指向散列函数的指针hashfun。对具体的简单散列向量而言，这个数据成分是在构造时建立，是一种不能改变的性质。12算法与数据结构散列结构简单散列向量类有两个类型参数，一个是向量的索引（关键码）类型H，另一个是向量元素类型T。13算法与数据结构散列结构templateclasssimpleHashVector:publicvectorpublic:/构造函数simpleHashVector(intmax,int(f)(constH&);simpleHashVector(int
6、max,int(f)(constH&),T&initialValue);simpleHashVector(constsimpleHashVector&v);/下标操作T&operator(constH&index);private:/记录散列函数的函数指针constint(hashfun)(constH&);qzy1;类10.1simpleHashVector类规范说明14算法与数据结构散列结构简单散列向量类的定义与枚举向量有相似的地方，例如对它们都可以用字符序列形式的向量下标直接存取相关元素。15算法与数据结构散列结构但是对于枚举向量，作为下标的字符序列必须是某个枚举类型的值，下标操作的实现
7、是由系统自动将枚举值转换成内部整数值。而对于简单散列向量，则可以使用真正的字符串，这种字符串可以送去打印等。16算法与数据结构散列结构在查询元素位置时，散列结构首先用给定的散列函数，把H类型的关键码（可以看作是一种广义“下标”）转换成一个适当的整数值，然后再把该整数转换成对于向量合法的下标值。后一转换一般直接采用按向量大小取余数的方式。17算法与数据结构散列结构templateT&hashVector:operator(constH&index)returnvector:operator(hashfun)(index)%size);简单散列向量类的其他成员函数都非常简单。读者不难自己实现它们。
8、10.2散散列列函函数数18算法与数据结构散列结构理想的散列函数是个一对一映射，它能把有关的一组关键码映射到连续的一组整数值，每个关键码对应一个整数值，反之依然。19算法与数据结构散列结构假设用假设用假设用假设用h(x)h(x)代表散列函数，一般来说，代表散列函数，一般来说，代表散列函数，一般来说，代表散列函数，一般来说，h h应该满足应该满足应该满足应该满足三个条件：三个条件：三个条件：三个条件： h h的定义域是全体可能出现的关键码的集合，的定义域是全体可能出现的关键码的集合，的定义域是全体可能出现的关键码的集合，的定义域是全体可能出现的关键码的集合，h h的值域是散列表空间位置的值域是散
9、列表空间位置的值域是散列表空间位置的值域是散列表空间位置( (向量下标向量下标向量下标向量下标) )的集合；的集合；的集合；的集合； 希望函数值分布对于散列空间位置而言要尽量均希望函数值分布对于散列空间位置而言要尽量均希望函数值分布对于散列空间位置而言要尽量均希望函数值分布对于散列空间位置而言要尽量均匀；匀；匀；匀； h h函数应该是足够简单的。函数应该是足够简单的。函数应该是足够简单的。函数应该是足够简单的。20算法与数据结构散列结构对一般类型的关键码，运用散列函数的过程通常对一般类型的关键码，运用散列函数的过程通常对一般类型的关键码，运用散列函数的过程通常对一般类型的关键码，运用散列函数的
10、过程通常分成两步：分成两步：分成两步：分成两步：第一步是将关键码转化成适当的整数值；第一步是将关键码转化成适当的整数值；第一步是将关键码转化成适当的整数值；第一步是将关键码转化成适当的整数值；第二步是将得到的整数转化为散列向量的合法下第二步是将得到的整数转化为散列向量的合法下第二步是将得到的整数转化为散列向量的合法下第二步是将得到的整数转化为散列向量的合法下标。标。标。标。21算法与数据结构散列结构实现第一步有很多种方法，下面列举常见的几种。实现第一步有很多种方法，下面列举常见的几种。实现第一步有很多种方法，下面列举常见的几种。实现第一步有很多种方法，下面列举常见的几种。1 1) )映射：将关
11、键码以某种数值方式映射成整数值。映射：将关键码以某种数值方式映射成整数值。映射：将关键码以某种数值方式映射成整数值。映射：将关键码以某种数值方式映射成整数值。 对于比较复杂的映射，一般可用一个映射数组来对于比较复杂的映射，一般可用一个映射数组来对于比较复杂的映射，一般可用一个映射数组来对于比较复杂的映射，一般可用一个映射数组来定义。数组中的元素都在程序编制前预先给出。定义。数组中的元素都在程序编制前预先给出。定义。数组中的元素都在程序编制前预先给出。定义。数组中的元素都在程序编制前预先给出。程序执行时，求散列值信息就是在映射数组中找程序执行时，求散列值信息就是在映射数组中找程序执行时，求散列值
12、信息就是在映射数组中找程序执行时，求散列值信息就是在映射数组中找到该元素，对于一组确定的关键码来说，这是产到该元素，对于一组确定的关键码来说，这是产到该元素，对于一组确定的关键码来说，这是产到该元素，对于一组确定的关键码来说，这是产生一个理想的散列函数的基本方法。生一个理想的散列函数的基本方法。生一个理想的散列函数的基本方法。生一个理想的散列函数的基本方法。22算法与数据结构散列结构2 2) )折叠：先把关键码分割成小块，各部分的值必要折叠：先把关键码分割成小块，各部分的值必要折叠：先把关键码分割成小块，各部分的值必要折叠：先把关键码分割成小块，各部分的值必要时可以先散列处理，然后再混合起来便
13、形成整个关时可以先散列处理，然后再混合起来便形成整个关时可以先散列处理，然后再混合起来便形成整个关时可以先散列处理，然后再混合起来便形成整个关键码的散列值。键码的散列值。键码的散列值。键码的散列值。 混合又有多种不同的方法，如加法、乘法或逻辑混合又有多种不同的方法，如加法、乘法或逻辑混合又有多种不同的方法，如加法、乘法或逻辑混合又有多种不同的方法，如加法、乘法或逻辑运算。运算。运算。运算。23算法与数据结构散列结构下面的小程序段实现了一种把字符串下面的小程序段实现了一种把字符串下面的小程序段实现了一种把字符串下面的小程序段实现了一种把字符串strstr变成整数变成整数变成整数变成整数值的过程，
14、所用的方法便是将所有字母值加起来。值的过程，所用的方法便是将所有字母值加起来。值的过程，所用的方法便是将所有字母值加起来。值的过程，所用的方法便是将所有字母值加起来。unsigned int hashval = 0;unsigned int hashval = 0;int i = str.length( );int i = str.length( );while (i 0)while (i 0) hashval += str hashval += stri;i;24算法与数据结构散列结构3 3) )移位：移位可以避免在折叠处理中由于运算的可移位：移位可以避免在折叠处理中由于运算的可移位：移位可
15、以避免在折叠处理中由于运算的可移位：移位可以避免在折叠处理中由于运算的可交换带来的碰撞。交换带来的碰撞。交换带来的碰撞。交换带来的碰撞。 如上段程序便对如上段程序便对如上段程序便对如上段程序便对aptapt、taptap、patpat会产生相同的散会产生相同的散会产生相同的散会产生相同的散列值，而使用移位便可能减少这些碰撞。下面是加列值，而使用移位便可能减少这些碰撞。下面是加列值，而使用移位便可能减少这些碰撞。下面是加列值，而使用移位便可能减少这些碰撞。下面是加入移位处理后的程序段：入移位处理后的程序段：入移位处理后的程序段：入移位处理后的程序段：25算法与数据结构散列结构unsigned i
16、nt hashval = 0;unsigned int hashval = 0;int i = str.length( );int i = str.length( );while (i 0)while (i 0) hashval = (hashval 1) + str hashval = (hashval 1) + str1;1;26算法与数据结构散列结构4 4) )数字分析法：常常有这样的情况：关键码的位数数字分析法：常常有这样的情况：关键码的位数数字分析法：常常有这样的情况：关键码的位数数字分析法：常常有这样的情况：关键码的位数比存储区域的地址码的位数多，同时其中各位的比存储区域的地址码的
17、位数多，同时其中各位的比存储区域的地址码的位数多，同时其中各位的比存储区域的地址码的位数多，同时其中各位的出现不是随机的，在这种情况下可以通过事先对出现不是随机的，在这种情况下可以通过事先对出现不是随机的，在这种情况下可以通过事先对出现不是随机的，在这种情况下可以通过事先对关键码的各位情况进行分析，散列时丢掉分布不关键码的各位情况进行分析，散列时丢掉分布不关键码的各位情况进行分析，散列时丢掉分布不关键码的各位情况进行分析，散列时丢掉分布不均匀的位，留下分布均匀的位。均匀的位，留下分布均匀的位。均匀的位，留下分布均匀的位。均匀的位，留下分布均匀的位。27算法与数据结构散列结构例如，需要对下列关键
18、码集合进行转换，实际关例如，需要对下列关键码集合进行转换，实际关例如，需要对下列关键码集合进行转换，实际关例如，需要对下列关键码集合进行转换，实际关键码有键码有键码有键码有9 9位数字，经过数字分析法可以丢掉位数字，经过数字分析法可以丢掉位数字，经过数字分析法可以丢掉位数字，经过数字分析法可以丢掉6 6位。位。位。位。 key h(key)key h(key) 000319426 326 000319426 326 000718309 709 000718309 709 000629443 643 000629443 643 000758615 715 000758615 715 000910
19、497 997 000910497 997 000310329 329 000310329 32928算法与数据结构散列结构这个方法的缺点是散列函数依赖于关键码集合，这个方法的缺点是散列函数依赖于关键码集合，这个方法的缺点是散列函数依赖于关键码集合，这个方法的缺点是散列函数依赖于关键码集合，具体到这具体到这具体到这具体到这6 6个关键码值，经过分析留下第个关键码值，经过分析留下第个关键码值，经过分析留下第个关键码值，经过分析留下第4 4、8 8、9 9位，若换一个关键码集合，就要重新分析，也许位，若换一个关键码集合，就要重新分析，也许位，若换一个关键码集合，就要重新分析，也许位，若换一个关键码
20、集合，就要重新分析，也许留下第留下第留下第留下第3 3、6 6、7 7位。通过对比较大的实例集合进行位。通过对比较大的实例集合进行位。通过对比较大的实例集合进行位。通过对比较大的实例集合进行分析，就可能得到比较合理的结果。分析，就可能得到比较合理的结果。分析，就可能得到比较合理的结果。分析，就可能得到比较合理的结果。29算法与数据结构散列结构散列函数的第二步工作是将已得到的整数值转化散列函数的第二步工作是将已得到的整数值转化散列函数的第二步工作是将已得到的整数值转化散列函数的第二步工作是将已得到的整数值转化成散列表的合法下标值，这时采用最多的是除余成散列表的合法下标值，这时采用最多的是除余成散
21、列表的合法下标值，这时采用最多的是除余成散列表的合法下标值，这时采用最多的是除余法。法。法。法。所谓除余法，就是选择一个恰当的正整数所谓除余法，就是选择一个恰当的正整数所谓除余法，就是选择一个恰当的正整数所谓除余法，就是选择一个恰当的正整数B B，用用用用B B去除前一步骤得到的整数，取其余数作为散列表去除前一步骤得到的整数，取其余数作为散列表去除前一步骤得到的整数，取其余数作为散列表去除前一步骤得到的整数，取其余数作为散列表的下标值。的下标值。的下标值。的下标值。30算法与数据结构散列结构这个方法的关键是选取恰当的这个方法的关键是选取恰当的这个方法的关键是选取恰当的这个方法的关键是选取恰当的
22、B B。如果如果如果如果B B选为一个选为一个选为一个选为一个偶数，则它将总是把奇整数值转换到奇数的下标，偶数，则它将总是把奇整数值转换到奇数的下标，偶数，则它将总是把奇整数值转换到奇数的下标，偶数，则它将总是把奇整数值转换到奇数的下标，把偶整数值转换到偶数的下标，这当然不太好。把偶整数值转换到偶数的下标，这当然不太好。把偶整数值转换到偶数的下标，这当然不太好。把偶整数值转换到偶数的下标，这当然不太好。选选选选B B为为为为1010的幂次就更不好，因为那样就等于选择的幂次就更不好，因为那样就等于选择的幂次就更不好，因为那样就等于选择的幂次就更不好，因为那样就等于选择整数的最后几位数字作为地址。
23、例如，选整数的最后几位数字作为地址。例如，选整数的最后几位数字作为地址。例如，选整数的最后几位数字作为地址。例如，选B=100B=100，则实际上就是取整数的最后两位作为地址。则实际上就是取整数的最后两位作为地址。则实际上就是取整数的最后两位作为地址。则实际上就是取整数的最后两位作为地址。31算法与数据结构散列结构在实际工作中一般认为选取在实际工作中一般认为选取在实际工作中一般认为选取在实际工作中一般认为选取B B为适当的素数为好。为适当的素数为好。为适当的素数为好。为适当的素数为好。例如：例如：例如：例如：B = 7B = 7，1313，3131，6161，127127，251251，503
24、503，1019101932算法与数据结构散列结构除余法的地址计算公式简单。然而实践证明，恰恰除余法的地址计算公式简单。然而实践证明，恰恰除余法的地址计算公式简单。然而实践证明，恰恰除余法的地址计算公式简单。然而实践证明，恰恰是这种简单的方法在许多情况下效果比较好。需要是这种简单的方法在许多情况下效果比较好。需要是这种简单的方法在许多情况下效果比较好。需要是这种简单的方法在许多情况下效果比较好。需要注意的是注意的是注意的是注意的是B B的选择，也就是散列表中桶的个数的确的选择，也就是散列表中桶的个数的确的选择，也就是散列表中桶的个数的确的选择，也就是散列表中桶的个数的确定，因为用除余法所计算的
25、结果一定在定，因为用除余法所计算的结果一定在定，因为用除余法所计算的结果一定在定，因为用除余法所计算的结果一定在0 0 B-1B-1的的的的范围之中。范围之中。范围之中。范围之中。33算法与数据结构散列结构同义词同义词同义词同义词负载因子负载因子负载因子负载因子 碰撞（开地址，桶）碰撞（开地址，桶）碰撞（开地址，桶）碰撞（开地址，桶）34算法与数据结构散列结构两个关键码散列成相同的值的现象被称为两个关键码散列成相同的值的现象被称为两个关键码散列成相同的值的现象被称为两个关键码散列成相同的值的现象被称为“ “碰撞碰撞碰撞碰撞” ”。碰撞的产生使散列的使用产生了问题。碰撞的产生使散列的使用产生了问
26、题。碰撞的产生使散列的使用产生了问题。碰撞的产生使散列的使用产生了问题。35算法与数据结构散列结构下面我们先引入下面我们先引入下面我们先引入下面我们先引入“ “同义词同义词同义词同义词” ”的概念。设有关键码的概念。设有关键码的概念。设有关键码的概念。设有关键码k k1 1和和和和k k2 2，经过散列函数经过散列函数经过散列函数经过散列函数f f的作用，把它们映射成相同的作用，把它们映射成相同的作用，把它们映射成相同的作用，把它们映射成相同的值，即的值，即的值，即的值，即f(kf(k1 1)= f(k)= f(k2 2) )，称称称称k k1 1和和和和k k2 2在函数在函数在函数在函数f
27、 f的解释下含的解释下含的解释下含的解释下含义相同，简称为义相同，简称为义相同，简称为义相同，简称为“ “同义词同义词同义词同义词” ”。显然同义词越多，。显然同义词越多，。显然同义词越多，。显然同义词越多，碰撞的可能性就越大。碰撞的可能性就越大。碰撞的可能性就越大。碰撞的可能性就越大。36算法与数据结构散列结构另外一个重要概念是另外一个重要概念是另外一个重要概念是另外一个重要概念是“ “负载因子负载因子负载因子负载因子” ”。简单地讲，一。简单地讲，一。简单地讲，一。简单地讲，一种结构的负载因子种结构的负载因子种结构的负载因子种结构的负载因子 可以定义为这个结构中实际元可以定义为这个结构中实
28、际元可以定义为这个结构中实际元可以定义为这个结构中实际元素的个数与能够容纳的元素个数之比。即：素的个数与能够容纳的元素个数之比。即：素的个数与能够容纳的元素个数之比。即：素的个数与能够容纳的元素个数之比。即： = = 结构中实际元素的个数结构中实际元素的个数结构中实际元素的个数结构中实际元素的个数 / / 结构中能够容纳的元结构中能够容纳的元结构中能够容纳的元结构中能够容纳的元素个数素个数素个数素个数37算法与数据结构散列结构10.3开地址散列向量开地址散列向量38算法与数据结构散列结构为了解决碰撞，人们提出了许多方法，本节先介绍其中的一种，称为“开地址法”。用这种方法建立的散列结构称为“开地
29、址散列向量”。39算法与数据结构散列结构类10.2给出openHashVector的规范说明。为了叙述简单，我们假设向量中每个元素都只包含关键码自身，元素类型就是关键码类型。这时模板类的参数只需要一个元素类型T（也是关键码类型）；进一步还假设对T类型有一个特定值，这个值不表示任何真正有意义的关键码。因此，如果向量中某元素取这个值，就表明该元素处于空闲状态。40算法与数据结构散列结构 templateclassopenHashVectortemplateclassopenHashVector public:public:/构造函数构造函数openHashVector(intmax,int(ope
30、nHashVector(intmax,int( f)(constT&),T&value);f)(constT&),T&value);openHashVector(constopenHashVector&);openHashVector(constopenHashVector&);/操作操作intadd(constT&);intadd(constT&);intincludes(T&);intincludes(T&);voidremove(constT&);voidremove(constT&);private:private:/数据域：散列函数，基向量和向量长度及初值数据域：散列函数，基向量和向
31、量长度及初值constint(constint( hashfun)(constT&);hashfun)(constT&);vectordata;vectordata;intsize;intsize;constTspareValue;constTspareValue; ;类类10.210.2openHashVectoropenHashVector类规范说明类规范说明 41算法与数据结构散列结构templateopenHashVector:openHashVector(intmax,int(f)(constT&),T&value):hashfun(f),data(max),spareValue(v
32、alue)/设置向量大小size=data.length();for(unsignedi=0;isize;i+)datai=spareValue;42算法与数据结构散列结构 templateintopenHashVector:add(consttemplateintopenHashVector:add(constT&v)T&v)/把一个确定数据记录存放到开地址散列向量把一个确定数据记录存放到开地址散列向量unsignedstart=(unsignedstart=( hashfun)(v)%size,index=start;hashfun)(v)%size,index=start;/检查位置是否
33、已被占用检查位置是否已被占用while(dataindex!=spareValue)while(dataindex!=spareValue)index=(index+1)%size;/index=(index+1)%size;/考察下一个位置考察下一个位置if(index=start)return0;if(index=start)return0;dataindex=v;/dataindex=v;/发现空位，插入新元素发现空位，插入新元素return1;return1; 43算法与数据结构散列结构templateintopenHashVector:includes(T&templateintop
34、enHashVector:includes(T&value)value) unsignedstart=(unsignedstart=( hashfun)(value)%size;hashfun)(value)%size;unsignedindex=start;unsignedindex=start;TcurValue=dataindex;TcurValue=dataindex;while(curValue!=value)/while(curValue!=value)/未找到对应值就继续循环未找到对应值就继续循环if(curValue=spareValue)return0;if(curValue
35、=spareValue)return0;index=(index+1)%size;index=(index+1)%size;if(index=start)return0;if(index=start)return0;curValue=dataindex;curValue=dataindex;return1;return1; 44算法与数据结构散列结构开地址散列的思想很简单，但是它的碰撞处理方开地址散列的思想很简单，但是它的碰撞处理方开地址散列的思想很简单，但是它的碰撞处理方开地址散列的思想很简单，但是它的碰撞处理方式也有些缺点。如果碰撞经常发生，插入和查找式也有些缺点。如果碰撞经常发生，插入和
36、查找式也有些缺点。如果碰撞经常发生，插入和查找式也有些缺点。如果碰撞经常发生，插入和查找的时间代价就要增加，特别是在向量中增加同义的时间代价就要增加，特别是在向量中增加同义的时间代价就要增加，特别是在向量中增加同义的时间代价就要增加，特别是在向量中增加同义词的时候，可能使原来并不是同义词的关键码也词的时候，可能使原来并不是同义词的关键码也词的时候，可能使原来并不是同义词的关键码也词的时候，可能使原来并不是同义词的关键码也被牵连进来（这种现象也被称为被牵连进来（这种现象也被称为被牵连进来（这种现象也被称为被牵连进来（这种现象也被称为“ “堆积堆积堆积堆积” ”），进），进），进），进一步增加了查
37、找的时间。一步增加了查找的时间。一步增加了查找的时间。一步增加了查找的时间。45算法与数据结构散列结构还有另外一点，在开地址散列向量中的做删除时还有另外一点，在开地址散列向量中的做删除时还有另外一点，在开地址散列向量中的做删除时还有另外一点，在开地址散列向量中的做删除时要特别谨慎，如果简单地把被删除向量元素置成要特别谨慎，如果简单地把被删除向量元素置成要特别谨慎，如果简单地把被删除向量元素置成要特别谨慎，如果简单地把被删除向量元素置成初始值，结果就可能导致某些原有同义词信息的初始值，结果就可能导致某些原有同义词信息的初始值，结果就可能导致某些原有同义词信息的初始值，结果就可能导致某些原有同义词
38、信息的丢失。这里面的具体原因和解决方法请读者自己丢失。这里面的具体原因和解决方法请读者自己丢失。这里面的具体原因和解决方法请读者自己丢失。这里面的具体原因和解决方法请读者自己考虑。考虑。考虑。考虑。46算法与数据结构散列结构10.410.4桶散列桶散列桶散列桶散列用桶解决碰撞用桶解决碰撞用桶解决碰撞用桶解决碰撞本节介绍碰撞的另一种处理方法。如果把散列表的元本节介绍碰撞的另一种处理方法。如果把散列表的元本节介绍碰撞的另一种处理方法。如果把散列表的元本节介绍碰撞的另一种处理方法。如果把散列表的元素扩充定义为一个能存放多个数据元素的结构，用这素扩充定义为一个能存放多个数据元素的结构，用这素扩充定义为
39、一个能存放多个数据元素的结构，用这素扩充定义为一个能存放多个数据元素的结构，用这种结构存放同义词，能够大大增强散列结构处理碰撞种结构存放同义词，能够大大增强散列结构处理碰撞种结构存放同义词，能够大大增强散列结构处理碰撞种结构存放同义词，能够大大增强散列结构处理碰撞的能力。人们把这种存放同义词的结构称为的能力。人们把这种存放同义词的结构称为的能力。人们把这种存放同义词的结构称为的能力。人们把这种存放同义词的结构称为“ “存储桶存储桶存储桶存储桶” ”，或简称，或简称，或简称，或简称“ “桶桶桶桶” ”。47算法与数据结构散列结构采用桶方式实现散列结构，向结构里加入一个元采用桶方式实现散列结构，向
40、结构里加入一个元采用桶方式实现散列结构，向结构里加入一个元采用桶方式实现散列结构，向结构里加入一个元素的动作就需要分两步走：首先在散列向量中选素的动作就需要分两步走：首先在散列向量中选素的动作就需要分两步走：首先在散列向量中选素的动作就需要分两步走：首先在散列向量中选择应该放入元素的桶，然后再向这个桶做元素插择应该放入元素的桶，然后再向这个桶做元素插择应该放入元素的桶，然后再向这个桶做元素插择应该放入元素的桶，然后再向这个桶做元素插入。寻找和删除元素的操作过程与插入类似。由入。寻找和删除元素的操作过程与插入类似。由入。寻找和删除元素的操作过程与插入类似。由入。寻找和删除元素的操作过程与插入类似
41、。由于每个桶可以容纳多个元素，碰撞问题自然就解于每个桶可以容纳多个元素，碰撞问题自然就解于每个桶可以容纳多个元素，碰撞问题自然就解于每个桶可以容纳多个元素，碰撞问题自然就解决了。我们把以这种方式实现的散列结构称为桶决了。我们把以这种方式实现的散列结构称为桶决了。我们把以这种方式实现的散列结构称为桶决了。我们把以这种方式实现的散列结构称为桶散列结构或桶散列表。散列结构或桶散列表。散列结构或桶散列表。散列结构或桶散列表。48算法与数据结构散列结构10.4.110.4.1桶散列的抽象模板类桶散列的抽象模板类桶散列的抽象模板类桶散列的抽象模板类抽象的桶散列模板类抽象的桶散列模板类抽象的桶散列模板类抽象
42、的桶散列模板类bucketHashVectorbucketHashVector带有三个带有三个带有三个带有三个类型参数：类类型参数：类类型参数：类类型参数：类B B是桶的实现类型，其实现细节方面是桶的实现类型，其实现细节方面是桶的实现类型，其实现细节方面是桶的实现类型，其实现细节方面的情况后面讨论；类的情况后面讨论；类的情况后面讨论；类的情况后面讨论；类H H是元素的关键码类型，它也是元素的关键码类型，它也是元素的关键码类型，它也是元素的关键码类型，它也是散列函数处理的对象类型；类是散列函数处理的对象类型；类是散列函数处理的对象类型；类是散列函数处理的对象类型；类T T是桶散列表中元素是桶散列
43、表中元素是桶散列表中元素是桶散列表中元素的类型。的类型。的类型。的类型。49算法与数据结构散列结构templateclassbucketHashVectortemplateclassbucketHashVector public:public:/构造函数构造函数构造函数构造函数bucketHashVector(unsignedintmax,unsignedint(bucketHashVector(unsignedintmax,unsignedint( f)(constH&);f)(constH&);virtualintisEmpty();/virtualintisEmpty();/判断是否为空
44、散列表判断是否为空散列表判断是否为空散列表判断是否为空散列表virtualvoiddeleteAllValues();/virtualvoiddeleteAllValues();/删除散列表里所有元素删除散列表里所有元素删除散列表里所有元素删除散列表里所有元素protected:protected:friendclassbucketHashVectorIterator;friendclassbucketHashVectorIterator;constunsignedinttablesize;/constunsignedinttablesize;/散列表里桶个数散列表里桶个数散列表里桶个数散列表
45、里桶个数vectorbuckets;/vectorbuckets;/散列表用一个以桶为元素的向量散列表用一个以桶为元素的向量散列表用一个以桶为元素的向量散列表用一个以桶为元素的向量constunsignedint(constunsignedint( hashfun)(constH&);/hashfun)(constH&);/散列函数指针散列函数指针散列函数指针散列函数指针unsignedinthash(constH&key)const;/unsignedinthash(constH&key)const;/实际使用的散列函数实际使用的散列函数实际使用的散列函数实际使用的散列函数/建立指定桶的遍历
46、器建立指定桶的遍历器建立指定桶的遍历器建立指定桶的遍历器virtualiteratorvirtualiterator makeIterator(unsignedint)=0;makeIterator(unsignedint)=0; ;类类类类10.310.3bucketHashVectorbucketHashVector类的规范说明类的规范说明类的规范说明类的规范说明 50算法与数据结构散列结构bucketHashVectorbucketHashVector类的对象有三个数据域：类的对象有三个数据域：类的对象有三个数据域：类的对象有三个数据域：bucketsbuckets是桶类型的向量，各个桶
47、里存放散列表是桶类型的向量，各个桶里存放散列表是桶类型的向量，各个桶里存放散列表是桶类型的向量，各个桶里存放散列表元素；整数元素；整数元素；整数元素；整数tablesizetablesize是桶向量的元素个数是桶向量的元素个数是桶向量的元素个数是桶向量的元素个数( (桶的桶的桶的桶的个数个数个数个数) )，由于桶的数目与散列函数直接相关，这，由于桶的数目与散列函数直接相关，这，由于桶的数目与散列函数直接相关，这，由于桶的数目与散列函数直接相关，这里采用确定之后就不能再修改的方式，把它说明里采用确定之后就不能再修改的方式，把它说明里采用确定之后就不能再修改的方式，把它说明里采用确定之后就不能再修
48、改的方式，把它说明为一个整型常量；为一个整型常量；为一个整型常量；为一个整型常量；hashfunhashfun是散列函数指针，在是散列函数指针，在是散列函数指针，在是散列函数指针，在散列表定义时设定到选定的散列函数。这个散列散列表定义时设定到选定的散列函数。这个散列散列表定义时设定到选定的散列函数。这个散列散列表定义时设定到选定的散列函数。这个散列函数以函数以函数以函数以H H类型的关键码作参数，计算出一个无符类型的关键码作参数，计算出一个无符类型的关键码作参数，计算出一个无符类型的关键码作参数，计算出一个无符号的整数结果。号的整数结果。号的整数结果。号的整数结果。51算法与数据结构散列结构在
49、在在在bucketHashVectorbucketHashVector类里只定义了两个公用操作：类里只定义了两个公用操作：类里只定义了两个公用操作：类里只定义了两个公用操作：一个操作测试散列表是否为空，另一个操作完成所有一个操作测试散列表是否为空，另一个操作完成所有一个操作测试散列表是否为空，另一个操作完成所有一个操作测试散列表是否为空，另一个操作完成所有桶的清除工作，其他操作都必须在这个类的子类里定桶的清除工作，其他操作都必须在这个类的子类里定桶的清除工作，其他操作都必须在这个类的子类里定桶的清除工作，其他操作都必须在这个类的子类里定义。义。义。义。上面两个公有函数都需要遍历所有的桶。要删除
50、散列上面两个公有函数都需要遍历所有的桶。要删除散列上面两个公有函数都需要遍历所有的桶。要删除散列上面两个公有函数都需要遍历所有的桶。要删除散列表里所有的项，必须清除每个桶的所有元素。表里所有的项，必须清除每个桶的所有元素。表里所有的项，必须清除每个桶的所有元素。表里所有的项，必须清除每个桶的所有元素。 52算法与数据结构散列结构templatetemplatevoidbucketHashVector:deleteAllValues()voidbucketHashVector:deleteAllValues() for(inti=0;itablesize;i+)for(inti=0;itable
51、size;i+)bucketsi.deleteAllValues();bucketsi.deleteAllValues(); 53算法与数据结构散列结构类似的，检查一个散列表里是否有元素就必须检测每类似的，检查一个散列表里是否有元素就必须检测每类似的，检查一个散列表里是否有元素就必须检测每类似的，检查一个散列表里是否有元素就必须检测每个桶的情况。在这些桶都为空的时候，才能说散列表个桶的情况。在这些桶都为空的时候，才能说散列表个桶的情况。在这些桶都为空的时候，才能说散列表个桶的情况。在这些桶都为空的时候，才能说散列表是空的。是空的。是空的。是空的。 templateinttemplateintb
52、ucketHashVector:isEmpty()bucketHashVector:isEmpty()/如果任一个筒非空就返回如果任一个筒非空就返回如果任一个筒非空就返回如果任一个筒非空就返回0 0值值值值for(inti=0;itablesize;i+)for(inti=0;itablesize;i+)if(!buckedsi.isEmpty()return0;if(!buckedsi.isEmpty()return0;return1;/return1;/全都为空，散列表空全都为空，散列表空全都为空，散列表空全都为空，散列表空 54算法与数据结构散列结构函数函数函数函数hashhash定义了
53、对关键码的散列值计算。由于该定义了对关键码的散列值计算。由于该定义了对关键码的散列值计算。由于该定义了对关键码的散列值计算。由于该函数不改变散列表本身，所以被说明为函数不改变散列表本身，所以被说明为函数不改变散列表本身，所以被说明为函数不改变散列表本身，所以被说明为constconst。函数函数函数函数hashhash通过函数指针通过函数指针通过函数指针通过函数指针hashfunhashfun调用桶散列表建调用桶散列表建调用桶散列表建调用桶散列表建立时设定的基本散列函数，并把散列值归入立时设定的基本散列函数，并把散列值归入立时设定的基本散列函数，并把散列值归入立时设定的基本散列函数，并把散列值
54、归入0 0与与与与tablezise-1tablezise-1之间。函数之间。函数之间。函数之间。函数hashhash在类的保护部分中在类的保护部分中在类的保护部分中在类的保护部分中说明，在说明，在说明，在说明，在bucketHashVectorbucketHashVector的子类和友元类里的子类和友元类里的子类和友元类里的子类和友元类里都可以直接调用它。都可以直接调用它。都可以直接调用它。都可以直接调用它。 55算法与数据结构散列结构templatetemplateunsignedintbucketHashVector:hash(constunsignedintbucketHashVect
55、or:hash(constH&key)constH&key)const/返回关键字的散列值返回关键字的散列值返回关键字的散列值返回关键字的散列值return(return( hashfun)(key)%tablesize;hashfun)(key)%tablesize; 56算法与数据结构散列结构在在在在bucketHashVectorbucketHashVector的保护部分还定义了一个的保护部分还定义了一个的保护部分还定义了一个的保护部分还定义了一个名为名为名为名为makeIteratormakeIterator的纯虚函数，其参数是一个整的纯虚函数，其参数是一个整的纯虚函数，其参数是一个整
56、的纯虚函数，其参数是一个整数。这个函数的作用是根据参数值生成指定的桶数。这个函数的作用是根据参数值生成指定的桶数。这个函数的作用是根据参数值生成指定的桶数。这个函数的作用是根据参数值生成指定的桶遍历器。由于桶类型遍历器。由于桶类型遍历器。由于桶类型遍历器。由于桶类型B B是模板参数，所以函数的是模板参数，所以函数的是模板参数，所以函数的是模板参数，所以函数的实现目前无法具体给出。所有实现目前无法具体给出。所有实现目前无法具体给出。所有实现目前无法具体给出。所有bucketHashVectorbucketHashVector的子类都必须重新定义这个的子类都必须重新定义这个的子类都必须重新定义这个
57、的子类都必须重新定义这个函数。例如下面的子类函数。例如下面的子类函数。例如下面的子类函数。例如下面的子类hashTreehashTree定义时就给出定义时就给出定义时就给出定义时就给出了它的重新定义。了它的重新定义。了它的重新定义。了它的重新定义。57算法与数据结构散列结构10.4.210.4.2用树作为桶的实现用树作为桶的实现用树作为桶的实现用树作为桶的实现要使用桶散列数据结构，必须建立要使用桶散列数据结构，必须建立要使用桶散列数据结构，必须建立要使用桶散列数据结构，必须建立bucketHashVectorbucketHashVector的非虚的子类，首先要做的是提的非虚的子类，首先要做的是
58、提的非虚的子类，首先要做的是提的非虚的子类，首先要做的是提供桶的实现类型。桶的实现类型应该适合进行插入和供桶的实现类型。桶的实现类型应该适合进行插入和供桶的实现类型。桶的实现类型应该适合进行插入和供桶的实现类型。桶的实现类型应该适合进行插入和删除操作，以便支持散列表的实现。删除操作，以便支持散列表的实现。删除操作，以便支持散列表的实现。删除操作，以便支持散列表的实现。58算法与数据结构散列结构例如链接实现的表或者某种树结构。采用链接表实现例如链接实现的表或者某种树结构。采用链接表实现例如链接实现的表或者某种树结构。采用链接表实现例如链接实现的表或者某种树结构。采用链接表实现桶比较简单，如果能保
59、证散列表里每个链表都很短，桶比较简单，如果能保证散列表里每个链表都很短，桶比较简单，如果能保证散列表里每个链表都很短，桶比较简单，如果能保证散列表里每个链表都很短，各种操作的效率是可以保证的。各种操作的效率是可以保证的。各种操作的效率是可以保证的。各种操作的效率是可以保证的。 定义定义定义定义hashListhashList类的类的类的类的工作留做练习。工作留做练习。工作留做练习。工作留做练习。59算法与数据结构散列结构如果对桶中可能出现的元素数目无法做出合理估如果对桶中可能出现的元素数目无法做出合理估如果对桶中可能出现的元素数目无法做出合理估如果对桶中可能出现的元素数目无法做出合理估计，采用
60、链表实现桶就可能出现操作效率比较低计，采用链表实现桶就可能出现操作效率比较低计，采用链表实现桶就可能出现操作效率比较低计，采用链表实现桶就可能出现操作效率比较低的情况，因为在反复的插入操作中，散列表里某的情况，因为在反复的插入操作中，散列表里某的情况，因为在反复的插入操作中，散列表里某的情况，因为在反复的插入操作中，散列表里某些桶（链表）可能变得很长，这时链表的线性查些桶（链表）可能变得很长，这时链表的线性查些桶（链表）可能变得很长，这时链表的线性查些桶（链表）可能变得很长，这时链表的线性查寻时间对操作效率就会产生决定性的影响。寻时间对操作效率就会产生决定性的影响。寻时间对操作效率就会产生决定
61、性的影响。寻时间对操作效率就会产生决定性的影响。60算法与数据结构散列结构类类类类10.410.4给出了给出了给出了给出了hashTreehashTree类的规范说明，它也定义类的规范说明，它也定义类的规范说明，它也定义类的规范说明，它也定义为为为为bucketHashVectorbucketHashVector的子类。这个类中采用第的子类。这个类中采用第的子类。这个类中采用第的子类。这个类中采用第七章中讨论的七章中讨论的七章中讨论的七章中讨论的AVLAVL树作为类型参数树作为类型参数树作为类型参数树作为类型参数B B的实现类型。的实现类型。的实现类型。的实现类型。这样做无论桶的大小如何变化，
62、都可以较好地保这样做无论桶的大小如何变化，都可以较好地保这样做无论桶的大小如何变化，都可以较好地保这样做无论桶的大小如何变化，都可以较好地保证桶内的查寻效率。在这个类里定义了插入、删证桶内的查寻效率。在这个类里定义了插入、删证桶内的查寻效率。在这个类里定义了插入、删证桶内的查寻效率。在这个类里定义了插入、删除、包含测试三个成员函数，并提供了实际的构除、包含测试三个成员函数，并提供了实际的构除、包含测试三个成员函数，并提供了实际的构除、包含测试三个成员函数，并提供了实际的构造函数和一个桶遍历器生成函数。造函数和一个桶遍历器生成函数。造函数和一个桶遍历器生成函数。造函数和一个桶遍历器生成函数。 6
63、1算法与数据结构散列结构templateclasshashTree:publictemplateclasshashTree:publicbucketHashVectoravlTree,T,TbucketHashVectoravlTree,T,T public:public:/构造函数构造函数构造函数构造函数hashTree(unsignedintmax,unsignedint(hashTree(unsignedintmax,unsignedint( f)(constTf)(constT&);&);voidadd(Tnewele);/voidadd(Tnewele);/增加一元素增加一元素增加一
64、元素增加一元素intincludes(Tele)const;/intincludes(Tele)const;/元素包含元素包含元素包含元素包含voidremove(Tele);/voidremove(Tele);/删除一元素删除一元素删除一元素删除一元素protected:protected:virtualiteratorvirtualiterator makeIterator(unsignedinti);makeIterator(unsignedinti); ;类类类类10.410.4hashTreehashTree类的规范说明（用类的规范说明（用类的规范说明（用类的规范说明（用AVLAVL
65、树作桶实现散列表）树作桶实现散列表）树作桶实现散列表）树作桶实现散列表） 62算法与数据结构散列结构在桶散列表里增加或删除元素，采用的实现方式在桶散列表里增加或删除元素，采用的实现方式在桶散列表里增加或删除元素，采用的实现方式在桶散列表里增加或删除元素，采用的实现方式应该与检测元素是否在散列表中类似：首先调用应该与检测元素是否在散列表中类似：首先调用应该与检测元素是否在散列表中类似：首先调用应该与检测元素是否在散列表中类似：首先调用散列函数完成桶的选择，然后对选定的桶进行具散列函数完成桶的选择，然后对选定的桶进行具散列函数完成桶的选择，然后对选定的桶进行具散列函数完成桶的选择，然后对选定的桶进
66、行具体操作。体操作。体操作。体操作。hashTreehashTree类里桶的类型已经确定，这类里桶的类型已经确定，这类里桶的类型已经确定，这类里桶的类型已经确定，这些操作的实现都非常简单。下面是些操作的实现都非常简单。下面是些操作的实现都非常简单。下面是些操作的实现都非常简单。下面是addadd操作的实操作的实操作的实操作的实现。现。现。现。 63算法与数据结构散列结构templatevoidhashTree:add(TtemplatevoidhashTree:add(Tnewele)newele)/先找到合适的桶，再把元素插入桶中先找到合适的桶，再把元素插入桶中先找到合适的桶，再把元素插入桶
67、中先找到合适的桶，再把元素插入桶中bucketshash(newele).add(newele);bucketshash(newele).add(newele); 64算法与数据结构散列结构10.4.310.4.3桶散列结构操作时间的分析桶散列结构操作时间的分析桶散列结构操作时间的分析桶散列结构操作时间的分析人们经常使用桶散列表结构，一个重要原因是在人们经常使用桶散列表结构，一个重要原因是在人们经常使用桶散列表结构，一个重要原因是在人们经常使用桶散列表结构，一个重要原因是在这种结构上各种操作的执行效率比较高。但是，这种结构上各种操作的执行效率比较高。但是，这种结构上各种操作的执行效率比较高。但
68、是，这种结构上各种操作的执行效率比较高。但是，另一方面，这种散列结构操作的执行时间估计却另一方面，这种散列结构操作的执行时间估计却另一方面，这种散列结构操作的执行时间估计却另一方面，这种散列结构操作的执行时间估计却比较复杂，它一方面与选定的散列函数和实际关比较复杂，它一方面与选定的散列函数和实际关比较复杂，它一方面与选定的散列函数和实际关比较复杂，它一方面与选定的散列函数和实际关键码的分布情况有关，另一方面又与结构的具体键码的分布情况有关，另一方面又与结构的具体键码的分布情况有关，另一方面又与结构的具体键码的分布情况有关，另一方面又与结构的具体设计有关。后者又不但受到桶类型选择的影响，设计有关
69、。后者又不但受到桶类型选择的影响，设计有关。后者又不但受到桶类型选择的影响，设计有关。后者又不但受到桶类型选择的影响，也受到桶的个数即向量大小的影响。也受到桶的个数即向量大小的影响。也受到桶的个数即向量大小的影响。也受到桶的个数即向量大小的影响。65算法与数据结构散列结构首先看桶的数目对处理速度的影响。很明显：桶首先看桶的数目对处理速度的影响。很明显：桶首先看桶的数目对处理速度的影响。很明显：桶首先看桶的数目对处理速度的影响。很明显：桶散列表里的桶越少，发生碰撞的可能性就越大。散列表里的桶越少，发生碰撞的可能性就越大。散列表里的桶越少，发生碰撞的可能性就越大。散列表里的桶越少，发生碰撞的可能性
70、就越大。 对桶个数的选择还有另一个需要考虑的因素：为对桶个数的选择还有另一个需要考虑的因素：为对桶个数的选择还有另一个需要考虑的因素：为对桶个数的选择还有另一个需要考虑的因素：为使实际元素的关键码能较均匀地映射到各桶里，使实际元素的关键码能较均匀地映射到各桶里，使实际元素的关键码能较均匀地映射到各桶里，使实际元素的关键码能较均匀地映射到各桶里，人们经常将桶的个数取定为某个素数，也用它作人们经常将桶的个数取定为某个素数，也用它作人们经常将桶的个数取定为某个素数，也用它作人们经常将桶的个数取定为某个素数，也用它作为散列函数的最后数值范围。为散列函数的最后数值范围。为散列函数的最后数值范围。为散列函
71、数的最后数值范围。66算法与数据结构散列结构其次，桶类型的选择对处理速度的影响也是显然其次，桶类型的选择对处理速度的影响也是显然其次，桶类型的选择对处理速度的影响也是显然其次，桶类型的选择对处理速度的影响也是显然的。在根据关键码选定某个桶后，下一步处理的的。在根据关键码选定某个桶后，下一步处理的的。在根据关键码选定某个桶后，下一步处理的的。在根据关键码选定某个桶后，下一步处理的速度就依赖于在桶内处理的情况。如果采用速度就依赖于在桶内处理的情况。如果采用速度就依赖于在桶内处理的情况。如果采用速度就依赖于在桶内处理的情况。如果采用AVLAVL树类型的桶，桶内查找元素的平均时间代价是树类型的桶，桶内
72、查找元素的平均时间代价是树类型的桶，桶内查找元素的平均时间代价是树类型的桶，桶内查找元素的平均时间代价是OO(log(logk k)( )(这里这里这里这里k k是桶内元素个数是桶内元素个数是桶内元素个数是桶内元素个数) )；如果用简单链；如果用简单链；如果用简单链；如果用简单链表结构作为桶，桶内查找元素就需要表结构作为桶，桶内查找元素就需要表结构作为桶，桶内查找元素就需要表结构作为桶，桶内查找元素就需要OO( (k k) )时间。时间。时间。时间。67算法与数据结构散列结构在所有有关因素中，最难分析的是散列函数的影在所有有关因素中，最难分析的是散列函数的影在所有有关因素中，最难分析的是散列函
73、数的影在所有有关因素中，最难分析的是散列函数的影响。由于散列表的内容是不断变化的，插入和删响。由于散列表的内容是不断变化的，插入和删响。由于散列表的内容是不断变化的，插入和删响。由于散列表的内容是不断变化的，插入和删除的关键码不能事先确定，对一个选定的散列函除的关键码不能事先确定，对一个选定的散列函除的关键码不能事先确定，对一个选定的散列函除的关键码不能事先确定，对一个选定的散列函数，它某时刻可能正好把所有元素均匀映射到各数，它某时刻可能正好把所有元素均匀映射到各数，它某时刻可能正好把所有元素均匀映射到各数，它某时刻可能正好把所有元素均匀映射到各个桶中，而另一时刻也可能把所有元素都映射到个桶中
74、，而另一时刻也可能把所有元素都映射到个桶中，而另一时刻也可能把所有元素都映射到个桶中，而另一时刻也可能把所有元素都映射到同一个桶里。这里还有一个重要因素，那就是散同一个桶里。这里还有一个重要因素，那就是散同一个桶里。这里还有一个重要因素，那就是散同一个桶里。这里还有一个重要因素，那就是散列函数本身的计算复杂性。列函数本身的计算复杂性。列函数本身的计算复杂性。列函数本身的计算复杂性。68算法与数据结构散列结构设在一个桶散列表里有设在一个桶散列表里有设在一个桶散列表里有设在一个桶散列表里有n n个元素、个元素、个元素、个元素、mm个桶，如果散列函数个桶，如果散列函数个桶，如果散列函数个桶，如果散列
75、函数具有最理想的效果，每个桶中应该有大约具有最理想的效果，每个桶中应该有大约具有最理想的效果，每个桶中应该有大约具有最理想的效果，每个桶中应该有大约n n/ /mm个元素。个元素。个元素。个元素。假定散列函数的计算时间是常量，确定一个元素对应的假定散列函数的计算时间是常量，确定一个元素对应的假定散列函数的计算时间是常量，确定一个元素对应的假定散列函数的计算时间是常量，确定一个元素对应的桶里只需要常数时间，那么，在这个散列表里增加一个桶里只需要常数时间，那么，在这个散列表里增加一个桶里只需要常数时间，那么，在这个散列表里增加一个桶里只需要常数时间，那么，在这个散列表里增加一个元素，花费的时间主要
76、就是向一个有元素，花费的时间主要就是向一个有元素，花费的时间主要就是向一个有元素，花费的时间主要就是向一个有n n/ /mm个元素的桶中个元素的桶中个元素的桶中个元素的桶中增加一个元素所需要的时间。对于有增加一个元素所需要的时间。对于有增加一个元素所需要的时间。对于有增加一个元素所需要的时间。对于有k k个元素的个元素的个元素的个元素的AVLAVL树而树而树而树而言，加一个元素的时间代价是言，加一个元素的时间代价是言，加一个元素的时间代价是言，加一个元素的时间代价是( (loglogk k) )，这意味着在对这意味着在对这意味着在对这意味着在对应散列结构里，增加一个元素的时间为应散列结构里，增
77、加一个元素的时间为应散列结构里，增加一个元素的时间为应散列结构里，增加一个元素的时间为( (loglogn n/ /mm) )。如如如如果加入表中的数据元素个数有限，能够保证果加入表中的数据元素个数有限，能够保证果加入表中的数据元素个数有限，能够保证果加入表中的数据元素个数有限，能够保证n n/ /mm非常小，非常小，非常小，非常小，在一定的限制范围里在一定的限制范围里在一定的限制范围里在一定的限制范围里( (loglogn n/ /mm) )几乎就可以看作常数。几乎就可以看作常数。几乎就可以看作常数。几乎就可以看作常数。69算法与数据结构散列结构10.510.5桶散列结构的遍历器桶散列结构的
78、遍历器桶散列结构的遍历器桶散列结构的遍历器为了遍历一个桶散列表，我们必须遍历表中的每为了遍历一个桶散列表，我们必须遍历表中的每为了遍历一个桶散列表，我们必须遍历表中的每为了遍历一个桶散列表，我们必须遍历表中的每个桶，因此，对整个结构的遍历过程实际上包含个桶，因此，对整个结构的遍历过程实际上包含个桶，因此，对整个结构的遍历过程实际上包含个桶，因此，对整个结构的遍历过程实际上包含了散列表向量本身的遍历和各个桶的遍历两个层了散列表向量本身的遍历和各个桶的遍历两个层了散列表向量本身的遍历和各个桶的遍历两个层了散列表向量本身的遍历和各个桶的遍历两个层次。要实现这种遍历过程，在桶散列表遍历器里次。要实现这
79、种遍历过程，在桶散列表遍历器里次。要实现这种遍历过程，在桶散列表遍历器里次。要实现这种遍历过程，在桶散列表遍历器里就必须必须保存两个值，以便能刻画遍历过程的就必须必须保存两个值，以便能刻画遍历过程的就必须必须保存两个值，以便能刻画遍历过程的就必须必须保存两个值，以便能刻画遍历过程的当前进展情况：一个值是当时正在被遍历的那个当前进展情况：一个值是当时正在被遍历的那个当前进展情况：一个值是当时正在被遍历的那个当前进展情况：一个值是当时正在被遍历的那个桶的下标；另一个值是个指针，它指向在桶散列桶的下标；另一个值是个指针，它指向在桶散列桶的下标；另一个值是个指针，它指向在桶散列桶的下标；另一个值是个指
80、针，它指向在桶散列表遍历过程中动态生成的当前桶的遍历器。表遍历过程中动态生成的当前桶的遍历器。表遍历过程中动态生成的当前桶的遍历器。表遍历过程中动态生成的当前桶的遍历器。70算法与数据结构散列结构 templateclassbucketHashVectorIterator:templateclassbucketHashVectorIterator:publiciteratorpubliciterator public:public:/构造函数构造函数构造函数构造函数bucketHashVectorIterator(bucketHashVector&v);bucketHashVectorIter
81、ator(bucketHashVector&v);bucketHashVectorIterator(constbucketHashVectorIterator&);bucketHashVectorIterator(constbucketHashVectorIterator&);/遍历器原型遍历器原型遍历器原型遍历器原型 virtualintinit();virtualintinit();virtualToperator()();virtualToperator()();virtualintoperator!();virtualintoperator!();virtualintoperator+
82、();virtualintoperator+();virtualvoidoperator=(Tvalue);virtualvoidoperator=(Tvalue);protected:protected:constbucketHashVector&base;constbucketHashVector&base;unsignedintcurrentIndex;unsignedintcurrentIndex;iteratoriterator itr;itr;intgetNextIterator();intgetNextIterator(); ;类类类类10.510.5bucketHashVect
83、orIteratorbucketHashVectorIterator类的规范说明类的规范说明类的规范说明类的规范说明 71算法与数据结构散列结构在开始散列表遍历时，首先必须创建一个桶遍历器。在开始散列表遍历时，首先必须创建一个桶遍历器。在开始散列表遍历时，首先必须创建一个桶遍历器。在开始散列表遍历时，首先必须创建一个桶遍历器。由于未必每个桶都实际存有元素，所以在创建遍历器由于未必每个桶都实际存有元素，所以在创建遍历器由于未必每个桶都实际存有元素，所以在创建遍历器由于未必每个桶都实际存有元素，所以在创建遍历器时就需要进行检查，可能要连续检测若干个桶才能找时就需要进行检查，可能要连续检测若干个桶才
84、能找时就需要进行检查，可能要连续检测若干个桶才能找时就需要进行检查，可能要连续检测若干个桶才能找到第一个非空的桶。创建遍历器的工作由到第一个非空的桶。创建遍历器的工作由到第一个非空的桶。创建遍历器的工作由到第一个非空的桶。创建遍历器的工作由getNextIteratorgetNextIterator函数完成。函数完成。函数完成。函数完成。 72算法与数据结构散列结构templateintbucketHashVectorIterator:inittemplateintbucketHashVectorIterator:init()()/初始化遍历器初始化遍历器初始化遍历器初始化遍历器current
85、Index=0;/currentIndex=0;/寻找第一个桶寻找第一个桶寻找第一个桶寻找第一个桶itr=0;itr=0;returngetNextIterator();returngetNextIterator(); 73算法与数据结构散列结构templateintbucketHashVectorIterator:getNextIteratortemplateintbucketHashVectorIterator:getNextIterator()()/如果存在旧遍历器则删除如果存在旧遍历器则删除如果存在旧遍历器则删除如果存在旧遍历器则删除if(itr!=0)deleteitr;if(itr
86、!=0)deleteitr;/寻找一个新的遍历器寻找一个新的遍历器寻找一个新的遍历器寻找一个新的遍历器for(;currentIndexbase.tablesize;for(;currentIndexinit()return1;if(itr-init()return1;/否则删除它，再试下一个桶否则删除它，再试下一个桶否则删除它，再试下一个桶否则删除它，再试下一个桶deleteitr;deleteitr;/没有下一个有效遍历器时结束没有下一个有效遍历器时结束没有下一个有效遍历器时结束没有下一个有效遍历器时结束itr=0;itr=0;return0;return0; 74算法与数据结构散列结构在
87、递增运算中也会遇到类似的情况，如果当前桶在递增运算中也会遇到类似的情况，如果当前桶在递增运算中也会遇到类似的情况，如果当前桶在递增运算中也会遇到类似的情况，如果当前桶的遍历器本身还能执行增量操作，那么这个遍历的遍历器本身还能执行增量操作，那么这个遍历的遍历器本身还能执行增量操作，那么这个遍历的遍历器本身还能执行增量操作，那么这个遍历器所访问的元素就是下一个元素；否则就需要调器所访问的元素就是下一个元素；否则就需要调器所访问的元素就是下一个元素；否则就需要调器所访问的元素就是下一个元素；否则就需要调用用用用getNextIteratorgetNextIterator函数，到随后的桶中去寻找下函数
88、，到随后的桶中去寻找下函数，到随后的桶中去寻找下函数，到随后的桶中去寻找下一个元素。一个元素。一个元素。一个元素。 75算法与数据结构散列结构templateintbucketHashVectorIterator:operator+templateintbucketHashVectorIterator:operator+()()/检查当前遍历器是否还能找到下一个元素检查当前遍历器是否还能找到下一个元素检查当前遍历器是否还能找到下一个元素检查当前遍历器是否还能找到下一个元素if(itr&(if(itr&( itr)+)return1;itr)+)return1;/若不能，则转到下一个遍历器若不能
89、，则转到下一个遍历器若不能，则转到下一个遍历器若不能，则转到下一个遍历器currentIndex+;currentIndex+;returngetNextIterator();returngetNextIterator(); 76算法与数据结构散列结构bucketHashVectorIteratorbucketHashVectorIterator类的子类也只是对其类的子类也只是对其类的子类也只是对其类的子类也只是对其父类的一些标识符换名。下面给出散列树遍历器父类的一些标识符换名。下面给出散列树遍历器父类的一些标识符换名。下面给出散列树遍历器父类的一些标识符换名。下面给出散列树遍历器类的定义，其
90、中散列树是桶类为类的定义，其中散列树是桶类为类的定义，其中散列树是桶类为类的定义，其中散列树是桶类为AVLAVL树的桶散列树的桶散列树的桶散列树的桶散列表。表。表。表。 77算法与数据结构散列结构templateclasshashTreeIteratortemplateclasshashTreeIterator:public:publicbucketHashVectorIteratoravlTree,T,TbucketHashVectorIteratoravlTree,T,T public:public:hashTreeIterator(hashTree&x);hashTreeIterator
91、(hashTree&x); ; 78算法与数据结构散列结构templatetemplatehashTreeIterator:hashTreeIteratorhashTreeIterator:hashTreeIterator(hashTree&x):(hashTree&x):bucketHashVectorIteratoravlTree,T,T(x)bucketHashVectorIteratoravlTree,T,T(x)79算法与数据结构散列结构10.610.6用散列表实现集合用散列表实现集合用散列表实现集合用散列表实现集合采用存储桶方式的散列表，元素分别放在各个桶采用存储桶方式的散列表，元
92、素分别放在各个桶采用存储桶方式的散列表，元素分别放在各个桶采用存储桶方式的散列表，元素分别放在各个桶里，每桶存放若干元素。考察元素时首先用散列里，每桶存放若干元素。考察元素时首先用散列里，每桶存放若干元素。考察元素时首先用散列里，每桶存放若干元素。考察元素时首先用散列函数确定对应的桶，然后再进行桶内操作。函数确定对应的桶，然后再进行桶内操作。函数确定对应的桶，然后再进行桶内操作。函数确定对应的桶，然后再进行桶内操作。这种实现方法的一个优点是能有效地实现集合求这种实现方法的一个优点是能有效地实现集合求这种实现方法的一个优点是能有效地实现集合求这种实现方法的一个优点是能有效地实现集合求并与求交等运
93、算，对两个集合的操作可以通过两并与求交等运算，对两个集合的操作可以通过两并与求交等运算，对两个集合的操作可以通过两并与求交等运算，对两个集合的操作可以通过两个集合中对应的各对桶的操作完成。个集合中对应的各对桶的操作完成。个集合中对应的各对桶的操作完成。个集合中对应的各对桶的操作完成。80算法与数据结构散列结构类类类类10.710.7是基于桶散列表定义的集合的规范，提供的是基于桶散列表定义的集合的规范，提供的是基于桶散列表定义的集合的规范，提供的是基于桶散列表定义的集合的规范，提供的操作包括相关的插入、删除、判断元素包含关系等操作包括相关的插入、删除、判断元素包含关系等操作包括相关的插入、删除、
94、判断元素包含关系等操作包括相关的插入、删除、判断元素包含关系等等，要实现这些运算，只需把有关参数散列到适当等，要实现这些运算，只需把有关参数散列到适当等，要实现这些运算，只需把有关参数散列到适当等，要实现这些运算，只需把有关参数散列到适当的桶里，然后再在各个桶中进行下一步的操作。的桶里，然后再在各个桶中进行下一步的操作。的桶里，然后再在各个桶中进行下一步的操作。的桶里，然后再在各个桶中进行下一步的操作。 81算法与数据结构散列结构templateclasssetTable:publictemplateclasssetTable:publicbucketHashVectorsetList,T,T
95、bucketHashVectorsetList,T,T public:public:/构造函数构造函数构造函数构造函数setTable(unsignedintmax,unsignedint(setTable(unsignedintmax,unsignedint( f)(constT&);f)(constT&);/成员函数成员函数成员函数成员函数voidvoidadd(Tval);add(Tval);voidvoiddifferenceFrom(setTable&);differenceFrom(setTable&);intint includes(Tval)const;includes(Tva
96、l)const;voidvoidintersectWith(setTable&);intersectWith(setTable&);voidvoidremove(Tremove(Tval);val);voidvoidunionWith(setTable&);unionWith(setTable&);intint subset(setTable&)const;subset(setTable&)const;intint operator=(setTable&)const;operator=(setTable&)const;protected:protected:iteratoriterator m
97、akeIterator(unsignedinti);makeIterator(unsignedinti); ;类类类类10.710.7setTablesetTable类的规范说明。类的规范说明。类的规范说明。类的规范说明。82算法与数据结构散列结构这里我们没有把这里我们没有把这里我们没有把这里我们没有把setTablesetTable定义为定义为定义为定义为setset类的子类，类的子类，类的子类，类的子类，主要是考虑集合操作的效率，考虑到上面提出的主要是考虑集合操作的效率，考虑到上面提出的主要是考虑集合操作的效率，考虑到上面提出的主要是考虑集合操作的效率，考虑到上面提出的集合运算实现方式。如
98、果把一个桶散列表作为这集合运算实现方式。如果把一个桶散列表作为这集合运算实现方式。如果把一个桶散列表作为这集合运算实现方式。如果把一个桶散列表作为这个集合的数据成分，程序里就不能直接访问其中个集合的数据成分，程序里就不能直接访问其中个集合的数据成分，程序里就不能直接访问其中个集合的数据成分，程序里就不能直接访问其中的各个桶了。在这里采用了继承方式，把的各个桶了。在这里采用了继承方式，把的各个桶了。在这里采用了继承方式，把的各个桶了。在这里采用了继承方式，把bucketHashVectorbucketHashVector作为基类，集合的有关操作作为基类，集合的有关操作作为基类，集合的有关操作作为
99、基类，集合的有关操作都可以通过直接访问都可以通过直接访问都可以通过直接访问都可以通过直接访问bucketHashVectorbucketHashVector的数据的数据的数据的数据成分成分成分成分bucketsbuckets而实现。而实现。而实现。而实现。83算法与数据结构散列结构下面是一些操作的实现：下面是一些操作的实现：下面是一些操作的实现：下面是一些操作的实现： templatevoidsetTable:add(Tval)templatevoidsetTable:add(Tval) bucketshash(val).add(val);bucketshash(val).add(val);
100、templatesetTable:includes(Tval)templatesetTable:includes(Tval)constconst returnbucketshash(val).includes(val);returnbucketshash(val).includes(val); 84算法与数据结构散列结构求并集和交集的运算，通过对桶向量进行循环，一桶一桶求并集和交集的运算，通过对桶向量进行循环，一桶一桶求并集和交集的运算，通过对桶向量进行循环，一桶一桶求并集和交集的运算，通过对桶向量进行循环，一桶一桶地实施相应操作来完成。地实施相应操作来完成。地实施相应操作来完成。地实施相应操
101、作来完成。 templatevoidtemplatevoidsetTable:unionWith(setTable&right)setTable:unionWith(setTable&right) assert(tablesize=right.tablesize);assert(tablesize=right.tablesize);for(inti=0;itablesize;i+)for(inti=0;itablesize;i+)bucketsi.unionWith(right.bucketsi);bucketsi.unionWith(right.bucketsi); 85算法与数据结构散列结
102、构templateinttemplateintsetTable:subset(setTable&right)setTable:subset(setTable&right) assert(tablesize=right.tablesize);assert(tablesize=right.tablesize);for(inti=0;itablesize;i+)for(inti=0;itablesize;i+)if(!bucketsi.subset(right.bucketsi)if(!bucketsi.subset(right.bucketsi)return0;return0;return1;re
103、turn1; 86算法与数据结构散列结构注意，在上面实现中，参加运算的两个集合注意，在上面实现中，参加运算的两个集合注意，在上面实现中，参加运算的两个集合注意，在上面实现中，参加运算的两个集合( (接接接接受者和参数受者和参数受者和参数受者和参数) )必须同是必须同是必须同是必须同是setTablesetTable类型。实际上，类型。实际上，类型。实际上，类型。实际上，这里不仅要求它们都是桶散列表，而且要求它们这里不仅要求它们都是桶散列表，而且要求它们这里不仅要求它们都是桶散列表，而且要求它们这里不仅要求它们都是桶散列表，而且要求它们具有相同的散列函数，相同的桶类型和具有相同的散列函数，相同的
104、桶类型和具有相同的散列函数，相同的桶类型和具有相同的散列函数，相同的桶类型和tablesizetablesize值。只有这样才能保证操作的正确性值。只有这样才能保证操作的正确性值。只有这样才能保证操作的正确性值。只有这样才能保证操作的正确性87算法与数据结构散列结构10.710.7用桶散列表实现字典用桶散列表实现字典用桶散列表实现字典用桶散列表实现字典下面用的是继承方式，从下面用的是继承方式，从下面用的是继承方式，从下面用的是继承方式，从bucketHashVectorbucketHashVector类类类类出发建立出发建立出发建立出发建立dictionaryTabledictionaryTa
105、ble类。类。类。类。dictionaryTabledictionaryTable类从类从类从类从bucketHashVectorbucketHashVector类那里继承了所有行为，类那里继承了所有行为，类那里继承了所有行为，类那里继承了所有行为，定义了作为字典的必要操作。定义了作为字典的必要操作。定义了作为字典的必要操作。定义了作为字典的必要操作。88算法与数据结构散列结构templateclassdictionaryTable:publictemplateclassdictionaryTable:publicbucketHashVectordictionaryList,K,associa
106、tionbucketHashVectordictionaryList,K,association public:public:/构造函数构造函数构造函数构造函数dictionaryTable(unsignedintmax,unsignedint(dictionaryTable(unsignedintmax,unsignedint( f)(constf)(constK&);K&);dictionaryTable(unsignedintmax,unsignedint(dictionaryTable(unsignedintmax,unsignedint( f)(constf)(constK&),V&
107、);K&),V&);/新的新的新的新的dictionaryTabledictionaryTable类的操作类的操作类的操作类的操作V&operator(Kkey);V&operator(Kkey);voidremoveKey(Kkey);voidremoveKey(Kkey);voidsetInitial(VinitialValue);voidsetInitial(VinitialValue);protected:protected:iteratorassociationiteratorassociation makeIterator(unsignedmakeIterator(unsigned
108、inti);inti); 类类类类10.810.8dictionaryTabledictionaryTable类的规范说明类的规范说明类的规范说明类的规范说明 89算法与数据结构散列结构我们在这里没有把我们在这里没有把我们在这里没有把我们在这里没有把dictionaryTabledictionaryTable类定义为类定义为类定义为类定义为dictionarydictionary类的子类，考虑的问题与前面定义类的子类，考虑的问题与前面定义类的子类，考虑的问题与前面定义类的子类，考虑的问题与前面定义setTablesetTable时类似。时类似。时类似。时类似。 90算法与数据结构散列结构 te
109、mplatedictionaryTabletemplatedictionaryTable:dictionaryTable:dictionaryTable(unsignedintmax,unsignedint(unsignedintmax,unsignedint( f)(constK&),V&f)(constK&),V&v)v):bucketHashVectordictionaryList,:bucketHashVectordictionaryList,K,associationK,association (max,f)(max,f)/在每一个桶中置初值在每一个桶中置初值在每一个桶中置初值在每一
110、个桶中置初值setInitial(v);setInitial(v); 91算法与数据结构散列结构成员函数成员函数成员函数成员函数setInitialsetInitial设置各个桶的初值。注意桶的设置各个桶的初值。注意桶的设置各个桶的初值。注意桶的设置各个桶的初值。注意桶的类型是类型是类型是类型是dictionaryListdictionaryList，实现这里的初值设置，实现这里的初值设置，实现这里的初值设置，实现这里的初值设置，只要对每个桶只要对每个桶只要对每个桶只要对每个桶( (bucketsi)bucketsi)执行执行执行执行dictionaryListdictionaryList类的
111、类的类的类的setInitialsetInitial函数即可。函数即可。函数即可。函数即可。 92算法与数据结构散列结构templatevoidtemplatevoiddictionaryTable:setInitial(Vval)dictionaryTable:setInitial(Vval)/在每一个桶中置初值在每一个桶中置初值在每一个桶中置初值在每一个桶中置初值for(inti=0;itablesize;i+)for(inti=0;itablesize;i+)bucketsi.setInitial(val);bucketsi.setInitial(val); 93算法与数据结构散列结构下
112、标操作和下标操作和下标操作和下标操作和removeKeyremoveKey函数的实现很简单，先函数的实现很简单，先函数的实现很简单，先函数的实现很简单，先根据给定关键码确定桶对象根据给定关键码确定桶对象根据给定关键码确定桶对象根据给定关键码确定桶对象( (dictionaryListdictionaryList类类类类的对象的对象的对象的对象) )，然后对该桶执行下标或，然后对该桶执行下标或，然后对该桶执行下标或，然后对该桶执行下标或removeKeyremoveKey操操操操作。作。作。作。 94算法与数据结构散列结构templateV&templateV&dictionaryTable:o
113、perator(Kkey)dictionaryTable:operator(Kkey)/寻找正确的字典，然后对字典进行下标操作寻找正确的字典，然后对字典进行下标操作寻找正确的字典，然后对字典进行下标操作寻找正确的字典，然后对字典进行下标操作returnbucketshash(key)key;returnbucketshash(key)key; templatevoidtemplatevoiddictionaryTable:removeKey(Kkey)dictionaryTable:removeKey(Kkey)/寻找正确的桶，然后删除该元素寻找正确的桶，然后删除该元素寻找正确的桶，然后删除该
114、元素寻找正确的桶，然后删除该元素bucketshash(key).removeKey(key);bucketshash(key).removeKey(key); 95算法与数据结构散列结构注意，在注意，在注意，在注意，在dictionaryTabledictionaryTable类中，继承而来的类中，继承而来的类中，继承而来的类中，继承而来的bucketHashVectorbucketHashVector类的第二、第三个模板参数类的第二、第三个模板参数类的第二、第三个模板参数类的第二、第三个模板参数具有不同类型，这一点与前面使用具有不同类型，这一点与前面使用具有不同类型，这一点与前面使用具有不
115、同类型，这一点与前面使用bucketHashVectorbucketHashVector类的情况都不同。这里对关类的情况都不同。这里对关类的情况都不同。这里对关类的情况都不同。这里对关键码进行散列处理，而遍历器的返回值是对关联键码进行散列处理，而遍历器的返回值是对关联键码进行散列处理，而遍历器的返回值是对关联键码进行散列处理，而遍历器的返回值是对关联的引用。的引用。的引用。的引用。96算法与数据结构散列结构templateclasstemplateclassdictionaryTableIteratordictionaryTableIterator:publicbucketHashVector
116、IteratordictionaryList:publicbucketHashVectorIteratordictionaryList,K,association,K,association public:public:/构造函数构造函数构造函数构造函数dictionaryTableIterator(dictionaryTable&dictionaryTableIterator(dictionaryTable&v);v); ;类类类类10.910.9dictionaryTableIteratordictionaryTableIterator类类类类 97算法与数据结构散列结构新类的构造函数非常
117、简单，只要将被遍历字典新类的构造函数非常简单，只要将被遍历字典新类的构造函数非常简单，只要将被遍历字典新类的构造函数非常简单，只要将被遍历字典( (函数参数函数参数函数参数函数参数d)d)从原来的从原来的从原来的从原来的dictionaryTabledictionaryTable类类类类型转换成型转换成型转换成型转换成( (实际上仅是把它看作实际上仅是把它看作实际上仅是把它看作实际上仅是把它看作) )98算法与数据结构散列结构bucketHashVectordictionaryList,K,associatibucketHashVectordictionaryList,K,associatio
118、non 类型的对象，对它直接调用类型的对象，对它直接调用类型的对象，对它直接调用类型的对象，对它直接调用bucketHashVectorIteratorbucketHashVectorIterator类的构造函数。类的构造函数。类的构造函数。类的构造函数。 templatedictionaryTableIteratortemplatedictionaryTableIterator:K,V:dictionaryTableIterator(dictionaryTable&dictionaryTableIterator(dictionaryTable&d):d):bucketHashVectorIt
119、eratordictionaryList,bucketHashVectorIteratordictionaryList,K,associationK,association (d)(d)/没有进一步动作没有进一步动作没有进一步动作没有进一步动作 99算法与数据结构散列结构小小小小 结结结结散列方法的基本思想就是用某个函数将关键码值散列方法的基本思想就是用某个函数将关键码值散列方法的基本思想就是用某个函数将关键码值散列方法的基本思想就是用某个函数将关键码值转换成整数，这一思想是构造一类非常有效的数转换成整数，这一思想是构造一类非常有效的数转换成整数，这一思想是构造一类非常有效的数转换成整数，这一
120、思想是构造一类非常有效的数据结构的基础。如果能找到关键码集合与整型下据结构的基础。如果能找到关键码集合与整型下据结构的基础。如果能找到关键码集合与整型下据结构的基础。如果能找到关键码集合与整型下标之间的一对一映射关系，那么就能直接构造出标之间的一对一映射关系，那么就能直接构造出标之间的一对一映射关系，那么就能直接构造出标之间的一对一映射关系，那么就能直接构造出使用非整型关键码作为使用非整型关键码作为使用非整型关键码作为使用非整型关键码作为“ “下标下标下标下标” ”的散列向量。在的散列向量。在的散列向量。在的散列向量。在大部分情况下，散列函数可能会把多个关键码映大部分情况下，散列函数可能会把多
121、个关键码映大部分情况下，散列函数可能会把多个关键码映大部分情况下，散列函数可能会把多个关键码映射到同一个整型下标，不同的关键码出现相同散射到同一个整型下标，不同的关键码出现相同散射到同一个整型下标，不同的关键码出现相同散射到同一个整型下标，不同的关键码出现相同散列值的情况称为碰撞。为了解决碰撞问题，当元列值的情况称为碰撞。为了解决碰撞问题，当元列值的情况称为碰撞。为了解决碰撞问题，当元列值的情况称为碰撞。为了解决碰撞问题，当元素不太多时，可以才用开地址散列的处理方法。素不太多时，可以才用开地址散列的处理方法。素不太多时，可以才用开地址散列的处理方法。素不太多时，可以才用开地址散列的处理方法。另
122、一个很有效的方法是把向量元素设计成桶的形另一个很有效的方法是把向量元素设计成桶的形另一个很有效的方法是把向量元素设计成桶的形另一个很有效的方法是把向量元素设计成桶的形式，每个桶中存放具有相同散列值的元素。这样式，每个桶中存放具有相同散列值的元素。这样式，每个桶中存放具有相同散列值的元素。这样式，每个桶中存放具有相同散列值的元素。这样得到的数据结构便被称为桶散列表。得到的数据结构便被称为桶散列表。得到的数据结构便被称为桶散列表。得到的数据结构便被称为桶散列表。100算法与数据结构散列结构对于存取和搜索等操作而言，如果下标的集合足对于存取和搜索等操作而言，如果下标的集合足对于存取和搜索等操作而言，
123、如果下标的集合足对于存取和搜索等操作而言，如果下标的集合足够大，散列表可能是一种最快的数据结构。但是，够大，散列表可能是一种最快的数据结构。但是，够大，散列表可能是一种最快的数据结构。但是，够大，散列表可能是一种最快的数据结构。但是，散列表的效率还依赖于散列函数的选择。一个好散列表的效率还依赖于散列函数的选择。一个好散列表的效率还依赖于散列函数的选择。一个好散列表的效率还依赖于散列函数的选择。一个好的散列函数应将元素比较均匀地放入各个桶中，的散列函数应将元素比较均匀地放入各个桶中，的散列函数应将元素比较均匀地放入各个桶中，的散列函数应将元素比较均匀地放入各个桶中，选择散列函数是实现散列表的关键
124、。选择散列函数是实现散列表的关键。选择散列函数是实现散列表的关键。选择散列函数是实现散列表的关键。 101算法与数据结构散列结构除去前一章和本章中介绍的几种集合和字典的实除去前一章和本章中介绍的几种集合和字典的实除去前一章和本章中介绍的几种集合和字典的实除去前一章和本章中介绍的几种集合和字典的实现方法以外，排序表和排序树也是常用的实现方现方法以外，排序表和排序树也是常用的实现方现方法以外，排序表和排序树也是常用的实现方现方法以外，排序表和排序树也是常用的实现方法。用各种方法实现集合的各方面特点总结在表法。用各种方法实现集合的各方面特点总结在表法。用各种方法实现集合的各方面特点总结在表法。用各种
125、方法实现集合的各方面特点总结在表10.110.1中（字典的情况与此类似），供读者参考。中（字典的情况与此类似），供读者参考。中（字典的情况与此类似），供读者参考。中（字典的情况与此类似），供读者参考。注意，除了位向量表示方法之外，其他实现方法注意，除了位向量表示方法之外，其他实现方法注意，除了位向量表示方法之外，其他实现方法注意，除了位向量表示方法之外，其他实现方法原则上都可以用来实现包原则上都可以用来实现包原则上都可以用来实现包原则上都可以用来实现包( (或称多重集合或称多重集合或称多重集合或称多重集合) )。102算法与数据结构散列结构字典是关联的集合，也可以看作一种索引结构。字典是关联的
126、集合，也可以看作一种索引结构。字典是关联的集合，也可以看作一种索引结构。字典是关联的集合，也可以看作一种索引结构。字典索引的关键码可以是任何类型，在前一章和字典索引的关键码可以是任何类型，在前一章和字典索引的关键码可以是任何类型，在前一章和字典索引的关键码可以是任何类型，在前一章和这一章里，我们探讨了实现字典的各种实用技术，这一章里，我们探讨了实现字典的各种实用技术，这一章里，我们探讨了实现字典的各种实用技术，这一章里，我们探讨了实现字典的各种实用技术，主要是用表和散列表实现字典的方法。主要是用表和散列表实现字典的方法。主要是用表和散列表实现字典的方法。主要是用表和散列表实现字典的方法。103
127、算法与数据结构散列结构主要概念主要概念主要概念主要概念散列和散列表，散列函数，碰撞，散列向量，开散列和散列表，散列函数，碰撞，散列向量，开散列和散列表，散列函数，碰撞，散列向量，开散列和散列表，散列函数，碰撞，散列向量，开地址散列，桶散列，桶。地址散列，桶散列，桶。地址散列，桶散列，桶。地址散列，桶散列，桶。104算法与数据结构散列结构习习习习 题题题题1.1.解释下列术语：散列、碰撞、开地址散列、桶。解释下列术语：散列、碰撞、开地址散列、桶。解释下列术语：散列、碰撞、开地址散列、桶。解释下列术语：散列、碰撞、开地址散列、桶。2.2.当小杨想加入老马这六个人的组织时，如果原当小杨想加入老马这六
128、个人的组织时，如果原当小杨想加入老马这六个人的组织时，如果原当小杨想加入老马这六个人的组织时，如果原来的向量空间已经放满，能不能简单地用动态改来的向量空间已经放满，能不能简单地用动态改来的向量空间已经放满，能不能简单地用动态改来的向量空间已经放满，能不能简单地用动态改变向量大小的方法去扩大向量空间，然后把小杨变向量大小的方法去扩大向量空间，然后把小杨变向量大小的方法去扩大向量空间，然后把小杨变向量大小的方法去扩大向量空间，然后把小杨的信息插入向量中，为什么？的信息插入向量中，为什么？的信息插入向量中，为什么？的信息插入向量中，为什么？105算法与数据结构散列结构3*.3*.假设对以下假设对以下
129、假设对以下假设对以下1414个关键码设计一个开地址散列向量，个关键码设计一个开地址散列向量，个关键码设计一个开地址散列向量，个关键码设计一个开地址散列向量，6097,3485,8129,407,8136,6617,6615,526,6097,3485,8129,407,8136,6617,6615,526,12287,9535,9173,2134,1903,9912287,9535,9173,2134,1903,99负载因子负载因子负载因子负载因子 =14/19(14/19(即向量大小取即向量大小取即向量大小取即向量大小取19)19)，散列函数取等价映射，按，散列函数取等价映射，按，散列函数取
130、等价映射，按，散列函数取等价映射，按给出的自然顺序对开地址散列向量插入，试给出最终给出的自然顺序对开地址散列向量插入，试给出最终给出的自然顺序对开地址散列向量插入，试给出最终给出的自然顺序对开地址散列向量插入，试给出最终的向量状态。的向量状态。的向量状态。的向量状态。106算法与数据结构散列结构8*.8*.某团体包括以下成员：某团体包括以下成员：某团体包括以下成员：某团体包括以下成员： AbelAbel，AbigailAbigail，AbrahamAbraham，AdaAda，AdrianAdrian，AdamAdam，AdrienneAdrienne，AgiesAgies，AlbertAlb
131、ert，AlexAlex，AlfredAlfred，AliceAlice，AmandaAmanda，AmyAmy，AndrewAndrew，AndyAndy，AngelaAngela，AnitaAnita，AnneAnne，AntoniaAntonia，ArnoldArnold，ArthurArthur，AudreyAudrey。( () )设计一种简单且有效的散列函数，然后算出设计一种简单且有效的散列函数，然后算出设计一种简单且有效的散列函数，然后算出设计一种简单且有效的散列函数，然后算出散列值。散列值。散列值。散列值。( () )按上面散列值将各成员放入桶中，桶号是简按上面散列值将各成员放
132、入桶中，桶号是简按上面散列值将各成员放入桶中，桶号是简按上面散列值将各成员放入桶中，桶号是简单地用除余法确定。当桶散列表的大小取单地用除余法确定。当桶散列表的大小取单地用除余法确定。当桶散列表的大小取单地用除余法确定。当桶散列表的大小取5 5个桶个桶个桶个桶时，桶中各有多少个元素？如果用时，桶中各有多少个元素？如果用时，桶中各有多少个元素？如果用时，桶中各有多少个元素？如果用1111个桶呢？个桶呢？个桶呢？个桶呢？107算法与数据结构散列结构上机实习题：针对本班的人名设计一个上机实习题：针对本班的人名设计一个上机实习题：针对本班的人名设计一个上机实习题：针对本班的人名设计一个hashhash表
133、，表，表，表，使得在对所有同学查找概率相同时，平均查找长使得在对所有同学查找概率相同时，平均查找长使得在对所有同学查找概率相同时，平均查找长使得在对所有同学查找概率相同时，平均查找长度不超过度不超过度不超过度不超过2 2，并实现相应的建表和查表程序。，并实现相应的建表和查表程序。，并实现相应的建表和查表程序。，并实现相应的建表和查表程序。 基本要求基本要求基本要求基本要求 （1 1） 所占的空间尽可能少所占的空间尽可能少所占的空间尽可能少所占的空间尽可能少; ;（2 2） hashhash函数尽可能简单；函数尽可能简单；函数尽可能简单；函数尽可能简单；（3 3） 选择适当的负载因子和不同的选择适当的负载因子和不同的选择适当的负载因子和不同的选择适当的负载因子和不同的hashhash函数函数函数函数, ,比较他们的平均查找长度。在函数确定的前提下，比较他们的平均查找长度。在函数确定的前提下，比较他们的平均查找长度。在函数确定的前提下，比较他们的平均查找长度。在函数确定的前提下，试验各种不同的处理碰撞的方法，考察平均查找试验各种不同的处理碰撞的方法，考察平均查找试验各种不同的处理碰撞的方法，考察平均查找试验各种不同的处理碰撞的方法，考察平均查找长度的变化。长度的变化。长度的变化。长度的变化。 108算法与数据结构散列结构
