作者：July褥紫、wuliming衣厘、pkuoliver

說明：本文分為三部分內(nèi)容捺典，第一部分為一道百度面試題Top K算法的詳解浅碾；第二部分為關(guān)于Hash表算法的詳細(xì)闡述大州；第三部分為打造一個(gè)最快的Hash表算法。

第一部分：Top K 算法詳解

問題描述（百度面試題）：

搜索引擎會通過日志文件把用戶每次檢索使用的所有檢索串都記錄下來及穗，每個(gè)查詢串的長度為1-255字節(jié)摧茴。假設(shè)目前有一千萬個(gè)記錄（這些查詢串的重復(fù)度比較高，雖然總數(shù)是1千萬埂陆，但如果除去重復(fù)后苛白，不超過3百萬個(gè)。一個(gè)查詢串的重復(fù)度越高焚虱，說明查詢它的用戶越多购裙，也就是越熱門。）鹃栽，請你統(tǒng)計(jì)最熱門的10個(gè)查詢串躏率，要求使用的內(nèi)存不能超過1G。

必備知識：

什么是哈希表民鼓？

哈希表（Hash table薇芝，也叫散列表），是根據(jù)key而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)丰嘉。也就是說夯到，它通過把key映射到表中一個(gè)位置來訪問記錄，以加快查找的速度饮亏。這個(gè)映射函數(shù)叫做散列函數(shù)耍贾，存放記錄的數(shù)組叫做散列表。

哈希表的做法其實(shí)很簡單路幸，就是把key通過一個(gè)固定的算法函數(shù)即所謂的哈希函數(shù)轉(zhuǎn)換成一個(gè)整型數(shù)字荐开，然后就將該數(shù)字對數(shù)組長度進(jìn)行取余，取余結(jié)果就當(dāng)作數(shù)組的下標(biāo)简肴，將value存儲在以該數(shù)字為下標(biāo)的數(shù)組空間里晃听。

而當(dāng)使用哈希表進(jìn)行查詢的時(shí)候，就是再次使用哈希函數(shù)將key轉(zhuǎn)換為對應(yīng)的數(shù)組下標(biāo)砰识，并定位到該空間獲取value能扒，如此一來，就可以充分利用到數(shù)組的定位性能進(jìn)行數(shù)據(jù)定位（文章第二仍翰、三部分赫粥，會針對Hash表詳細(xì)闡述）。

問題解析：

要統(tǒng)計(jì)最熱門查詢予借，首先就是要統(tǒng)計(jì)每個(gè)Query出現(xiàn)的次數(shù)越平，然后根據(jù)統(tǒng)計(jì)結(jié)果频蛔，找出Top 10。所以我們可以基于這個(gè)思路分兩步來設(shè)計(jì)該算法秦叛。

即晦溪，此問題的解決分為以下兩個(gè)步驟：

第一步：Query統(tǒng)計(jì)

Query統(tǒng)計(jì)有以下倆個(gè)方法，可供選擇：

1挣跋、直接排序法

首先我們最先想到的的算法就是排序了三圆，首先對這個(gè)日志里面的所有Query都進(jìn)行排序，然后再遍歷排好序的Query避咆，統(tǒng)計(jì)每個(gè)Query出現(xiàn)的次數(shù)了舟肉。

但是題目中有明確要求，那就是內(nèi)存不能超過1G查库，一千萬條記錄路媚，每條記錄是255Byte，很顯然要占據(jù)2.375G內(nèi)存樊销，這個(gè)條件就不滿足要求了整慎。

讓我們回憶一下數(shù)據(jù)結(jié)構(gòu)課程上的內(nèi)容，當(dāng)數(shù)據(jù)量比較大而且內(nèi)存無法裝下的時(shí)候围苫，我們可以采用外排序的方法來進(jìn)行排序裤园，這里我們可以采用歸并排序，因?yàn)闅w并排序有一個(gè)比較好的時(shí)間復(fù)雜度O(nlogn)剂府。

