本文转自 标点符

暴雪公司的魔兽、星际等游戏都一样一个非常大的MPQ文件，该文件存储了游戏中的大部分数据，想要把这些文字找出来，简单的办法是从数组头开始，一个个字符串读过去，比较每一个，直到找到对应的内容。Blizzard的天才和牛人们当然不会这样做，他们用了更聪明的方法: 用某种算法，把一个字符串压缩成一个整数，即hash。然后，根据这个整数值，直接得到此字符串在整个文件中的位置，从而直接读取之。

Blizzard的这个算法是非常高效的，被称为”One-Way Hash”。所谓One-Way Hash,就是无法从求得的hash值通过简单的逆运算就得到原来的字符串。关于具体的实现原理，inside MPQ 的第二章有详细的介绍，以下为第二章内容的翻译：

贯穿计算机发展历史，大多数进步都是源于某些问题的解决，在这一节中，我们来看一看与MPQ 格式相关问题及解决方案；

问题一：你有一个很大的字符串数组，同时，你另外还有一个字符串，需要知道这个字符串是否 已经存在于字符串数组中。你可能会对数组中的每一个字符串进行比较，但是在实际项目中，你会发现这种做法对某些特殊应用来说太慢了。必须寻求其他途径。那么如何才能在不作遍历比较的情况下知道这个字符串是否存在于数组中呢？

解决方案：哈希表。哈希表是通过更小的数据类型表示其他更大的数据类型。在这种情况下， 你可以把哈希表存储在字符串数组中，然后你可以计算字符串的哈希值，然后与已经存储的字符串的哈希值进行比较。如果有匹配的哈希值，就可以通过字符串比较 进行匹配验证。这种方法叫索引，根据数组的大小以及字符串的平均长度可以约00倍。

上面代码中的函数演示了一种非常简单的散列算法。这个函数在遍历字符串过程中，将哈希值左移一位，然后加上字符值；通过这个算法，字符串”arrunits.dat” 的哈希值是0x5A858026，字符串”unitneutralacritter.grp” 的哈希值是0x694CD020；现在，众所周知的，这是一个基本没有什么实用价值的简单算法，因为它会在较低的数据范围内产生相对可预测的输出，从而可能会产生大量冲突（不同的字符串产生相同的哈希值）。

MPQ格式，使用了一种非常复杂的散列算法（如下所示），产生完全不可预测的哈希值，这个算法十分有效，这就是所谓的单向散列算法。通过单向散列算法几乎不可能通过哈希值来唯一的确定输入值。使用这种算法，文件名 “arrunits.dat” 的哈希值是0xF4E6C69D，”unitneutralacritter.grp” 的哈希值是 0xA26067F3。

问题二：您尝试在前面的示例中使用相同索引，您的程序一定会有中断现象发生，而且不够快 。如果想让它更快，您能做的只有让程序不去查询数组中的所有散列值。或者 您可以只做一次对比就可以得出在列表中是否存在字符串。听起来不错，真的么？不可能的啦

解决：一个哈希表就是以字符串的哈希值作为下标的一类数组。我的意思是，哈希表使用一个固定长度的字符串数组（比如024，2的偶次幂）进行存储；当你要看看这个字符串是否存在于哈希表中，为了获取这个字符串在哈希表中的位置，你首先计算字符串的哈希值，然后哈希表的长度取模。这样如果你像上一节那样使用简单的哈希算法，字符串”arrunits.dat” 的哈希值是0x5A858026,偏移量0x26（0x5A858026 除于0x400等于0x6A60，模0x400等于0x26）。因此，这个位置的字符串将与新加入的字符串进行比较。如果0X26处的字符串不匹配或不存在，那么表示新增的字符串在数组中不存在。下面是示意的代码：

上面的说明中存在一个刺眼的缺陷。当有冲突（两个不同的字符串有相同的哈希值）发生的时候怎么办？显而易见的，它们不能占据哈希表中的同一个位置。通常的解决办法是为每一个哈希值指向一个链表，用于存放所有哈希冲突的值；

MPQs使用一个存放文件名的哈希表来跟踪文件内部，但是表的格式与通常方法有点不同，首先不像通常的做法使用哈希值作为偏移量，存储实际的文件名。MPQs 根本不存储文件名，而是使用了三个不同的哈希值：一个用做哈希表偏移量，两个用作核对。这两个核对的哈希值用于替代文件名。当然从理论上说存在两个不同的文件名得到相同的三个哈希值，但是这种情况发送的几率是：:888946593478580854784,这应该足够安全了。

MPQ’s的哈希表的实现与传统实现的另一个不同的地方是，相对与传统做法（为每个节点使用一个链表，当冲突发生的时候，遍历链表进行比较），看一下下面的示范代码，在MPQ中定位一个文件进行读操作：

