一個(gè)簡(jiǎn)單的問(wèn)題：有一個(gè)龐大的字符串?dāng)?shù)組，然后給你一個(gè)單獨(dú)的字符串，讓你從這個(gè)數(shù)組中查找是否有這個(gè)字符串并找到它，你會(huì)怎么做？有一個(gè)方法最簡(jiǎn)單，老老 實(shí)實(shí)從頭查到尾，一個(gè)一個(gè)比較，直到找到為止，我想只要學(xué)過(guò)程序設(shè)計(jì)的人都能把這樣一個(gè)程序作出來(lái)，但要是有程序員把這樣的程序交給用戶，我只能用無(wú)語(yǔ)來(lái) 評(píng)價(jià)，或許它真的能工作，但...也只能如此了。
最合適的算法自然是使用HashTable（哈希表），先介紹介紹其中的基本知識(shí)，所謂Hash，一般是一個(gè)整數(shù)，通過(guò)某種算法，可以把一個(gè)字符串"壓縮" 成一個(gè)整數(shù)。當(dāng)然，無(wú)論如何，一個(gè)32位整數(shù)是無(wú)法對(duì)應(yīng)回一個(gè)字符串的，但在程序中，兩個(gè)字符串計(jì)算出的Hash值相等的可能非常小，下面看看在MPQ中的Hash算法：
以下的函數(shù)生成一個(gè)長(zhǎng)度為0x500（合10進(jìn)制數(shù)：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 );
}
}
}
以下函數(shù)計(jì)算lpszFileName 字符串的hash值，其中dwHashType 為hash的類(lèi)型，在下面GetHashTablePos函數(shù)里面調(diào)用本函數(shù)，其可以取的值為0、1、2；該函數(shù)返回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的這個(gè)算法是非常高效的，被稱(chēng)為"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, actually) is virtually impossible)。舉個(gè)例子，字符串"unitneutralacritter.grp"通過(guò)這個(gè)算法得到的結(jié)果是0xA26067F3。
是不是把第一個(gè)算法改進(jìn)一下，改成逐個(gè)比較字符串的Hash值就可以了呢，答案是，遠(yuǎn)遠(yuǎn)不夠，要想得到最快的算法，就不能進(jìn)行逐個(gè)的比較，通常是構(gòu)造一個(gè)哈希表(Hash Table)來(lái)解決問(wèn)題，哈希表是一個(gè)大數(shù)組，這個(gè)數(shù)組的容量根據(jù)程序的要求來(lái)定義，例如1024，每一個(gè)Hash值通過(guò)取模運(yùn)算 (mod) 對(duì)應(yīng)到數(shù)組中的一個(gè)位置，這樣，只要比較這個(gè)字符串的哈希值對(duì)應(yīng)的位置又沒(méi)有被占用，就可以得到最后的結(jié)果了，想想這是什么速度？是的，是最快的O(1)，現(xiàn)在仔細(xì)看看這個(gè)算法吧：
typedef struct
{
int nHashA;
int nHashB;
char bExists;
......
} SOMESTRUCTRUE;
一種可能的結(jié)構(gòu)體定義？
lpszString 為要在hash表中查找的字符串；lpTable 為存儲(chǔ)字符串hash值的hash表
int GetHashTablePos( har *lpszString, SOMESTRUCTURE *lpTable )
{
int nHash = HashString(lpszString);
int nHashPos = nHash % nTableSize;
if ( lpTable[nHashPos].bExists && !strcmp( lpTable[nHashPos].pString, lpszString ) )
{
return nHashPos;
}
else
{
return -1;
}
看到此，我想大家都在想一個(gè)很?chē)?yán)重的問(wèn)題：“如果兩個(gè)字符串在哈希表中對(duì)應(yīng)的位置相同怎么辦？”,畢竟一個(gè)數(shù)組容量是有限的，這種可能性很大。解決該問(wèn)題的方法很多，我首先想到的就是用“鏈表”,感謝大學(xué)里學(xué)的數(shù)據(jù)結(jié)構(gòu)教會(huì)了這個(gè)百試百靈的法寶，我遇到的很多算法都可以轉(zhuǎn)化成鏈表來(lái)解決，只要在哈希表的每個(gè)入口掛一個(gè)鏈表，保存所有對(duì)應(yīng)的字符串就OK了。事情到此似乎有了完美的結(jié)局，如果是把問(wèn)題獨(dú)自交給我解決，此時(shí)我可能就要開(kāi)始定義數(shù)據(jù)結(jié)構(gòu)然后寫(xiě)代碼了。然而Blizzard的程序員使用的方法則是更精妙的方法。基本原理就是：他們?cè)诠１碇胁皇怯靡粋€(gè)哈希值而是用三個(gè)哈希值來(lái)校驗(yàn)字符串。
MPQ使用文件名哈希表來(lái)跟蹤內(nèi)部的所有文件。但是這個(gè)表的格式與正常的哈希表有一些不同。首先，它沒(méi)有使用哈希作為下標(biāo)，把實(shí)際的文件名存儲(chǔ)在表中用于驗(yàn)證，實(shí)際上它根本就沒(méi)有存儲(chǔ)文件名。而是使用了3種不同的哈希：一個(gè)用于哈希表的下標(biāo)，兩個(gè)用于驗(yàn)證。這兩個(gè)驗(yàn)證哈希替代了實(shí)際文件名。
當(dāng)然了，這樣仍然會(huì)出現(xiàn)2個(gè)不同的文件名哈希到3個(gè)同樣的哈希。但是這種情況發(fā)生的概率平均是1:18889465931478580854784，這個(gè)概率對(duì)于任何人來(lái)說(shuō)應(yīng)該都是足夠小的。現(xiàn)在再回到數(shù)據(jù)結(jié)構(gòu)上，Blizzard使用的哈希表沒(méi)有使用鏈表，而采用"順延"的方式來(lái)解決問(wèn)題，看看這個(gè)算法：
lpszString 為要在hash表中查找的字符串；lpTable 為存儲(chǔ)字符串hash值的hash表；nTableSize 為hash表的長(zhǎng)度；
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;
int nHashPos = nHashStart;
while ( lpTable[nHashPos].bExists )
{
/*如果僅僅是判斷在該表中時(shí)候存在這個(gè)字符串，就比較這兩個(gè)hash值就可以了，不用對(duì)
*結(jié)構(gòu)體中的字符串進(jìn)行比較。這樣會(huì)加快運(yùn)行的速度？減少hash表占用的空間？這種
*方法一般應(yīng)用在什么場(chǎng)合？*/
if ( lpTable[nHashPos].nHashA == nHashA
&& lpTable[nHashPos].nHashB == nHashB )
{
return nHashPos;
}
else
{
nHashPos = (nHashPos + 1) % nTableSize;
}
if (nHashPos == nHashStart)
break;
}
return -1;
}
1. 計(jì)算出字符串的三個(gè)哈希值（一個(gè)用來(lái)確定位置，另外兩個(gè)用來(lái)校驗(yàn))
2. 察看哈希表中的這個(gè)位置
3. 哈希表中這個(gè)位置為空嗎？如果為空，則肯定該字符串不存在，返回
4. 如果存在，則檢查其他兩個(gè)哈希值是否也匹配，如果匹配，則表示找到了該字符串，返回
5. 移到下一個(gè)位置，如果已經(jīng)移到了表的末尾，則反繞到表的開(kāi)始位置起繼續(xù)查詢
6. 看看是不是又回到了原來(lái)的位置，如果是，則返回沒(méi)找到
7. 回到3
補(bǔ)充1：其他比較簡(jiǎn)單一些的hash函數(shù)：
/*key為一個(gè)字符串，nTableLength為哈希表的長(zhǎng)度
*該函數(shù)得到的hash值分布比較均勻*/
unsigned long getHashIndex( const char *key, int nTableLength )
{
unsigned long nHash = 0;
while (*key)
{
nHash = (nHash<<5) + nHash + *key++;
}
return ( nHash % nTableLength );
}
補(bǔ)充2：
哈 希表的數(shù)組是定長(zhǎng)的，如果太大，則浪費(fèi)，如果太小，體現(xiàn)不出效率。合適的數(shù)組大小是哈希表的性能的關(guān)鍵。哈希表的尺寸最好是一個(gè)質(zhì)數(shù)。當(dāng)然，根據(jù)不同的數(shù) 據(jù)量，會(huì)有不同的哈希表的大小。對(duì)于數(shù)據(jù)量時(shí)多時(shí)少的應(yīng)用，最好的設(shè)計(jì)是使用動(dòng)態(tài)可變尺寸的哈希表，那么如果你發(fā)現(xiàn)哈希表尺寸太小了，比如其中的元素是哈 希表尺寸的2倍時(shí)，我們就需要擴(kuò)大哈希表尺寸，一般是擴(kuò)大一倍。下面是哈希表尺寸大小的可能取值：
17, 37, 79, 163, 331,
673, 1361, 2729, 471, 10949,
21911, 43853, 87719, 175447, 350899,
701819, 1403641, 2807303, 5614657, 11229331,
22458671, 44917381, 89834777, 179669557, 359339171,
718678369, 1437356741, 2147483647
以下為該程序的源代碼，在linux下測(cè)試通過(guò)：
#include <stdio.h>
/*crytTable[]里面保存的是HashString函數(shù)里面將會(huì)用到的一些數(shù)據(jù)，在prepareCryptTable
*函數(shù)里面初始化*/
unsigned long cryptTable[0x500];
/***********************************************************
*以下的函數(shù)生成一個(gè)長(zhǎng)度為0x500（合10進(jìn)制數(shù)：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 );
}
}
}
/***********************************************************
*以下函數(shù)計(jì)算lpszFileName 字符串的hash值，其中dwHashType 為hash的類(lèi)型，
*在下面GetHashTablePos函數(shù)里面調(diào)用本函數(shù)，其可以取的值為0、1、2；該函數(shù)
*返回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;
}
/***********************************************************
*在main中測(cè)試argv[1]的三個(gè)hash值：
* ./hash "arr\units.dat"
* ./hash "unit\neutral\acritter.grp"
***********************************************************/
int main( int argc, char **argv )
{
unsigned long ulHashValue;
int i = 0;
if ( argc != 2 )
{
printf("please input two arguments\n");
return -1;
}
/*初始化數(shù)組：crytTable[0x500]*/
prepareCryptTable();
/*打印數(shù)組crytTable[0x500]里面的值*/
for ( ; i < 0x500; i++ )
{
if ( i % 10 == 0 )
{
printf("\n");
}
printf("%-12X", cryptTable[i] );
}
ulHashValue = HashString( argv[1], 0 );
printf("\n----%X ----\n", ulHashValue );
ulHashValue = HashString( argv[1], 1 );
printf("----%X ----\n", ulHashValue );
ulHashValue = HashString( argv[1], 2 );
printf("----%X ----\n", ulHashValue );
return 0;
}