排完序之后我們再對已經(jīng)有序的Query文件進(jìn)行遍歷拧揽，統(tǒng)計(jì)每個(gè)Query出現(xiàn)的次數(shù)，再次寫入文件中周循。

綜合分析一下强法，排序的時(shí)間復(fù)雜度是O(nlogn)万俗，而遍歷的時(shí)間復(fù)雜度是O(n)湾笛，因此該算法的總體時(shí)間復(fù)雜度就是O(n+nlogn)=O(nlogn)。

2闰歪、Hash Table法

在第1個(gè)方法中嚎研，我們采用了排序的辦法來統(tǒng)計(jì)每個(gè)Query出現(xiàn)的次數(shù)，時(shí)間復(fù)雜度是O(nlogn)库倘，那么能不能有更好的方法來存儲临扮，而時(shí)間復(fù)雜度更低呢？

題目中說明了教翩，雖然有一千萬個(gè)Query杆勇，但是由于重復(fù)度比較高，因此事實(shí)上只有300萬的Query饱亿，每個(gè)Query 255Byte蚜退，因此我們可以考慮把他們都放進(jìn)內(nèi)存中去闰靴，而現(xiàn)在只是需要一個(gè)合適的數(shù)據(jù)結(jié)構(gòu)，在這里钻注，Hash Table絕對是我們優(yōu)先的選擇蚂且，因?yàn)镠ash Table的查詢速度非常的快，幾乎是O(1)的時(shí)間復(fù)雜度幅恋。

那么杏死，我們的算法就有了：維護(hù)一個(gè)Key為Query字串，Value為該Query出現(xiàn)次數(shù)的HashTable捆交，每次讀取一個(gè)Query淑翼，如果該字串不在Table中，那么加入該字串品追，并且將Value值設(shè)為1窒舟；如果該字串在Table中，那么將該字串的計(jì)數(shù)加一即可诵盼。最終我們在O(n)的時(shí)間復(fù)雜度內(nèi)完成了對該海量數(shù)據(jù)的處理惠豺。

本方法相比算法1：在時(shí)間復(fù)雜度上提高了一個(gè)數(shù)量級，為O(n)风宁，但不僅僅是時(shí)間復(fù)雜度上的優(yōu)化洁墙，該方法只需要IO數(shù)據(jù)文件一次，而算法1的IO次數(shù)較多的戒财，因此該算法2比算法1在工程上有更好的可操作性热监。

第二步：找出Top 10

算法一：普通排序

我想對于排序算法大家都已經(jīng)不陌生了，這里不在贅述饮寞，我們要注意的是排序算法的時(shí)間復(fù)雜度是O(nlogn)孝扛，在本題目中，三百萬條記錄幽崩，用1G內(nèi)存是可以存下的苦始。

算法二：部分排序

題目要求是求出Top 10，因此我們沒有必要對所有的Query都進(jìn)行排序慌申，我們只需要維護(hù)一個(gè)10個(gè)大小的數(shù)組陌选，初始化放入10個(gè)Query，按照每個(gè)Query的統(tǒng)計(jì)次數(shù)由大到小排序蹄溉，然后遍歷這300萬條記錄咨油，每讀一條記錄就和數(shù)組最后一個(gè)Query對比，如果小于這個(gè)Query柒爵，那么繼續(xù)遍歷役电，否則，將數(shù)組中最后一條數(shù)據(jù)淘汰棉胀，加入當(dāng)前的Query法瑟。最后當(dāng)所有的數(shù)據(jù)都遍歷完畢之后囱晴，那么這個(gè)數(shù)組中的10個(gè)Query便是我們要找的Top10了。

不難分析出瓢谢，這樣畸写，算法的最壞時(shí)間復(fù)雜度是N*K， 其中K是指top多少氓扛。

算法三：堆