无论代码看上去有多么复杂，其背后的理论并不难。读一个文件的时候基本遵循下面这样一个过程：

. 计算出字符串的三个哈希值（一个用来确定位置，另外两个用来校验)

2. 察看哈希表中的这个位置

3. 哈希表中这个位置为空吗？如果为空，则肯定该字符串不存在，返回

4. 如果存在，则检查其他两个哈希值是否也匹配，如果匹配，则表示找到了该字符串，返回

5. 移到下一个位置，如果已经越界，则表示没有找到，返回

6. 看看是不是又回到了原来的位置，如果是，则返回没找到

7. 回到3

如果您注意的话，您可能已经从我们的解释和示例代码注意到，MPQ的哈希表已经将所有的文件入口放入MPQ中；那么当哈希表的每个项都被填充的时候，会发生什么呢？答案可能会让你惊讶：你不能添加任何文件。有些人可能会问我为什么文件数量上有这样的限制（文件限制），是否有办法绕过这个限制？就此而言，如果不重新创建MPQ 的项，甚至无法调整哈希表的大小。这是因为每个项在哈希表中的位置会因为跳闸尺寸而改变，而我们无法得到新的位置，因为这些位置值是文件名的哈希值，而我们根本不知道文件名是什么。

暴雪公司有个经典的字符串的hash公式 

先提一个简单的问题，假如有一个庞大的字符串数组，然后给你一个单独的字符串，让你从这个数组中查找是否有这个字符串并找到它，你会怎么做？ 

有一个方法最简单，老老实实从头查到尾，一个一个比较，直到找到为止，我想只要学过程序设计的人都能把这样一个程序作出来，但要是有程序员把这样的程序交给用户，我只能用无语来评价，或许它真的能工作，但也只能如此了。 

最合适的算法自然是使用HashTable（哈希表），先介绍介绍其中的基本知识，所谓Hash，一般是一个整数，通过某种算法，可以把一个字符串"压缩" 成一个整数，这个数称为Hash，当然，无论如何，一个32位整数是无法对应回一个字符串的，但在程序中，两个字符串计算出的Hash值相等的可能非常小，下面看看在MPQ中的Hash算法

Blizzard的这个算法是非常高效的，被称为"One-Way Hash"，举个例子，字符串"unitneutralacritter.grp"通过这个算法得到的结果是0xA26067F3。 

是不是把第一个算法改进一下，改成逐个比较字符串的Hash值就可以了呢，答案是，远远不够，要想得到最快的算法，就不能进行逐个的比较，通常是构造一个哈希表(Hash Table)来解决问题，哈希表是一个大数组，这个数组的容量根据程序的要求来定义，例如1024，每一个Hash值通过取模运算 (mod)对应到数组中的一个位置，这样，只要比较这个字符串的哈希值对应的位置又没有被占用，就可以得到最后的结果了，想想这是什么速度？是的，是最快的O(1)，现在仔细看看这个算法吧。

看到此，我想大家都在想一个很严重的问题："假如两个字符串在哈希表中对应的位置相同怎么办？",究竟一个数组容量是有限的，这种可能性很大。解决该问题的方法很多，我首先想到的就是用"链表",感谢大学里学的数据结构教会了这个百试百灵的法宝，我碰到的很多算法都可以转化成链表来解决，只要在哈希表的每个入口挂一个链表，保存所有对应的字符串就OK了。 

事情到此似乎有了完美的结局，假如是把问题独自交给我解决，此时我可能就要开始定义数据结构然后写代码了。然而Blizzard的程序员使用的方法则是更精妙的方法。基本原理就是：他们在哈希表中不是用一个哈希值而是用三个哈希值来校验字符串。 

中国有句古话"再一再二不能再三再四"，看来Blizzard也深得此话的精髓，假如说两个不同的字符串经过一个哈希算法得到的入口点一致有可能，但用三个不同的哈希算法算出的入口点都一致，那几乎可以肯定是不可能的事了，这个几率是1:18889465931478580854784，大概是10的 22.3次方分之一，对一个游戏程序来说足够安全了。 

现在再回到数据结构上，Blizzard使用的哈希表没有使用链表，而采用"顺延"的方式来解决问题，看看这个算法：

1. 计算出字符串的三个哈希值（一个用来确定位置，另外两个用来校验) 

2. 察看哈希表中的这个位置 

3. 哈希表中这个位置为空吗？假如为空，则肯定该字符串不存在，返回 

4. 假如存在，则检查其他两个哈希值是否也匹配，假如匹配，则表示找到了该字符串，返回 

5. 移到下一个位置，假如已经越界，则表示没有找到，返回 

6. 看看是不是又回到了原来的位置，假如是，则返回没找到 

7. 回到3 

怎么样，很简单的算法吧，但确实是天才的idea, 其实最优秀的算法往往是简单有效的算法。

附上完整的算法代码：

点赞~~