資源描述：
《暴雪哈希算法》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。
1、暴雪公司有個經(jīng)典的字符串的hash公式 先提一個簡單的問題，假如有一個龐大的字符串數(shù)組，然后給你一個單獨的字符串，讓你從這個數(shù)組中查找是否有這個字符串并找到它，你會怎么做？有一個方法最簡單，老老實實從頭查到尾，一個一個比較，直到找到為止，我想只要學過程序設計的人都能把這樣一個程序作出來，但要是有程序員把這樣的程序交給用戶，我只能用無語來評價，或許它真的能工作，但...也只能如此了。最合適的算法自然是使用HashTable（哈希表），先介紹介紹其中的基本知識，所謂Hash，一般是一個整數(shù)，通過某種算法，可以把一個字符串"壓縮"成一個整數(shù)，這個數(shù)稱為Hash，當然，無論如何，一個32位整數(shù)是無
2、法對應回一個字符串的，但在程序中，兩個字符串計算出的Hash值相等的可能非常小，下面看看在MPQ中的Hash算法 代碼 unsignedlongHashString(char*lpszFileName,unsignedlongdwHashType) { unsignedchar*key=(unsignedchar*)lpszFileName; unsignedlongseed1=0x7FED7FED,seed2=0xEEEEEEEE; intch; while(*key!=0) { ch=toupper(*key); seed1=cryptTable[(dwHashTyp
3、e<<8)ch]^(seed1seed2); seed2=chseed1seed2(seed2<<5)3; } returnseed1; } Blizzard的這個算法是非常高效的，被稱為"One-WayHash"，舉個例子，字符串"unitneutralacritter.grp"通過這個算法得到的結(jié)果是0xA26067F3。是不是把第一個算法改進一下，改成逐個比較字符串的Hash值就可以了呢，答案是，遠遠不夠，要想得到最快的算法，就不能進行逐個的比較，通常是構(gòu)造一個哈希表(HashTable)來解決問題，哈希表是一個大數(shù)組，這個數(shù)組的容量根據(jù)程序的要求來定義，例如1024，每一個
4、Hash值通過取模運算(mod)對應到數(shù)組中的一個位置，這樣，只要比較這個字符串的哈希值對的位置又沒有被占用，就可以得到最后的結(jié)果了，想想這是什么速度？是的，是最快的O(1)，現(xiàn)在仔細看看這個算法吧 代碼 intGetHashTablePos(char*lpszString,SOMESTRUCTURE*lpTable,intnTableSize) { intnHash=HashString(lpszString),nHashPos=nHash%nTableSize; if(lpTable[nHashPos].bExists&&!strcmp(lpTable[nHashPos].pS
5、tring,lpszString)) returnnHashPos; else return-1;//Errorvalue } 看到此，我想大家都在想一個很嚴重的問題："假如兩個字符串在哈希表中對應的位置相同怎么辦？",究竟一個數(shù)組容量是有限的，這種可能性很大。解決該問題的方法很多，我首先想到的就是用"鏈表",感謝大學里學的數(shù)據(jù)結(jié)構(gòu)教會了這個百試百靈的法寶，我碰到的很多算法都可以轉(zhuǎn)化成鏈表來解決，只要在哈希表的每個入口掛一個鏈表，保存所有對應的字符串就OK了。事情到此似乎有了完美的結(jié)局，假如是把問題獨自交給我解決，此時我可能就要開始定義數(shù)據(jù)結(jié)構(gòu)然后寫代碼了。然而Blizzard的程
6、序員使用的方法則是更精妙的方法?；驹砭褪牵核麄冊诠１碇胁皇怯靡粋€哈希值而是用三個哈希值來校驗字符串。中國有句古話"再一再二不能再三再四"，看來Blizzard也深得此話的精髓，假如說兩個不同的字符串經(jīng)過一個哈希算法得到的入口點一致有可能，但用三個不同的哈希算法算出的入口點都一致，那幾乎可以肯定是不可能的事了，這個幾率是1:18889465931478580854784，大概是10的22.3次方分之一，對一個游戲程序來說足夠安全了?，F(xiàn)在再回到數(shù)據(jù)結(jié)構(gòu)上，Blizzard使用的哈希表沒有使用鏈表，而采用"順延"的方式來解決問題，看看這個算法： 代碼 intGetHashTablePos
7、(char*lpszString,MPQHASHTABLE*lpTable,intnTableSize) { constintHASH_OFFSET=0,HASH_A=1,HASH_B=2; intnHash=HashString(lpszString,HASH_OFFSET); intnHashA=HashString(lpszString,HASH_A); intnHashB=HashStrin
