您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 咨询培训 > 浅谈竞赛中哈希表的应用
浅谈竞赛中哈希表的应用第1页共26页浅谈竞赛中哈希表的应用哈尔滨市第三中学刘翀[关键词]应用哈希表数据结构[摘要]哈希表是一种高效的数据结构。本文分五个部分:首先提出了哈希表的优点,其次介绍了它的基础操作,接着从简单的例子中作了效率对比,指出其适用范围以及特点,然后通过例子说明了如何在题目中运用哈希表以及需要注意的问题,最后总结全文。[正文]1.引言哈希表(HashTable)的应用近两年才在NOI中出现,作为一种高效的数据结构,它正在竞赛中发挥着越来越重要的作用。哈希表最大的优点,就是把数据的存储和查找消耗的时间大大降低,几乎可以看成是常数时间;而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下,用空间换时间的做法是值得的。另外,编码比较容易也是它的特点之一。哈希表又叫做散列表,分为“开散列”和“闭散列”。考虑到竞赛时多数人通常避免使用动态存储结构,本文中的“哈希表”仅指“闭散列”,关于其他方面读者可参阅其他书籍。2.基础操作2.1基本原理我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数浅谈竞赛中哈希表的应用第2页共26页(哈希函数,也叫做散列函数),使得每个元素的关键字都与一个函数值(即数组下标)相对应,于是用这个数组单元来存储这个元素;也可以简单的理解为,按照关键字为每一个元素“分类”,然后将这个元素存储在相应“类”所对应的地方。但是,不能够保证每个元素的关键字与函数值是一一对应的,因此极有可能出现对于不同的元素,却计算出了相同的函数值,这样就产生了“冲突”,换句话说,就是把不同的元素分在了相同的“类”之中。后面我们将看到一种解决“冲突”的简便做法。总的来说,“直接定址”与“解决冲突”是哈希表的两大特点。2.2函数构造构造函数的常用方法(下面为了叙述简洁,设h(k)表示关键字为k的元素所对应的函数值):a)除余法:选择一个适当的正整数p,令h(k)=kmodp这里,p如果选取的是比较大的素数,效果比较好。而且此法非常容易实现,因此是最常用的方法。b)数字选择法:如果关键字的位数比较多,超过长整型范围而无法直接运算,可以选择其中数字分布比较均匀的若干位,所组成的新的值作为关键字或者直接作为函数值。2.3冲突处理线性重新散列技术易于实现且可以较好的达到目的。令数组元素个数为S,则当h(k)已经存储了元素的时候,依次探查(h(k)+i)modS,i=1,2,3……,直到找到空的存储单元为止(或者从头到尾扫描一圈仍未发现空单元,这就是哈希表已经满了,发生了错误。当然这是可以通过扩大数组范围避免的)。2.4支持运算哈希表支持的运算主要有:初始化(makenull)、哈希函数值的运算(h(x))、插入元素(insert)、查找元素(member)。设插入的元素的关键字为x,A为存储的数组。初始化比较容易,例如constempty=maxlongint;//用非常大的整数代表这个位置没有存储元素p=9997;//表的大小proceduremakenull;vari:integer;beginfori:=0top-1doA[i]:=empty;End;浅谈竞赛中哈希表的应用第3页共26页哈希函数值的运算根据函数的不同而变化,例如除余法的一个例子:functionh(x:longint):Integer;beginh:=xmodp;end;我们注意到,插入和查找首先都需要对这个元素定位,即如果这个元素若存在,它应该存储在什么位置,因此加入一个定位的函数locatefunctionlocate(x:longint):integer;varorig,i:integer;beginorig:=h(x);i:=0;while(iS)and(A[(orig+i)modS]x)and(A[(orig+i)modS]empty)doinc(i);//当这个循环停下来时,要么找到一个空的存储单元,要么找到这个元//素存储的单元,要么表已经满了locate:=(orig+i)modS;end;插入元素procedureinsert(x:longint);varposi:integer;beginposi:=locate(x);//定位函数的返回值ifA[posi]=emptythenA[posi]:=xelseerror;//error即为发生了错误,当然这是可以避免的end;查找元素是否已经在表中proceduremember(x:longint):boolean;varposi:integer;beginposi:=locate(x);ifA[posi]=xthenmember:=trueelsemember:=false;end;这些就是建立在哈希表上的常用基本运算。下文提到的所有程序都能在附录中找到。3.效率对比浅谈竞赛中哈希表的应用第4页共26页3.1简单的例子与实验下面是一个比较简单的例子:===================================================================集合(Subset)问题描述:给定两个集合A、B,集合内的任一元素x满足1≤x≤109,并且每个集合的元素个数不大于104个。我们希望求出A、B之间的关系。只需确定在B中但是不在A中的元素的个数即可。这个题目是根据OIBHNOIP2002模拟赛#1的第一题改编的。分析:我们先不管A与B的具体关系如何,注意到这个问题的本质就是对于给定的集合A,确定B中的元素是否在A中。所以,我们使用哈希表来处理。至于哈希函数,只要按照除余法就行了,由于故意扩大了原题的数据规模,H(x)=xmod15889;当然本题可以利用别的方法解决,所以选取了速度最快的快速排序+二分查找,让这两种方法作效率对比。我们假定|A|=|B|,对于随机生成的数据,计算程序重复运行50次所用时间。对比表格如下:哈希表(sec)快速排序+二分查找(sec)复杂度O(N)(只有忽略了冲突才是这个结果。当然实际情况会比这个大,但是重复的几率与哈希函数有关,不容易估计)O(NlogN+N)=O(NlogN)测试数据规模————5000.9570.57810001.1010.82525001.4761.56550002.1452.82075002.9054.203100003.7405.579135007.7757.7531500027.5508.673对于数据的说明:在Celeron566下用TP测试,为了使时间的差距明显,让程序重复运了行50次。同时哈希表中的P=15889,下标范围0..15888。由于快速排序不稳定,因此使用了随机数据。3.2对试验结果的分析:浅谈竞赛中哈希表的应用第5页共26页注意到两个程序的用时并不像我们期望的那样,总是哈希表快。设哈希表的大小为P.首先,当规模比较小的时候(大约为a10%*P,这个数据仅仅是通过若干数据估记出来的,没有严格证明,下同),第二种方法比哈希表快。这是由于,虽然每次计算哈希函数用O(1)的时间,但是这个系数比较大。例如这道题的H(x)=xmod15589,通过与做同样次数的加法相比较,测试发现系数12,因为mod运算本身与快速排序的比较大小和交换元素运算相比,比较费时间。所以规模小的时候,O(N)(忽略冲突)的算法反而不如O(NlogN)。这一点在更复杂的哈希函数上会体现的更明显,因为更复杂的函数系数会更大。其次,当规模稍大(大约为15%*Pa85%*P)的时候,很明显哈希表的效率高。这是因为冲突的次数较少。再次,当规模再大(大约为90%*PaP)的时候,哈希表的效率大幅下降。这是因为冲突的次数大大提高了,为了解决冲突,程序不得不遍历一段都存储了元素的数组空间来寻找空位置。用白箱测试的方法统计,当规模为13500的时候,为了找空位置,线性重新散列平均做了150000次运算;而当规模为15000的时候,平均竟然高达2000000次运算,某些数据甚至能达到4265833次。显然浪费这么多次运算来解决冲突是不合算的,解决这个问题可以扩大表的规模,或者使用“开散列”(尽管它是动态数据结构)。然而需要指出的是,冲突是不可避免的。初步结论:当数据规模接近哈希表上界或者下界的时候,哈希表完全不能够体现高效的特点,甚至还不如一般算法。但是如果规模在中央,它高效的特点可以充分体现。我们可以从图像直观的观察到这一点。试验表明当元素充满哈希表的90%的时候,效率就已经开始明显下降。这就给了我们提示:如果确定使用哈希表,应该尽量使数组开大(由时间效率数据规模其他方法哈希表浅谈竞赛中哈希表的应用第6页共26页于竞赛中可利用内存越来越多,大数组通常不是问题,当然也有少数情况例外),但对最太大的数组进行操作也比较费时间,需要找到一个平衡点。通常使它的容量至少是题目最大需求的120%,效果比较好(这个仅仅是经验,没有严格证明)。4.应用举例4.1应用的简单原则什么时候适合应用哈希表呢?如果发现解决这个问题时经常要询问:“某个元素是否在已知集合中?”,也就是需要高效的数据存储和查找,则使用哈希表是最好不过的了!那么,在应用哈希表的过程中,值得注意的是什么呢?哈希函数的设计很重要。一个不好的哈希函数,就是指造成很多冲突的情况,从前面的例子已经可以看出来,解决冲突会浪费掉大量时间,因此我们的目标就是尽力避免冲突。前面提到,在使用“除余法”的时候,h(k)=kmodp,p最好是一个大素数。这就是为了尽力避免冲突。为什么呢?假设p=1000,则哈希函数分类的标准实际上就变成了按照末三位数分类,这样最多1000类,冲突会很多。一般地说,如果p的约数越多,那么冲突的几率就越大。简单的证明:假设p是一个有较多约数的数,同时在数据中存在q满足gcd(p,q)=d1,即有p=a*d,q=b*d,则有qmodp=q–p*[qdivp]=q–p*[bdiva].①其中[bdiva]的取值范围是不会超过[0,b]的正整数。也就是说,[bdiva]的值只有b+1种可能,而p是一个预先确定的数。因此①式的值就只有b+1种可能了。这样,虽然mod运算之后的余数仍然在[0,p-1]内,但是它的取值仅限于①可能取到的那些值。也就是说余数的分布变得不均匀了。容易看出,p的约数越多,发生这种余数分布不均匀的情况就越频繁,冲突的几率越高。而素数的约数是最少的,因此我们选用大素数。记住“素数是我们的得力助手”。另一方面,一味的追求低冲突率也不好。理论上,是可以设计出一个几乎完美,几乎没有冲突的函数的。然而,这样做显然不值得,因为这样的函数设计很浪费时间而且编码一定很复杂,与其花费这么大的精力去设计函数,还不如用一个虽然冲突多一些但是编码简单的函数。因此,函数还需要易于编码,即易于实现。综上所述,设计一个好的哈希函数是很关键的。而“好”的标准,就是较低的冲突率和易于实现。另外,使用哈希表并不是记住了前面的基本操作就能以不变应万变的。有的时候,需要按照题目的要求对哈希表的结构作一些改进。往往一些简单的改进就可以带来巨大的方便。这些只是一般原则,真正遇到试题的时候实际情况千变万化,需要具体问题具体分析才行。下面,我们看几个例子,看看这些原则是如何体现的。浅谈竞赛中哈希表的应用第7页共26页4.2有关字符串的例子我们经常会遇到处理字符串的问题,下面我们来看这个例子:======================================================================找名字问题描述:给定一个全部由字符串组成的字典,字符串全部由大写字母构成。其中为每个字符串编写密码,编写的方式是对于n位字符串,给定一个n位数,大写字母与数字的对应方式按照电话键盘的方式:2:A,B,C5:J,K,L8:T,U,V3:D,E,F6:M,N,O9:W,X,Y4:G,H,I7:P,R,S题目给出一个1——12位的数,找出在字典中出现且密码是这个数的所有字符串。字典中字符串的个数不超过8000。这个是USACOTrainingG
本文标题:浅谈竞赛中哈希表的应用
链接地址:https://www.777doc.com/doc-2317105 .html