算法与数据结构散列结构.ppt

1、第十章 散 列 结 构,算法与数据结构,2,枚举向量，这种向量中使用的下标不是整数，而是某枚举类型的实例。对枚举向量，查询的出发点是一个枚举值，要做就是由这个枚举值出发，确定有关数据元素的存储位置。,算法与数据结构,3,作为查询出发点的值可能有各种不同情况，需要进一步研究有关的技术和方法。在集合与字典的一章里，已经讨论了一些结构和技术，那里使用的基本技术是关键码比较。,算法与数据结构,4,散列结构与枚举向量有类似之处：这里采用的基本存储结构也是一个向量，要做的也是从关键码出发，直接确定数据元素的存储位置。但是散列结构更具一般性，原则上说它允许任意种类的关键码。,算法与数据结构,5,设计良好的散

2、列结构可以具有非常高的操作效率，因此这种结构在计算机领域中应用广泛，是一种非常有效的存储和查询结构。,算法与数据结构,6,下面将首先介绍散列结构的基本思想，然后重点讨论散列结构实现的两个基本要素：散列函数和“碰撞”的各种解决技术。本章的后面部分把散列结构作为集合和字典的重要实现技术，讨论这些方面的有关问题。,算法与数据结构,7,10.1 基本概念,算法与数据结构,8,存储方式和检索方法： 散列函数关键码 地址(固定，连续空间),算法与数据结构,9,“散列”一词的意思是进行某种随机的混合，有的中文教科书或文献中把它称为“杂凑”，对应的英文词是一样的hash。,算法与数据结构,10,散列函数是一种

3、数据转换函数，它的参数应该是某种查询的依据，一般称为“关键词”或“关键码”，而函数返回的是一个无符号整数值，作为确定下标的依据。散列的基本想法就是构造一个对应关系，把每个关键码对应到一个整数（存储位置）。这样，如果需要存储与某个关键码相关的数据，就将它存到与关键码对应的存储位置里去；如果需要查询与某个关键码有关的信息，就到与这个关键码对应的位置中去找。,算法与数据结构,11,“散列”（hash）一词的意思是进行某种混合性的变换，从关键码本身看，这种变换可能并没有很清楚的具体意义。散列这个词在有些中文教科书或文献中被译为“杂凑”，散列结构也被称为“散列表”、“杂凑表”，或者按照音译称为“哈希表”

4、等。,算法与数据结构,12,根据散列函数概念，可以定义一种新向量类，叫作simpleHashVector类（简单散列向量类）。这里把它定义为向量类Vector的一个子类。简单散列向量比普通向量多一个数据成分，那就是一个指向散列函数的指针hashfun。对具体的简单散列向量而言，这个数据成分是在构造时建立，是一种不能改变的性质。,算法与数据结构,13,简单散列向量类有两个类型参数，一个是向量的索引（关键码）类型H，另一个是向量元素类型T。,算法与数据结构,14,template class simpleHashVector : public vectorpublic: /构造函数 simpleH

5、ashVector(int max, int (f)(const H 类10.1 simpleHashVector类规范说明,算法与数据结构,15,简单散列向量类的定义与枚举向量有相似的地方，例如对它们都可以用字符序列形式的向量下标直接存取相关元素。,算法与数据结构,16,但是对于枚举向量，作为下标的字符序列必须是某个枚举类型的值，下标操作的实现是由系统自动将枚举值转换成内部整数值。而对于简单散列向量，则可以使用真正的字符串，这种字符串可以送去打印等。,算法与数据结构,17,在查询元素位置时，散列结构首先用给定的散列函数，把H类型的关键码（可以看作是一种广义“下标”）转换成一个适当的整数值，然

6、后再把该整数转换成对于向量合法的下标值。后一转换一般直接采用按向量大小取余数的方式。,算法与数据结构,18,template T 简单散列向量类的其他成员函数都非常简单。读者不难自己实现它们。10.2 散 列 函 数,算法与数据结构,19,理想的散列函数是个一对一映射，它能把有关的一组关键码映射到连续的一组整数值，每个关键码对应一个整数值，反之依然。,算法与数据结构,20,假设用h(x)代表散列函数，一般来说，h应该满足三个条件： h的定义域是全体可能出现的关键码的集合，h的值域是散列表空间位置(向量下标)的集合； 希望函数值分布对于散列空间位置而言要尽量均匀； h函数应该是足够简单的。,算法

7、与数据结构,21,对一般类型的关键码，运用散列函数的过程通常分成两步：第一步是将关键码转化成适当的整数值；第二步是将得到的整数转化为散列向量的合法下标。,算法与数据结构,22,实现第一步有很多种方法，下面列举常见的几种。1)映射：将关键码以某种数值方式映射成整数值。 对于比较复杂的映射，一般可用一个映射数组来定义。数组中的元素都在程序编制前预先给出。程序执行时，求散列值信息就是在映射数组中找到该元素，对于一组确定的关键码来说，这是产生一个理想的散列函数的基本方法。,算法与数据结构,23,2)折叠：先把关键码分割成小块，各部分的值必要时可以先散列处理，然后再混合起来便形成整个关键码的散列值。 混

