【正文】 發(fā)生這種余數(shù)分布不均勻的情況就越頻繁，沖突的幾率越高。記住 素?cái)?shù)是我們的得力助手 。理論上，是可以設(shè)計(jì)出一個(gè)幾乎完美，幾乎沒(méi)有沖突的函數(shù)的。因此，函數(shù)還需要易于編碼，即易于實(shí)現(xiàn)。而 好 的標(biāo)準(zhǔn)，就是較低的沖突率和易于實(shí)現(xiàn)。有的時(shí)候，需要按照題目的要求對(duì)哈希表的結(jié)構(gòu)作一些改進(jìn)。 這些只是一般原則，真正遇到試題的時(shí)候?qū)嶋H情況千變?nèi)f化，需要具體問(wèn)題具體分析才行。 有關(guān)字符串的例子 我們經(jīng)常會(huì)遇到處理字符串的問(wèn)題，下面我們來(lái)看這個(gè)例子： 找名字 問(wèn)題描述： 給定一個(gè)全部由字符串組成的字典，字符串全部由大寫(xiě)字母構(gòu)成。字典中字符串的個(gè)數(shù)不超過(guò) 8000 。） 分析： 看懂題目之后，對(duì)于給定的編碼，只需要一個(gè)回溯的過(guò)程，所有可能的原字符串都可以被列舉出來(lái)，剩下的就是檢查這個(gè)字符串是否在給定的 字典中了。那么，如何設(shè)計(jì)這個(gè)哈希函數(shù)呢？注意到題目給出的字典中，最多能有 5000 個(gè)不同元素，而一個(gè)字符的 ASCII 碼只能有 26 種不同的取值，因此至少需要用在 3 個(gè)位置上的字符（ 26^3 5000，但是 26^2 5000 ），于是我們就選取 3 個(gè)位置上的字符。讓這 3 個(gè)字符組 成 27 進(jìn)制的 3 位數(shù)，則這個(gè)數(shù)的值就是這個(gè)字符串的編碼。 這個(gè)函數(shù)是這樣的： function hash(s:string):integer。 begin tmp:=0。 for i:=1 downto 0 do tmp:=tmp*27+ord(s[length(s)i])64。{當(dāng)長(zhǎng)度為 1的時(shí)候特殊處理 } hash:=tmp mod 13883。 值得指出的是，本題給出的字符串大都沒(méi)有什么規(guī)律，用哈希表可以 做到近似 平均 ，但是對(duì)于大多數(shù)情況，字符串是有規(guī)律的（例如英文單詞），這個(gè)時(shí)候用哈希表反而不好（例如英語(yǔ)中有很多以 con 開(kāi)頭的單詞），通常用檢索樹(shù)解決這樣的查找問(wèn)題。而判重的本質(zhì)也是數(shù)據(jù)的存儲(chǔ)與查找，因此哈希表大有用武之地。一次 操作是：選定不在邊上的一盆花，將這盆花周圍的 6 盆花按照順時(shí)針或者逆時(shí)針的順序依次移動(dòng)一個(gè)單位。（這是 SGOI8 的一道題） 分析： 首先確定本題可以用廣度優(yōu)先搜索處理，然后來(lái)看問(wèn)題的規(guī)模。然而操作的時(shí)候，可以預(yù)料產(chǎn)生的重復(fù)節(jié)點(diǎn)是相當(dāng)多的，需要迅速判 重才能在限定時(shí)間內(nèi)出解，因此想到了哈希表。于是我們將每一個(gè)狀態(tài)與一個(gè)整數(shù)對(duì)應(yīng)起來(lái)，使用除余法就可以了。而其他方法，例如利用檢索樹(shù)的查找，編寫(xiě)代碼不如哈 希表簡(jiǎn)潔。 另外，我們看到這兩個(gè)題目都是設(shè)計(jì)好哈希函數(shù)之后，直接利用前面的基本操作就可以了，因此重點(diǎn)應(yīng)該是在哈希函數(shù)的設(shè)計(jì)上（盡管這兩個(gè)例子的設(shè)計(jì)都很簡(jiǎn)單），需要注意題目本身可以利用的條件，以及估計(jì)值域的范圍。 需要微小變化的例子 下面，我們來(lái)分析一道 NOI 的試題： 方程的解數(shù) 問(wèn)題描述 已知一個(gè) n 元高次方程： 其中： 是未知數(shù)， 是系數(shù)， 是指數(shù)。 假設(shè)未知數(shù) 1≤ ≤ M, i=1,n，求這個(gè)方程的整數(shù)解的個(gè)數(shù)。 本題中，指數(shù) Pi(i=1,2,…… ,n)均為正整數(shù)。 分析： 初看此題，題目要求出給定的方程解的個(gè)數(shù)，這個(gè)方程在最壞的情況下可以有 6 個(gè)未知數(shù)，而且次數(shù)由輸入決定。最簡(jiǎn)單的思路是窮舉所有未知數(shù)的取值，這樣時(shí)間復(fù)雜度是 O(M^6) ，無(wú)法承受。我們?cè)俅巫⒁獾組 的范圍，若想不超時(shí)，似乎算法的復(fù)雜度上限應(yīng)該是 O(M^3) 左右，這是因?yàn)? 150^3 10000000 。這樣只相當(dāng)于在 O(M^3) 前面加了一個(gè)系數(shù)，當(dāng)然還需要預(yù)先算出 1 到 150 的各個(gè)冪次的值。所以，我們還是使用哈希表解決這個(gè)問(wèn)題。然而有一點(diǎn)需要注意，這個(gè)例子我們不僅需要紀(jì)錄某個(gè) S 是否出現(xiàn)，出現(xiàn)的次數(shù)也很重要，所以可以用一個(gè) 2 維數(shù)組，僅僅是加了一個(gè)存儲(chǔ)出現(xiàn)次數(shù)的域而已。 {e[x,1] 記錄哈希函數(shù)值為 x 的 S 值， e[x,2] 記錄這個(gè) S 值出現(xiàn)了幾次 } 因此 insert 過(guò)程也需要一些變化： procedure ins(x:longint)。 begin posi:=locate(x)。 inc(e[posi,2])。 最后一個(gè)例子 下面我們來(lái)仔細(xì)分析下面這個(gè)問(wèn)題： 迷宮的墻 題意描述 : 神話中 byte 山邊有一個(gè)井之迷宮。迷宮中有許多房間，每個(gè)的顏色是 以下之一：紅、綠、藍(lán)。每個(gè)房間里有三口井標(biāo)以 1,2,3?？梢詮娜肟诜块g到達(dá)任何其他房間。所有的迷宮之旅對(duì)應(yīng)了一系列在相繼訪問(wèn)的房間里選擇的井的標(biāo)號(hào)。一個(gè)走過(guò)好幾次迷宮的英雄 bytezar 畫(huà)好了圖，然而有的房間重復(fù)出現(xiàn)了多次。房間從１到 n 標(biāo)號(hào)，較大編號(hào)的房間再較低處（入口房間編號(hào)１，龍宮編號(hào) n）。每行有一個(gè)字母，一個(gè)空格，和三個(gè)由空格分隔的整數(shù)。 輸出： 迷宮最少的房間數(shù)目 這是 IOI 2020 中國(guó)國(guó)家集訓(xùn)隊(duì)難題討論活動(dòng)的 0020 題。于是關(guān)鍵就是確定什么樣的房間是重復(fù)的。因?yàn)檫@樣從 i 和 j 可到達(dá)的房間是完全相同的。于是又需要用到高效的數(shù)據(jù)存儲(chǔ)與查找，自然想到哈希表。 具體這樣實(shí)現(xiàn)： var e:array[0..2,0..p1,1..4]of longint。 {r[i] 表示與 i 相同的節(jié)點(diǎn)。 var t:longint。 begin t:=r[b]*10037+r[c]*5953+r[d]*2999。 i:=0。 {線性重新散列 } locate:=(t+i)mod p。 但是后來(lái)發(fā)現(xiàn)完全沒(méi)有必要這樣做，這樣的哈希函數(shù)在計(jì)算 t 的時(shí)候浪費(fèi)了很多時(shí)間（不過(guò)數(shù)據(jù)規(guī)模不是很大，所以這點(diǎn)不十分明顯），而且素?cái)?shù)起到的作用也不應(yīng)當(dāng)是這樣的。因此改為 t:=r[b]*sqr(n)+r[c]*n+r[d]。 小結(jié) 第一個(gè)例子，乍一看與哈希表毫無(wú)關(guān)系；第二個(gè)例子敘述比較復(fù)雜，但是經(jīng)過(guò)仔細(xì)分析，發(fā)現(xiàn)問(wèn)題的本質(zhì)都是確定 某個(gè)元素是否在給定集合中 ，這正是哈希表的特點(diǎn)。第一個(gè)例子加入了紀(jì)錄某個(gè)值出現(xiàn)次數(shù)的域，第二個(gè)例子加入了紀(jì)錄所有墻的情況以及原節(jié)點(diǎn)編號(hào)的域。因此我們得到提示：哈希表雖然有標(biāo)準(zhǔn)的操作，但也不是一成不變的，需要具體問(wèn)題具體分析，根據(jù)題目的要求和特點(diǎn)作出相應(yīng)變化。希望讀者讀完本文能夠?qū)１碛懈娴牧私?，并能在?jìng)賽中應(yīng)用自如！ 參考文獻(xiàn)： 1． 《算法與數(shù)據(jù)結(jié)構(gòu)（第二版）》 付清祥 王曉東 編著 2． 《奧賽兵法信息學(xué)（計(jì)算機(jī)）》 朱全民 主編 3． 《 SGOI8 煩惱的設(shè)計(jì)師 解題報(bào)告》 曙光網(wǎng)信息學(xué) 4． 《 Data Structures》 USACO Training Gate 附錄： 這是我第一次寫(xiě)論文，水平很有限，希望大家指出我的缺點(diǎn)和不足！ 我的郵箱 下面是所有前面提到的程序。 1． 哈希表的程序 program subset。 var fin,fout:text。 index:array[0..max1]of longint。 function locate(t:longint):longint。 begin tmp:=t mod max。 locate:=tmp。 procedure int(t:longint)。 end。 begin if index[locate(t)]=t then member:=true else member:=false。 procedure init。 begin assign(fin,39。)。39。 reset(fin)。 close(fout)。 read(fin,a)。 int(shu)。 end。 var i,shu:longint。 s:=0。 if not member(shu) then inc(s)。 end。 begin writeln(s)。 end。 for j:=1 to 50 do begin init。 out。 t:=meml[$40:$6C]t。 end. 2． 快速排序 +二分查找的程序 program subset。 var a,b,s,j:longint。 fin:text。 procedure init。 begin assign(fin,39。)。 read(fin,a)。 end。 var p:longint。 var value,i,j,temp:longint。 i:=m1。 while true do begin repeat inc(i)。 repeat dec(j)。 if ij then begin temp:=da[i]。 da[j]:=temp。 exit。 end。 begin if mn then begin p:=locate。 sort(p+1,n)。 end。 var i,x:longint。 var p,e,mid:longint。 e:=a。 while (pmid)and(emid)and(da[mid]x) do begin if x=da[mid] then begin member:=true。 end。 mid:=(p+e)div 2。 mid:=(p+e)div 2。 end。 end。 s:=0。 if not member(x) then inc(s)。 end。 begin writeln(s)。 end。 for j:=1 to 50 do begin init。 main。 end。 writeln(t/:0:8)。 const empty:string[12]=39。 value:array[2..9,1..3]of string=((39。,39。,39。), (39。,39。,39。), (39。,39。,39。), (39。,39。,39。), (39