【正文】 得力助手 。 另一方 面，一味的追求低沖突率也不好。理論上，是可以設(shè)計(jì)出一個(gè)幾乎完美，幾乎沒有沖突的函數(shù)的。然而，這樣做顯然不值得，因?yàn)檫@樣的函數(shù)設(shè)計(jì)很浪費(fèi)時(shí)間而且編碼一定很復(fù)雜，與其花費(fèi)這么大的精力去設(shè)計(jì)函數(shù)，還不如用一個(gè)雖然沖突多一些但是編碼簡(jiǎn)單的函數(shù)。因此，函數(shù)還需要易于編碼，即易于實(shí)現(xiàn)。 綜上所述，設(shè)計(jì)一個(gè)好的哈希函數(shù)是很關(guān)鍵的。而 好 的標(biāo)準(zhǔn)，就是較低的沖突率和易于實(shí)現(xiàn)。 另外，使用哈希表并不是記住了前面的基本操作就能以不變應(yīng)萬變的。有的時(shí)候，需要按照題目的要求對(duì)哈希表的結(jié)構(gòu)作一些改進(jìn)。往往一些簡(jiǎn)單的改進(jìn)就 可以帶來巨大的方便。 這些只是一般原則，真正遇到試題的時(shí)候?qū)嶋H情況千變?nèi)f化，需要具體問題具體分析才行。下面，我們看幾個(gè)例子，看看這些原則是如何體現(xiàn)的。 有關(guān)字符串的例子 我們經(jīng)常會(huì)遇到處理字符串的問題，下面我們來看這個(gè)例子： 找名字 問題描述： 給定一個(gè)全部由字符串組成的字典，字符串全部由大寫字母構(gòu)成。其中為每個(gè)字符串編寫密碼，編寫的方式是對(duì)于 n 位字符串，給定一個(gè) n 位數(shù)，大寫字母與數(shù)字的對(duì)應(yīng)方式按照電話鍵盤的方式： 2: A,B,C 5: J,K,L 8: T,U,V 3: D,E,F 6: M,N,O 9: W,X,Y 4: G,H,I 7: P,R,S 題目給出一個(gè) 112 位的數(shù)，找出在字典中出現(xiàn)且密碼是這個(gè)數(shù)的所有字符串。字典中字符串的個(gè)數(shù)不超過 8000 。（這個(gè)是 USACO Training Gate 的一道題。） 分析： 看懂題目之后，對(duì)于給定的編碼，只需要一個(gè)回溯的過程，所有可能的原字符串都可以被列舉出來，剩下的就是檢查這個(gè)字符串是否在給定的 字典中了。所以這個(gè)問題需要的還是 某個(gè)元素是否在已知集合中？ 由于給出的 姓名 都是字符串，因此我們可以利用字符的 ASCII 碼。那么，如何設(shè)計(jì)這個(gè)哈希函數(shù)呢？注意到題目給出的字典中，最多能有 5000 個(gè)不同元素，而一個(gè)字符的 ASCII 碼只能有 26 種不同的取值，因此至少需要用在 3 個(gè)位置上的字符（ 26^3 5000，但是 26^2 5000 ），于是我們就選取 3 個(gè)位置上的字符。由于給定的字符串的長(zhǎng)度從 112 都有可能，為了容易實(shí)現(xiàn)，選取最開始的 1 個(gè)字符，和最末尾的 2 個(gè)字符。讓這 3 個(gè)字符組 成 27 進(jìn)制的 3 位數(shù)，則這個(gè)數(shù)的值就是這個(gè)字符串的編碼。這樣哈希函數(shù)就設(shè)計(jì)出來了！ 不過，由于可能出現(xiàn)只有 1 位的字符串，在寫函數(shù)代碼的時(shí)候需要特殊考慮；大素?cái)?shù)選取 13883 。 這個(gè)函數(shù)是這樣的： function hash(s:string):integer。 var i,tmp:longint。 begin tmp:=0。 {用來記錄 27 進(jìn)制數(shù)的值 } if length(s)1 then begin tmp:=tmp*27+ord(s[1])64。 for i:=1 downto 0 do tmp:=tmp*27+ord(s[length(s)i])64。 {取第一位和后兩位 } end else for i:=1 to 3 do tmp:=tmp*27+ord(s[1])64。{當(dāng)長(zhǎng)度為 1的時(shí)候特殊處理 } hash:=tmp mod 13883。 end。 值得指出的是，本題給出的字符串大都沒有什么規(guī)律，用哈希表可以 做到近似 平均 ，但是對(duì)于大多數(shù)情況，字符串是有規(guī)律的（例如英文單詞），這個(gè)時(shí)候用哈希表反而不好（例如英語中有很多以 con 開頭的單詞），通常用檢索樹解決這樣的查找問題。 在廣度優(yōu)先搜索中應(yīng)用的例子 在廣度優(yōu)先搜索中，一個(gè)通用而且有效的剪枝就是在拓展節(jié)點(diǎn)之前先判重。而判重的本質(zhì)也是數(shù)據(jù)的存儲(chǔ)與查找，因此哈希表大有用武之地。來看下面的例子： 轉(zhuǎn)花盆 題意描述 : 給定兩個(gè)正 6 邊形的花壇，要求求出從第一個(gè)變化到第二個(gè)的最小操作次數(shù)以及操作方式。一次 操作是：選定不在邊上的一盆花，將這盆花周圍的 6 盆花按照順時(shí)針或者逆時(shí)針的順序依次移動(dòng)一個(gè)單位。限定一個(gè)花壇里擺放的不同種類的花不超過 3種，對(duì)于任意兩種花，數(shù)量多的花的盆數(shù)至少是數(shù)量少的花的 2 倍 。（這是 SGOI8 的一道題） 分析： 首先確定本題可以用廣度優(yōu)先搜索處理，然后來看問題的規(guī)模。正 6 邊形共有 19 個(gè)格子可以用來放花，而且根據(jù)最后一句限定條件，至多只能存在 C(2,19) * C(5,17) = 1058148 種狀態(tài)，用搜索完全可行。然而操作的時(shí)候，可以預(yù)料產(chǎn)生的重復(fù)節(jié)點(diǎn)是相當(dāng)多的，需要迅速判 重才能在限定時(shí)間內(nèi)出解，因此想到了哈希表。那么這個(gè)哈希函數(shù)如何設(shè)計(jì)呢？注意到 19 個(gè)格子組成 6 邊形是有順序的，而且每一個(gè)格子只有 3種可能情況，那么用 3 進(jìn)制 19 位數(shù)最大 3^201=3486784400 用 Cardinal 完全可以承受。于是我們將每一個(gè)狀態(tài)與一個(gè)整數(shù)對(duì)應(yīng)起來，使用除余法就可以了。 小結(jié) 從這兩個(gè)例子可以發(fā)現(xiàn)，對(duì)于字符串的查找，哈希表雖然不是最好的方法，但是每個(gè)字符都有 天生 的 ASCII 碼，在設(shè)計(jì)哈希函數(shù)的時(shí)候可以直接利用。而其他方法，例如利用檢索樹的查找，編寫代碼不如哈 希表簡(jiǎn)潔。至于廣度優(yōu)先搜索中的判重更是直接利用了哈希表的特點(diǎn)。 另外，我們看到這兩個(gè)題目都是設(shè)計(jì)好哈希函數(shù)之后，直接利用前面的基本操作就可以了，因此重點(diǎn)應(yīng)該是在哈希函數(shù)的設(shè)計(jì)上（盡管這兩個(gè)例子的設(shè)計(jì)都很簡(jiǎn)單），需要注意題目本身可以利用的條件，以及估計(jì)值域的范圍。下面我們看兩個(gè)需要在哈希表基礎(chǔ)上作一些變化的例子。 需要微小變化的例子 下面，我們來分析一道 NOI 的試題： 方程的解數(shù) 問題描述 已知一個(gè) n 元高次方程： 其中： 是未知數(shù)， 是系數(shù)， 是指數(shù)。且方程中的所有數(shù)均為整數(shù)。 假設(shè)未知數(shù) 1≤ ≤ M, i=1,n，求這個(gè)方程的整數(shù)解的個(gè)數(shù)。 約束條件 1≤ n≤ 6； 1≤ M≤ 150； 方程的整數(shù)解的個(gè)數(shù)小于 。 本題中，指數(shù) Pi(i=1,2,…… ,n)均為正整數(shù)。 這個(gè)是 NOI 2020 的第二試中的《方程的解數(shù)》。 分析： 初看此題，題目要求出給定的方程解的個(gè)數(shù)，這個(gè)方程在最壞的情況下可以有 6 個(gè)未知數(shù)，而且次數(shù)由輸入決定。這樣就不能利用數(shù)學(xué)方法直接求出解的個(gè)數(shù)，而且注意到解的范圍最多 150 個(gè)數(shù)，因此恐怕只能使用枚舉法了。最簡(jiǎn)單的思路是窮舉所有未知數(shù)的取值，這樣時(shí)間復(fù)雜度是 O(M^6) ，無法承受。因此我們需要尋找更好的方法，自然想到能否縮小枚舉的范圍呢？但 是發(fā)現(xiàn)這樣也有很大的困難。我們?cè)俅巫⒁獾組 的范圍，若想不超時(shí)，似乎算法的復(fù)雜度上限應(yīng)該是 O(M^3) 左右，這是因?yàn)? 150^3 10000000 。這就啟示我們能否僅僅通過枚舉 3 個(gè)未知數(shù)的值來找到答案呢？如果這樣，前一半式子的值 S 可以確定，這時(shí)只要枚舉后 3 個(gè)數(shù)的值，檢查他們的和是否等于 S 即可。這樣只相當(dāng)于在 O(M^3) 前面加了一個(gè)系數(shù)，當(dāng)然還需要預(yù)先算出 1 到 150 的各個(gè)冪次的值。想到了這里，問題就是如何迅速的找到某個(gè) S 是否曾經(jīng)出現(xiàn)過，以及出現(xiàn)過了多少次，于是又變成了 某 個(gè)元素是否在給定集合中 這個(gè)問題。所以，我們還是使用哈希表解決這個(gè)問題。至于哈希函數(shù)不是問題，還是把 S 的值作為關(guān)鍵字使用除余法即可。然而有一點(diǎn)需要注意，這個(gè)例子我們不僅需要紀(jì)錄某個(gè) S 是否出現(xiàn)，出現(xiàn)的次數(shù)也很重要，所以可以用一個(gè) 2 維數(shù)組，僅僅是加了一個(gè)存儲(chǔ)出現(xiàn)次數(shù)的域而已。 Var e:array[0..max1,1..2]of longint。 {e[x,1] 記錄哈希函數(shù)值為 x 的 S 值， e[x,2] 記錄這個(gè) S 值出現(xiàn)了幾次 } 因此 insert 過程也需要一些變化： procedure ins(x:longint)。 var posi:longint。 begin posi:=locate(x)。 e[posi,1]:=x。 inc(e[posi,2])。 {僅僅這一條語句，就可以記錄下來 S 出現(xiàn)了幾次 } end。 最后一個(gè)例子 下面我們來仔細(xì)分析下面這個(gè)問題： 迷宮的墻 題意描述 : 神話中 byte 山邊有一個(gè)井之迷宮。迷宮的入口在山頂。迷宮中有許多房間，每個(gè)的顏色是 以下之一：紅、綠、藍(lán)。兩個(gè)相同顏色的房間看起來相似而不可區(qū)分。每個(gè)房間里有三口井標(biāo)以 1,2,3。從一個(gè)房間到另一間只有一種方式：從上面房間的井里跳到（不一定豎直地）井底的房間?？梢詮娜肟诜块g到達(dá)任何其他房間。迷宮中的所有通路走向坐落在最底部的龍宮。所有的迷宮之旅對(duì)應(yīng)了一系列在相繼訪問的房間里選擇的井的標(biāo)號(hào)。這一列數(shù)稱為一個(gè)旅行計(jì)劃。一個(gè)走過好幾次迷宮的英雄 bytezar 畫好了圖，然而有的房間重復(fù)出現(xiàn)了多次。 輸入： 第一行有一個(gè)整數(shù) n,2=n=6000，房間數(shù)（包括龍宮）。房間從１到 n 標(biāo)號(hào)，較大編號(hào)的房間再較低處（入口房間編號(hào)１，龍宮編號(hào) n）。接下的 n1 行描述迷宮的房間（除了龍宮）和井。每行有一個(gè)字母，一個(gè)空格，和三個(gè)由空格分隔的整數(shù)。字母代表了房間的顏色（ C紅， Z綠， N藍(lán)），第 i(i=1,2,3)個(gè)數(shù)是第 i 個(gè)井通往的房間號(hào)。 輸出： 迷宮最少的房間數(shù)目 這是 IOI 2020 中國(guó)國(guó)家集訓(xùn)隊(duì)難題討論活動(dòng)的 0020 題。 分析： 題目的意思是給出這個(gè)迷宮的地圖，去掉重復(fù)出現(xiàn)的房間，找出這個(gè)迷宮的最少房間數(shù)目。于是關(guān)鍵就是確定什么樣的房間是重復(fù)的。通過對(duì)樣例的分析，可以看出 這樣的房間是重復(fù)的：如果兩個(gè)房間 i 和 j （ 1=i,j =n1），他們的顏色相同，而且第 k (k=1,2,3) 堵墻通向的房間或者相同、或者重復(fù)。因?yàn)檫@樣從 i 和 j 可到達(dá)的房間是完全相同的。 所以，我們只需要記錄下每個(gè)房間的情況和已經(jīng)被確定相同的房間，然后挨個(gè)比較即可。于是又需要用到高效的數(shù)據(jù)存儲(chǔ)與查找，自然想到哈希表。然而，這里面需要對(duì)哈希表作更大的改進(jìn)：首先每個(gè)房間只能是 3 種顏色之一，因此針對(duì)每種顏色分別建立哈希表，可以使哈希函數(shù)的自變量減少一個(gè)；其次還需要紀(jì)錄每個(gè)不重復(fù)的房間每 堵墻都通向哪個(gè)房間，還有哪些房間是重復(fù)的。 具體這樣實(shí)現(xiàn)： var e:array[0..2,0..p1,1..4]of longint。 {0..2 代表共有 3 種顏色， 0..p1 是哈希函數(shù)的值域，而 1..4 中的 1..3 表示三堵墻連接到那個(gè)房間， 4 表示這個(gè)單元存儲(chǔ)的是哪個(gè)節(jié)點(diǎn) } r:array[1..maxn]of longint。 {r[i] 表示與 i 相同的節(jié)點(diǎn)。如果有多個(gè)節(jié)點(diǎn)都是相同的，擇取其中最大的（這一點(diǎn)不需要特殊的操作，只要在處理節(jié)點(diǎn)的時(shí)候注意就行了） } 至于哈希函數(shù)，最開始我是隨意