打造最快的 Hash 表
2007-11-05 14:37
一个简单的问题：有一个庞大的字符串数组，然后给你一个单独的字符串，让你从这个数
组中查找是否有这个字符串并找到它，你会怎么做？有一个方法最简单，老老 实实从头查到
尾，一个一个比较，直到找到为止，我想只要学过程序设计的人都能把这样一个程序作出来，
但要是有程序员把这样的程序交给用户，我只能用无语来 评价，或许它真的能工作，但...也只
能如此了。
最合适的算法自然是使用 HashTable（哈希表），先介绍介绍其中的基本知识，所谓 Hash，一
般是一个整数，通过某种算法，可以把一个字符串"压缩" 成一个整数。当然，无论如何，一个
32 位整数是无法对应回一个字符串的，但在程序中，两个字符串计算出的 Hash 值相等的可能
非常小，下面看看在 MPQ 中的 Hash 算法：
以下的函数生成一个长度为 0x500（合 10 进制数：1280）的 cryptTable[0x500]
void prepareCryptTable()
{
unsigned long seed = 0x00100001, index1 = 0, index2 = 0, i;
for( index1 = 0; index1 < 0x100; index1++ )
{
for( index2 = index1, i = 0; i < 5; i++, index2 += 0x100 )
{
unsigned long temp1, temp2;
seed = (seed * 125 + 3) % 0x2AAAAB;
temp1 = (seed & 0xFFFF) << 0x10;
seed = (seed * 125 + 3) % 0x2AAAAB;
temp2 = (seed & 0xFFFF);
cryptTable[index2] = ( temp1 | temp2 );
}
}
}
以下函数计算 lpszFileName 字符串的 hash 值，其中 dwHashType 为 hash 的类型，在下面 GetHashTablePos 函数
里面调用本函数，其可以取的值为 0、1、2；该函数返回 lpszFileName 字符串的 hash 值；
unsigned long HashString( char *lpszFileName, unsigned long dwHashType )
{
unsigned char *key = (unsigned char *)lpszFileName;
unsigned long seed1 = 0x7FED7FED;
unsigned long 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"( A one-way hash is a an
algorithm that is constructed in such a way that deriving the original string (set of strings,
评论1