打造最快的Hash表(转)

《打造最快的Hash表(转)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、F-Blog打造最快的Hash表(暴雪用的MPQ文件)最近在网上看到篇文章，一起拜一拜暴雪先提一个简单的问题，如果有一个庞大的字符串数组，然后给你一个单独的字符串，让你从这个数组中查找是否有这个字符串并找到它，你会怎么做？有一个方法最简单，老老实实从头查到尾，一个一个比较，直到找到为止，我想只要学过程序设计的人都能把这样一个程序作出来，但要是有程序员把这样的程序交给用户，我只能用无语来评价，或许它真的能工作，但...也只能如此了。最合适的算法自然是使用HashTable（哈希表），先介绍介绍其中的基本知识，所谓Hash，一般是一

2、个整数，通过某种算法，可以把一个字符串"压缩"成一个整数，这个数称为Hash，当然，无论如何，一个32位整数是无法对应回一个字符串的，但在程序中，两个字符串计算出的Hash值相等的可能非常小，下面看看在MPQ中的Hash算法unsignedlongHashString(char*lpszFileName,unsignedlongdwHashType){unsignedchar*key=(unsignedchar*)lpszFileName;unsignedlongseed1=0x7FED7FED,seed2=0xEEEEEEEE

3、;intch;while(*key!=0){ch=toupper(*key++);seed1=cryptTable[(dwHashType<<8)+ch]^(seed1+seed2);seed2=ch+seed1+seed2+(seed2<<5)+3;}returnseed1;}Blizzard的这个算法是非常高效的，被称为"One-WayHash"，举个例子，字符串"unitneutralacritter.grp"通过这个算法得到的结果是0xA26067F3。是不是把第一个算法改进一下，改成逐个比较字符串的Hash值就可以了呢

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

5、{intnHash=HashString(lpszString),nHashPos=nHash%nTableSize;if(lpTable[nHashPos].bExists&&!strcmp(lpTable[nHashPos].pString,lpszString))returnnHashPos;elsereturn-1;//Errorvalue}第2页2021-7-17F-Blog看到此，我想大家都在想一个很严重的问题："如果两个字符串在哈希表中对应的位置相同怎么办？",毕竟一个数组容量是有限的，这种可能性很大。解决该问题的

6、方法很多，我首先想到的就是用"链表",感谢大学里学的数据结构教会了这个百试百灵的法宝，我遇到的很多算法都可以转化成链表来解决，只要在哈希表的每个入口挂一个链表，保存所有对应的字符串就OK了。事情到此似乎有了完美的结局，如果是把问题独自交给我解决，此时我可能就要开始定义数据结构然后写代码了。然而Blizzard的程序员使用的方法则是更精妙的方法。基本原理就是：他们在哈希表中不是用一个哈希值而是用三个哈希值来校验字符串。中国有句古话"再一再二不能再三再四"，看来Blizzard也深得此话的精髓，如果说两个不同的字符串经过一个哈希算法

7、得到的入口点一致有可能，但用三个不同的哈希算法算出的入口点都一致，那几乎可以肯定是不可能的事了，这个几率是1:18889465931478580854784，大概是10的22.3次方分之一，对一个游戏程序来说足够安全了。现在再回到数据结构上，Blizzard使用的哈希表没有使用链表，而采用"顺延"的方式来解决问题，看看这个算法：intGetHashTablePos(char*lpszString,MPQHASHTABLE*lpTable,intnTableSize){constintHASH_OFFSET=0,HASH_A=1,

8、HASH_B=2;intnHash=HashString(lpszString,HASH_OFFSET);intnHashA=HashString(lpszString,HASH_A);intnHashB=HashString(lpszString,HASH_B