第9章 查找 part4.ppt

1、第九章 查找,主講：戚玉濤,第九章 查找,9.1 查找的基本概念 9.2 靜態(tài)查找表基于線性表的查找法 9.3 動態(tài)查找表基于樹表的查找法 9.4 哈希表計算式查找法,哈希表,前面介紹的內(nèi)容中，記錄在文件中的存儲地址是隨機的，即記錄在表中的位置和它的關(guān)鍵字之間不存在一個確定的關(guān)系。,查找某一條記錄需要進行一系列的“比較”。,查找的效率依賴于比較的次數(shù)。,哈希表,用這類方法表示的查找表，其平均查找長度都不為零。不同的表示方法，其差別僅在于：關(guān)鍵字和給定值進行比較的順序不同。 對于頻繁使用的查找表，希望 ASL = 0。 只有一個辦法：預(yù)先知道所查關(guān)鍵字在表中的位置。即，要求：記錄在表中位置和其關(guān)

2、鍵字之間存在一種確定的關(guān)系。 此對應(yīng)關(guān)系稱為哈希函數(shù)?？梢酝ㄟ^哈希函數(shù)從關(guān)鍵字直接計算出記錄在表中位置。,哈希表的基本概念,哈希法的思想：在元素的關(guān)鍵字Key和元素的存儲位置p之間建立一個對應(yīng)關(guān)系H，使 p=H(Key)。哈希法又稱散列法、雜湊法或關(guān)鍵字地址計算法等。 哈希函數(shù)：H稱為哈希函數(shù)(散列函數(shù))，是一個壓縮映象，是從關(guān)鍵字空間到存儲地址空間的一種映象。 當查找關(guān)鍵字為k的元素時，利用哈希函數(shù)計算出該元素的存儲位置p=H(k)，從而達到按關(guān)鍵字直接存取元素的目的。,哈希表的基本概念,哈希地址： H(Key)也稱為哈希地址 或散列地址 哈希表：根據(jù)設(shè)定的哈希函數(shù) H(key) 和所選中的

3、處理沖突的方法，將一組關(guān)鍵字映象到一個有限的、地址連續(xù)的地址集 (區(qū)間) 上，并以關(guān)鍵字在地址集中的“象”作為相應(yīng)記錄在表中的存儲位置，如此構(gòu)造所得的查找表稱之為“哈希表”。,哈希表的例子：30個地區(qū)的各民族人口統(tǒng)計表,編號 地區(qū)別 總?cè)丝?漢族 回族.,1 北京,2 上海,.,.,以編號作關(guān)鍵字， 構(gòu)造哈希函數(shù)：H(key)=key H(1)=1 H(2)=2,以地區(qū)別作關(guān)鍵字，取地區(qū) 名稱第一個拼音字母的序號 作哈希函數(shù)：H(Beijing)=2 H(Shanghai)=19 H(Shenyang)=19,從例子可見：哈希函數(shù)只是一種映象，所以哈希函數(shù)的設(shè)定很靈活，只要使任何關(guān)鍵字的哈希函

4、數(shù)值都落在表長允許的范圍之內(nèi)即可。 當關(guān)鍵字集合很大時，關(guān)鍵字值不同的元素可能會映象到哈希表的同一地址上，即 k1k2，但 H(k1)=H(k2)，這種現(xiàn)象稱為“沖突”，此時稱k1和k2為“同義詞”。實際中，沖突是不可避免的， 只能通過改進哈希函數(shù)的性能來減少沖突。 綜上所述， 哈希法主要包括以下兩方面的內(nèi)容： (1)如何構(gòu)造哈希函數(shù)； (2)如何處理沖突。,哈希函數(shù)構(gòu)造方法,1、直接定址法 2、數(shù)字分析法 3、平方取中法 4、折疊法 5、除留余數(shù)法 6、偽隨機數(shù)法,哈希函數(shù)構(gòu)造方法,1、直接定址法 取關(guān)鍵字或關(guān)鍵字的某個線性函數(shù)值為哈希地址。直接定址法的哈希函數(shù)H(key)為： H(key)

