從頭到尾徹底解析哈希表算法
說明:本文分為三部分內(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ù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)。也就是說,它通過把關(guān)鍵碼值映射到表中一個(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(NlgN)。
排完序之后我們再對已經(jīng)有序的Query文件進(jìn)行遍歷,統(tǒng)計(jì)每個(gè)Query出現(xiàn)的次數(shù),再次寫入文件中。
綜合分析一下,排序的時(shí)間復(fù)雜度是O(NlgN),而遍歷的時(shí)間復(fù)雜度是O(N),因此該算法的總體時(shí)間復(fù)雜度就是O(N+NlgN)=O(NlgN)。
2、Hash Table法
在第1個(gè)方法中,我們采用了排序的辦法來統(tǒng)計(jì)每個(gè)Query出現(xiàn)的次數(shù),時(shí)間復(fù)雜度是NlgN,那么能不能有更好的方法來存儲,而時(shí)間復(fù)雜度更低呢?
題目中說明了,雖然有一千萬個(gè)Query,但是由于重復(fù)度比較高,因此事實(shí)上只有300萬的Query,每個(gè)Query255Byte,因此我們可 以考慮把他們都放進(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ù)雜度是NlgN,在本題目中,三百萬條記錄,用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萬)。如果各位有什么更好的算法,歡迎留言評論。第一部分,完。
#p#
第二部分: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ì)。
#p#
第三部分、最快的Hash表算法
接下來,咱們來具體分析一下一個(gè)最快的Hasb表算法。
我們由一個(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è)長度為0×500(合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ù)二、以下函數(shù)計(jì)算lpszFileName 字符串的hash值,其中dwHashType 為hash的類型,在下面的函數(shù)三、GetHashTablePos函數(shù)中調(diào)用此函數(shù)二,其可以取的值為0、1、2;該函數(shù)返回lpszFileName 字符串的hash值:
- unsigned long <strong>HashString</strong>( 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è)算法是非常高效的,被稱為”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è)算法吧:
- typedef struct
- {
- int nHashA;
- int nHashB;
- char bExists;
- ……
- } SOMESTRUCTRUE;
一種可能的結(jié)構(gòu)體定義?
函數(shù)三、下述函數(shù)為在Hash表中查找是否存在目標(biāo)字符串,有則返回要查找字符串的Hash值,無則,return -1.
- int <strong>GetHashTablePos</strong>( har *lpszString, SOMESTRUCTURE *lpTable )
- //lpszString要在Hash表中查找的字符串,lpTable為存儲字符串Hash值的Hash表。
- {
- int nHash = HashString(lpszString); //調(diào)用上述函數(shù)二,返回要查找字符串lpszString的Hash值。
- int nHashPos = nHash % nTableSize;
- if ( lpTable[nHashPos].bExists && !strcmp( lpTable[nHashPos].pString, lpszString ) )
- { //如果找到的Hash值在表中存在,且要查找的字符串與表中對應(yīng)位置的字符串相同,
- return nHashPos; //則返回上述調(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)該都是足夠小的?,F(xiàn)在再回到數(shù)據(jù)結(jié)構(gòu)上,Blizzard使用的哈希表沒有使用鏈表,而采用”順延”的方式來解決問題,看看這個(gè)算 法:
#p#
函數(shù)四、lpszString 為要在hash表中查找的字符串;lpTable 為存儲字符串hash值的hash表;nTableSize 為hash表的長度:
- int <strong>GetHashTablePos</strong>( 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值就可以了,不用對
- *結(jié)構(gòu)體中的字符串進(jìn)行比較。這樣會加快運(yùn)行的速度?減少hash表占用的空間?這種
- *方法一般應(yī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è)用來確定位置,另外兩個(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值分布比較均勻*/
- unsigned long getHashIndex( const char *key, int nTableLength )
- {
- unsigned long nHash = 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 <stdio.h>
- #include <ctype.h> //多謝citylove指正。
- //crytTable[]里面保存的是HashString函數(shù)里面將會用到的一些數(shù)據(jù),在prepareCryptTable
- //函數(shù)里面初始化
- unsigned long cryptTable[0x500];
- //以下的函數(shù)生成一個(gè)長度為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的類型,
- //在下面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中測試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;
- }
原文鏈接:http://blog.csdn.net/v_JULY_v/article/details/6256463譯文鏈接: