哈希的基本概念

1、6、8哈希表及其查找* 34哈希譯自“ ha s h 一詞，也稱為散列或雜湊。？哈希表查找得基本思想就是:根據(jù)當前待查找數(shù)據(jù)得特征 ,以記錄關鍵字為自變量 ,設計一個哈希函數(shù) ,依該 函數(shù)按關鍵碼計算元素得存儲位置 ,并按此存放 ;查找時 ,由同一個函數(shù)對給定值 ke y計算地址，將kc y與地址單元中元素關鍵碼進行比較，確定查找就是否成 功。哈希方法中使用得轉(zhuǎn)換函數(shù)稱為哈希函數(shù) (雜湊函數(shù) ),按這個思想構(gòu)造得表稱 為哈希表 (雜湊表 )。 ? 對于 n 個數(shù)據(jù)元素得集合 ,總能找到關鍵碼與存放地址一 一對應得函數(shù)、若最大關鍵為 m, 可以分配 m 個數(shù)據(jù)元素存放單元 ,選取函數(shù) f(ke

2、y )= k ey即可,但這樣會造成存儲空間得很大浪費，甚至不可能分配這么大得存 儲空間、通常關鍵碼得集合比哈希地址集合大得多 ,因而經(jīng)過哈希函數(shù)變換后 ,可 能將不同得關鍵碼映射到同一個哈希地址上，這種現(xiàn)象稱為沖突(C o l li sion )。映射到同一哈希地址上得關鍵碼稱為同義詞?？梢哉f ，沖突不可能避免，只能 盡可能減少。所以 ,哈希方法需要解決以下兩個問題 :?(1)構(gòu)造好得哈希函數(shù) ? 所選函數(shù)盡可能簡單 ,以便提高轉(zhuǎn)換速度。 ? 所選函數(shù)對關鍵碼計算出得地址 ,應在哈希地址集中大致均勻分布 ,以減少空間浪費。(2)制定解決沖突得方案1.常用得哈希函數(shù)(1)直接定址法即取關鍵碼得

3、某個線性函數(shù)值為哈希地址 ,這類函數(shù)就是一一對應函數(shù) ,不會產(chǎn)生沖突 ,但要求地址集合與關鍵碼集合大小相同,因此 ,對于較大得關鍵碼集合不適用。如關鍵碼集合為 100,300,500,7 0 0,8 0 0,900 ，選取哈希函數(shù)為H a sh(key)= k ey/100,則存放如表6-3所示。表63直接定址法構(gòu)造哈希表地址0123456789關鍵碼8 00900(2 )除留余數(shù)法即取關鍵碼除以p得余數(shù)作為哈希地址。使用除留余數(shù)法，選取合適得p很 重要，若哈希表表長為m,則要求p m,且接近m或等于m。p 一般選取質(zhì)數(shù)，也可 以就是不包含小于20質(zhì)因子得合數(shù)、？(3)數(shù)字分析法設關鍵碼集合中

4、，每個關鍵碼均由m位組成，每位上可能有r種不同得符號、? 數(shù)字分析法根據(jù)種不同得符號及在各位上得分布情況，選取某幾位，組合成哈希 地址。所選得位應就是各種符號在該位上出現(xiàn)得頻率大致相同。(4)平方取中法？對關鍵碼平方后，按哈希表大小，取中間得若干位作為哈希地址。?(5)折疊法(F o Id in g )?此方法將關鍵碼自左到右分成位數(shù)相等得幾部分，最后一部分位數(shù)可以短些，然后將這幾部分疊加求與，并按哈希表表長，取 后幾位作為哈希地址。這種方法稱為折疊法。？有兩種疊加方法:? 移位法-將各部分得最后一位對齊相加。 間界疊加法一-從一端向另一端沿各部分分界來回折疊后 ，最后一位對齊 相加。？ 如對

5、關鍵碼為key=25 3 46358705,設哈希表長為3位數(shù)，則可對關 鍵碼每3位一部分來分割。關鍵碼分割為如下 4組：253 4 6 3 5 8 7 05 分別 用上述方法計算哈希地址如圖612所示、對于位數(shù)很多得關鍵碼，且每一位上符 號分布較均勻時，可采用此方法求得哈希地址。2。處理沖突得方法？(1)開放定址法所謂開放定址法，即由關鍵碼得到得哈希地址一旦產(chǎn)生了沖突，也就就是說，該 地址已經(jīng)存放了數(shù)據(jù)元素。我們需要尋找下一個空得哈希地址，只要哈希表足夠大，空得哈希地址總能找到，并將數(shù)據(jù)元素存入。常用得找空哈希地址方法有下列 三種、？線性探測法其中,Has h (k ey )為哈希函數(shù),m為