在算法二中枯芬，我們已經(jīng)將時(shí)間復(fù)雜度由NlogN優(yōu)化到NK，不得不說這是一個(gè)比較大的改進(jìn)了采郎，可是有沒有更好的辦法呢千所？

分析一下，在算法二中蒜埋，每次比較完成之后淫痰，需要的操作復(fù)雜度都是K，因?yàn)橐言夭迦氲揭粋€(gè)線性表之中整份，而且采用的是順序比較待错。這里我們注意一下，該數(shù)組是有序的烈评，一次我們每次查找的時(shí)候可以采用二分的方法查找火俄，這樣操作的復(fù)雜度就降到了logK，可是讲冠，隨之而來的問題就是數(shù)據(jù)移動瓜客，因?yàn)橐苿訑?shù)據(jù)次數(shù)增多了。不過竿开，這個(gè)算法還是比算法二有了改進(jìn)谱仪。

基于以上的分析，我們想想否彩，有沒有一種既能快速查找疯攒，又能快速移動元素的數(shù)據(jù)結(jié)構(gòu)呢？回答是肯定的胳搞，那就是堆卸例。

借助堆結(jié)構(gòu)称杨，我們可以在log量級的時(shí)間內(nèi)查找和調(diào)整/移動肌毅。因此到這里，我們的算法可以改進(jìn)為這樣姑原，維護(hù)一個(gè)K(該題目中是10)大小的小根堆悬而，然后遍歷300萬的Query，分別和根元素進(jìn)行對比锭汛。

思想與上述算法二一致笨奠，只是算法在算法三袭蝗，我們采用了最小堆這種數(shù)據(jù)結(jié)構(gòu)代替數(shù)組，把查找目標(biāo)元素的時(shí)間復(fù)雜度有O(K)降到了O(logK)般婆。

那么這樣到腥，采用堆數(shù)據(jù)結(jié)構(gòu)，算法三蔚袍，最終的時(shí)間復(fù)雜度就降到了N‘logK乡范，和算法二相比，又有了比較大的改進(jìn)啤咽。

總結(jié)：

至此晋辆，算法就完全結(jié)束了，經(jīng)過上述第一步宇整、先用Hash表統(tǒng)計(jì)每個(gè)Query出現(xiàn)的次數(shù)瓶佳，O(N)；然后第二步鳞青、采用堆數(shù)據(jù)結(jié)構(gòu)找出Top 10霸饲，N*O(logK)。所以臂拓，我們最終的時(shí)間復(fù)雜度是：O(N)+N'*O(logK)贴彼。（N為1000萬，N’為300萬）埃儿。如果各位有什么更好的算法器仗，歡迎留言評論。

第二部分童番、Hash表算法的詳細(xì)解析

什么是Hash

Hash精钮，一般翻譯做“散列”，也有直接音譯為“哈咸旮”的轨香，就是把任意長度的輸入（又叫做預(yù)映射， pre-image）幼东，通過散列算法臂容，變換成固定長度的輸出，該輸出就是散列值根蟹。這種轉(zhuǎn)換是一種壓縮映射脓杉，也就是，散列值的空間通常遠(yuǎn)小于輸入的空間简逮，不同的輸入可能會散列成相同的輸出球散，而不可能從散列值來唯一的確定輸入值。簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數(shù)散庶。

Hash主要用于信息安全領(lǐng)域中加密算法蕉堰，它把一些不同長度的信息轉(zhuǎn)化成雜亂的128位的編碼凌净，這些編碼值叫做HASH值. 也可以說，Hash就是找到一種數(shù)據(jù)內(nèi)容和數(shù)據(jù)存放地址之間的映射關(guān)系屋讶。

