浅谈竞赛中哈希表的应用一

浅谈竞赛中哈希表的应用一内容摘要：

的写了一个（因为越是随意的，就越是随机的。 ），定位函数是这样的： function locate(var a,b,c,d:longint):longint。 var t:longint。 i:integer。 begin t:=r[b]*10037+r[c]*5953+r[d]*2999。 {用 3 堵墙的值任意乘大素数相加再取余数，使得结果分布比较随机，也就比较均匀 } t:=t mod p。 i:=0。 while (e[a,(t+i)mod p,1]0)and(e[a,(t+i)mod p,1]r[b]) do if (e[a,(t+i)mod p,2]r[c])or(e[a,(t+i)mod p,3]r[d]) then inc(i)。 {线性重新散列 } locate:=(t+i)mod p。 end。 但是后来发现完全没有必要这样做，这样的哈希函数在计算 t 的时候浪费了很多时间（不过数据规模不是很大，所以这点不十分明显），而且素数起到的作用也不应当是这样的。 其实让 r[b],r[c],r[d] 组成 n 进制数就完全能够达到目的了，加入了素数不仅是小规模数据计算浪费时间，对大数据最后结果的分布平均也没有起到比 n 进制数更多的作用。 因此改为 t:=r[b]*sqr(n)+r[c]*n+r[d]。 当然肯定会有更好的哈希函数的。 小结 第一个例子，乍一看与哈希表毫无关系；第二个例子叙述比较复杂，但是经过仔细分析，发现问题的本质都是确定 某个元素是否在给定集合中 ，这正是哈希表的特点。 所以，不论题目的表面看起来如何，只要本质是需要 高效的数据检索，哈希表通常就是最好的选择。 另外，这两个例子都在原来哈希表的基础上作了一些变化。 第一个例子加入了纪录某个值出现次数的域，第二个例子加入了纪录所有墙的情况以及原节点编号的域。 虽然都只是很小的变化，但是却给问题的解决带来了不小的方便。 因此我们得到提示：哈希表虽然有标准的操作，但也不是一成不变的，需要具体问题具体分析，根据题目的要求和特点作出相应变化。 5. 总结 本文介绍了有关哈希表方面的内容，分析了它的特点和优点，指出了应用需要注意的问题，并且重点举了几个例子来说明它在竞赛中的应用。 希望读者读完本文能够对哈希表有更全面的了解，并能在竞赛中应用自如。 参考文献： 1． 《算法与数据结构（第二版）》 付清祥 王晓东 编著 2． 《奥赛兵法信息学（计算机）》 朱全民 主编 3． 《 SGOI8 烦恼的设计师 解题报告》 曙光网信息学 4． 《 Data Structures》 USACO Training Gate 附录： 这是我第一次写论文，水平很有限，希望大家指出我的缺点和不足。 我的邮箱 下面是所有前面提到的程序。 其中只有 SGOI8 Flowers 的程序是网上提供的标程，其余的都是我自己写的，并且已经通过所有测试数据。 1． 哈希表的程序 program subset。 const max=15889。 var fin,fout:text。 a,b,s,j:longint。 index:array[0..max1]of longint。 t:real。 function locate(t:longint):longint。 var tmp:longint。 begin tmp:=t mod max。 while (index[tmp]0)and(index[tmp]t) do tmp:=(tmp+1) mod max。 locate:=tmp。 end。 procedure int(t:longint)。 begin index[locate(t)]:=t。 end。 function member(t:longint):boolean。 begin if index[locate(t)]=t then member:=true else member:=false。 end。 procedure init。 var shu,i:longint。 begin assign(fin,39。 39。 )。 assign(fout,39。 39。 )。 reset(fin)。 rewrite(fout)。 close(fout)。 fillchar(index,sizeof(index),0)。 read(fin,a)。 for i:=1 to a do begin read(fin,shu)。 int(shu)。 end。 end。 procedure main。 var i,shu:longint。 begin read(fin,b)。 s:=0。 for i:=1 to b do begin read(fin,shu)。 if not member(shu) then inc(s)。 end。 end。 procedure out。 begin writeln(s)。 close(fin)。 end。 begin t:=meml[$40:$6C]。 for j:=1 to 50 do begin init。 main。 out。 end。 t:=meml[$40:$6C]t。 writeln(t/:0:8)。 end. 2． 快速排序 +二分查找的程序 program subset。 const max=16101。 var a,b,s,j:longint。 da:array[1..max]of longint。 fin:text。 t:real。 procedure init。 var i:longint。 begin assign(fin,39。 39。 )。 reset(fin)。 read(fin,a)。 for i:=1 to a do read(fin,da[i])。 end。 procedure sort(m,n:longint)。 var p:longint。 function locate:longint。 var value,i,j,temp:longint。 begin value:=da[(m+n) div 2]。 i:=m1。 j:=n+1。 while true do begin repeat inc(i)。 until da[i]=value。 repeat dec(j)。 until da[j]=value。 if ij then begin temp:=da[i]。 da[i]:=da[j]。 da[j]:=temp。 end else begin if Ij then locate:=j else locate:=j1。 exit。 end。 end。 end。 begin if mn then begin p:=locate。 sort(m,p)。 sort(p+1,n)。 end。 end。 procedure main。 var i,x:longint。 function member(x:longint):boolean。 var p,e,mid:longint。 begin p:=1。 e:=a。 mid:=(p+e) div 2。 while (pmid)and(emid)and(da[mid]x) do begin if x=da[mid] then begin member:=true。 exit。 end。 if xda[mid] then begin e:=mid。 mid:=(p+e)div 2。 end else begin p:=mid。 mid:=(p+e)div 2。 end。 end。 if (da[p]=x)or(da[e]=x)or(da[mid]=x) then member:=true else member:=false。 end。 begin read(fin,b)。 s:=0。 for i:=1 to b do begin read(fin,x)。 if not member(x) then inc(s)。 end。 end。 procedure out。 begin writeln(s)。 close(fin)。 end。 begin t:=meml[$40:$6C]。 for j:=1 to 50 do begin init。 sort(1,a)。 main。 out。 end。 t:=meml[$40:$6C]t。 writeln(t/:0:8)。 end. 3． 《找名字》的程序 program namenum。 const empty:string[12]=39。 39。 value:array[2..9,1..3]of string=((39。 A39。 ,39。 B39。 ,39。 C39。 ), (39。 D39。 ,39。 E39。 ,39。 F39。 ), (39。 G。