5、 = key 或 H(key) = akey+b 計算簡單，并且不可能有沖突發(fā)生。當關(guān)鍵字的分布基本連續(xù)時，可用直接定址法的哈希函數(shù)；否則，若關(guān)鍵字分布不連續(xù)將造成內(nèi)存單元的大量浪費。,直接定址法的例子,(i) 例，以年齡作為關(guān)鍵字,(ii)例，統(tǒng)計解放后出生人口，以出生年份作為關(guān)鍵字,H(key) = key 1949 + 1,哈希函數(shù)構(gòu)造方法,2、數(shù)字分析法 假設(shè)關(guān)鍵字集合中的每個關(guān)鍵字都是由 s 位數(shù)字組成 (u1, u2, , us)； 分析關(guān)鍵字集中的全體， 并從中提取分布均勻的若干位或它們的組合作為地址 此法適于能預(yù)先估計出全體關(guān)鍵字的每一位上各種數(shù)字出現(xiàn)的頻度。,有80個記錄，關(guān)

6、鍵字為8位十進制數(shù)，哈希地址為2位十進制數(shù),分析：只取8 只取1 只取3、4 只取2、7、5 數(shù)字分布近乎隨機 所以：取任意兩位或兩位 與另兩位的疊加作哈希地址,數(shù)字分析法的例子,哈希函數(shù)構(gòu)造方法,3、平方取中法 當無法確定關(guān)鍵字中哪幾位分布較均勻時，取關(guān)鍵字平方后的中間幾位作為哈希函數(shù)。 實驗證明: 一個數(shù)字的平方值的中間部分通常對各位數(shù)字都比較敏感。故不同關(guān)鍵字會以較高的概率產(chǎn)生不同的哈希地址。,平方取中法的例子,哈希函數(shù)構(gòu)造方法,4、折疊法 將關(guān)鍵字分割成位數(shù)相同的幾部分，然后取這幾部分的疊加和作為哈希函數(shù)。 兩種疊加處理的方法： 移位疊加：將分割后的幾部分低位對齊相加 折疊疊加：從一端

7、沿分割界來回折送，然后對齊相加。此法適于關(guān)鍵字的數(shù)字位數(shù)特別多的情況。,折疊法的例子,Key = 12360324711220,(a) 移位疊加,(b) 折疊疊加,哈希函數(shù)構(gòu)造方法,5、除留余數(shù)法 設(shè)定哈希函數(shù)為: H(key) = key MOD p ( pm ) 其中：m為表長 p 為不大于 m 的素數(shù) 或是不含 20 以下的質(zhì)因子,哈希函數(shù)構(gòu)造方法,除留余數(shù)法為什么要對 p 加限制？ 例如： 給定一組關(guān)鍵字為: 12, 39, 18, 24, 33, 21， 若取 p=9, 則他們對應(yīng)的哈希函數(shù)值將為: 3, 3, 0, 6, 6, 3 可見，若 p 中含質(zhì)因子 3，則所有含質(zhì)因子 3

8、的關(guān)鍵字均映射到“3 的倍數(shù)”的地址上，從而增加了“沖突”的可能。,假設(shè)哈希表長為m， p為小于等于m的最大素數(shù)， 則哈希函數(shù)為：H(key) = key % p,已知待散列元素為18, 75, 60, 43, 54, 90, 46, m=p=13, 則有: H(18)=18 % 13=5 H(75)=75 % 13=10 H(60)=60 % 13=8 H(43)=43 % 13=4 H(54)=54 % 13=2 H(90)=90 % 13=12 H(46)=46 % 13=7,0 1 2 3 4 5 6 7 8 9 10 11 12,裝填因子(Load Factor): = n / m.

9、 n: 表中關(guān)鍵字數(shù)； m: 表長。,除留余數(shù)法的例子,哈希函數(shù)構(gòu)造方法,6、偽隨機數(shù)法 采用一個偽隨機函數(shù)作哈希函數(shù)，即： H(key) = random(key) 適于關(guān)鍵字長度不等的情況,哈希函數(shù)的選擇,選取哈希函數(shù)考慮以下因素： 計算哈希函數(shù)所需時間 關(guān)鍵字長度 哈希表長度（哈希地址范圍） 關(guān)鍵字分布情況，即沖突越少越好 記錄的查找頻率,哈希表處理沖突的方法,對于不同的關(guān)鍵字可能得到同一哈希地址，即 key1 key2 ，而 H(key1) H(key2) ，這種現(xiàn)象稱為哈希沖突。 造成沖突的原因: 1、主觀設(shè)計不當,例，數(shù)字分析法中,沖突！,例，除留余數(shù)法中,關(guān)鍵字 28 35 63