數(shù)組的特點(diǎn)是：尋址容易冰寻，插入和刪除困難；而鏈表的特點(diǎn)是：尋址困難皿渗，插入和刪除容易性雄。那么我們能不能綜合兩者的特性，做出一種尋址容易羹奉，插入刪除也容易的數(shù)據(jù)結(jié)構(gòu)秒旋？答案是肯定的，這就是我們要提起的哈希表诀拭，哈希表有多種不同的實(shí)現(xiàn)方法迁筛，我接下來解釋的是最常用的一種方法——拉鏈法，我們可以理解為“鏈表的數(shù)組”耕挨，如圖：

左邊很明顯是個(gè)數(shù)組细卧，數(shù)組的每個(gè)成員包括一個(gè)指針，指向一個(gè)鏈表的頭筒占，當(dāng)然這個(gè)鏈表可能為空贪庙，也可能元素很多。我們根據(jù)元素的一些特征把元素分配到不同的鏈表中去翰苫，也是根據(jù)這些特征止邮，找到正確的鏈表，再從鏈表中找出這個(gè)元素奏窑。

元素特征轉(zhuǎn)變?yōu)閿?shù)組下標(biāo)的方法就是散列法导披。散列法當(dāng)然不止一種，下面列出三種比較常用的：

1埃唯，除法散列法

最直觀的一種撩匕，上圖使用的就是這種散列法，公式：

index = value % 16

學(xué)過匯編的都知道墨叛，求模數(shù)其實(shí)是通過一個(gè)除法運(yùn)算得到的止毕，所以叫“除法散列法”。

2漠趁，平方散列法

求index是非常頻繁的操作扁凛，而乘法的運(yùn)算要比除法來得省時(shí)（對現(xiàn)在的CPU來說，估計(jì)我們感覺不出來）棚潦，所以我們考慮把除法換成乘法和一個(gè)位移操作令漂。公式：

index = (value * value) >> 28（右移，除以2^28丸边。記法：左移變大叠必，是乘。右移變小妹窖，是除纬朝。）

如果數(shù)值分配比較均勻的話這種方法能得到不錯(cuò)的結(jié)果，但我上面畫的那個(gè)圖的各個(gè)元素的值算出來的index都是0——非常失敗骄呼。也許你還有個(gè)問題共苛，value如果很大，value * value不會溢出嗎蜓萄？答案是會的隅茎，但我們這個(gè)乘法不關(guān)心溢出，因?yàn)槲覀兏静皇菫榱双@取相乘結(jié)果嫉沽，而是為了獲取index辟犀。

3，斐波那契（Fibonacci）散列法

平方散列法的缺點(diǎn)是顯而易見的绸硕，所以我們能不能找出一個(gè)理想的乘數(shù)堂竟，而不是拿value本身當(dāng)作乘數(shù)呢？答案是肯定的玻佩。

1出嘹，對于16位整數(shù)而言，這個(gè)乘數(shù)是40503咬崔。

2税稼，對于32位整數(shù)而言，這個(gè)乘數(shù)是2654435769垮斯。

3娶聘，對于64位整數(shù)而言，這個(gè)乘數(shù)是11400714819323198485甚脉。

這幾個(gè)“理想乘數(shù)”是如何得出來的呢丸升？這跟一個(gè)法則有關(guān)，叫黃金分割法則牺氨，而描述黃金分割法則的最經(jīng)典表達(dá)式無疑就是著名的斐波那契數(shù)列狡耻，即如此形式的序列：0,?1,?1,?2,?3,?5,?8,?13,?21,?34,?55,?89,?144,233,?377,?610， 987, 1597, 2584, 4181, 6765, 10946猴凹，…夷狰。另外，斐波那契數(shù)列的值和太陽系八大行星的軌道半徑的比例出奇吻合郊霎。

對我們常見的32位整數(shù)而言沼头，公式：

index = (value * 2654435769) >> 28

如果用這種斐波那契散列法的話，那上面的圖就變成這樣了：

很明顯，用斐波那契散列法調(diào)整之后要比原來的取摸散列法好很多进倍。

適用范圍

快速查找土至，刪除的基本數(shù)據(jù)結(jié)構(gòu)，通常需要總數(shù)據(jù)量可以放入內(nèi)存猾昆。

