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

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

分析：只取8

只取1

只取3、4

只取2、7、5

數(shù)字分布近乎隨機(jī)所以：取作為哈希地址數(shù)字分析法平方取中法求關(guān)鍵字的平方值，擴(kuò)大相近數(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)鍵字與存儲(chǔ)位置的關(guān)系為：h(key)=keymod11散列函數(shù)22113251527618412010除留余數(shù)法取關(guān)鍵字除以自然數(shù)n的余數(shù)作為散列地址散列表的沖突現(xiàn)象兩個(gè)不同的關(guān)鍵字，可能得到相同的散列函數(shù)值，從而被映射到表的同一位置上稱為沖突或碰撞發(fā)生沖突的若干個(gè)關(guān)鍵字稱為該散列函數(shù)的同義詞避免沖突選擇合適的散列函數(shù)關(guān)鍵字的個(gè)數(shù)小于或等于散列表的長度沖突處理沖突不可能完全避免若關(guān)鍵字的個(gè)數(shù)大于散列表的長度,則無論怎樣設(shè)計(jì)h，也不可能完全避免沖突設(shè)計(jì)散列函數(shù)時(shí)盡可能使沖突最少要確定解決沖突的方法，使發(fā)生沖突的同義詞能夠存儲(chǔ)到散列表中。散列表的沖突線性探測(cè)例：{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ā)生沖突，用線性探測(cè)法，h1=(2+1)%13，得到位置3此位置未填值，是開放的位置，則15存進(jìn)t[3]68與15發(fā)生沖突，原本不是同義詞的兩個(gè)關(guān)鍵字，爭奪同一個(gè)后繼散列地址，出現(xiàn)堆積用線性探測(cè)法，h1=(3+1)%13,則68存進(jìn)t[4];12與38沖突，用線性探測(cè)法，h1=(12+1)%13,此位置與26沖突繼續(xù)線性探測(cè)，h2=(12+2)%13,開放地址，則t[1]=12; ……沖突處理-開放地址法堆積現(xiàn)象散列地址不同的關(guān)鍵字，爭奪同一個(gè)后繼位置使得非同義詞也加入了探測(cè)序列，增加了探查的長度，即增加了查找時(shí)間若散列函數(shù)不好或裝填因子過大，會(huì)使堆積加劇裝填因子α=填入表中的元素個(gè)數(shù)/哈希表的長度沖突處理-開放地址法再平方探測(cè)按順序決定值時(shí)，如果某數(shù)據(jù)的值已經(jīng)存在，則在原來值的基礎(chǔ)上先加1的平方個(gè)單位，若仍然存在，則減1的平方個(gè)單位。隨之是2的平方，3的平方等等。直至不發(fā)生哈希沖突。偽隨機(jī)探測(cè)按順序決定值時(shí)，如果某數(shù)據(jù)已經(jīng)存在，通過隨機(jī)函數(shù)隨機(jī)生成一個(gè)數(shù)，在原來值的基礎(chǔ)上加上偽隨機(jī)數(shù)，直至不發(fā)生哈希沖突。沖突處理-開放地址法沖突處理-鏈地址法分配指針數(shù)組，建立m個(gè)空鏈表，由哈希函數(shù)對(duì)關(guān)鍵字轉(zhuǎn)換后，映射到同一哈希地址的同義詞均加入到相應(yīng)指向的鏈表中。又稱：拉鏈法優(yōu)點(diǎn)：鏈?zhǔn)降刂贩ㄌ幚頉_突簡單，且無堆積現(xiàn)象由于鏈?zhǔn)降刂贩ㄖ懈麈湵砩系墓?jié)點(diǎn)空間是動(dòng)態(tài)申請(qǐng)的，故它更適合于造表前無法確定表長的情況鏈?zhǔn)降刂贩ㄖ醒b填因子可以α≥1，空間利用率高在用鏈?zhǔn)降刂贩?gòu)造的散列表中，刪除節(jié)點(diǎn)的操作易于實(shí)現(xiàn)。只要簡單地刪去鏈表上相應(yīng)的節(jié)點(diǎn)即可。缺點(diǎn)：指針占用較大空間時(shí)，會(huì)造成空間浪費(fèi)。鏈地址法分析查找過程中，關(guān)鍵字的比較次數(shù)，取決于產(chǎn)生沖