6、哈希表長度,為增量序列1, 2，,m- 1，且=i o設關鍵碼集為 4 7 ,7 ,29,1 1 ,16,92,22,8,3，哈希表表長為 11,H a sh( k ey)=key m od 11,用線性探測法處理沖突，構(gòu)造哈希表如表6-4所示。表6 4哈希表011224 79 21 637298 47 ,7, 1 1,1 6 ,92均就是由哈希函數(shù)得到得沒有沖突得哈希地址，因而就是直接存入得。？H ash(29)=7，哈希地址上沖突，需尋找下一個空得哈希地址：另外,22,8同樣在哈希地址上有沖突，也就是由找到空得哈希地址得；而Hash(3)= 3，哈希地址上沖突，因為：線性探測法可能使第i個

7、哈希地址得同義詞存入第i+1個哈希地址，這樣本應 存入第i+ 1個哈希地址得元素變成了第i+2個哈希地址得同義詞因此，可能 出現(xiàn)很多元素在相鄰得哈希地址上“堆積”起來 ，大大降低了查找效率。為此， 可采用二次探測法，或再哈希函數(shù)探測法，以改善“堆積”問題。？二次探測法其中,Hash(key)為哈希函數(shù),m為哈希表長度，為增量序列12 ,12,22,22 ,q 2 , q 2 且仍對前面例子得關鍵碼序列 47 , 7 ,29,11,1 6 ,92,22, 8 ,3,用二次探測法 處理沖突，構(gòu)造哈希表如表6 5所示。表6-5二次探測法構(gòu)造哈希表0112234 792167298 與關鍵碼尋找空得哈

8、希地址只有 3這個關鍵碼不同,Has h ( 3 )= 3，哈希地址上沖突，由H 2= (Hash( 3 )+ 1 2 )%1 1 =2,找到空得哈希地址，存入、？ 再哈希法其中,Ha sh (ke y), R eH ash (key)就是兩個哈希函數(shù)，m%哈希表長度。? 再哈希法，先用第一個函數(shù)Hash(key)對關鍵碼計算哈希地址，一旦產(chǎn)生地址沖突, 再用第二個函數(shù) ReHa s h(key)確定移動得步長因子，最后,通過步長因子序列由 探測函數(shù)尋找空得哈希地址、？ 比如,Has h (key) = a時產(chǎn)生地址沖突，就計算 R eHash( k ey) = b,則探測得地址序列為:(2)

9、鏈地址法又稱拉鏈法，設哈希函數(shù)得到得哈希地址域在區(qū)間0 ,m 1上,以每個哈希地 址作為一個指針，指向一個鏈，即分配指針數(shù)組:? E l em Type衣e pt r m ;建立m個空鏈表,由哈希函數(shù)對關鍵碼轉(zhuǎn)換后，映射到同一哈希地址1得同 義詞均加入* ep t ri指向得鏈表中。？對關鍵碼序列為 4 7,7,29,11,16,9 2 ,2 2,8, 3 ,5 0, 3 7,89,94,21，哈希函數(shù)為 H a sh(key)=ke y mod 1 1，用拉鏈法處理沖突，建表如圖6 13所示。(3)建立一個公共溢出區(qū)？則分配兩個表：一個基本表E l e mType一個溢出表El e mTyp

10、 e01510團花門縫地址袪構(gòu)造噲希恚設哈希函數(shù)產(chǎn)生得哈希地址集為0,m 1,b as e _tbl m;每個單元只能存放一個元素。ove r _ tbl k ;只要關鍵碼對應得哈希地址在基本表上產(chǎn)生沖突，則所有這樣得元素一律存入該表中。查找時，對給定值k x通過哈希函數(shù)計算出哈希地址i,先與基本表得base_tbl i單元比較，若相等，查找成功;否則，再到溢出表中進行查找。3 .哈希表得查找分析哈希表得查找過程基本上與造表過程相同。 一些關鍵碼可通過哈希函數(shù)轉(zhuǎn)換得地址直接找到，另一些關鍵碼在哈希函數(shù)得到得地址上產(chǎn)生了沖突，需要按處理沖突得方法進行查找。在介紹得三種處理沖突得方法中，產(chǎn)生沖突后

11、得查找仍然就是給定值與關鍵碼進行比較得過程。所以，對哈希表查找效率得量度，依然用平均查找長度來衡量。查找過程中，關鍵碼得比較次數(shù)取決于產(chǎn)生沖突得多少。如果產(chǎn)生得沖突少，查找效率就高，如果產(chǎn)生得沖突多，查找效率就低、因此，影響產(chǎn)生沖突多少得因素也就就是影響查找效率得因素。影響產(chǎn)生沖突多少有以下三個因素 哈希函數(shù)就是否均勻； 處理沖突得方法;? 哈希表得裝填因子。分析這三個因素，盡管哈希函數(shù)得“好壞”直接影響沖突產(chǎn)生得頻度 ，但一般 情況下，我們總認為所選得哈希函數(shù)就是“均勻得”。因此，可不考慮哈希函數(shù)對 平均查找長度得影響。就是哈希表裝滿程度得標志因子。由于表長就是定值 ,a與“填入表中得元 素個數(shù)”成正比，所以,a越大,填入表中得元素較多，產(chǎn)生沖突得可能性就越大；a 越小,填入表中得元素較少，產(chǎn)生沖突得可能性就越小。實際上，哈