暴雪公司字元串散列函數

暴雪公司有個經典的字元串的hash公式

先提一個簡單的問題，假如有一個龐大的字元串數組，然後給你一個單獨的字元串，讓你從這個數組中查找是否有這個字元串并找到它，你會怎麼做？

有一個方法最簡單，老老實實從頭查到尾，一個一個比較，直到找到為止，我想隻要學過程式設計的人都能把這樣一個程式作出來，但要是有程式員把這樣的程式交給使用者，我隻能用無語來評價，或許它真的能工作，但...也隻能如此了。

最合适的算法自然是使用HashTable（哈希表），先介紹介紹其中的基本知識，所謂Hash，一般是一個整數，通過某種算法，可以把一個字元串"壓縮"成一個整數，這個數稱為Hash，當然，無論如何，一個32位整數是無法對應回一個字元串的，但在程式中，兩個字元串計算出的Hash值相等的可能非常小，下面看看在MPQ中的Hash算法

unsigned long HashString(char *lpszFileName, unsigned long dwHashType)  
    {  
    unsigned char *key = (unsigned char *)lpszFileName;  
    unsigned long seed1 = 0x7FED7FED, seed2 = 0xEEEEEEEE;  
    int ch;  
    while(*key != 0)  
    {  
    ch = toupper(*key );  
    seed1 = cryptTable[(dwHashType < < 8) ch] ^ (seed1 seed2);  
    seed2 = ch seed1 seed2 (seed2 < < 5) 3;  
    }  
    return seed1;  
    }   
           

Blizzard的這個算法是非常高效的，被稱為"One-Way Hash"，舉個例子，字元串"unitneutralacritter.grp"通過這個算法得到的結果是0xA26067F3。

是不是把第一個算法改進一下，改成逐個比較字元串的Hash值就可以了呢，答案是，遠遠不夠，要想得到最快的算法，就不能進行逐個的比較，通常是構造一個哈希表(Hash Table)來解決問題，哈希表是一個大數組，這個數組的容量根據程式的要求來定義，例如1024，每一個Hash值通過取模運算(mod)對應到數組中的一個位置，這樣，隻要比較這個字元串的哈希值對應的位置又沒有被占用，就可以得到最後的結果了，想想這是什麼速度？是的，是最快的O(1)，現在仔細看看這個算法吧

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

看到此，我想大家都在想一個很嚴重的問題："假如兩個字元串在哈希表中對應的位置相同怎麼辦？",究竟一個數組容量是有限的，這種可能性很大。解決該問題的方法很多，我首先想到的就是用"連結清單",感謝大學裡學的資料結構教會了這個百試百靈的法寶，我碰到的很多算法都可以轉化成連結清單來解決，隻要在哈希表的每個入口挂一個連結清單，儲存所有對應的字元串就OK了。

事情到此似乎有了完美的結局，假如是把問題獨自交給我解決，此時我可能就要開始定義資料結構然後寫代碼了。然而Blizzard的程式員使用的方法則是更精妙的方法。基本原理就是：他們在哈希表中不是用一個哈希值而是用三個哈希值來校驗字元串。

中國有句古話"再一再二不能再三再四"，看來Blizzard也深得此話的精髓，假如說兩個不同的字元串經過一個雜湊演算法得到的入口點一緻有可能，但用三個不同的雜湊演算法算出的入口點都一緻，那幾乎可以肯定是不可能的事了，這個幾率是1:18889465931478580854784，大概是10的22.3次方分之一，對一個遊戲程式來說足夠安全了。

現在再回到資料結構上，Blizzard使用的哈希表沒有使用連結清單，而采用"順延"的方式來解決問題，看看這個算法：

int GetHashTablePos(char *lpszString, MPQHASHTABLE *lpTable, int nTableSize)  
    {  
    const int HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;  
    int nHash = HashString(lpszString, HASH_OFFSET);  
    int nHashA = HashString(lpszString, HASH_A);  
    int nHashB = HashString(lpszString, HASH_B);  
    int nHashStart = nHash % nTableSize, nHashPos = nHashStart;  
    while (lpTable[nHashPos].bExists)  
    {  
    if (lpTable[nHashPos].nHashA == nHashA && lpTable[nHashPos].nHashB == nHashB)  
    return nHashPos;  
    else  
    nHashPos = (nHashPos 1) % nTableSize;  
    if (nHashPos == nHashStart)  
    break;  
    }  
    return -1; //Error value  
    }   


           

void prepareCryptTable()  
    {   
        unsigned long seed = 0x00100001, index1 = 0,   index2 = 0, i;  
        for(index1 = 0; index1 < 0x100; index1++)  
        {   
            for(index2 = index1, i = 0; i < 5; i++, index2 += 0x100)  
            {   
                unsigned long temp1, temp2;  
                seed = (seed * 125 + 3) % 0x2AAAAB;  
                temp1 = (seed & 0xFFFF) << 0x10;  
                seed = (seed * 125 + 3) % 0x2AAAAB;  
                temp2 = (seed & 0xFFFF);  
                cryptTable[index2] = (temp1 | temp2);   
            }   
        }   
    }  

  
           

1. 計算出字元串的三個哈希值（一個用來确定位置，另外兩個用來校驗)

2. 察看哈希表中的這個位置

3. 哈希表中這個位置為空嗎？假如為空，則肯定該字元串不存在，傳回

4. 假如存在，則檢查其他兩個哈希值是否也比對，假如比對，則表示找到了該字元串，傳回

5. 移到下一個位置，假如已經越界，則表示沒有找到，傳回

6. 看看是不是又回到了原來的位置，假如是，則傳回沒找到

7. 回到3