星际、魔兽和WOW里面都有一个非常大的.MPQ文件，这个文件存储了游戏中大部分的资源数据，比如对话中的文字等等。Blizzard使用了hash table来组织对这个庞大文件的读写。
在WOW中，如果我跑到荆棘谷和地精卫兵聊天，那些绿色小矮人头上冒出来的叽叽咕咕的文字，就是从那个奇大无比的资源文件里取出来的。嗯，小绿人有那么多台词，怎么从这么一个庞大的字符串数组里找出某个特定的呢？或者，给你一句话，怎么找出相同的那一句出来？
当然你可以从这个数组头开始，一个个字符串读过去，比较每一个，直到找到对应的。这样的方法当然也没问题，如果你的PC真的有那么快的话...
Blizzard的天才和牛人们当然不会这样做，他们用了更聪明的方法: 用某种算法，把一个字符串压缩成一个整数，比如把每个字符按ASCII码值相加，得到的这个整数，称为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 seed2 = ch + seed1 + seed2 + (seed2 }
return seed1;
}
得到这个Hash值后，还需要某种算法来得出它对应的存储位置。通常构造一个称为Hash Table的数组来避免逐个的比较。Hash值通过模运算来得到表中的对应位置。
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
}
那么，如果两个字符串在表中对应的位置相同怎么办？这种可能性是极大的，解决的方法也很多。比较简单和常规的是使用链表，在Hash表每个值上挂一个链表来保存多个字符串。
en, Blizzard的牛人使用了更强的办法：他们使用三个Hash值(而不是通常的一个)来校验字符串。如果两个字符串用三个hash算法得出的入口点都一致，那几乎是不可能的事情。
Blizzard使用的hash表没有链表，看看这个算法：
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
}
只有在hash入口值不为空，并且两个校验Hash值也匹配的情况下，才算真正找到对应的字符串位置。非常简单清晰的算法，但非常非常的高效。
绝大部分的资料来自于Justin Olbrantz的Inside MoPaQ，非常感谢和佩服这位牛人