基本原理及要點(diǎn)

hash函數(shù)選擇陶因，針對字符串、整數(shù)垂蜗、排列楷扬，具體相應(yīng)的hash方法。

碰撞處理贴见，一種是open hashing烘苹，也稱為拉鏈法；另一種就是closed hashing片部，也稱開地址法镣衡，opened addressing。

擴(kuò)展

d-left hashing中的d是多個(gè)的意思吞琐，我們先簡化這個(gè)問題捆探，看一看2-left hashing。2-left hashing指的是將一個(gè)哈希表分成長度相等的兩半站粟，分別叫做T1和T2黍图，給T1和T2分別配備一個(gè)哈希函數(shù)，h1和h2奴烙。在存儲一個(gè)新的key時(shí)助被，同時(shí)用兩個(gè)哈希函數(shù)進(jìn)行計(jì)算，得出兩個(gè)地址h1[key]和h2[key]切诀。這時(shí)需要檢查T1中的h1[key]位置和T2中的h2[key]位置揩环，哪一個(gè)位置已經(jīng)存儲的（有碰撞的）key比較多，然后將新key存儲在負(fù)載少的位置幅虑。如果兩邊一樣多丰滑，比如兩個(gè)位置都為空或者都存儲了一個(gè)key，就把新key存儲在左邊的T1子表中倒庵，2-left也由此而來褒墨。在查找一個(gè)key時(shí)，必須進(jìn)行兩次hash擎宝，同時(shí)查找兩個(gè)位置郁妈。

問題實(shí)例（海量數(shù)據(jù)處理）

我們知道hash 表在海量數(shù)據(jù)處理中有著廣泛的應(yīng)用，下面绍申，請看另一道百度面試題：

題目：海量日志數(shù)據(jù)噩咪，提取出某日訪問百度次數(shù)最多的那個(gè)IP顾彰。

方案：IP的數(shù)目還是有限的，最多2^32個(gè)胃碾，所以可以考慮使用hash將IP直接存入內(nèi)存涨享，然后進(jìn)行統(tǒng)計(jì)。

第三部分书在、最快的Hash表算法

接下來灰伟，咱們來具體分析一下一個(gè)最快的Hash表算法拆又。

我們由一個(gè)簡單的問題逐步入手：有一個(gè)龐大的字符串?dāng)?shù)組儒旬，然后給你一個(gè)單獨(dú)的字符串，讓你從這個(gè)數(shù)組中查找是否有這個(gè)字符串并找到它帖族，你會怎么做栈源？有一個(gè)方法最簡單，老老實(shí)實(shí)從頭查到尾竖般，一個(gè)一個(gè)比較甚垦，直到找到為止，我想只要學(xué)過程序設(shè)計(jì)的人都能把這樣一個(gè)程序作出來涣雕，但要是有程序員把這樣的程序交給用戶艰亮，我只能用無語來評價(jià)，或許它真的能工作挣郭，但...也只能如此了迄埃。

最合適的算法自然是使用HashTable（哈希表），先介紹介紹其中的基本知識兑障，所謂Hash侄非，一般是一個(gè)整數(shù)，通過某種算法流译，可以把一個(gè)字符串"壓縮" 成一個(gè)整數(shù)逞怨。當(dāng)然，無論如何福澡，一個(gè)32位整數(shù)是無法對應(yīng)回一個(gè)字符串的叠赦，但在程序中，兩個(gè)字符串計(jì)算出的Hash值相等的可能非常小革砸，下面看看在MPQ中的Hash算法：

函數(shù)一除秀、以下的函數(shù)生成一個(gè)長度為0x500（合10進(jìn)制數(shù)：1280）的cryptTable[0x500]

voidprepareCryptTable()

