在暴雪娱乐（Blizzard Entertainment）出品的《魔兽争霸》《星际争霸》等经典游戏中，大部分游戏数据都被封装在一个名为MPQ的大型档案文件中。如果采用最朴素的查找方式——从文件头部开始逐个比对字符串，直到找到目标内容，其效率之低可想而知。暴雪的工程师们采用了一种更为精妙的解决方案：哈希算法。该算法能够将任意长度的字符串“压缩”成一个整数（即哈希值），并通过这个值直接定位到字符串在文件中的存储位置，从而实现快速访问。
什么是单向哈希（One-Way Hash）？
暴雪采用的哈希算法被称为“单向哈希”。其核心特性是：无法通过哈希值反向推导出原始字符串。这种不可逆性保证了算法的安全性，使得哈希值成为字符串的唯一“指纹”。
哈希表：快速查找的基石
假设你有一个庞大的字符串数组，需要判断某个字符串是否已存在于数组中。遍历比对的方式效率低下，尤其在数据量极大时几乎不可行。
解决方案：哈希表
哈希表通过将大数据类型（如字符串）映射为小数据类型（如整数索引）来提升查找效率。具体步骤为：
- 计算目标字符串的哈希值。
- 将哈希值转换为数组范围内的索引（通常通过取模运算）。
- 直接访问索引位置，比对字符串内容。
这种方法可以将查找效率提升约百倍。
简单哈希算法的示例与局限
以下是一个简单的哈希函数示例：
unsigned long HashString(char *lpszString) {
unsigned long ulHash = 0xf1e2d3c4;
while (*lpszString != 0) {
ulHash <<= 1;
ulHash += *lpszString++;
}
return ulHash;
}
上面代码中的函数演示了一种非常简单的散列算法。这个函数在遍历字符串过程中，将哈希值左移一位，然后加上字符值；通过这个算法，字符串”arrunits.dat” 的哈希值是0x5A858026，字符串”unitneutralacritter.grp” 的哈希值是0x694CD020；该算法在遍历字符串时，将当前哈希值左移一位并加上字符的ASCII值。然而，这种简单算法容易产生哈希冲突（不同字符串产生相同哈希值），且输出分布较为集中，实际应用价值有限。
MPQ采用的高强度哈希算法
为应对简单哈希的缺陷，MPQ格式使用了一种更为复杂、均匀性更好的哈希算法：
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;
}
使用这种算法，文件名 “arrunits.dat” 的哈希值是0xF4E6C69D，”unitneutralacritter.grp” 的哈希值是 0xA26067F3。该算法通过内置的密码表（cryptTable）和动态种子计算，使得哈希结果分布均匀、不可预测，极大降低了冲突概率。
MPQ哈希表的创新设计
您尝试在前面的示例中使用相同索引，您的程序一定会有中断现象发生，而且不够快 。如果想让它更快，您能做的只有让程序不去查询数组中的所有散列值。或者您可以只做一次对比就可以得出在列表中是否存在字符串。听起来不错，真的么？不可能的啦。
解决方案：一个哈希表就是以字符串的哈希值作为下标的一类数组。我的意思是，哈希表使用一个固定长度的字符串数组（比如1024，2的偶次幂）进行存储；当你要看看这个字符串是否存在于哈希表中，为了获取这个字符串在哈希表中的位置，你首先计算字符串的哈希值，然后哈希表的长度取模。这样如果你像上一节那样使用简单的哈希算法，字符串”arrunits.dat” 的哈希值是0x5A858026,偏移量0x26（0x5A858026 除于0x400等于0x16A160，模0x400等于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
}
上面的说明中存在一个刺眼的缺陷。当有冲突（两个不同的字符串有相同的哈希值）发生的时候怎么办？显而易见的，它们不能占据哈希表中的同一个位置。通常的解决办法是为每一个哈希值指向一个链表，用于存放所有哈希冲突的值；
MPQs使用一个存放文件名的哈希表来跟踪文件内部，但是表的格式与通常方法有点不同，首先不像通常的做法使用哈希值作为偏移量，存储实际的文件名。MPQs 根本不存储文件名，而是使用了三个不同的哈希值：一个用做哈希表偏移量，两个用作核对。这两个核对的哈希值用于替代文件名。当然从理论上说存在两个不同的文件名得到相同的三个哈希值，但是这种情况发送的几率是：1:18889465931478580854784,这应该足够安全了。
MPQ’s的哈希表的实现与传统实现的另一个不同的地方是，相对与传统做法（为每个节点使用一个链表，当冲突发生的时候，遍历链表进行比较）。
传统哈希表在冲突时常采用链地址法（每个索引位置维护一个链表）。MPQ则采用了截然不同的设计：
- 三哈希值校验系统 MPQ不为每个文件存储原始文件名，而是计算并存储三个哈希值：
- HASH_OFFSET：用于确定在哈希表中的初始位置。
- HASH_A 与 HASH_B：用于唯一性校验，替代文件名比对。
- 冲突解决策略 当发生冲突时，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);
int nHashA = HashString(lpszString, HASH_A);
int nHashB = HashString(lpszString, HASH_B);
int nHashStart = nHash % nTableSize;
int 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; // 未找到
}
流程归纳：
- 计算字符串的三个哈希值。
- 根据 HASH_OFFSET 定位初始索引。
- 若该位置为空，则文件不存在。
- 若该位置已被占用，则比对 HASH_A 和 HASH_B。
- 若匹配，则文件找到；否则继续线性探测下一个位置。
- 若回到起点或越界，则判定文件不存在。
哈希表的容量限制与扩展性
MPQ哈希表在设计上存在一个固有限制：哈希表的大小固定，且所有文件条目必须预先填入。当哈希表被完全填满后，无法再新增文件。这是因为文件位置完全由文件名哈希决定，若调整哈希表大小，所有条目的位置将发生改变，而系统无法回溯原始文件名以重新计算哈希。因此，MPQ的容量上限在创建时即被确定，后期无法动态扩展。
暴雪哈希算法的延伸应用思考
暴雪在MPQ格式中采用的高强度哈希算法和创新的三哈希值校验机制，虽然是针对游戏数据存储的特定需求设计，但其核心思想和设计理念在现代软件工程中仍有广泛借鉴价值。我们可以从以下几个维度进行延伸思考：
数据库索引与高冲突环境优化
暴雪哈希算法的三值校验机制（HASH_OFFSET、HASH_A、HASH_B）为解决传统哈希表的严重冲突问题提供了优雅方案。在现代数据库中，当面临极高并发写入或Key分布不均的场景时，借鉴这一多值校验思路可有效：
- 降低哈希碰撞概率
- 提高唯一性验证准确性
- 减少线性探测链长度
分布式存储系统的数据寻址借鉴
MPQ哈希表的设计本质上是一种基于文件名哈希的“静态寻址系统”。这一理念与分布式哈希表（DHT）的设计思想有相通之处。在P2P文件共享系统中，考虑：
- 将文件内容的哈希值作为系统寻址的唯一标识
- 借鉴三值校验确保数据块完整性和唯一性
- 避免单纯依赖简单哈希导致的“哈希污染”攻击
游戏引擎资源管理的新应用
暴雪的哈希方案可直接应用于现代游戏引擎的资产管理系统：
- 资源热更新时，通过文件哈希快速定位差异
- 依赖关系管理中，使用资源哈希替代易冲突的路径字符串
- 增量打包时，利用哈希排重复用相同资源
层状安全系统中的快速校验
三哈希值系统的分层设计理念同样适用于需要多层安全保障的场景：
- 第一层哈希（HASH_OFFSET）提供快速定位
- 第二层校验（HASH_A、HASH_B）确保数据真实性
- 这一“定位+验证”双阶段模式可应用于API鉴权、数据传输完整性检查等场景
面向扩展性的创新改进方向
原始MPQ方案的硬约束在于哈希表大小固定。我们可以提出扩展性改进思路：
- 设计支持动态扩容的哈希表结构，在扩容时保留“旧表”到“新表”的映射关系
- 采用一致性哈希思想解决扩容后哈希分布变化问题
- 通过空间换时间的方式，为每个哈希条目存放原始文件名或引用，解除对文件名的依赖
暴雪哈希算法的优雅之处在于它将复杂的文件查找问题转化为简洁的数学运算，其设计哲学体现了“复杂问题简单化、简单问题高效化”的工程思维。虽然现代哈希算法在性能、安全性、扩展性上有更大创新，但MPQ方案为解决特定场景问题提供的范式性思考，仍然是软件设计领域值得深入研究的宝贵财富。
暴雪在MPQ格式中实现的哈希算法与哈希表结构，充分体现了在工程实践中对效率与可靠性的极致追求。通过采用高强度单向哈希与三值校验机制，既保障了快速的文件定位能力，又确保了极低的冲突概率。这一设计已成为游戏数据存储领域的经典范例，其思想至今仍影响着许多大型系统的数据索引设计。
