數(shù)據(jù)結(jié)構(gòu)（Python Java）（微課版） 課件 8.4 散列查找

數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計散列查找散列函數(shù)沖突處理8.4散列表查找查找性能分析概念的引入二分法，順序查找，二叉排序樹都以關(guān)鍵字的比較作為查找的基礎(chǔ)如果建立關(guān)鍵字與存儲地址的映射關(guān)系，則已知關(guān)鍵字時，可以直接定位到相應(yīng)的存儲位置上，從而達到查找的目的理想情況下，無須任何比較就可以找到待查關(guān)鍵字，查找的期望時間為O(1)散列查找以節(jié)點的關(guān)鍵字K為自變量，通過一個確定的函數(shù)關(guān)系h，計算出函數(shù)值h(K)這個值可理解為節(jié)點的存儲地址，將節(jié)點存入h(K)所指的存儲位置上查找時，根據(jù)關(guān)鍵字，用函數(shù)h(K)計算出地址，再到相應(yīng)的單元里去取出節(jié)點函數(shù)h稱為散列函數(shù)，h(K)稱為散列地址散列方法存儲的線性表稱為散列表(HashTable)，也稱為哈希表散列查找直接定址法取關(guān)鍵字或關(guān)鍵字的某個線性函數(shù)值為散列地址，即H(key)=key或H(key)=a×key+b，其中a和b為常數(shù)散列函數(shù)有如下序列的關(guān)鍵字集合{1000，2000，5000，7000，8000，10000}，選取散列函數(shù)為H(key)=key/1000有幾十個記錄，關(guān)鍵字為8位十進制數(shù)，哈希地址為4位十進制數(shù)散列函數(shù)8134653281372242813874228130136781322817813389678136853781419355…..…..

分析：只取8

只取1

只取3、4

只取2、7、5

數(shù)字分布近乎隨機所以：取作為哈希地址數(shù)字分析法平方取中法求關(guān)鍵字的平方值，擴大相近數(shù)的差別根據(jù)表長度取中間的幾位數(shù)作為散列函數(shù)值散列函數(shù)平方后得到：{0010000，0012100，1020100，1002001，0012321}根據(jù)表長度，取中間三位數(shù)作為散列地址：{100，121，201，020，123}數(shù)據(jù)集{0100,0010,1010,1001,0111}，散列表長度為1000關(guān)鍵字為：0442205864，哈希地址位數(shù)為4散列函數(shù)586442200410088H(key)=0088移位疊加5864022404

6092H(key)=6092折疊疊加折疊法將關(guān)鍵字分成位數(shù)相同的幾部分，然后取這幾部分的疊加和作為散列地址。數(shù)據(jù)集合{18,27,1,20,22,6,10,13,41,15,25}，建立關(guān)鍵字與存儲位置的關(guān)系為：h(key)=keymod11散列函數(shù)22113251527618412010除留余數(shù)法取關(guān)鍵字除以自然數(shù)n的余數(shù)作為散列地址散列表的沖突現(xiàn)象兩個不同的關(guān)鍵字，可能得到相同的散列函數(shù)值，從而被映射到表的同一位置上稱為沖突或碰撞發(fā)生沖突的若干個關(guān)鍵字稱為該散列函數(shù)的同義詞避免沖突選擇合適的散列函數(shù)關(guān)鍵字的個數(shù)小于或等于散列表的長度沖突處理沖突不可能完全避免若關(guān)鍵字的個數(shù)大于散列表的長度,則無論怎樣設(shè)計h，也不可能完全避免沖突設(shè)計散列函數(shù)時盡可能使沖突最少要確定解決沖突的方法，使發(fā)生沖突的同義詞能夠存儲到散列表中。散列表的沖突線性探測例：{26，36，41，38，44，15，68，12，06，51}

構(gòu)造哈希表t[0..12],哈希函數(shù)：h(key)=key%13余數(shù)分別為：{0，10，2，12，5，2，3，12，6，12}(26，36，41，38，44)沒有沖突15發(fā)生沖突，用線性探測法，h1=(2+1)%13，得到位置3此位置未填值，是開放的位置，則15存進t[3]68與15發(fā)生沖突，原本不是同義詞的兩個關(guān)鍵字，爭奪同一個后繼散列地址，出現(xiàn)堆積用線性探測法，h1=(3+1)%13,則68存進t[4];12與38沖突，用線性探測法，h1=(12+1)%13,此位置與26沖突繼續(xù)線性探測，h2=(12+2)%13,開放地址，則t[1]=12; ……沖突處理-開放地址法堆積現(xiàn)象散列地址不同的關(guān)鍵字，爭奪同一個后繼位置使得非同義詞也加入了探測序列，增加了探查的長度，即增加了查找時間若散列函數(shù)不好或裝填因子過大，會使堆積加劇裝填因子α=填入表中的元素個數(shù)/哈希表的長度沖突處理-開放地址法再平方探測按順序決定值時，如果某數(shù)據(jù)的值已經(jīng)存在，則在原來值的基礎(chǔ)上先加1的平方個單位，若仍然存在，則減1的平方個單位。隨之是2的平方，3的平方等等。直至不發(fā)生哈希沖突。偽隨機探測按順序決定值時，如果某數(shù)據(jù)已經(jīng)存在，通過隨機函數(shù)隨機生成一個數(shù)，在原來值的基礎(chǔ)上加上偽隨機數(shù)，直至不發(fā)生哈希沖突。沖突處理-開放地址法沖突處理-鏈地址法分配指針數(shù)組，建立m個空鏈表，由哈希函數(shù)對關(guān)鍵字轉(zhuǎn)換后，映射到同一哈希地址的同義詞均加入到相應(yīng)指向的鏈表中。又稱：拉鏈法優(yōu)點：鏈式地址法處理沖突簡單，且無堆積現(xiàn)象由于鏈式地址法中各鏈表上的節(jié)點空間是動態(tài)申請的，故它更適合于造表前無法確定表長的情況鏈式地址法中裝填因子可以α≥1，空間利用率高在用鏈式地址法構(gòu)造的散列表中，刪除節(jié)點的操作易于實現(xiàn)。只要簡單地刪去鏈表上相應(yīng)的節(jié)點即可。缺點：指針占用較大空間時，會造成空間浪費。鏈地址法分析查找過程中，關(guān)鍵字的比較次數(shù)，取決于產(chǎn)生沖