10、 77 105,p = 21,哈希地址,7,14,0,14,0,沖突！,哈希表處理沖突的方法,造成沖突的原因: 2、客觀存在 如何設(shè)計都不可能完全避免沖突的出現(xiàn)？ 哈希地址是有限的，而記錄是無限的。 沖突解決方法: (1) 開放定址法 (2) 再哈希法 (3)建立一個公共溢出區(qū) (4)鏈地址法,哈希表處理沖突的方法,(1)開放定址法 為產(chǎn)生沖突的地址 H(key) 求得一個地址序列： H0, H1, H2, , Hs 1sm-1,di: 稱為增量序列 線性探測再散列：di = 1, 2, 3, , m-1 二次探測再散列：di = 12, -12, 22, -22, , k2, -k2 (km

11、/2) 隨機探測再散列：di = 偽隨機數(shù)序列,線性探測法 di = 1 , 2 , 3 , , m-1,隨機探測法 di = 隨機數(shù),例，關(guān)鍵字為 ( 17 , 60 , 29 , 38 ) ，哈希表長 11 ，H(key)=key%11,初始，,17,60,29,線性探測法,38,二次探測法,38,隨機探測法,不妨設(shè)第一次隨機數(shù)為 9,38,練習：關(guān)鍵字序列26, 36, 41, 38, 44, 15, 68, 12, 6, 51, 25，除留余數(shù)法構(gòu)造哈希函數(shù)，線性探測再散列處理沖突，= 0.75。,m = n / = 15, p = 13, H(key) = key%13.,H(26)

12、 = 0; H(36) = 10; H(41) = 2; H(38) = 12; H(44) = 5; H(15) = 2, (2+1)%15 = 3; H(68) = 3, (3+1)%15 = 4; H(12) = 12, (12+1)%15 = 13; H(6) = 6; H(51) = 12, (12+1)%15 = 13, (12+2)%15 = 14; H(25) = 12, (12+1)%15 = 13, (12+2)%15 = 14, (12+3)%15 = 0, (12+4)%15 = 1.,非同義詞的沖突：“二次聚集”或“堆積”,哈希表處理沖突的方法,(2) 再哈希法 同時

13、構(gòu)造多個不同的哈希函數(shù)： Hi=RHi( key )， i=1, 2, , k 當哈希地址發(fā)生沖突時，再計算另一個哈希函數(shù)地址，直到?jīng)_突不再產(chǎn)生。 這種方法不易產(chǎn)生聚集，但增加了計算時間。 (3) 建立一個公共溢出區(qū) 將哈希表分為基本表和溢出表兩部分，凡是與基本表發(fā)生沖突的元素一律填入溢出表。,哈希表處理沖突的方法,(4) 鏈地址法 將所有哈希地址為i的元素構(gòu)成一個稱為同義詞鏈的單鏈表，并將單鏈表的頭指針存在哈希表的第i個單元中。,鏈地址法,H(26) = 0; H(36) = 10; H(41) = 2; H(38) = 12; H(44) = 5; H(15) = 2; H(68) = 3

14、; H(12) = 12; H(6) = 6; H(51) = 12; H(25) = 12.,H(key) = key%13,哈希表的查找,哈希表的查找過程： 對于給定值 K, 計算哈希地址 i = H(K) 若 ri = NULL, 則查找不成功 若 ri.key = K, 則查找成功 否則 “求下一地址 Hi” ， 直至rHi = NULL (查找不成功) 或rHi.key = K (查找成功) 為止。,哈希表的查找,哈希查找分析: 哈希查找過程仍是一個給定值與關(guān)鍵字進行比較的過程 評價哈希查找效率仍要用ASL 哈希查找過程與給定值進行比較的關(guān)鍵字的個數(shù)取決于： 哈希函數(shù) 處理沖突的方法 哈希表的裝填因子=表中填入的記錄數(shù)/哈希表長度,哈希表的查找,哈希表的裝填因子 表明了表中的裝滿程度。 越大，說明表越滿，再插入新元素時發(fā)生沖突的可能性就越大。 哈希的查找性能，即平均查找長度依賴于哈希表的裝填因子，不直接依賴于 n 或 m。 不論表的長度有多大，總能選擇一