8、合又有多种不同的方法，如加法、乘法或逻辑运算。,算法与数据结构,24,下面的小程序段实现了一种把字符串str变成整数值的过程，所用的方法便是将所有字母值加起来。unsigned int hashval = 0;int i = str.length( );while (i 0) hashval += stri;,算法与数据结构,25,3)移位：移位可以避免在折叠处理中由于运算的可交换带来的碰撞。 如上段程序便对apt、tap、pat会产生相同的散列值，而使用移位便可能减少这些碰撞。下面是加入移位处理后的程序段：,算法与数据结构,26,unsigned int hashval = 0;int i

9、= str.length( );while (i 0) hashval = (hashval 1) + str1;,算法与数据结构,27,4)数字分析法：常常有这样的情况：关键码的位数比存储区域的地址码的位数多，同时其中各位的出现不是随机的，在这种情况下可以通过事先对关键码的各位情况进行分析，散列时丢掉分布不均匀的位，留下分布均匀的位。,算法与数据结构,28,例如，需要对下列关键码集合进行转换，实际关键码有9位数字，经过数字分析法可以丢掉6位。 key h(key) 000319426 326 000718309 709 000629443 643 000758615 715 00091049

10、7 997 000310329 329,算法与数据结构,29,这个方法的缺点是散列函数依赖于关键码集合，具体到这6个关键码值，经过分析留下第4、8、9位，若换一个关键码集合，就要重新分析，也许留下第3、6、7位。通过对比较大的实例集合进行分析，就可能得到比较合理的结果。,算法与数据结构,30,散列函数的第二步工作是将已得到的整数值转化成散列表的合法下标值，这时采用最多的是除余法。所谓除余法，就是选择一个恰当的正整数B，用B去除前一步骤得到的整数，取其余数作为散列表的下标值。,算法与数据结构,31,这个方法的关键是选取恰当的B。如果B选为一个偶数，则它将总是把奇整数值转换到奇数的下标，把偶整数值

11、转换到偶数的下标，这当然不太好。选B为10的幂次就更不好，因为那样就等于选择整数的最后几位数字作为地址。例如，选B=100，则实际上就是取整数的最后两位作为地址。,算法与数据结构,32,在实际工作中一般认为选取B为适当的素数为好。例如：B = 7，13，31，61，127，251，503，1019,算法与数据结构,33,除余法的地址计算公式简单。然而实践证明，恰恰是这种简单的方法在许多情况下效果比较好。需要注意的是B的选择，也就是散列表中桶的个数的确定，因为用除余法所计算的结果一定在0 B-1的范围之中。,算法与数据结构,34,同义词负载因子 碰撞（开地址，桶）,算法与数据结构,35,两个关键

12、码散列成相同的值的现象被称为“碰撞”。碰撞的产生使散列的使用产生了问题。,算法与数据结构,36,下面我们先引入“同义词”的概念。设有关键码k1和k2，经过散列函数f的作用，把它们映射成相同的值，即f(k1)= f(k2)，称k1和k2在函数f的解释下含义相同，简称为“同义词”。显然同义词越多，碰撞的可能性就越大。,算法与数据结构,37,另外一个重要概念是“负载因子”。简单地讲，一种结构的负载因子可以定义为这个结构中实际元素的个数与能够容纳的元素个数之比。即： = 结构中实际元素的个数 / 结构中能够容纳的元素个数,算法与数据结构,38,10.3 开地址散列向量,算法与数据结构,39,为了解决碰

