一個簡單的問題：有一個龐大的字符串數組，然后給你一個單獨的字符串，讓你從這個數組中查找是否有這個字符串并找到它，你會怎么做？有一個方法最簡單，老老 實實從頭查到尾，一個一個比較，直到找到為止，我想只要學過程序設計的人都能把這樣一個程序作出來，但要是有程序員把這樣的程序交給用戶，我只能用無語來 評價，或許它真的能工作，但...也只能如此了。
最合適的算法自然是使用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, actually) is virtually impossible)。舉個例子，字符串"unitneutralacritter.grp"通過這個算法得到的結果是0xA26067F3。
是不是把第一個算法改進一下，改成逐個比較字符串的Hash值就可以了呢，答案是，遠遠不夠，要想得到最快的算法，就不能進行逐個的比較，通常是構造一個哈希表(Hash Table)來解決問題，哈希表是一個大數組，這個數組的容量根據程序的要求來定義，例如1024，每一個Hash值通過取模運算 (mod) 對應到數組中的一個位置，這樣，只要比較這個字符串的哈希值對應的位置又沒有被占用，就可以得到最后的結果了，想想這是什么速度？是的，是最快的O(1)，現在仔細看看這個算法吧：
typedef struct
{
int nHashA;
int nHashB;
char bExists;
......
} SOMESTRUCTRUE;
一種可能的結構體定義？
lpszString 為要在hash表中查找的字符串；lpTable 為存儲字符串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;
}
看到此，我想大家都在想一個很嚴重的問題：“如果兩個字符串在哈希表中對應的位置相同怎么辦？”,畢竟一個數組容量是有限的，這種可能性很大。解決該問題的方法很多，我首先想到的就是用“鏈表”,感謝大學里學的數據結構教會了這個百試百靈的法寶，我遇到的很多算法都可以轉化成鏈表來解決，只要在哈希表的每個入口掛一個鏈表，保存所有對應的字符串就OK了。事情到此似乎有了完美的結局，如果是把問題獨自交給我解決，此時我可能就要開始定義數據結構然后寫代碼了。然而Blizzard的程序員使用的方法則是更精妙的方法。基本原理就是：他們在哈希表中不是用一個哈希值而是用三個哈希值來校驗字符串。
MPQ使用文件名哈希表來跟蹤內部的所有文件。但是這個表的格式與正常的哈希表有一些不同。首先，它沒有使用哈希作為下標，把實際的文件名存儲在表中用于驗證，實際上它根本就沒有存儲文件名。而是使用了3種不同的哈希：一個用于哈希表的下標，兩個用于驗證。這兩個驗證哈希替代了實際文件名。
當然了，這樣仍然會出現2個不同的文件名哈希到3個同樣的哈希。但是這種情況發生的概率平均是1:18889465931478580854784，這個概率對于任何人來說應該都是足夠小的。現在再回到數據結構上，Blizzard使用的哈希表沒有使用鏈表，而采用"順延"的方式來解決問題，看看這個算法：
lpszString 為要在hash表中查找的字符串；lpTable 為存儲字符串hash值的hash表；nTableSize 為hash表的長度；
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 )
{
/*如果僅僅是判斷在該表中時候存在這個字符串，就比較這兩個hash值就可以了，不用對
*結構體中的字符串進行比較。這樣會加快運行的速度？減少hash表占用的空間？這種
*方法一般應用在什么場合？*/
if ( lpTable[nHashPos].nHashA == nHashA
&& lpTable[nHashPos].nHashB == nHashB )
{
return nHashPos;
}
else
{
nHashPos = (nHashPos + 1) % nTableSize;
}
if (nHashPos == nHashStart)
break;
}
return -1;
}
1. 計算出字符串的三個哈希值（一個用來確定位置，另外兩個用來校驗)
2. 察看哈希表中的這個位置
3. 哈希表中這個位置為空嗎？如果為空，則肯定該字符串不存在，返回
4. 如果存在，則檢查其他兩個哈希值是否也匹配，如果匹配，則表示找到了該字符串，返回
5. 移到下一個位置，如果已經移到了表的末尾，則反繞到表的開始位置起繼續查詢
6. 看看是不是又回到了原來的位置，如果是，則返回沒找到
7. 回到3
補充1：其他比較簡單一些的hash函數：
/*key為一個字符串，nTableLength為哈希表的長度
*該函數得到的hash值分布比較均勻*/
unsigned long getHashIndex( const char *key, int nTableLength )
{
unsigned long nHash = 0;
while (*key)
{
nHash = (nHash<<5) + nHash + *key++;
}
return ( nHash % nTableLength );
}
補充2：
哈 希表的數組是定長的，如果太大，則浪費，如果太小，體現不出效率。合適的數組大小是哈希表的性能的關鍵。哈希表的尺寸最好是一個質數。當然，根據不同的數 據量，會有不同的哈希表的大小。對于數據量時多時少的應用，最好的設計是使用動態可變尺寸的哈希表，那么如果你發現哈希表尺寸太小了，比如其中的元素是哈 希表尺寸的2倍時，我們就需要擴大哈希表尺寸，一般是擴大一倍。下面是哈希表尺寸大小的可能取值：
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下測試通過：
#include <stdio.h>
/*crytTable[]里面保存的是HashString函數里面將會用到的一些數據，在prepareCryptTable
*函數里面初始化*/
unsigned long cryptTable[0x500];
/***********************************************************
*以下的函數生成一個長度為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;
}
/***********************************************************
*在main中測試argv[1]的三個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;
}
/*初始化數組：crytTable[0x500]*/
prepareCryptTable();
/*打印數組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;
}