下载

2下载券

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 高二下期5月12日附件文章解题利器——散列表

高二下期5月12日附件文章解题利器——散列表.doc

高二下期5月12日附件文章解题利器——散列表

faint
2018-09-07 0人阅读 举报 0 0 0 暂无简介

简介:本文档为《高二下期5月12日附件文章解题利器——散列表doc》,可适用于工程科技领域

解题利器散列表广东省佛山市石门中学邓尚文引言如今计算机发展带动着比赛条件的改变从以往的几十KB的内存限制发展到现在几十兆甚至几百兆。内存限制已经不再是选手们主要考虑的问题重点都放在如何优化程序使其运行时间更短跑得更快。其中一个重要的思路就是用空间换时间散列表正是利用了这一点。哈希表(HashTable)又叫做散列表是一种非常高效的数据结构它支持在接近O()的时间内完成“插入、查找、删除”这几种工作。本文将介绍散列表的工作原理其特点使用范围以及如何在竞赛中使用散列表。基本原理当我们遇到要判断某个数字是否出现过的时候一种很简单的做法就是开个布尔数组把出现过的数在数组中标记为True其余的为False检查某个数有没有出现过只要看看在数组中有没有被标记成True就行了。比如我们出现了数字、、、、我们把数组对应位置标记一下然后在检查的时候直接判断花费的时间为O()。FFTFFFTFTTFFTF然而有时事情并不是那么顺利如果出现的数字很大比如甚至更大在一台计算机允许的内存中开辟一个这样的表就会不太实际甚至不可能。如果要开一个那么大的布尔数组我们需要G的内存。有时出现的个数并不多却要开辟巨大的空间而利用率却非常低下造成了不必要的浪费。为解决这些问题我们引入了散列表这种数据结构。在保持仅需O()的操作时间内储存的空间需求可以下降到只跟出现的数的个数有关而跟出现的数的大小无关。这里我们要利用到散列函数h它的作用就是将每一个不同的关键字尽量等可能地映射到散列表Tm的每一个槽上。目的就是把数组缩小用个较小的数组储存起来。而散列表至少要多大呢?不同做法有不同的要求一般来说它的大小m只需要大于等于出现的数的个数就行了。当然这里并不建议为了节约空间而把它开得尽量小因为从工作原理上来讲散列表开得越大运行的速度就会越快。由于我们要把一堆数映射到一个相对较小的范围内这样做就会出现一个小问题两个关键字有可能被映射到同一个槽上这种情况就是发生了碰撞。所幸的是我们有有效的解决方法。精心设计一个散列函数h使得散列的结果尽可能地随机分布从而避免一些特殊原因使得散列后有太多的关键字被映射到同一个槽中术语“散列”正体现这点。设计散列函数:首先我们来看看一个好的散列函数h该怎样构造。一个好的散列函数要使得关键字尽量等可能地散列到每一个槽那么我们可以利用关键字本身特有的信息加上一些固定的特殊变化使得即使非常相近的关键字被散列进同一个槽附近的概率最小化。因为在后面提到的无论哪一种解决碰撞的方法所耗费的时间都是跟碰撞的次数成正比的减少碰撞次数就意味着节省时间。有时我们碰到的关键字并不是正整数而是浮点数或字符那么我们就必须有一种方法将他们解释为自然数。例如字符串adbc我们可以把它看成是一个位的进制数那么转换成十进制表示就是*^*^*=那么h(adbc)=一般的来讲h函数得到的值会比散列表T的范围要大这时就要把它折叠起来我们可以使函数h’(k)=h(k)modm如果m=那么h’(abcd)=h(adbc)modm=mod=它的散列值就是这时候我们要注意m要选一个尽量大但又不接近的幂的大质数。选质数的原因是它的因子最少对减少某些特殊的数据的冲突有帮助。而不选接近的幂的大质数是因为当k是按基数p解释的字符串时m=p可能是个很糟糕的选择。比如我们开了一个m=的散列表输入了一些很大的数如一种最简单的方法就是h()=mod=。但是这种方法有很明显的弊端如果输入的数都是m的倍数也就是的倍数时这种方法散列出来的结果都是运行的速度会变得惨不忍赌。而有一种办法就是使每一位的数相加后与它自身的积去与m取模即:h()=(()*)mod=或者把它取一半分成两个数相乘再取余也行即:h()=(*)mod=总之只要遵守它的构造原则对每个输入都有一个唯一与它对应的自然数并且尽可能地随机分布在表中我们就可以发挥自己的想象力去创造一个属于自己的散列函数了。面对一个想搞垮你的对手他会选择让所有的关键字都被散列到同一个槽中使得检索时间为O(N)就像有瑕疵的快速排序一样在早已有顺序的情况下运行反而会蜕化成O(N)。唯一有效的解决办法就是加上随机化使得即使是同一个输入每一次执行也会有不同的运行状态这便是全域散列。一个很简单的全域散列方法就是选择一个足够大的质数p在计算的中途代替m。h’(k)=h(k)modp在最后得出散列值的时候再让h’(k)=h’(k)modm于是就可以写成h’(k)=(h(k)modp)modm这样做就相当于在p范围内折叠完以后再折叠进m的范围内经过全域散列后散列值将进一步无序化。用上面的例子来讲我们取p=那么在运算的每一步我们都可以模p:h()=(*)mod=((mod)*(mod))mod=h’()=h()modm=mod=所以最终散列值就是了。但是由于散列表的范围比关键字的范围小很多再优秀的散列函数也会产生碰撞碰撞在所难免我们还是要回归到如何解决碰撞这个问题上面。解决碰撞:一、用链接法解决碰撞这种方法采用链表的方式把映射到同一个槽的关键字都储存起来检查的时候就要检查同一个槽里的所有关键字。首先我们要求出散列值h(k)在对应的槽里面开辟一个指针把这个关键字记录下来。查找的时候要把槽里的每一个记录下来的指针都检查一遍而删除时直接释放掉指针就行了。显然碰撞的次数越多在解决碰撞所花费的时间代价就越高。链接法插入伪代码:hashnum=gethash(k)*temppoint=hashtablehashnumwhile(temppoint不为空)dotemppoint=temppointnext开辟新空间把k存下来temppoint指向新开辟的空间二、开放寻址法当要插入的关键字发生碰撞时可以直接重复加直到遇到第一个空槽停下来然后就可以插入这个空槽了。当然重复加时如果到了散列表末尾我们就要让回到表头而检查某个关键字是否出现的时候要将后面所有相连的全部检查直到遇到要找的关键字或第一个空槽时为止。End开放寻址法插入伪代码:hashnum=gethash(k)while(hashtablehashnum不为空)dohashnum=(hashnum)modmhashtablehashnum=k这样做可以省下开链表的空间从而创建更多的槽使得碰撞的概率更小。从它的工作原理我们就可以明白为什么散列函数要尽可能地使关键字在表中随机分布了因为如果很多关键字集中在一块那么找到第一个空槽就要花费不少时间。如果担心全部关键字都非常不幸地被散列进同一个槽附近的话我们还有一些技巧使得探查的次数变得更少。我们可以开一个由随机数构成的辅助常数数组使每个不同的散列值的后续的探查位置都加上一个偏移量这样就可以避免连续地向下探查。这种技术就我们称之为二次探查。End二次探查插入伪代码:hashnum=gethash(k)startlocation=getlocate(k)if(hashtablehashnum不为空)thenhashnum=(hashnumstartlocation)modmwhile(hashtablehashnum不为空)dohashnum=(hashnum)modmhashtablehashnum=k还有一种方法叫做双重散列是用于开放寻址法的最好方法之一因为它的随机性能带来非常可观的优秀的特性。这里我们需要另一个散列函数它的作用就是通过对原函数生成的数分配一个步长。End如图我们要插入关键字散列函数h()=表示它被散列到第一个槽中在此与碰撞于是它加上它的步长步长由第二个散列函数h()=得到这样它每次跳两步可以有效地避开连续的长段。而第二个散列函数h有个小要求就是得到的值一定要与散列表T的大小M互质这样跳跃的时候可以就访问表里所有的槽避免表未填满却找不到位置而出现死循环的现象发生。特别注意一点就是不能使得h(k)=因为当步长为的时候就会进入死循环。双重散列技术使得每一个k都有起始位置为h(k)步长为h(k)的不同的探查序列因此它的性能与理想的无碰撞散列非常接近了。双重散列插入伪代码:hashnum=gethash(k)step=getstep(k)while(hashtablehashnum不为空)dohashnum=(hashnumstep)modmhashtablehashnum=k散列技术的使用其实是很广泛的在计算机领域里面主要应用在加密与解密里面而在竞赛中我们可以拿它作为有力的解题利器。比如在一场重要的比赛中要写一个字符串匹配可是忘记了高效KMP算法那么就只好拿出散列表当两个字符串散列值匹配时再去扫描一遍这样做所得到的程序的性能非常接近KMP。我们来看两个个非常简单的应用:应用一:有N个m*m的字符矩阵称之为地图数据保证只有两幅图相同问哪两幅地图是相同的。(<N<,<M<)显然地图和图是相同的地图那么用计算机如何解决这个问题呢?有一种很直接的方法就是枚举ij两幅地图然后逐一判断这两幅地图是否是相同的。然而这种做法时间复杂度为O(N*N*M*M)如果给出极限数据电脑要运行分多钟才出结果。然而散列表的使用使复杂度降为O(N*M*M)可以不到一秒就得出解来。我们可以把每一个矩阵都看做一个字符串然后把这个字符串看做一个进制数用这个数对应的十进制数直接模一个大质数一个简单的散列函数h就完成了。这里我们开个大小len=的表。散列函数h(ABABCBACB)=转换为十进制数的(ABABCBACB)modlen当我们遇到碰撞的时候才去把碰撞的两幅地图扫描一遍而像这种情况碰撞的可能几乎为所以程序的效率非常高。应用二:已知一个n元高次方程:其中:x,x,…,xn是未知数k,k,…,kn是系数p,p,…pn是指数。且方程中的所有数均为整数。假设未知数≤xi≤M,i=,,,n求这个方程的整数解的个数。输入格式文件的第行包含一个整数n。第行包含一个整数M。第行到第n行每行包含两个整数分别表示ki和pi。两个整数之间用一个空格隔开。第行的数据对应i=第n行的数据对应i=n。输出格式文件仅一行包含一个整数表示方程的整数解的个数。输入样例输出样例数据规模与约定≤n≤≤M≤方程的整数解的个数小于。★本题中指数Pi(i=,,……,n)均为正整数。题目来源:NOIhttp:oitjueducnproblemsource分析:首先我们可以发现它数据规模不大但是枚举全部未知数Mi必定超时。那么我们就可以枚举一半未知数Mi。把前半枚举的式子的结果都用散列表记下来再枚举后半式子在表里找是否有前半记录过的相反数统计一下即可。时间复杂度为O(M)。程序代码:#include<fstream>#include<cmath>usingnamespacestdifstreamfin("equationin")ofstreamfout("equationout")intn,mintansintoperatelonglonglimit=llstructnode{intk,p}datconstinttablelength=(<<)structhashnode{intans,num}hashtabletablelengthlonglongctvoidinit(){fin>>n>>mfor(inti=i<ni)fin>>datik>>datip预处理~的p次方for(inti=i<=i){for(intj=j<j){ctij=for(intk=k<=datjpk){ctij*=iif(ctij>*limit)ctij=*limit如果超过最大值}}}}intgethash(longlongtemp)散列函数{intretif(temp<)temp*=ret=((temp<<)(temp<<)(temp))tablelengthreturnret}voidinsert(inthashnum,inttemp)插入操作{while(hashtablehashnumnum!=){if(hashtablehashnumans==temp)找到了以前算的结果{hashtablehashnumnumreturn}hashnum=hashnum向下寻址if(hashnum>=tablelength)hashnum=tablelength}没有找到新建一个hashtablehashnumans=temphashtablehashnumnum=}intfind(inthashnum,inttemp)查找操作{while(hashtablehashnumnum!=){if(hashtablehashnumans==temp)找到了returnhashtablehashnumnumhashnum=hashnum向下寻址if(hashnum>=tablelength)hashnum=tablelength}return}voidgetm(intnow,inted,longlongsum)递归枚举未知数的过程{if(now==ed)枚举结束{if(operate==)sum=suminthashnum=gethash(sum)if(operate==)insert(hashnum,sum)elseans=find(hashnum,sum)return}for(inti=i<=mi)枚举中途{longlongnewsum=sumdatnowk*ctinowif(newsum>limit||newsum<limit)returngetm(now,ed,newsum)}}intmain(){init()初始化operate=getm(,n,)枚举前半operate=getm(n,n,)枚举后半fout<<ans<<endlreturn}h(k)h(k)mT实际关键字kkk关键字域h(k)kkkkkT实际关键字关键字域kkkkk散列表示意图链接法解决碰撞布尔数组标记法开放寻址法示意图二次探查示意图双重散列示意图

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

评分:

/10

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利