浅谈竞赛中哈希表的应用.doc

《浅谈竞赛中哈希表的应用.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、浅谈竞赛中哈希表的应用哈尔滨市第三中学刘翀[关键词]应用哈希表数据结构[摘要]哈希表是一种高效的数据结构。本文分五个部分：首先提出了哈希表的优点，其次介绍了它的基础操作，接着从简单的例子中作了效率对比，指出其适用范围以及特点，然后通过例子说明了如何在题目中运用哈希表以及需要注意的问题，最后总结全文。[正文]1.引言哈希表（HashTable）的应用近两年才在NOI中出现，作为一种高效的数据结构，它正在竞赛中发挥着越来越重要的作用。哈希表最大的优点，就是把数据的存储和查找消耗的时间大大降低，几乎可以看成是常数时间；而代价仅仅是消耗比较多的内存。然而在当

2、前可利用内存越来越多的情况下，用空间换时间的做法是值得的。另外，编码比较容易也是它的特点之一。哈希表又叫做散列表，分为“开散列”和“闭散列”。考虑到竞赛时多数人通常避免使用动态存储结构，本文中的“哈希表”仅指“闭散列”，关于其他方面读者可参阅其他书籍。2.基础操作2.1基本原理我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数，也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素“分类”，然后将这个元素存储在相应“类”所对应的地方。但

3、是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了“冲突”，换句话说，就是把不同的元素分在了相同的“类”之中。后面我们将看到一种解决“冲突”的简便做法。总的来说，“直接定址”与“解决冲突”是哈希表的两大特点。2.1函数构造构造函数的常用方法（下面为了叙述简洁，设h(k)表示关键字为k的元素所对应的函数值）：a)除余法：选择一个适当的正整数p，令h(k)=kmodp这里，p如果选取的是比较大的素数，效果比较好。而且此法非常容易实现，因此是最常用的方法。b)数字选择法：如果关键字的位数

4、比较多，超过长整型范围而无法直接运算，可以选择其中数字分布比较均匀的若干位，所组成的新的值作为关键字或者直接作为函数值。2.2冲突处理线性重新散列技术易于实现且可以较好的达到目的。令数组元素个数为S，则当h(k)已经存储了元素的时候，依次探查(h(k)+i)modS,i=1,2,3……，直到找到空的存储单元为止（或者从头到尾扫描一圈仍未发现空单元，这就是哈希表已经满了，发生了错误。当然这是可以通过扩大数组范围避免的）。2.3支持运算哈希表支持的运算主要有：初始化(makenull)、哈希函数值的运算(h(x))、插入元素(insert)、查找元素(m

5、ember)。设插入的元素的关键字为x，A为存储的数组。初始化比较容易，例如constempty=maxlongint;//用非常大的整数代表这个位置没有存储元素p=9997;//表的大小proceduremakenull;vari:integer;beginfori:=0top-1doA[i]:=empty;End;哈希函数值的运算根据函数的不同而变化，例如除余法的一个例子：functionh(x:longint):Integer;beginh:=xmodp;end;我们注意到，插入和查找首先都需要对这个元素定位，即如果这个元素若存在，它应该存储在

6、什么位置，因此加入一个定位的函数locatefunctionlocate(x:longint):integer;varorig,i:integer;beginorig:=h(x);i:=0;while(ix)and(A[(orig+i)modS]<>empty)doinc(i);//当这个循环停下来时，要么找到一个空的存储单元，要么找到这个元//素存储的单元，要么表已经满了locate:=(orig+i)modS;end;插入元素procedureinsert(x:longint);varposi:in

7、teger;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;这些就是建立在哈希表上的常用基本运算。下文提到的所有程序都能在附录中找到。1.效率对

8、比3.1简单的例子与实验下面是一个比较简单的例子：=============================