江苏龙网

  1. 主页 > 生活百科 > >

神奇的暴雪哈希算法

哈希算法

暴雪公司的魔兽、星际等游戏都一样一个非常大的MPQ文件，该文件存储了游戏中的大部分数据，想要把这些文字找出来，简单的办法是从数组头开始，一个个字符串读过去，比较每一个，直到找到对应的内容 。Blizzard的天才和牛人们当然不会这样做，他们用了更聪明的方法: 用某种算法，把一个字符串压缩成一个整数，即hash 。然后，根据这个整数值，直接得到此字符串在整个文件中的位置，从而直接读取之 。
Blizzard的这个算法是非常高效的，被称为”One-Way Hash” 。所谓One-Way Hash,就是无法从求得的hash值通过简单的逆运算就得到原来的字符串 。关于具体的实现原理，inside MPQ 的第二章有详细的介绍，以下为第二章内容的翻译：
贯穿计算机发展历史，大多数进步都是源于某些问题的解决，在这一节中，我们来看一看与MPQ 格式相关问题及解决方案；
问题一：你有一个很大的字符串数组，同时，你另外还有一个字符串，需要知道这个字符串是否 已经存在于字符串数组中 。你可能会对数组中的每一个字符串进行比较，但是在实际项目中，你会发现这种做法对某些特殊应用来说太慢了 。必须寻求其他途径 。那么如何才能在不作遍历比较的情况下知道这个字符串是否存在于数组中呢？
解决方案：哈希表 。哈希表是通过更小的数据类型表示其他更大的数据类型 。在这种情况下，你可以把哈希表存储在字符串数组中，然后你可以计算字符串的哈希值，然后与已经存储的字符串的哈希值进行比较 。如果有匹配的哈希值，就可以通过字符串比较 进行匹配验证 。这种方法叫索引，根据数组的大小以及字符串的平均长度可以约100倍 。
01 . unsigned long HashString(char *lpszString)02 . {03 . unsigned long ulHash = 0xf1e2d3c4;04 . while (*lpszString != 0)05 . {06 . ulHash <<= 1;07 . ulHash += *lpszString++;08 . }09 . return ulHash;10. }上面代码中的函数演示了一种非常简单的散列算法 。这个函数在遍历字符串过程中，将哈希值左移一位，然后加上字符值；通过这个算法，字符串”arrunits.dat” 的哈希值是0x5A858026，字符串”unitneutralacritter.grp” 的哈希值是0x694CD020；现在，众所周知的，这是一个基本没有什么实用价值的简单算法，因为它会在较低的数据范围内产生相对可预测的输出，从而可能会产生大量冲突（不同的字符串产生相同的哈希值） 。
MPQ格式，使用了一种非常复杂的散列算法（如下所示），产生完全不可预测的哈希值，这个算法十分有效，这就是所谓的单向散列算法 。通过单向散列算法几乎不可能通过哈希值来唯一的确定输入值 。使用这种算法，文件名 “arrunits.dat” 的哈希值是0xF4E6C69D，”unitneutralacritter.grp” 的哈希值是 0xA26067F3 。
01 . unsigned long HashString(char *lpszFileName, unsigned long dwHashType)02 . {03 . unsigned char *key = (unsigned char *)lpszFileName;04 . unsigned long seed1 = 0x7FED7FED, seed2 = 0xEEEEEEEE;05 . int ch;06 . while(*key != 0)07 . {08 . ch = toupper(*key++);09 . seed1 = cryptTable[(dwHashType << 8) + ch] ^ (seed1 + seed2);10 . seed2 = ch + seed1 + seed2 + (seed2 << 5) + 3;11 . }12 . return seed1;13. }【神奇的暴雪哈希算法】问题二：您尝试在前面的示例中使用相同索引，您的程序一定会有中断现象发生，而且不够快。如果想让它更快，您能做的只有让程序不去查询数组中的所有散列值 。或者 您可以只做一次对比就可以得出在列表中是否存在字符串 。听起来不错，真的么？不可能的啦
解决：一个哈希表就是以字符串的哈希值作为下标的一类数组 。我的意思是，哈希表使用一个固定长度的字符串数组（比如1024，2的偶次幂）进行存储；当你要看看这个字符串是否存在于哈希表中，为了获取这个字符串在哈希表中的位置，你首先计算字符串的哈希值，然后哈希表的长度取模 。这样如果你像上一节那样使用简单的哈希算法，字符串”arrunits.dat” 的哈希值是0x5A858026,偏移量0×26（0x5A858026 除于0×400等于0x16A160，模0×400等于0×26） 。因此，这个位置的字符串将与新加入的字符串进行比较 。如果0X26处的字符串不匹配或不存在，那么表示新增的字符串在数组中不存在 。下面是示意的代码：
01 . int GetHashTablePos(char *lpszString, SOMESTRUCTURE *lpTable, int nTableSize)02 . {03 . int nHash = HashString(lpszString), nHashPos = nHash % nTableSize;04 . if (lpTable[nHashPos].bExists && !strcmp(lpTable[nHashPos].pString, lpszString))05 . return nHashPos;06 . else07 . return -1; //Error value08. }


推荐阅读


上一篇：淘宝上架数量限制 淘宝对卖家发布商品数量限制

下一篇：梦见狐狸扑向自己还想咬是什么意思 梦见狐狸扑向自己吓醒