{

unsignedlongseed =0x00100001, index1 =0, index2 =0, i;for( index1 =0; index1 <0x100; index1++)

{for( index2 = index1, i =0; i <5; i++, index2 +=0x100)

{

unsignedlongtemp1, temp2;

seed= (seed *125+3) %0x2AAAAB;

temp1= (seed &0xFFFF) <<0x10;

seed= (seed *125+3) %0x2AAAAB;

temp2= (seed &0xFFFF);

cryptTable[index2]= ( temp1 |temp2 );

}

}

}

函數(shù)二、以下函數(shù)計(jì)算lpszFileName字符串的hash值业岁，其中dwHashType為hash的類型（在下面的函數(shù)三GetHashTablePos函數(shù)中調(diào)用此函數(shù)二）鳞仙，其可以取的值為0、1笔时、2棍好；該函數(shù)返回lpszFileName 字符串的hash值：

unsignedlongHashString(char*lpszFileName, unsignedlongdwHashType )

{

unsignedchar*key? = (unsignedchar*)lpszFileName;

unsignedlongseed1 =0x7FED7FED;

unsignedlongseed2 =0xEEEEEEEE;intch;while(*key !=0)

{

ch= toupper(*key++);

seed1= cryptTable[(dwHashType <<8) + ch] ^ (seed1 +seed2);

seed2= ch + seed1 + seed2 + (seed2 <<5) +3;

}returnseed1;

}

Blizzard的這個(gè)算法是非常高效的，被稱為"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"通過這個(gè)算法得到的結(jié)果是0xA26067F3扒怖。

是不是把第一個(gè)算法改進(jìn)一下，改成逐個(gè)比較字符串的Hash值就可以了呢业稼？答案是盗痒，遠(yuǎn)遠(yuǎn)不夠。要想得到最快的算法低散，就不能進(jìn)行逐個(gè)的比較俯邓，通常是構(gòu)造一個(gè)哈希表(Hash Table)來解決問題。哈希表是一個(gè)大數(shù)組熔号，這個(gè)數(shù)組的容量根據(jù)程序的要求來定義稽鞭，例如1024，每一個(gè)Hash值通過取模運(yùn)算 (mod) 對應(yīng)到數(shù)組中的一個(gè)位置引镊。這樣朦蕴，只要比較這個(gè)字符串的哈希值對應(yīng)的位置有沒有被占用，就可以得到最后的結(jié)果了弟头，想想這是什么速度吩抓？是的，是最快的O(1)赴恨，現(xiàn)在仔細(xì)看看這個(gè)算法吧：

typedefstruct{intnHashA;intnHashB;charbExists;

......

} SOMESTRUCTRUE;

一種可能的結(jié)構(gòu)體定義疹娶？

函數(shù)三、下述函數(shù)為在Hash表中查找是否存在目標(biāo)字符串嘱支，有則返回要查找字符串的Hash值蚓胸，無則，return -1.

intGetHashTablePos( har *lpszString, SOMESTRUCTURE *lpTable )//lpszString要在Hash表中查找的字符串除师，lpTable為存儲字符串Hash值的Hash表沛膳。{intnHash = HashString(lpszString);//調(diào)用上述函數(shù)二，返回要查找字符串lpszString的Hash值汛聚。intnHashPos = nHash %nTableSize;if( lpTable[nHashPos].bExists? &&? !strcmp( lpTable[nHashPos].pString, lpszString ) )//如果找到的Hash值在表中存在锹安，且要查找的字符串與表中對應(yīng)位置的字符串相同{returnnHashPos;//則返回上述調(diào)用函數(shù)二后，找到的Hash值}else{return-1;

}

}

