您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

神奇的暴雪哈希算法

时间:2019-10-09 14:30:08  来源:  作者:

暴雪公司的魔兽、星际等游戏都一样一个非常大的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 . else
07 . return -1; //Error value
08. }

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

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

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

01 . int GetHashTablePos(char *lpszString, MPQHASHTABLE *lpTable, int nTableSize)
02 . {
03 . const int HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;
04 . int nHash = HashString(lpszString, HASH_OFFSET);
05 . int nHashA = HashString(lpszString, HASH_A);
06 . int nHashB = HashString(lpszString, HASH_B);
07 . int nHashStart = nHash % nTableSize,nHashPos = nHashStart;
08 . while (lpTable[nHashPos].bExists)
09 . {
10 . if (lpTable[nHashPos].nHashA == nHashA && lpTable[nHashPos].nHashB == nHashB)
11 . return nHashPos;
12 . else
13 . nHashPos = (nHashPos + 1) % nTableSize;
14 . if (nHashPos == nHashStart)
15 . break;
16 . }
17 . return -1; //Error value
18. }

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

  • 1. 计算出字符串的三个哈希值(一个用来确定位置,另外两个用来校验)
  • 2. 察看哈希表中的这个位置
  • 3. 哈希表中这个位置为空吗?如果为空,则肯定该字符串不存在,返回
  • 4. 如果存在,则检查其他两个哈希值是否也匹配,如果匹配,则表示找到了该字符串,返回
  • 5. 移到下一个位置,如果已经越界,则表示没有找到,返回
  • 6. 看看是不是又回到了原来的位置,如果是,则返回没找到
  • 7. 回到3

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



Tags:哈希算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
哈希 Hash 算法介绍哈希算法也叫散列算法, 不过英文单词都是 Hash, 简单一句话概括, 就是可以把任意长度的输入信息通过算法变换成固定长度的输出信息, 输出信息也就是哈希...【详细内容】
2021-08-17  Tags: 哈希算法  点击:(72)  评论:(0)  加入收藏
在程序员的实际开发中,哈希算法常常能用得到,本文以哈希算法的原理和应用为核心,和大家详细讲解一下哈希算法的概念、常见算法以及原理、在信息安全的应用等等。 一、概念哈希...【详细内容】
2021-06-25  Tags: 哈希算法  点击:(147)  评论:(0)  加入收藏
一、介绍及原理1.1 简介哈希算法(Hash)又称摘要算法(Digest),它的作用是:对任意一组输入数据进行计算,得到一个固定长度的输出摘要。比如Java字符串的hashCode()就是哈希算法,输出是...【详细内容】
2020-11-12  Tags: 哈希算法  点击:(199)  评论:(0)  加入收藏
哈希函数,想必大家都不陌生。通过哈希函数我们可以将数据映射成一个数字(哈希值),然后可用于将数据打乱。例如,在HashMap中则是通过哈希函数使得每个桶中的数据尽量均匀。那一致...【详细内容】
2020-07-07  Tags: 哈希算法  点击:(71)  评论:(0)  加入收藏
最近,区块链的概念是火爆了,就在最近,腾讯公司与中国信通院发表白皮书,将主导中国区块链发票。可以预见的是,在未来一段时间,区块链还会继续火爆下去,如果掌握了区块链的技术,不敢说...【详细内容】
2019-11-01  Tags: 哈希算法  点击:(78)  评论:(0)  加入收藏
一致性哈希算法普通的哈希算法使用取余操作:hash(o) mod n,其中 n 代表机器的数量。如果在集群中新增加一个节点时,计算公式会变为:hash(o) mod (n+1);在集群中删除一个机器时,计...【详细内容】
2019-10-22  Tags: 哈希算法  点击:(102)  评论:(0)  加入收藏
暴雪公司的魔兽、星际等游戏都一样一个非常大的MPQ文件,该文件存储了游戏中的大部分数据,想要把这些文字找出来,简单的办法是从数组头开始,一个个字符串读过去,比较每一个,直到找...【详细内容】
2019-10-09  Tags: 哈希算法  点击:(136)  评论:(0)  加入收藏
话说前几天有一次,某大厂的二面。然后呢,烟哥那天刚好有事,所以去不了。于是就约了一场视频面试了!...【详细内容】
2019-09-03  Tags: 哈希算法  点击:(186)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(11)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  老师明明可以靠颜值    Tags:算法   点击:(7)  评论:(0)  加入收藏
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  青石野草    Tags:希尔排序   点击:(6)  评论:(0)  加入收藏
ROP是一种技巧,我们对execve函数进行拼凑来进行system /bin/sh。栈迁移的特征是溢出0x10个字符,在本次getshell中,还碰到了如何利用printf函数来进行canary的泄露。ROP+栈迁移...【详细内容】
2021-12-15  星云博创    Tags:栈迁移   点击:(22)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(14)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯&middot;奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(40)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条