【文章內(nèi)容簡介】 的寫了一個（因為越是隨意的，就越是隨機的?。ㄎ缓瘮?shù)是這樣的： 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 堵墻的值任意乘大素數(shù)相加再取余數(shù)，使得結果分布比較隨機，也就比較均勻 } 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。 但是后來發(fā)現(xiàn)完全沒有必要這樣做，這樣的哈希函數(shù)在計算 t 的時候浪費了很多時間（不過數(shù)據(jù)規(guī)模不是很大，所以這點不十分明顯），而且素數(shù)起到的作用也不應當是這樣的。其實讓 r[b],r[c],r[d] 組成 n 進制數(shù)就完全能夠達到目的了，加入了素數(shù)不僅是小規(guī)模數(shù)據(jù)計算浪費時間，對大數(shù)據(jù)最后結果的分布平均也沒有起到比 n 進制數(shù)更多的作用。因此改為 t:=r[b]*sqr(n)+r[c]*n+r[d]。 當然肯定會有更好的哈希函數(shù)的。 小結 第一個例子，乍一看與哈希表毫無關系；第二個例子敘述比較復雜，但是經(jīng)過仔細分析，發(fā)現(xiàn)問題的本質都是確定 某個元素是否在給定集合中 ，這正是哈希表的特點。所以，不論題目的表面看起來如何，只要本質是需要 高效的數(shù)據(jù)檢索，哈希表通常就是最好的選擇！ 另外，這兩個例子都在原來哈希表的基礎上作了一些變化。第一個例子加入了紀錄某個值出現(xiàn)次數(shù)的域，第二個例子加入了紀錄所有墻的情況以及原節(jié)點編號的域。雖然都只是很小的變化，但是卻給問題的解決帶來了不小的方便。因此我們得到提示：哈希表雖然有標準的操作，但也不是一成不變的，需要具體問題具體分析，根據(jù)題目的要求和特點作出相應變化。 5. 總結 本文介紹了有關哈希表方面的內(nèi)容，分析了它的特點和優(yōu)點，指出了應用需要注意的問題，并且重點舉了幾個例子來說明它在競賽中的應用 。希望讀者讀完本文能夠對哈希表有更全面的了解，并能在競賽中應用自如！ 參考文獻： 1． 《算法與數(shù)據(jù)結構（第二版）》 付清祥 王曉東 編著 2． 《奧賽兵法信息學（計算機）》 朱全民 主編 3． 《 SGOI8 煩惱的設計師 解題報告》 曙光網(wǎng)信息學 4． 《 Data Structures》 USACO Training Gate 附錄： 這是我第一次寫論文，水平很有限，希望大家指出我的缺點和不足！ 我的郵箱 下面是所有前面提到的程序。其中只有 SGOI8 Flowers 的程序是網(wǎng)上提供的標程，其余的都是我自己寫的，并且已經(jīng)通過所有測試數(shù)據(jù)。 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