看到此倚舀，我想大家都在想一個(gè)很嚴(yán)重的問題：“如果兩個(gè)字符串在哈希表中對應(yīng)的位置相同怎么辦叹哭？”，畢竟一個(gè)數(shù)組容量是有限的痕貌，這種可能性很大风罩。解決該問題的方法很多，我首先想到的就是用“鏈表”舵稠，感謝大學(xué)里學(xué)的數(shù)據(jù)結(jié)構(gòu)教會了這個(gè)百試百靈的法寶超升，我遇到的很多算法都可以轉(zhuǎn)化成鏈表來解決入宦，只要在哈希表的每個(gè)入口掛一個(gè)鏈表，保存所有對應(yīng)的字符串就OK了室琢。事情到此似乎有了完美的結(jié)局乾闰，如果是把問題獨(dú)自交給我解決，此時(shí)我可能就要開始定義數(shù)據(jù)結(jié)構(gòu)然后寫代碼了盈滴。

然而Blizzard的程序員使用的方法則是更精妙的方法涯肩。基本原理就是：他們在哈希表中不是用一個(gè)哈希值而是用三個(gè)哈希值來校驗(yàn)字符串巢钓。

MPQ使用文件名哈希表來跟蹤內(nèi)部的所有文件病苗。但是這個(gè)表的格式與正常的哈希表有一些不同。首先竿报，它沒有使用哈希作為下標(biāo)铅乡，把實(shí)際的文件名存儲在表中用于驗(yàn)證继谚，實(shí)際上它根本就沒有存儲文件名烈菌。而是使用了3種不同的哈希：一個(gè)用于哈希表的下標(biāo)，兩個(gè)用于驗(yàn)證花履。這兩個(gè)驗(yàn)證哈希替代了實(shí)際文件名芽世。

當(dāng)然了，這樣仍然會出現(xiàn)2個(gè)不同的文件名哈希到3個(gè)同樣的哈希诡壁。但是這種情況發(fā)生的概率平均是：1:18889465931478580854784济瓢，這個(gè)概率對于任何人來說應(yīng)該都是足夠小的。現(xiàn)在再回到數(shù)據(jù)結(jié)構(gòu)上妹卿，Blizzard使用的哈希表沒有使用鏈表旺矾，而采用"順延"的方式來解決問題，看看這個(gè)算法：

函數(shù)四夺克、lpszString為要在hash表中查找的字符串箕宙；lpTable為存儲字符串hash值的hash表；nTableSize 為hash表的長度：

intGetHashTablePos(char*lpszString, MPQHASHTABLE *lpTable,intnTableSize )

{constintHASH_OFFSET =0, HASH_A =1, HASH_B =2;intnHash =HashString(lpszString, HASH_OFFSET);intnHashA =HashString(lpszString, HASH_A);intnHashB =HashString(lpszString, HASH_B);intnHashStart = nHash %nTableSize;intnHashPos =nHashStart;while( lpTable[nHashPos].bExists )

{/*如果僅僅是判斷在該表中時(shí)候存在這個(gè)字符串铺纽，就比較這兩個(gè)hash值就可以了柬帕，不用對結(jié)構(gòu)體中的字符串進(jìn)行比較。這樣會加快運(yùn)行的速度狡门？減少hash表占用的空間陷寝？這種

方法一般應(yīng)用在什么場合？*/if(lpTable[nHashPos].nHashA ==nHashA&&? lpTable[nHashPos].nHashB ==nHashB )

{returnnHashPos;

}else{

nHashPos= (nHashPos +1) %nTableSize;

}if(nHashPos == nHashStart)break;

}return-1;

}

上述程序解釋：

1. 計(jì)算出字符串的三個(gè)哈希值（一個(gè)用來確定位置其馏，另外兩個(gè)用來校驗(yàn))

2. 察看哈希表中的這個(gè)位置

3. 哈希表中這個(gè)位置為空嗎凤跑？如果為空，則肯定該字符串不存在叛复，返回-1仔引。

4. 如果存在鹏控，則檢查其他兩個(gè)哈希值是否也匹配，如果匹配肤寝，則表示找到了該字符串当辐，返回其Hash值。

5. 移到下一個(gè)位置鲤看，如果已經(jīng)移到了表的末尾缘揪，則反繞到表的開始位置起繼續(xù)查詢

