哈希算法圖解?暴雪公司的魔獸、星際等遊戲都一樣一個非常大的MPQ文件，該文件存儲了遊戲中的大部分數據，想要把這些文字找出來，簡單的辦法是從數組頭開始，一個個字符串讀過去，比較每一個，直到找到對應的内容Blizzard的天才和牛人們當然不會這樣做，他們用了更聰明的方法: 用某種算法，把一個字符串壓縮成一個整數，即hash然後，根據這個整數值，直接得到此字符串在整個文件中的位置，從而直接讀取之，現在小編就來說說關于哈希算法圖解?下面内容希望能幫助到你，我們來一起看看吧!

哈希算法圖解

暴雪公司的魔獸、星際等遊戲都一樣一個非常大的MPQ文件，該文件存儲了遊戲中的大部分數據，想要把這些文字找出來，簡單的辦法是從數組頭開始，一個個字符串讀過去，比較每一個，直到找到對應的内容。Blizzard的天才和牛人們當然不會這樣做，他們用了更聰明的方法: 用某種算法，把一個字符串壓縮成一個整數，即hash。然後，根據這個整數值，直接得到此字符串在整個文件中的位置，從而直接讀取之。

Blizzard的這個算法是非常高效的，被稱為”One-Way Hash”。所謂One-Way Hash,就是無法從求得的hash值通過簡單的逆運算就得到原來的字符串。關于具體的實現原理，inside MPQ 的第二章有詳細的介紹，以下為第二章内容的翻譯：

貫穿計算機發展曆史，大多數進步都是源于某些問題的解決，在這一節中，我們來看一看與MPQ 格式相關問題及解決方案；

問題一：你有一個很大的字符串數組，同時，你另外還有一個字符串，需要知道這個字符串是否 已經存在于字符串數組中。你可能會對數組中的每一個字符串進行比較，但是在實際項目中，你會發現這種做法對某些特殊應用來說太慢了。必須尋求其他途徑。那麼如何才能在不作遍曆比較的情況下知道這個字符串是否存在于數組中呢？

解決方案：哈希表。哈希表是通過更小的數據類型表示其他更大的數據類型。在這種情況下， 你可以把哈希表存儲在字符串數組中，然後你可以計算字符串的哈希值，然後與已經存儲的字符串的哈希值進行比較。如果有匹配的哈希值，就可以通過字符串比較 進行匹配驗證。這種方法叫索引，根據數組的大小以及字符串的平均長度可以約100倍。

01 . unsigned long HashString(char *lpszString) 02 . { 03 . unsigned long ulHash = 0xf1e2d3c4; 04 . while (*lpszString != 0) 05 . { 06 . ulHash <<= 1; 07 . ulHash = *lpszString ; 08 . } 09 . return ulHash; 10. }

上面代碼中的函數演示了一種非常簡單的散列算法。這個函數在遍曆字符串過程中，将哈希值左移一位，然後加上字符值；通過這個算法，字符串”arrunits.dat” 的哈希值是0x5A858026，字符串”unitneutralacritter.grp” 的哈希值是0x694CD020；現在，衆所周知的，這是一個基本沒有什麼實用價值的簡單算法，因為它會在較低的數據範圍内産生相對可預測的輸出，從而可能會産生大量沖突（不同的字符串産生相同的哈希值）。

MPQ格式，使用了一種非常複雜的散列算法（如下所示），産生完全不可預測的哈希值，這個算法十分有效，這就是所謂的單向散列算法。通過單向散列算法幾乎不可能通過哈希值來唯一的确定輸入值。使用這種算法，文件名 “arrunits.dat” 的哈希值是0xF4E6C69D，”unitneutralacritter.grp” 的哈希值是 0xA26067F3。

01 . unsigned long HashString(char *lpszFileName, unsigned long dwHashType) 02 . { 03 . unsigned char *key = (unsigned char *)lpszFileName; 04 . unsigned long seed1 = 0x7FED7FED, seed2 = 0xEEEEEEEE; 05 . int ch; 06 . while(*key != 0) 07 . { 08 . ch = toupper(*key ); 09 . seed1 = cryptTable[(dwHashType << 8) ch] ^ (seed1 seed2); 10 . seed2 = ch seed1 seed2 (seed2 << 5) 3; 11 . } 12 . return seed1; 13. }

問題二：您嘗試在前面的示例中使用相同索引，您的程序一定會有中斷現象發生，而且不夠快 。如果想讓它更快，您能做的隻有讓程序不去查詢數組中的所有散列值。或者 您可以隻做一次對比就可以得出在列表中是否存在字符串。聽起來不錯，真的麼？不可能的啦

