魔兽改图MPQ技术内幕

上面的代码，体现了一个很简单的散列算法。 

功能是在每个字符添加前，把哈希值向左移动1bit，并总计字符串中的字符。 

使用这种算法，字符串“arr\ units.dat ”将散列为0x5a858026，“unit\neutral\ acritter.grp ”将散列为0x694cd020 。 

无可否认，这是一个很简单的算法，但是不是非常实用。因为在较低的数字范围内会产生一个相对可预见的输出，以及出现大量的冲突。当多于一个字符串散列为相同值就会出现冲突。 

MPQ格式使用一个非常复杂的散列算法（如下所示），产生完全不可预测的哈希值，这个算法十分有效，这就是所谓的单向散列。 

就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。从预映射，能够简单迅速的得到散列值，而在计算上不可能构造一个预映射，使其散列结果等于某个特定的散列值。 

即构造相应的任意长度明文=固定长度散列值-1（固定长度散列值）不可行。 

故此使用特别算法，文件名“arr\ units.dat ”将散列为0xf4e6c69d ，和“unit\neutral\ acritter.grp ”将散列为0xa26067f3 。 

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;

}

HASH TABLES(散列表或哈希表) 

问题：您尝试在前面的示例中使用相同索引，您的程序一定会有中断现象发生，而且不够快。 

您能做的只有让程序不去查询数组中的所有散列值。或者 您可以只做一次对比就可以得出在列表 中是否存在字符串。 

听起来不错，真的么？ 

骗你的啦！！！ 

解决方案：a hash table 

哈希表是数组中的一种特殊类型，也就是设定指定字符串的偏移量为那个字符串的散列值。 

我的意思是，假如您设置一个字符串列表，使用一个单独的固定大小的数组作为哈希表。 

您想查看新的字符串是否在前面的哈希表里。 

那么您需要先计算要查看字符串的散列值，然后以哈希表大小的散列值为模求余数。 

因此，如果您使用上面列出的简单散列算法，"arr\units.dat"将散列为0x5A858026，使其偏移量 

0x26(0x5A858026 divided by 0x400 is 0x16A160, with a remainder of 0x26)。 

假如这个地方有字符串，那么就会与被添加的字符串比较。 

假如字符串在0x26不匹配，或直接不存在，那说明该添加的字符并不在在数组中。 

下面的代码说明了这： 

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

}

现在在这方面的解释有一个明显的缺陷。您认为发生冲突时（两个不同的字符串哈希以同等价值的） ？显然，他们不能在哈希表占用相同的接口。通常，解决的方法是在哈希表每个接口作为一个指针到一个链表，然后将链表里所有接口的散列值设置相同。 

MPQ使用一个关于文件名称的哈希表记录内部文件，但是这个哈希表的格式与普通哈希表有所不同。 

首先，MPQ根本不保存文件名，用三个散列值代替保存散列值的偏移量和为了核查文件名保存真实的文件名。 

而是使用三个不同哈希值：一个做为哈希表的偏移量，两个是做为核查。 

两个做为核查的哈希值被用来代替真实的文件名称。当然，也有可能两个不同文件名称的散列值相同， 

不过这种情况发生的可能性为平均1:18889465931478580854784 ，对于任何人来说这应该足够安全了。 

另一种方法：不同于常规的执行情况的mpq哈希表。 

代替使用每个接口的链接表。当冲突发生时，把接口移动动下一个序列，并且重复动作，直到找到空闲空间。 

下面的代码是在MPQ设置读取的基本方法： 

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), nHashA = HashString(lpszString, HASH_A), nHashB = HashString(lpszString, HASH_B), 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.计算3个散列值（一个冲突和两个检查）并将其存储在变量。 

2.移动冲突散列值的接口 

3.接口未使用的吗？如果是的话，停止搜寻，并传回'文件没有被发现' 。 

4.两个检查是否匹配检查我们正在寻找文件的散列值呢？如果是的话，停止搜寻，并传回目前的接口。 

5.如果在最后一个接口，移动到列表中的下一个接口，（wrapping around to the beginning ？？）。 

6.刚移动的借口是否和冲突时的散列值相同（是否检查了整个哈希表？ ） ？如果是的话，停止搜寻，并传回'文件没有被发现' 。 

7.回到第3步。 

如果您很仔细的话，您可能会从我的解释和示例代码注意到，是因为mpq的哈希表已保留所有文件接口在MPQ 。那么您认为每一个哈希表项如何得到填补？答案可能出乎您的意料却显而易见：您不能继续添加文件。几个人都问我为什么有一个上限（所谓的档案限制），在一个MPQ中可以有多少档案， ，是否有任何的方式解决这个限制。那么，您已经有了第一个问题的答案。至于第二项;没有，您不能绕开该文件的限制。对这个问题，哈希表，甚至不能调整大小，除非您重新改造MPQ。在哈希表每个接口因为重新设置大小不同位置可能会改变。而且导致无法获得新的地址，因为地址是文件名的散列值，并且我们还可能不知道档案名称。