13、撞，人们提出了许多方法，本节先介绍其中的一种，称为“开地址法”。用这种方法建立的散列结构称为“开地址散列向量”。,算法与数据结构,40,类10.2给出openHashVector的规范说明。为了叙述简单，我们假设向量中每个元素都只包含关键码自身，元素类型就是关键码类型。这时模板类的参数只需要一个元素类型T（也是关键码类型）；进一步还假设对T类型有一个特定值，这个值不表示任何真正有意义的关键码。因此，如果向量中某元素取这个值，就表明该元素处于空闲状态。,算法与数据结构,41,template class openHashVector public: /构造函数 openHashVector(in

14、t max,int(f)(const T 类10.2 openHashVector类规范说明,算法与数据结构,42,template openHashVector:openHashVector (int max, int(f)(const T ,算法与数据结构,43,template int openHashVector:add (const T ,算法与数据结构,44,template int openHashVector:includes(T ,算法与数据结构,45,开地址散列的思想很简单，但是它的碰撞处理方式也有些缺点。如果碰撞经常发生，插入和查找的时间代价就要增加，特别是在向量中增加同

15、义词的时候，可能使原来并不是同义词的关键码也被牵连进来（这种现象也被称为“堆积”），进一步增加了查找的时间。,算法与数据结构,46,还有另外一点，在开地址散列向量中的做删除时要特别谨慎，如果简单地把被删除向量元素置成初始值，结果就可能导致某些原有同义词信息的丢失。这里面的具体原因和解决方法请读者自己考虑。,算法与数据结构,47,10.4 桶散列用桶解决碰撞本节介绍碰撞的另一种处理方法。如果把散列表的元素扩充定义为一个能存放多个数据元素的结构，用这种结构存放同义词，能够大大增强散列结构处理碰撞的能力。人们把这种存放同义词的结构称为“存储桶”，或简称“桶”。,算法与数据结构,48,采用桶方式实现散

16、列结构，向结构里加入一个元素的动作就需要分两步走：首先在散列向量中选择应该放入元素的桶，然后再向这个桶做元素插入。寻找和删除元素的操作过程与插入类似。由于每个桶可以容纳多个元素，碰撞问题自然就解决了。我们把以这种方式实现的散列结构称为桶散列结构或桶散列表。,算法与数据结构,49,10.4.1桶散列的抽象模板类抽象的桶散列模板类bucketHashVector带有三个类型参数：类B是桶的实现类型，其实现细节方面的情况后面讨论；类H是元素的关键码类型，它也是散列函数处理的对象类型；类T是桶散列表中元素的类型。,算法与数据结构,50,template class bucketHashVectorpu

17、blic: / 构造函数 bucketHashVector(unsigned int max, unsigned int (f) (const H 类10.3 bucketHashVector类的规范说明,算法与数据结构,51,bucketHashVector类的对象有三个数据域：buckets是桶类型的向量，各个桶里存放散列表元素；整数tablesize是桶向量的元素个数(桶的个数)，由于桶的数目与散列函数直接相关，这里采用确定之后就不能再修改的方式，把它说明为一个整型常量；hashfun是散列函数指针，在散列表定义时设定到选定的散列函数。这个散列函数以H类型的关键码作参数，计算出一个无符号

18、的整数结果。,算法与数据结构,52,在bucketHashVector类里只定义了两个公用操作：一个操作测试散列表是否为空，另一个操作完成所有桶的清除工作，其他操作都必须在这个类的子类里定义。上面两个公有函数都需要遍历所有的桶。要删除散列表里所有的项，必须清除每个桶的所有元素。,算法与数据结构,53,template void bucketHashVector:deleteAllValues( ) for (int i = 0;i tablesize;i+) bucketsi.deleteAllValues( );,算法与数据结构,54,类似的，检查一个散列表里是否有元素就必须检测每个桶的情况

19、。在这些桶都为空的时候，才能说散列表是空的。template int bucketHashVector:isEmpty( ) / 如果任一个筒非空就返回0值 for (int i = 0;i tablesize;i+) if (!buckedsi.isEmpty( ) return 0; return 1; / 全都为空，散列表空,算法与数据结构,55,函数hash定义了对关键码的散列值计算。由于该函数不改变散列表本身，所以被说明为const。函数hash通过函数指针hashfun调用桶散列表建立时设定的基本散列函数，并把散列值归入0与tablezise-1之间。函数hash在类的保护部分中说

20、明，在bucketHashVector的子类和友元类里都可以直接调用它。,算法与数据结构,56,template unsigned int bucketHashVector:hash (const H,算法与数据结构,57,在bucketHashVector的保护部分还定义了一个名为makeIterator的纯虚函数，其参数是一个整数。这个函数的作用是根据参数值生成指定的桶遍历器。由于桶类型B是模板参数，所以函数的实现目前无法具体给出。所有bucketHashVector的子类都必须重新定义这个函数。例如下面的子类hashTree定义时就给出了它的重新定义。,算法与数据结构,58,10.4.2

21、用树作为桶的实现要使用桶散列数据结构，必须建立bucketHashVector的非虚的子类，首先要做的是提供桶的实现类型。桶的实现类型应该适合进行插入和删除操作，以便支持散列表的实现。,算法与数据结构,59,例如链接实现的表或者某种树结构。采用链接表实现桶比较简单，如果能保证散列表里每个链表都很短，各种操作的效率是可以保证的。 定义hashList类的工作留做练习。,算法与数据结构,60,如果对桶中可能出现的元素数目无法做出合理估计，采用链表实现桶就可能出现操作效率比较低的情况，因为在反复的插入操作中，散列表里某些桶（链表）可能变得很长，这时链表的线性查寻时间对操作效率就会产生决定性的影响。,

22、算法与数据结构,61,类10.4给出了hashTree类的规范说明，它也定义为bucketHashVector的子类。这个类中采用第七章中讨论的AVL树作为类型参数B的实现类型。这样做无论桶的大小如何变化，都可以较好地保证桶内的查寻效率。在这个类里定义了插入、删除、包含测试三个成员函数，并提供了实际的构造函数和一个桶遍历器生成函数。,算法与数据结构,62,template class hashTree : public bucketHashVector, T, Tpublic: /构造函数 hashTree(unsigned int max, unsigned int (f)(const T

23、类10.4 hashTree类的规范说明（用AVL树作桶实现散列表）,算法与数据结构,63,在桶散列表里增加或删除元素，采用的实现方式应该与检测元素是否在散列表中类似：首先调用散列函数完成桶的选择，然后对选定的桶进行具体操作。hashTree类里桶的类型已经确定，这些操作的实现都非常简单。下面是add操作的实现。,算法与数据结构,64,template void hashTree:add(T newele) /先找到合适的桶，再把元素插入桶中 bucketshash(newele).add(newele);,算法与数据结构,65,10.4.3桶散列结构操作时间的分析人们经常使用桶散列表结构，一

24、个重要原因是在这种结构上各种操作的执行效率比较高。但是，另一方面，这种散列结构操作的执行时间估计却比较复杂，它一方面与选定的散列函数和实际关键码的分布情况有关，另一方面又与结构的具体设计有关。后者又不但受到桶类型选择的影响，也受到桶的个数即向量大小的影响。,算法与数据结构,66,首先看桶的数目对处理速度的影响。很明显：桶散列表里的桶越少，发生碰撞的可能性就越大。 对桶个数的选择还有另一个需要考虑的因素：为使实际元素的关键码能较均匀地映射到各桶里，人们经常将桶的个数取定为某个素数，也用它作为散列函数的最后数值范围。,算法与数据结构,67,其次，桶类型的选择对处理速度的影响也是显然的。在根据关键码

25、选定某个桶后，下一步处理的速度就依赖于在桶内处理的情况。如果采用AVL树类型的桶，桶内查找元素的平均时间代价是O(log k)(这里k是桶内元素个数)；如果用简单链表结构作为桶，桶内查找元素就需要O(k) 时间。,算法与数据结构,68,在所有有关因素中，最难分析的是散列函数的影响。由于散列表的内容是不断变化的，插入和删除的关键码不能事先确定，对一个选定的散列函数，它某时刻可能正好把所有元素均匀映射到各个桶中，而另一时刻也可能把所有元素都映射到同一个桶里。这里还有一个重要因素，那就是散列函数本身的计算复杂性。,算法与数据结构,69,设在一个桶散列表里有n个元素、m个桶，如果散列函数具有最理想的效

26、果，每个桶中应该有大约n/m个元素。假定散列函数的计算时间是常量，确定一个元素对应的桶里只需要常数时间，那么，在这个散列表里增加一个元素，花费的时间主要就是向一个有n/m个元素的桶中增加一个元素所需要的时间。对于有k个元素的AVL树而言，加一个元素的时间代价是(log k)，这意味着在对应散列结构里，增加一个元素的时间为(log n/m)。如果加入表中的数据元素个数有限，能够保证n/m非常小，在一定的限制范围里(log n/m)几乎就可以看作常数。,算法与数据结构,70,10.5 桶散列结构的遍历器为了遍历一个桶散列表，我们必须遍历表中的每个桶，因此，对整个结构的遍历过程实际上包含了散列表向量

27、本身的遍历和各个桶的遍历两个层次。要实现这种遍历过程，在桶散列表遍历器里就必须必须保存两个值，以便能刻画遍历过程的当前进展情况：一个值是当时正在被遍历的那个桶的下标；另一个值是个指针，它指向在桶散列表遍历过程中动态生成的当前桶的遍历器。,算法与数据结构,71,template class bucketHashVectorIterator : public iteratorpublic: / 构造函数 bucketHashVectorIterator(bucketHashVector 类10.5 bucketHashVectorIterator类的规范说明,算法与数据结构,72,在开始散列表遍历

28、时，首先必须创建一个桶遍历器。由于未必每个桶都实际存有元素，所以在创建遍历器时就需要进行检查，可能要连续检测若干个桶才能找到第一个非空的桶。创建遍历器的工作由getNextIterator函数完成。,算法与数据结构,73,template int bucketHashVectorIterator:init( ) / 初始化遍历器 currentIndex = 0; / 寻找第一个桶 itr = 0; return getNextIterator( );,算法与数据结构,74,template int bucketHashVectorIterator:getNextIterator( ) / 如

29、果存在旧遍历器则删除 if (itr != 0) delete itr; / 寻找一个新的遍历器 for(; currentIndex init( ) return 1; / 否则删除它，再试下一个桶 delete itr; / 没有下一个有效遍历器时结束 itr = 0; return 0;,算法与数据结构,75,在递增运算中也会遇到类似的情况，如果当前桶的遍历器本身还能执行增量操作，那么这个遍历器所访问的元素就是下一个元素；否则就需要调用getNextIterator函数，到随后的桶中去寻找下一个元素。,算法与数据结构,76,template int bucketHashVectorIte

30、rator:operator+( ) / 检查当前遍历器是否还能找到下一个元素 if (itr ,算法与数据结构,77,bucketHashVectorIterator类的子类也只是对其父类的一些标识符换名。下面给出散列树遍历器类的定义，其中散列树是桶类为AVL树的桶散列表。,算法与数据结构,78,template class hashTreeIterator : public bucketHashVectorIterator,T,Tpublic : hashTreeIterator(hashTree ,算法与数据结构,79,template hashTreeIterator:hashTree

31、Iterator (hashTree template setTable:includes(T val)const return bucketshash(val).includes(val);,算法与数据结构,85,求并集和交集的运算，通过对桶向量进行循环，一桶一桶地实施相应操作来完成。template void setTable:unionWith(setTable ,算法与数据结构,86,template int setTable:subset(setTable ,算法与数据结构,87,注意，在上面实现中，参加运算的两个集合(接受者和参数)必须同是setTable类型。实际上，这里不仅要求

32、它们都是桶散列表，而且要求它们具有相同的散列函数，相同的桶类型和tablesize值。只有这样才能保证操作的正确性,算法与数据结构,88,10.7 用桶散列表实现字典下面用的是继承方式，从bucketHashVector类出发建立dictionaryTable类。dictionaryTable类从bucketHashVector类那里继承了所有行为，定义了作为字典的必要操作。,算法与数据结构,89,template class dictionaryTable : public bucketHashVector , K,association public : / 构造函数 dictionaryTable(unsigned int max, unsigned int ( f)(const K 类10.8 dictionaryTable类的规范说明,算法与数据结构,90,我们在这里没有把dictionaryTable类定义为dictionary类的子类，考虑的问题与前面定义setTable时类似。,算法与数据结构,91,template