6. 看看是不是又回到了原來的位置，如果是义桂，則返回沒找到

7. 回到3

ok找筝，這就是本文中所說的最快的Hash表算法。什么?不夠快?:D慷吊。歡迎袖裕，各位批評指正。

--------------------------------------------

補(bǔ)充1溉瓶、一個(gè)簡單的hash函數(shù)：

/*key為一個(gè)字符串急鳄，nTableLength為哈希表的長度

*該函數(shù)得到的hash值分布比較均勻*/unsignedlonggetHashIndex(constchar*key,intnTableLength )

{

unsignedlongnHash =0;while(*key)

{

nHash= (nHash<<5) + nHash + *key++;

}return(nHash %nTableLength);

}

補(bǔ)充2、一個(gè)完整測試程序：

哈希表的數(shù)組是定長的堰酿，如果太大疾宏，則浪費(fèi)，如果太小触创，體現(xiàn)不出效率坎藐。合適的數(shù)組大小是哈希表的性能的關(guān)鍵。哈希表的尺寸最好是一個(gè)質(zhì)數(shù)哼绑。當(dāng)然岩馍，根據(jù)不同的數(shù)據(jù)量，會有不同的哈希表的大小抖韩。對于數(shù)據(jù)量時(shí)多時(shí)少的應(yīng)用蛀恩，最好的設(shè)計(jì)是使用動態(tài)可變尺寸的哈希表，那么如果你發(fā)現(xiàn)哈希表尺寸太小了帽蝶，比如其中的元素是哈希表尺寸的2倍時(shí)赦肋，我們就需要擴(kuò)大哈希表尺寸，一般是擴(kuò)大一倍励稳。

下面是哈希表尺寸大小的可能取值：

17,??????????? 37,????????? 79,??????? 163,????????? 331,

673,?????????? 1361,??????? 2729,?????? 5471,???????? 10949,

21911,????????? 43853,????? 87719,????? 175447,????? 350899,

701819,???????? 1403641,??? 2807303,???? 5614657,???? 11229331,

22458671,?????? 44917381,??? 89834777,??? 179669557,?? 359339171,

718678369,????? 1437356741,? 2147483647

以下為該程序的完整源碼佃乘，已在Linux下測試通過：

#include #include//多謝citylove指正。//crytTable[]里面保存的是HashString函數(shù)里面將會用到的一些數(shù)據(jù)驹尼，在prepareCryptTable//函數(shù)里面初始化unsignedlongcryptTable[0x500];//以下的函數(shù)生成一個(gè)長度為0x500（合10進(jìn)制數(shù)：1280）的cryptTable[0x500]voidprepareCryptTable()

{

unsignedlongseed =0x00100001, index1 =0, index2 =0, i;for( index1 =0; index1 <0x100; index1++)

{for( index2 = index1, i =0; i <5; i++, index2 +=0x100)

{

unsignedlongtemp1, 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的類型啸箫，//在下面GetHashTablePos函數(shù)里面調(diào)用本函數(shù)提岔，其可以取的值為0、1、2故黑；該函數(shù)//返回lpszFileName 字符串的hash值骑科；unsignedlongHashString(char*lpszFileName, unsignedlongdwHashType )

{

unsignedchar*key? = (unsignedchar*)lpszFileName;

unsignedlongseed1 =0x7FED7FED;

unsignedlongseed2 =0xEEEEEEEE;intch;while( *key !=0)

{

ch= toupper(*key++);

seed1= cryptTable[(dwHashType <<8) + ch] ^ (seed1 +seed2);

seed2= ch + seed1 + seed2 + (seed2 <<5) +3;

}returnseed1;

}//在main中測試argv[1]的三個(gè)hash值：//./hash? "arr/units.dat"http://./hash? "unit/neutral/acritter.grp"intmain(intargc,char**argv )

{

unsignedlongulHashValue;inti =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 );return0;

}