國家集訓(xùn)隊2007論文集1.楊弋《hash在信息學(xué)

《國家集訓(xùn)隊2007論文集1.楊弋《hash在信息學(xué)》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、Hash在信息學(xué)競賽中的一類應(yīng)用【正文】Hash表作為一種高效的數(shù)據(jù)結(jié)構(gòu)，有著廣泛的應(yīng)用。如果Hash函數(shù)設(shè)計合理，理想情況下每次查詢的時間花費(fèi)僅僅為O(h/r)，即和Hash表容量與剩余容量的比值成正比。只要Hash表容量達(dá)到實(shí)際使用量的大約1.5倍以上，查詢花費(fèi)的時間基本就可以認(rèn)為恒為O(1)。對于一個Hash表，一個好的Hash函數(shù)是尤其重要的，因為它能使Hash表保證效率。一個好的Hash函數(shù)最顯而易見的特征是，能使不相同的東西經(jīng)過Hash之后只有很小的幾率相同。這樣能避免過多沖突的產(chǎn)生。Hash表離不開Hash函數(shù)，但是反過來

2、呢？有的時候，Hash函數(shù)卻是可以離開Hash表的。一個常見的例子就是著名的MD5算法，它是一個Hash函數(shù)，但是它的用途往往是對信息進(jìn)行加密，以驗證信息的正確性。換句話說，我們事實(shí)上是通過直接比較MD5算出的結(jié)果是否相同以推斷原文內(nèi)容是否一致。除了MD5，常用的CRC32校驗碼和SHA-1算法也是基于類似的想法而產(chǎn)生的。那么，信息學(xué)競賽中，這樣的算法有沒有用武之地呢？本文要討論的，就是這一類以判重或判等價為目標(biāo)的Hash函數(shù)。讓我們來看看例題1。例題1多維匹配題目大意在一個串中求另一個串第一次出現(xiàn)的位置，很簡單，KMP即可。擴(kuò)展到二維

3、情況，就是求在一個矩陣中求另一個矩陣第一次出現(xiàn)的位置。而如果擴(kuò)展到k維的情況，又該怎么做呢？待匹配數(shù)組X各維的尺寸為N1，N2，…，Nk，模式數(shù)組Y各維的尺寸為M1，M2，…，Mk。記N=N1N2…Nk，M=M1M2…Mk。保證k≤10，Ni≥Mi，而N和M都不超過500000。算法分析本題常見的算法是多維情況的KMP，先算1維時的匹配情況，然后處理2維，3維……直到N維時的情況。時間復(fù)雜度為O(k*(N+M))。但是它難以理解和記憶，也不容易在比賽中的短短幾個小時完成和寫對。樸素的解法相對易于實(shí)現(xiàn)，但是使樸素算法很容易想到，而且針對數(shù)

4、據(jù)又很容易制作，因此只有在完全沒有思路的時候才值得一試。有沒有第三種選擇呢？答案是肯定的。樸素的解法相當(dāng)于枚舉了每個起點(diǎn)（起點(diǎn)數(shù)量顯然不會超過N）并加以判斷，然而判斷兩個子數(shù)組是否相同的時間復(fù)雜度高達(dá)O(M)，這就是導(dǎo)致樸素算法在遇到針對數(shù)據(jù)的情況下很慢的原因。能不能在比較兩個子數(shù)組之前先快速地排除一些明顯不可能的情況呢？由于很容易構(gòu)造出僅有一個字符不同的數(shù)據(jù)，不管采用什么順序比較都會消耗大量的時間。Hash函數(shù)在這里派上了用場。我們可以對每個尺寸與模式數(shù)組一樣的子數(shù)組計算一個Hash值。顯然，只有當(dāng)某個子數(shù)組的Hash值與模式數(shù)組的H

5、ash值一樣，它們才值得比較。多維的KMP要從1維的情況開始考慮，并推廣至高維。那么這種計算Hash函數(shù)的匹配算法我們也可以先考慮一維的情況——就是Rabin-Karp算法。對于一個字符串S，可以使用這個函數(shù)求出其Hash值：那么，模式串Y的Hash值就可以輕松地求出。記待匹配串X從第i個字符開始的長度為M的子串為Si，則不難發(fā)現(xiàn)f(Si+1)和f(Si)的關(guān)系：換個角度，如果不考慮modq，這個函數(shù)就是把字符串看作一個p進(jìn)制數(shù)求出的值，這樣，Xi+1就是Xi“左移”一位，然后去掉最前面一位，再加上右面新進(jìn)來的一位得到的。因此上面的遞推

6、公式也是顯然的。有了這個遞推公式，不難在線性時間內(nèi)求出X的所有長度為M的子串的Hash值?，F(xiàn)在把問題擴(kuò)展到高維的情況。不難發(fā)現(xiàn)要計算的Hash值的個數(shù)仍然不超過N個，可見，只要有合適的遞推方法，仍然可以在線性時間內(nèi)求出所有子矩陣的Hash值。事實(shí)上，一個M1行，M2列的子矩陣可以被看作是M2個“豎條”組成的一個串。我們可以先把每個長度為M1的“豎條”計算出一個Hash值，然后再計算二維情況的Hash值。需要注意的一點(diǎn)是，在計算一維的Hash值（“豎條”的Hash值）和計算二維的Hash值時使用的b值不能一樣，不然不難想到下面反例：aba

7、aaaba它們并不相同，但是Hash的結(jié)果肯定一樣。這就違背了使用Hash的初衷。因此，在第一維的計算和第二維的計算中要使用不同的p值。二維情況時，求出所有長度為M1的“豎條”所需要花費(fèi)的時間是O(N)的，然后把這些豎條的Hash值看作“字母”計算橫向的Hash值（即各個子矩陣的Hash值），所花費(fèi)的時間也是O(N)的?？倳r間復(fù)雜度仍然是O(N)的。二維情況的Hash函數(shù)為（len1(S)和len2(S)分別表示S在兩個維度上的大?。侯愃频兀洿ヅ渚仃嘪從第i1行，第i2列為左上角的M1行，M2列的子矩陣為，我們有遞推式：式中和都是

8、一維情況下的Hash值，即預(yù)先計算出的“豎條”的Hash值。擴(kuò)展到k維情況，則不難想到，先算出所有尺寸為M1×M2×…×Mk-1的子數(shù)組的Hash值，再使用類似上面的辦法把這些尺寸為M1×M2×…×Mk-1