散列表实验报告(不同装载因子下的链表法和开放寻址法的对比).doc

1概述22原理介绍22.1散列表介绍22.2直接寻址表32.3散列函数32.3.1除法散列42.3.2乘法散列42.3.3全域散列42.4解决碰撞问题52.4.1链接法52.4.2开放寻址法52.4.2.1线性探查62.4.2.2二次探查62.4.2.3双重散列73算法说明73.1概述73.2使用链接法解决碰撞问题83.2.1算法思想83.2.2伪代码描述93.2.3算法分析与证明103.3使用开放寻址法的双重散列解决碰撞问题123.3.1算法思想123.3.2伪代码描述123.3.3算法分析与证明143.4两个算法的比较144实验设计与分析165C+实现与结果分析185.1C+实现与结果185.2结果分析266实验总结和感想271 概述该实验报告主要是通过介绍散列表的各种技术，包括散列函数、解决碰撞的机制等技术，并对两种解决碰撞的机制：链接法和开放寻址法进行分析和证明，并通过实验分析两者在不同的规模下的运行时间和空间占用的对比，来证明在“算法说明”一章中的理论分析。2 原理介绍2.1 散列表介绍散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。它实际上是是普通数组概念的推广，因为可以对数组进行直接寻址，故可以而在O(1)时间内访问数组的任意元素。如果存储空间允许，我们可以提供一个数组，为每个可能的关键字保留一个位置，就可以应用直接寻址技术。基本概念若结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数(Hash function)，按这个思想建立的表为散列表。 对不同的关键字可能得到同一散列地址，即key1key2，而f(key1)=f(key2)，这种现象称冲突。具有相同函数值的关键字对该散列函数来说称作同义词。综上所述，根据散列函数H(key)和处理冲突的方法将一组关键字映射到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象”作为记录在表中的存储位置，这种表便称为散列表，这一映射过程称为散列造表或散列，所得的存储位置称散列地址。 若对于关键字集合中的任一个关键字，经散列函数映射到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数(Uniform Hash function)，这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。 常用的构造散列函数的方法散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快地定位当实际存储的关键字数比可能的关键字总数较小时，此时采用散列表就会较直接数组寻找更为有效，因为散列表通常采用的数组尺寸与所要存储的关键字数十成比例的。在散列表中，不是直接把关键字用作数组下标，而是根据关键字计算出下标。名词解释：碰撞：就是指多个关键字映射到同一个数组下标位置2.2 直接寻址表当关键字的全域U比较小时，直接寻址是一种简单而有效的技术。假设某应用要用到一个动态集合，其中每个元素都有一个取自全域U=0，1，2，的关键字，此外M是一个不很大的数。另假设没有两个元素具有相同的关键字。此时动态集合中的元素可以放在直接寻址表中。亦即不把每个元素的关键字及其卫星数据都放在直接讯指标外部的一个对象中，再由表中某个槽的指针指向该对象，而是直接把对象放在表的槽中，从而节省了空间。此外，通常不需要存储对象的关键字域，因为如果我们有了一个对象的在表中的下标，就可以得到它的关键字。但是，如果不存储关键字，我们必须有某种办法来确定某个槽是否为空。一般来说，直接寻址法比较浪费存储空间，而且容易发生碰撞（当有关键字相等的时候）。这里不与讨论。2.3 散列函数好的散列函数的特点：一个好的散列函数应（近似地）满足简单一致散列的假设：每个关键字都等可能地散列到m个槽位的任何一个之中去，并与其他得到关键字已被散列到哪一个槽位中无关。不幸的是，一般情况下不太可能检查这一条件是否成立，因为人们很少能知道关键字所符合的概率分布，而各关键字可能并不是完全相互独立的。有时，我们偶尔也能知道关键字的概率分布。例如，如果已知各关键字都是随机的实数k，他们独立地、一致地分布于范围0=k1中，那么散列函数：h(k)=km就能满足简单一致散列这一假设条件。将关键字解释为自然数：一个字符串关键字可以被解释为按适当的基数记号表示的整数。一般来说按照ASCII码来翻译字符。后面的所有算法和实现都是按照自然数来做的。2.3.1 除法散列在用来设计散列函数的除法散列函数中，通过取k除以m的余数，来将关键字k映射到m槽的某一个当中去。亦即，散列函数为：h(k)=k mod m当应用除法散列时，要注意m的选择。例如，m不应是2的幂，因为如果m=2p，则h(k)就是k的p个最低位数字。除非我们事先知道，关键字的概率分布使得k的各种最低p位的排列形式的可能性相同，否则在设计散列函数时，最好考虑关键字的所有为的情况。可以选作m的值常常是与2的整数幂不太接近的质数。例如，假设我们要分配一张散列表，并用链接法解决碰撞，表中大约要存放n=3000个字符串，每个字符有8位。一次不成功的查找大约要检查4个元素，故分配散列表的大小为m=749。之所以选择749这个数，是因为它是个接近a=3000/4,但又不接近2的任何次幂的质数。2.3.2 乘法散列构造散列函数的乘法方法包含两个步骤。第一步，用关键字k乘上常数A（0A0,1,2m-1(称为辅助散列函数)，线性探查方法采用的散列函数为：h(k,i)=(h(k)+i) mode m , i=0,1,2,m-1给定一个关键字k，第一个探查的槽式T(h(k),接下来探查下一个槽，知道Tm-1。线性探查方法比较容易实现，但存在一个问题，成为一次群集。随着时间的推移，连续被占用的槽不断增加，平均查找时间也随着不断增加。群集现象很容易出现，这是因为当一个空槽前有i个满的槽时，该空槽为下一个将被占用的槽的概率是(i+1)/m，连续被占用的槽的序列将会变得越来越长，因而平均查找时间也会随之增加。2.4.2.2 二次探查二次探查（quadratic probing）采用的形式如下：h(k,i)=(h(k)+c1i+c2i2)mod m其中h是一个辅助散列函数，c1和c2为辅助常数，i=0,1,m-1。处事的探查位置为Th(k),后续的探查位置要在此基础上加上一个偏移量，该偏移量是以二次的方式依赖于探查号i的。如果两个关键字的初始探查位置是相同的，那么他们的后续二次探查的序列也是相同的。这种性质会导致一种程度较轻的群集现象，成为二次群集。2.4.2.3 双重散列双重散列是用在开放寻址法的最好方法之一，因为它所产生的排列具有随机选择的排列的许多特性。它采用如下形式的散列函数：h(k,i)=(h1(k)+ih(k)mod m其中h1和h2是辅助散列函数。初始探查位置为Th1(k),后续的探查位置在此基础上加上偏移量h2(k)模m。与线性探查和二次探查不同的是，这里的探查序列以两种方式依赖于k，因为初始探查位置和偏移量都可能发生变化。3 算法说明3.1 概述对于一个散列表，最重要的事情是做两件事情：l 选择散列函数，使关键字的分布尽量的均匀l 使用一种解决碰撞的机制对于选择散列函数，我们从原理介绍中可以看出，在我们提供的三种散列函数当中，全域散列具有最好的性能。因为这篇实验报告主要的讨论的是解决碰撞的机制问题，所以，这里我就直接选择了性能最好的散列函数全域散列函数。在后面的文章中，所有的散列函数都是全域散列。特此说明。对于解决碰撞的机制，课文提供了两种方法：链接法和开放寻址法。链接法一般来说就是一种，即不排序的双向链表。而开放寻址法又至少有三种方法：线性探查、二次探查和双重散列，因为在原理介绍中也谈到：线性探查会产生群集现象，二次探查也会产生程度较轻的群集现象，性能最好的就是双重散列。所以我在用开放寻址法与链接法的对比当中，开放寻址法也相应地采用性能最优的算法，也即双重散列方法。3.2 使用链接法解决碰撞问题3.2.1 算法思想在链接法中，把散列到同一槽的所有元素都放在一个链表中。槽j中有一个指针，它指向由所有散列到j的元素构成的链表头；如果不存在这样的元素，则j中位NIL。链表法是最简单的解决碰撞的方法，但是非常有用。即使是java.util.HashMap的类当中，也是采用链表法。它采用的链表法的方式，链表是单向链表，因此在删除过程中要自己维持prev节点，我想不采用双向链表是从节省空间考虑。HashMap采用链表法而不是开放地址法，猜想可能的原因是从实用角度出发，对空间和时间效率做出的折中选择。采用开放地址法，无论是线性探测或者二次探测都可能造成群集现象，而双重散列会要求散列表的装填程度比较低的情况下会有比较好的查找效率，容易造成空间的浪费。主要操作：l 插入首先，使用散列函数计算出要插入的关键字的散列值，然后查找该散列表对应的位置上的指针是否为空。如果为空，则说明该位置上的链表的长度为0，则可以将该元素添加到该散列表对应位置上的链表上。如果不为空，则将该元素添加到已经存在的链表中。l 查找首先使用散列函数计算出要查找的关键字的散列值，然后查找该散列表对应位置上的指针。如果为空，则说明该元素不在散列表中，返回NIL；如果不为空，则沿着该位置上的链表一直搜索下去，知道找到该元素为止，如果还是没有找到，则返回NIL，表明该元素不在散列表中；如果找到，则返回该元素的指针。l 删除首先，使用散列函数计算出要插入的关键字的散列值，然后查找该散列表对应的位置上的指针是否为空。然后类似查找操作，找到该元素的指针，如果找不到则返回操作失败。如果能找到该元素的指针，则首先保存该节点的next指针，然后将next指针覆盖该节点的pre元素的next指针，最后释放该节点的内存。3.2.2 伪代码描述l 插入CHAINED-HASH-INSERT(T,x)index=HASH(x)if(hash_tableindex=NIL)then create a chaininsert x to the chainelse then insert x to the head of the chainreturnl 查找CHAINED-HASH-SEARCH(T,k)index=HASH(x)if(hsh_tableindex=NIL)then return falseelsethen find x in the chainreturn xl 删除CHAINED-HASH-DELETE(T,x)index=HASH(x)if(hash_tableindex=NIL)then return falseelsethen find x in the chainif !find(x)return falseelse then delete xreturn true3.2.3 算法分析与证明对于查找操作：给定一个能存放n个元素的、具有m个槽位的散列表T,定义T的装载因子（load factor），=n/m.即一个链中平均存储的元素数。用链接法散列的最坏性能很差，所以n个关键字都散列在同一个槽中，从而产生一个长度为n的链表。此时，最坏情况下查找的时间为O(n)，加上计算散列函数的时间，这么一来就和一个链表来链接所有时间差不多。散列方法的平均性态一来与所选取的散列函数h在一般情况下，将所有的关键字分布在m个槽位上的均匀程度。我们假定任何元素散列到m个槽中的概率都是一样的，且与其他元素已经被散列到什么位置上独立无关，即简单一致散列。对于j=0，1m-1，列表Tj的长度用nj表示，这样有：n=n0+n1+n2+nm1-1nj的平均值为Enj= =n/m假定可以再O(1)时间内计算出散列值h(k),从而查找具有关键字为k的元素的时间线性地依赖于表Th(k)的长度nh(k).先不考虑计算散列函数和寻址槽h(k)的O(1)的时间，我们查找算法期望查找的元素数，即为比较元素的关键字时候为k而检查的表Th(k)中的元素数。我们分两种情况来考虑：l 查找成功假定要查找的关键字时表中存放的n个关键字当中任何一个的可能性事相同的。在对元素x的一次成功的查找中，所检查的元素都是在x之后插入的，这是以内新的元素都是在表头插入的。为了确定所查找的元素的期望数目。对x所在的链表中，在x之后插入到表中的期望元素加1，再对表中的n个元素x取平均。所以对于一次成功的查找来说，所需的全部时间为.l 查找不成功在简单一致散列的假设下，任何尚未被存储在表中的关键字k都是等可能地被散列到m个槽的任一个当中。因为，当查找一个关键字k时，在不成功的情况下，查找的期望时间就是查找到链尾的期望时间，这一时间的期望商都是En(k)= 。于是一次不成功的查找平均要检查个元素，所需的总时间（包括计算h(k)的时间）为（1+）。对于插入操作：主要有两部分运行时间构成，一部分是运行散列函数的时间，还有一部分是在链表头插入元素的部分。因为两个部分的时间都是O(1)，所以其运行时间为.对于删除操作：也是主要有两部分运行时间构成,一部分是查找元素的时间，另外一部分是删除元素并调整链表的时间。无论查找成功与否，其运行时间都是（1+）。所以总的运行时间是。操作成功运行时间不成功的运行时间平均运行时间查找（1+）（1+）（1+）插入（1+）（1）删除（1+）（1+）（1+）3.3 使用开放寻址法的双重散列解决碰撞问题3.3.1 算法思想如前面概述所说，这里讨论的是开放寻址法的双重散列方法。双重散列事开放寻址法的最好方法. 它的散列函数大体如下:h(k,i) = ( h1(k) + i*h2(k) ) mod m, 其中 i是发生碰撞的次数, k是关键字值, m是散列表的容量, h1, h2是两个散列函数称为辅助散列函数,为了能查找整个散列表, 值h2(k)要与表大小m互质! 一般设计为h2(k)是一个总是产生质数的函数, 或者m是一个质数并且h2总是产生比m小的正整数.比如, 我们可以去m为质数, h1(k) = k mod m, h2(k) = 1+ ( k mod (m-1) ) -m-1比m略小.双重散列的探查序列是m的平方级别的, 而线性和二次都是m级别的, 因此双重散列的效果要好得多。l 插入操作首先进行散列函数运算，得出散列值，先查找该位置有没有被元素占据，如果有则进行第一次散列函数运算，计算出下一个探查序列，直到找到一个空的位置插入为止。l 查找操作与插入操作类似，通过运行散列函数得到下一个探查的位置，一直到找个该元素为止。如果探查完所有的序列，但仍旧没有找到，则返回错误。l 删除操作首先执行查找操作，找到后删除该位置的元素。因为对于开放地址法，删除是一个比较困难的问题。删除该位置的元素后，我们置该位置一个DELETE值，表示该位置曾经有元素，但已经被删除了。则程序认可继续探查后面的序列，找到之前插入的其他元素。3.3.2 伪代码描述插入HASH-INSERT(T,k)i=0repeat j=h(k,j)if Tj=NILthen Tj=kreturn jelse i=i+1until i=merror “hash table overflow”查找HASH-SEARCH(T,k)i=0repeat j=h(k,i)if Tj=kthen return ji=i+1until Tj=NIL or i=mreturn NIL删除HASH-DELETE(T,k)i=0repeat j=h(k,i)if Tj=kthen Tj=DELETEDi=i+1until Tj=NIL or i=mreturn NIL3.3.3 算法分析与证明像在分析链接法时一样，对开放寻址法的分析是以散列表的装载因子=n/m来表达的，n和m趋向于无穷。当然，在开放寻址法中，每个槽中至多只有一个元素，因为n=m，这意味着=1。现假设采用的是一致散列法。在这种理想的方法中，用于插入和查找每一个关键字k的探查序列为的任一种排列的可能性是相同的。当然，每一个给定的关键字有唯一固定的探查序列。对于查找操作：在一次不成功的查找当中，除了最后一次探查之外，每一次探查都要检查一个被占用的，但并不包含所求关键字的槽，最后检查的槽时空的。先定义随机变量X为一次不成功的查找中所做的探查数，在定义事件Ai(i=1,2,)为进行了第i次探查，且探查到的是一个已被占用的槽的事件。那么事件X=i即为事件的交集。由于共有n个元素和m个槽，因为PrA1=n/m。对于j1,在前j-1次探查到的都是已占用槽的前提下，有第j次探查到的是已占用槽的概率是(n-j+1)/(m-j+1)。之所以会得出这一概率，是因为我们要在(m-(j-1)这个未探查的槽中，查找余下的(n-(j-1)个元素。根据一致散列假设，这一概率为这几个量的壁纸。注意到nm蕴含对于所有满足0=jm的j来说，有(n-j)/(m-j)=n/m，于是对所有满足1=i=m，有：所以得出期望探查数的界是：如果是一个常数，一次不成功查找的运行时间为O(1)。例如，如果散列表是半满的，在一次不成功查找中，平均的探查数至多是1/(1-0.5)=2。3.4 两个算法的比较从理论上，链表法和开放寻址法的运行时间对比如下：其中m为槽位总数，n为元素总数，=n/m为装载因子最坏情况平均情况理论平均探查界说明插入链表法假设需要插入到链表中的元素都是不相同的开放寻址法查找链表法开放寻址法虽为常数，但与系数相关删除链表法开放寻址法空间使用对比：给定n个需要散列的元素，每个元素的长度是固定的a,指针的固定长度为b，假设使用链表法的装载因子为,而使用开放寻址法的装载因子为。则链表法的空间使用量是：而开放寻址法的空间使用量是：假设指针长度为4bytes,元素固定长度为4bytes. 则两中算法的使用空间为：(单位bytes)平均探查数目链表法n=10000开放寻址法n=100002=1120K=0.580K3=2100K=0.6660K4=393K=0.7553.3K5=490K=0.850K从图中我们可以看出，同等平均性能的情况下，链表法要比开放寻址法占用的空间多50%80%。4 实验设计与分析测试环境：配置说明CPUIntel Pentium E52002.5GHZ， 2M二级缓存内存威刚 DRR2 1066 2G硬盘希捷 500G32M缓存显卡昂达 9600GS384M显存，DDR2颗粒操作系统windows 7旗舰版开发环境：硬件部分：如上说明操作系统：window 7旗舰版开发平台Visual studio 2008 编程语言C+该实验主要是验证链表法和开放寻址法的运行时间。链表法的实验流程:开放寻址法的实验流程：与链表法的流程是基本一样的，只是插入、删除和查找的具体实现不一样。5 C+实现与结果分析5.1 C+实现与结果该图是在n=10000,m=2000,的情况下运行的，从创建10000个随机数组到全部插入，再到全部删除的过程。该图是链表法在25的装载因子下的表现（全部均为成功）：开放寻址法实验结果：该图是在n=10000,m=20000,的情况下运行的，从创建10000个随机数组到全部插入，再到全部删除的过程。该图是开放寻址法在0.30.9的装载因子下的表现（全部均为成功）：装载因子实际值实际比例理论比例=0.31.0ns11=0.41.5ns1.51.2=0.51.88ns1.881.4=0.62.8ns2.81.75=0.75.8ns5.82.331=0.810.9ns10.93.5=0.920.1ns20.17实际比例跟理论比例有出入，是因为实验的时候查找的是在散列表中都有的关键字，所以查找起来速度会比较慢。算法分析中的理论比例是全部成功和不成功的平均查找性能。实验部分程序如下图：5.2 结果分析由实验可知：链表法（n=10000）：平均探查数目装载因子实际使用空间实际平均查找时间(不考虑命中)实际平均查找时间(全部命中)2=1120K1.688ns1.3ns3=2100K1.700ns1.4ns4=393K1.703ns1.6ns5=490K1.734ns1.8ns6=588K1.834ns2.0ns开放寻址法（n=10000）：平均探查数目装载因子实际使用空间实际平均查找时间(不考虑命中)实际平均查找时间(全部命中)2=0.580K2.03ns0.9ns3=0.6660K2.5ns1.1ns4=0.7553.3K2.97ns1.2ns5=0.850K5.47ns1.3ns6=0.8648K8.75ns1.5ns从表格我们可以看出链表法和开放寻址法的查找时间都是常数，而这个常数和装载因子是密切相关的。这也证明了我们在算法说明中的分析是正确的。由表格可见，开放寻址法在相同的探查数目的情况下（忽略程序因素）是比链接法要快一些的，而当开放寻址法在装载因子比较小的时候，其发生碰撞的几率极小，所以其寻址速度接近普通数组。如果元素所占的空间和指针相比而言较大时，也即链接法使用的指针所占的空间可以忽略不计的时候，链接法以其比较稳定的查找性能胜出。特别是在存储空间有限定的情况下，链接法不失为一种处理碰撞的好方法。6 实验总结和感想这个实验大作业花了我整整一个星期，其中所有的代码都是独立完成，调试和完善的时间用很大一部分。除了深入了解散列是如何运作的之外，最重要是在写程序的过程中学到了不少东西。总结了一下，从算法方面的体会如下：l 散列的效率是很高的无论是链表法还是开放寻址法，它的运行时间都是常数，当然这取决于装载因子。实际上散列就是用空间来换取查找的速度。散列的另外一层意义就是通过关键字散列后的值作为数组索引查找。l 散列函数很重要理论上，全域散列的一致性比较好，但是在实验的过程中还没有用到l 链接法和开放寻址法的对比链表法比较适用于空间要求比较严格，不允许将左右的元素装在散列表当中的情况，而当关键字的卫星数据比较大的时候，可以使用链表法，简单实用。而开放寻址法的探查方法很讲究，线性查找和二次查找都会导致不同程度的群集，所以基本上不用。最好还是用双重散列，它的探查序列可以达到m的二次方种，比线性探查和二次探查的探查序列可能性要高得多。从编写程序方面学习到的东西有如下几点：l 突