解決：一個哈希表就是以字符串的哈希值作為下标的一類數組。我的意思是，哈希表使用一個固定長度的字符串數組（比如1024，2的偶次幂）進行存儲；當你要看看這個字符串是否存在于哈希表中，為了獲取這個字符串在哈希表中的位置，你首先計算字符串的哈希值，然後哈希表的長度取模。這樣如果你像上一節那樣使用簡單的哈希算法，字符串”arrunits.dat” 的哈希值是0x5A858026,偏移量0×26（0x5A858026 除于0×400等于0x16A160，模0×400等于0×26）。因此，這個位置的字符串将與新加入的字符串進行比較。如果0X26處的字符串不匹配或不存在，那麼表示新增的字符串在數組中不存在。下面是示意的代碼：

01 . int GetHashTablePos(char *lpszString, SOMESTRUCTURE *lpTable, int nTableSize) 02 . { 03 . int nHash = HashString(lpszString), nHashPos = nHash % nTableSize; 04 . if (lpTable[nHashPos].bExists && !strcmp(lpTable[nHashPos].pString, lpszString)) 05 . return nHashPos; 06 . else 07 . return -1; //Error value 08. }

上面的說明中存在一個刺眼的缺陷。當有沖突（兩個不同的字符串有相同的哈希值）發生的時候怎麼辦？顯而易見的，它們不能占據哈希表中的同一個位置。通常的解決辦法是為每一個哈希值指向一個鍊表，用于存放所有哈希沖突的值；

MPQs使用一個存放文件名的哈希表來跟蹤文件内部，但是表的格式與通常方法有點不同，首先不像通常的做法使用哈希值作為偏移量，存儲實際的文件名。MPQs 根本不存儲文件名，而是使用了三個不同的哈希值：一個用做哈希表偏移量，兩個用作核對。這兩個核對的哈希值用于替代文件名。當然從理論上說存在兩個不同的文件名得到相同的三個哈希值，但是這種情況發送的幾率是：1:18889465931478580854784,這應該足夠安全了。

MPQ’s的哈希表的實現與傳統實現的另一個不同的地方是，相對與傳統做法（為每個節點使用一個鍊表，當沖突發生的時候，遍曆鍊表進行比較），看一下下面的示範代碼，在MPQ中定位一個文件進行讀操作：

01 . int GetHashTablePos(char *lpszString, MPQHASHTABLE *lpTable, int nTableSize) 02 . { 03 . const int HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2; 04 . int nHash = HashString(lpszString, HASH_OFFSET); 05 . int nHashA = HashString(lpszString, HASH_A); 06 . int nHashB = HashString(lpszString, HASH_B); 07 . int nHashStart = nHash % nTableSize,nHashPos = nHashStart; 08 . while (lpTable[nHashPos].bExists) 09 . { 10 . if (lpTable[nHashPos].nHashA == nHashA && lpTable[nHashPos].nHashB == nHashB) 11 . return nHashPos; 12 . else 13 . nHashPos = (nHashPos 1) % nTableSize; 14 . if (nHashPos == nHashStart) 15 . break; 16 . } 17 . return -1; //Error value 18. }

無論代碼看上去有多麼複雜，其背後的理論并不難。讀一個文件的時候基本遵循下面這樣一個過程：

• 1. 計算出字符串的三個哈希值（一個用來确定位置，另外兩個用來校驗)
• 2. 察看哈希表中的這個位置
• 3. 哈希表中這個位置為空嗎？如果為空，則肯定該字符串不存在，返回
• 4. 如果存在，則檢查其他兩個哈希值是否也匹配，如果匹配，則表示找到了該字符串，返回
• 5. 移到下一個位置，如果已經越界，則表示沒有找到，返回
• 6. 看看是不是又回到了原來的位置，如果是，則返回沒找到
• 7. 回到3

如果您注意的話，您可能已經從我們的解釋和示例代碼注意到，MPQ的哈希表已經将所有的文件入口放入MPQ中；那麼當哈希表的每個項都被填充的時候，會發生什麼呢？答案可能會讓你驚訝：你不能添加任何文件。有些人可能會問我為什麼文件數量上有這樣的限制（文件限制），是否有辦法繞過這個限制？就此而言，如果不重新創建MPQ 的項，甚至無法調整哈希表的大小。這是因為每個項在哈希表中的位置會因為跳閘尺寸而改變，而我們無法得到新的位置，因為這些位置值是文件名的哈希值，而我們根本不知道文件名是什麼。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!