posts - 126,  comments - 73,  trackbacks - 0

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

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

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

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;
}

Blizzard的这个算法是非常高效的,被称为"One-Way Hash",举个例子,字符串"unitneutralacritter.grp"通过这个算法得到的结果是0xA26067F3。
是不是把第一个算法改进一下,改成逐个比较字符串的Hash值就可以了呢,答案是,远远不够,要想得到最快的算法,就不能进行逐个的比较,通常是构造一个哈希表(Hash Table)来解决问题,哈希表是一个大数组,这个数组的容量根据程序的要求来定义,例如1024,每一个Hash值通过取模运算 (mod)对应到数组中的一个位置,这样,只要比较这个字符串的哈希值对应的位置又没有被占用,就可以得到最后的结果了,想想这是什么速度?是的,是最快的O(1),现在仔细看看这个算法吧
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
}

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

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

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

现在再回到数据结构上,Blizzard使用的哈希表没有使用链表,而采用"顺延"的方式来解决问题,看看这个算法:
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, 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; //Error value
}

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

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

http://blog.blogchina.com/article_85296.361466.html

posted on 2007-08-21 11:51 我风 阅读(6901) 评论(8)  编辑 收藏 引用

FeedBack:
# re: 打造最快的Hash表(转)
2007-11-03 01:07 | wo
不是很懂,"从这个数组中查找是否有这个字符串并找到它",和这怎么联系上的?谢谢  回复  更多评论
  
# re: 打造最快的Hash表(转)
2007-12-05 17:07 | 祁祁
果然精妙  回复  更多评论
  
# re: 打造最快的Hash表(转)
2009-03-25 17:03 | akore
无聊, 跟在字符串数组中找到目标字符串有个屁联系!  回复  更多评论
  
# re: 打造最快的Hash表(转)
2009-04-21 14:41 | brightcoder
跟你提的问题有什么关联  回复  更多评论
  
# re: 打造最快的Hash表(转)[未登录]
2009-05-22 00:41 | joe
@akore
对你相当无语..先看懂再说吧  回复  更多评论
  
# re: 打造最快的Hash表(转)
2009-09-01 13:59 | charrie
顶,最后三个哈希值的还没有太明白,前面的正是我需要的,谢谢楼主!  回复  更多评论
  
# re: 打造最快的Hash表(转)
2009-10-12 16:32 | river
如果只进行一次这样的查找操作,那么顺序查找,当然是唯一选择;
你说的高效,是针对要进行无数次这样在同一个长串中查找子串的操作的情况,对吧?道理是很简单,确实还不错。
你这个文章,意思没有表达的很清楚,怨不得别人提出质疑;
同时,题目为“打造最快的hash表”,我不太认同。  回复  更多评论
  
# re: 打造最快的Hash表(转)
2009-10-13 23:17 | Veiir
@river
Hash表的目的是让搜索时间稳定在一个数字上。

比如有几百个模型包,要依靠名称取其中一个,那么如果你逐个比较文件名筛选,如果是这个文件名是a开头还好,万一是z开头呢?会不会花费的时间很长?那么你这个游戏画面的载入时间岂不是很不稳定?

如果把这些模型包通过文件名hash运算得出来一个数字,比如20,放到同一个数组array的这个数字的位置array[20],那么以后要读取这个模型包,仅用知道文件名,通过hash运算得出同样的数字20,那么你可以直接去取数组array的这个数字位置就好了array[20]。那么你只用了一个hash运算,这个运算所花费的时间是一定的,要比不知道做多少次文件名比较花的时间短多了,取址当然是很快的,那么你游戏画面载入时间就不会很长,也比较稳定.  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

常用链接

留言簿(12)

随笔分类

随笔档案

文章档案

相册

收藏夹

C++

MyFavorite

搜索

  •  

积分与排名

  • 积分 - 319580
  • 排名 - 74

最新评论

阅读排行榜

评论排行榜