BS一下自己的物質(zhì)，支持一下 狗父叙，同時(shí)貼出
《暴雪公司有個(gè)經(jīng)典的字符串的hash公式》（網(wǎng)上搜的）
打造最快的Hash表(和Blizzard的對(duì)話)
開(kāi)元最近學(xué)習(xí)了一下Blizzard的MPQ文件格式几莽，頗有一些心得迅办，其中一條就是對(duì)HastTable的理解，很想寫(xiě)出來(lái)給大家共享章蚣，感謝Justin Olbrantz的文章《Inside MoPaQ》站欺，大多認(rèn)識(shí)來(lái)源于此。
先提一個(gè)簡(jiǎn)單的問(wèn)題纤垂，如果有一個(gè)龐大的字符串?dāng)?shù)組矾策，然后給你一個(gè)單獨(dú)的字符串，讓你從這個(gè)數(shù)組中查找是否有這個(gè)字符串并找到它峭沦，你會(huì)怎么做蝴韭？
有一個(gè)方法最簡(jiǎn)單，老老實(shí)實(shí)從頭查到尾熙侍，一個(gè)一個(gè)比較，直到找到為止履磨，我想只要學(xué)過(guò)程序設(shè)計(jì)的人都能把這樣一個(gè)程序作出來(lái)蛉抓，但要是有程序員把這樣的程序交給用戶，我只能用無(wú)語(yǔ)來(lái)評(píng)價(jià)剃诅，或許它真的能工作巷送，但...也只能如此了。
最合適的算法自然是使用HashTable（哈希表）矛辕，先介紹介紹其中的基本知識(shí)笑跛，所謂Hash，一般是一個(gè)整數(shù)聊品，通過(guò)某種算法飞蹂，可以把一個(gè)字符串"壓縮" 成一個(gè)整數(shù)，這個(gè)數(shù)稱(chēng)為Hash翻屈，當(dāng)然陈哑，無(wú)論如何，一個(gè)32位整數(shù)是無(wú)法對(duì)應(yīng)回一個(gè)字符串的，但在程序中惊窖，兩個(gè)字符串計(jì)算出的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的這個(gè)算法是非常高效的，被稱(chēng)為"One-Way Hash"界酒，舉個(gè)例子圣拄，字符串"unitneutralacritter.grp"通過(guò)這個(gè)算法得到的結(jié)果是0xA26067F3毁欣。
是不是把第一個(gè)算法改進(jìn)一下族铆，改成逐個(gè)比較字符串的Hash值就可以了呢，答案是逝淹，遠(yuǎn)遠(yuǎn)不夠，要想得到最快的算法欣簇，就不能進(jìn)行逐個(gè)的比較，通常是構(gòu)造一個(gè)哈希表(Hash Table)來(lái)解決問(wèn)題横殴，哈希表是一個(gè)大數(shù)組，這個(gè)數(shù)組的容量根據(jù)程序的要求來(lái)定義文狱，例如1024，每一個(gè)Hash值通過(guò)取模運(yùn)算 (mod)對(duì)應(yīng)到數(shù)組中的一個(gè)位置尚猿，這樣，只要比較這個(gè)字符串的哈希值對(duì)應(yīng)的位置又沒(méi)有被占用，就可以得到最后的結(jié)果了，想想這是什么速度忍捡？是的，是最快的O(1)凌埂，現(xiàn)在仔細(xì)看看這個(gè)算法吧
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
}
看到此伏恐，我想大家都在想一個(gè)很?chē)?yán)重的問(wèn)題："如果兩個(gè)字符串在哈希表中對(duì)應(yīng)的位置相同怎么辦？",畢竟一個(gè)數(shù)組容量是有限的，這種可能性很大闻鉴。解決該問(wèn)題的方法很多，我首先想到的就是用"鏈表",感謝大學(xué)里學(xué)的數(shù)據(jù)結(jié)構(gòu)教會(huì)了這個(gè)百試百靈的法寶，我遇到的很多算法都可以轉(zhuǎn)化成鏈表來(lái)解決，只要在哈希表的每個(gè)入口掛一個(gè)鏈表送巡，保存所有對(duì)應(yīng)的字符串就OK了蔽介。
事情到此似乎有了完美的結(jié)局，如果是把問(wèn)題獨(dú)自交給我解決圆凰，此時(shí)我可能就要開(kāi)始定義數(shù)據(jù)結(jié)構(gòu)然后寫(xiě)代碼了。然而B(niǎo)lizzard的程序員使用的方法則是更精妙的方法累铅≡拘耄基本原理就是：他們?cè)诠１碇胁皇怯靡粋€(gè)哈希值而是用三個(gè)哈希值來(lái)校驗(yàn)字符串。
中國(guó)有句古話"再一再二不能再三再四"娃兽，看來(lái)Blizzard也深得此話的精髓菇民，如果說(shuō)兩個(gè)不同的字符串經(jīng)過(guò)一個(gè)哈希算法得到的入口點(diǎn)一致有可能，但用三個(gè)不同的哈希算法算出的入口點(diǎn)都一致投储，那幾乎可以肯定是不可能的事了第练，這個(gè)幾率是1:18889465931478580854784，大概是10的 22.3次方分之一玛荞，對(duì)一個(gè)游戲程序來(lái)說(shuō)足夠安全了娇掏。
現(xiàn)在再回到數(shù)據(jù)結(jié)構(gòu)上，Blizzard使用的哈希表沒(méi)有使用鏈表勋眯，而采用"順延"的方式來(lái)解決問(wèn)題婴梧，看看這個(gè)算法：
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
}
1. 計(jì)算出字符串的三個(gè)哈希值（一個(gè)用來(lái)確定位置下梢，另外兩個(gè)用來(lái)校驗(yàn))
2. 察看哈希表中的這個(gè)位置
3. 哈希表中這個(gè)位置為空嗎？如果為空塞蹭，則肯定該字符串不存在孽江，返回
4. 如果存在，則檢查其他兩個(gè)哈希值是否也匹配浮还，如果匹配竟坛，則表示找到了該字符串，返回
5. 移到下一個(gè)位置钧舌，如果已經(jīng)越界担汤，則表示沒(méi)有找到，返回
6. 看看是不是又回到了原來(lái)的位置洼冻，如果是崭歧，則返回沒(méi)找到
7. 回到3
怎么樣，很簡(jiǎn)單的算法吧撞牢，但確實(shí)是天才的idea, 其實(shí)最優(yōu)秀的算法往往是簡(jiǎn)單有效的算法率碾，
Blizzard被稱(chēng)為最卓越的游戲制作公司，不愧于此屋彪。
