1 概述
鏈表查找的時間效率為O(N)，二分法為log2N，B+ Tree為log2N，但Hash鏈表查找的時間效率為O(1)。
設計高效算法往往需要使用Hash鏈表，常數級的查找速度是任何別的算法無法比擬的，Hash鏈表的構造和衝突的不同實現方法對效率當然有一定的影響，然而Hash函數是Hash鏈表最核心的部分，本文嚐試分析一些經典軟件中使用到的字符串Hash函數在執行效率、離散性、空間利用率等方麵的性能問題。
打造最快的Hash表(和Blizzard的對話)
先提一個簡單的問題，如果有一個龐大的字符串數組，然後給你一個單獨的字符串，讓你從這個數組中查找是否有這個字符串並找到它，你會怎麼做？
有一個方法最簡單，老老實實從頭查到尾，一個一個比較，直到找到為止，我想隻要學過程序設計的人都能把這樣一個程序作出來。
最合適的算法自然是使用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。
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的程序員使用的方法則是更精妙的方法。基本原理就是：他們在哈希表中不是用一個哈希值而是用三個哈希值來校驗字符串。如果說兩個不同的字符串經過一個哈希算法得到的入口點一致有可能，但用三個不同的哈希算法算出的入口點都一致，那幾乎可以肯定是不可能的事了，這個幾率是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
/////////////////////////////////////////////////////////
其他的一些哈希函數：
/////////////////////////////////////////////////////////
2經典字符串Hash函數介紹
作者閱讀過大量經典軟件原代碼，下麵分別介紹幾個經典軟件中出現的字符串Hash函數。
2.1 PHP中出現的字符串Hash函數
static unsigned long hashpjw(char *arKey, unsigned int nKeyLength)
{
unsigned long h = 0, g;
char *arEnd=arKey+nKeyLength;
while (arKey < arEnd) {
h = (h << 4) + *arKey++;
if ((g = (h & 0xF0000000))) {
h = h ^ (g >> 24);
h = h ^ g;
}
}
return h;
}
2.2 OpenSSL中出現的字符串Hash函數
unsigned long lh_strhash(char *str)
{
int i,l;
unsigned long ret=0;
unsigned short *s;
if (str == NULL) return(0);
l=(strlen(str)+1)/2;
s=(unsigned short *)str;
for (i=0; i
ret^=(s[i]<<(i&0x0f));
return(ret);
} */
/* The following hash seems to work very well on normal text strings
* no collisions on /usr/dict/words and it distributes on %2^n quite
* well, not as good as MD5, but still good.
*/
unsigned long lh_strhash(const char *c)
{
unsigned long ret=0;
long n;
unsigned long v;
int r;
if ((c == NULL) || (*c == '/0'))
return(ret);
/*
unsigned char b[16];
MD5(c,strlen(c),b);
return(b[0]|(b[1]<<8)|(b[2]<<16)|(b[3]<<24));
*/
n=0x100;
while (*c)
{
v=n|(*c);
n+=0x100;
r= (int)((v>>2)^v)&0x0f;
ret=(ret(32-r));
ret&=0xFFFFFFFFL;
ret^=v*v;
c++;
}
return((ret>>16)^ret);
}
在下麵的測量過程中我們分別將上麵的兩個函數標記為OpenSSL_Hash1和OpenSSL_Hash2，至於上麵的實現中使用MD5算法的實現函數我們不作測試。
2.3 MySql中出現的字符串Hash函數
#ifndef NEW_HASH_FUNCTION
/* Calc hashvalue for a key */
static uint calc_hashnr(const byte *key,uint length)
{
register uint nr=1, nr2=4;
while (length--)
{
nr^= (((nr & 63)+nr2)*((uint) (uchar) *key++))+ (nr << 8);
nr2+=3;
}
return((uint) nr);
}
/* Calc hashvalue for a key, case indepenently */
static uint calc_hashnr_caseup(const byte *key,uint length)
{
register uint nr=1, nr2=4;
while (length--)
{
nr^= (((nr & 63)+nr2)*((uint) (uchar) toupper(*key++)))+ (nr << 8);
nr2+=3;
}
return((uint) nr);
}
#else
/*
* Fowler/Noll/Vo hash
*
* The basis of the hash algorithm was taken from an idea sent by email to the
* IEEE Posix P1003.2 mailing list from Phong Vo (kpv@research.att.com) and
* Glenn Fowler (gsf@research.att.com). Landon Curt Noll (chongo@toad.com)
* later improved on their algorithm.
*
* The magic is in the interesting relationship between the special prime
* 16777619 (2^24 + 403) and 2^32 and 2^8.
*
* This hash produces the fewest collisions of any function that we've seen so
* far, and works well on both numbers and strings.
*/
uint calc_hashnr(const byte *key, uint len)
{
const byte *end=key+len;
uint hash;
for (hash = 0; key < end; key++)
{
hash *= 16777619;
hash ^= (uint) *(uchar*) key;
}
return (hash);
}
uint calc_hashnr_caseup(const byte *key, uint len)
{
const byte *end=key+len;
uint hash;
for (hash = 0; key < end; key++)
{
hash *= 16777619;
hash ^= (uint) (uchar) toupper(*key);
}
return (hash);
}
#endif
Mysql中對字符串Hash函數還區分了大小寫，我們的測試中使用不區分大小寫的字符串Hash函數，另外我們將上麵的兩個函數分別記為MYSQL_Hash1和MYSQL_Hash2。
2.4 另一個經典字符串Hash函數
unsigned int hash(char *str)
{
register unsigned int h;
register unsigned char *p;
for(h=0, p = (unsigned char *)str; *p ; p++)
h = 31 * h + *p;
return h;
}
3 測試及結果
3.1 測試說明
從上麵給出的經典字符串Hash函數中可以看出，有的涉及到字符串大小敏感問題，我們的測試中隻考慮字符串大小寫敏感的函數，另外在上麵的函數中有的函數需要長度參數，有的不需要長度參數，這對函數本身的效率有一定的影響，我們的測試中將對函數稍微作一點修改，全部使用長度參數，並將函數內部出現的計算長度代碼刪除。
我們用來作測試用的Hash鏈表采用經典的拉鏈法解決衝突，另外我們采用靜態分配桶（Hash鏈表長度）的方法來構造Hash鏈表，這主要是為了簡化我們的實現，並不影響我們的測試結果。
測試文本采用單詞表，測試過程中從一個輸入文件中讀取全部不重複單詞構造一個Hash表，測試內容分別是函數總調用次數、函數總調用時間、最大拉鏈長度、 平均拉鏈長度、桶利用率（使用過的桶所占的比率），其中函數總調用次數是指Hash函數被調用的總次數，為了測試出函數執行時間，該值在測試過程中作了一 定的放大，函數總調用時間是指Hash函數總的執行時間，最大拉鏈長度是指使用拉鏈法構造鏈表過程中出現的最大拉鏈長度，平均拉鏈長度指拉鏈的平均長度。
測試過程中使用的機器配置如下：
PIII600筆記本，128M內存，windows 2000 server操作係統。
3.2 測試結果
以下分別是對兩個不同文本文件中的全部不重複單詞構造Hash鏈表的測試結果，測試結果中函數調用次數放大了100倍，相應的函數調用時間也放大了100倍。
從上表可以看出，這些經典軟件雖然構造字符串Hash函數的方法不同，但是它們的效率都是不錯的，相互之間差距很小，讀者可以參考實際情況從其中借鑒使用。
552
