數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)(第二版) 第7章 查找

第7章查找教學(xué)要求相關(guān)知識(shí)點(diǎn)順序查找、折半查找算法二叉排序樹(shù)的插入和查找算法哈希表、哈希函數(shù)、哈希地址、裝填因子哈希函數(shù)的選取原則及產(chǎn)生沖突的原因采用開(kāi)放地址法和鏈地址法解決沖突時(shí)，哈希表的建表方法、查找過(guò)程學(xué)習(xí)重點(diǎn)掌握順序查找、折半查找、二叉排序樹(shù)查找以及哈希表查找的基本思想和算法實(shí)現(xiàn)。目錄靜態(tài)查找算法動(dòng)態(tài)查找表

哈希表3查找的基本概念

124本章小結(jié)57.1查找的基本概念7.1查找的基本概念查找的基本概念1.關(guān)鍵字（key）關(guān)鍵字(Key)是數(shù)據(jù)元素中唯一標(biāo)識(shí)該元素的某個(gè)數(shù)據(jù)項(xiàng)的值，使用基于關(guān)鍵字的查找，查找結(jié)果應(yīng)該是唯一的。比如由一個(gè)學(xué)生元素構(gòu)成的數(shù)據(jù)集合，則學(xué)生元素中“學(xué)號(hào)”這一數(shù)據(jù)項(xiàng)的值唯一地標(biāo)識(shí)一個(gè)學(xué)生。2.查找根據(jù)給定的某個(gè)值，在數(shù)據(jù)集合中尋找一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素。結(jié)果分兩種情況：（1）查找成功：數(shù)據(jù)集合中存在相應(yīng)的數(shù)據(jù)元素；（2）查找不成功：數(shù)據(jù)集合中不存在關(guān)鍵字等于給定值的數(shù)據(jù)元素。7.1查找的基本概念查找的基本概念3.查找表（searchtable）

由同一數(shù)據(jù)類型的數(shù)據(jù)元素構(gòu)成的數(shù)據(jù)集合，可以是一個(gè)數(shù)組或一個(gè)鏈表等數(shù)據(jù)類型。

(1)靜態(tài)查找表(StaticSearchTable)如果一個(gè)查找表的操作只涉及查詢某個(gè)特定的數(shù)據(jù)元素是否在查找表中或者檢索滿足條件的某個(gè)特定的數(shù)據(jù)元素的各屬性值，無(wú)須修改查找表，這類查找表稱為靜態(tài)查找表。靜態(tài)查找表適用于：查找表一經(jīng)生成，便只對(duì)其進(jìn)行查找，而不進(jìn)行插入和刪除操作，或經(jīng)過(guò)一段時(shí)間的查找之后，集中地進(jìn)行插入和刪除等修改操作。7.1查找的基本概念查找的基本概念3.查找表（searchtable）

由同一數(shù)據(jù)類型的數(shù)據(jù)元素構(gòu)成的數(shù)據(jù)集合，可以是一個(gè)數(shù)組或一個(gè)鏈表等數(shù)據(jù)類型。

(2)動(dòng)態(tài)查找表(DynamicSearchTable)如果對(duì)一個(gè)查找表的操作在查找的同時(shí)需要?jiǎng)討B(tài)地插入或刪除的查找表則稱為動(dòng)態(tài)查找表。動(dòng)態(tài)查找表適用于：查找與插入或刪除操作在同一個(gè)階段進(jìn)行，例如，在某些問(wèn)題中，當(dāng)查找成功時(shí)，要?jiǎng)h除查找的記錄，當(dāng)查找不成功時(shí)，要插入被查找的記錄。7.1查找的基本概念查找的基本概念4.查找算法的時(shí)間復(fù)雜度對(duì)于不同的數(shù)據(jù)結(jié)構(gòu)，有不同的查找方法，也有不同的查找效率。而在查找中，要衡量一種查找算法的優(yōu)劣，主要是看要查找的值與關(guān)鍵字的比較次數(shù)。因此，通常把查找過(guò)程中對(duì)關(guān)鍵字的最多比較次數(shù)和平均比較次數(shù)作為衡量一個(gè)查找算法效率優(yōu)劣兩個(gè)基本技術(shù)指標(biāo)。前者叫做最大查找長(zhǎng)度（MaximunSearchLength），簡(jiǎn)記為MSL。后者叫做平均查找長(zhǎng)度（AverageSearchLength），簡(jiǎn)記ASL，其計(jì)算公式定義為：

ASL=7.1查找的基本概念查找的基本概念5.查找結(jié)構(gòu)各種數(shù)據(jù)結(jié)構(gòu)都會(huì)涉及查找操作，如前面介紹的線性表、隊(duì)列、棧、樹(shù)與圖等。在某些應(yīng)用中，查找操作是最主要的操作，為提高查找效率，需要專門為查找操作設(shè)置數(shù)據(jù)結(jié)構(gòu)，這種面向查找操作的數(shù)據(jù)結(jié)構(gòu)成為查找結(jié)構(gòu)(SearchStructure)。本章討論的查找結(jié)構(gòu)有：靜態(tài)查找表、動(dòng)態(tài)查找表和哈希表。7.2靜態(tài)查找算法7.2靜態(tài)查找算法靜態(tài)查找算法通常采用順序查找和折半查找。順序查找順序查找(SequnceSearch)又稱線性查找(LinearSearch)，主要用于在線性表中進(jìn)行查找。順序查找通常分為無(wú)序表的順序查找和有序順序表的順序查找。7.2靜態(tài)查找算法順序查找1.無(wú)序表的順序查找（1）基本思想從線性表的一端開(kāi)始，逐個(gè)檢查關(guān)鍵字是否滿足給定的條件。若查到某個(gè)元素的關(guān)鍵字滿足給定條件，則查找成功，返回該元素在線性表中的位置；若已經(jīng)查到表的另一端，還沒(méi)有找到符合給定條件的元素，則返回查找失敗的信息。為了提高查找速度，可在算法中設(shè)置“哨兵”。哨兵就是待檢查值，將它放在查找方向的“盡頭”處，這免去了在查找過(guò)程中每一次比較完之后都要判斷查找位置是否越界，從而節(jié)省了時(shí)間。7.2靜態(tài)查找算法順序查找1.無(wú)序表的順序查找(2)靜態(tài)查找表的順序存儲(chǔ)結(jié)構(gòu)#defineMAXSIZE100typedefintkeyType;typedefstruct{keyTypekey; /*關(guān)鍵字域*/}SElemType;typedefstruct{SElemType*elem;//數(shù)據(jù)元素存儲(chǔ)空間基址

intlength; /*表長(zhǎng)度*/}SeqTable;7.2靜態(tài)查找算法順序查找1.無(wú)序表的順序查找(3)順序查找算法intSearch_Seq(SSTableST,ElemTypekey)

/*在順序表ST中順序查找關(guān)鍵字等于key的數(shù)據(jù)元素。若找到，則返回該元素在表中的位置；否則返回-1*/{

ST.elem[ST.TableLen]=key;/*"哨兵"*/

for(i=0;ST.elem[i].key!=key;++i);

/*從前往后找*/

if(i<ST.TableLen)returni;

elsereturn-1;/*未找到，返回-1*/}7.2靜態(tài)查找算法順序查找1.無(wú)序表的順序查找對(duì)于有n個(gè)元素的表，給定值key與表中第i個(gè)元素的關(guān)鍵字相等，即定位第i個(gè)元素時(shí)，需要進(jìn)行n-i+1次關(guān)鍵字的比較，即Ci=n-i+1，等概率Pi=1/n。查找成功時(shí)，平均長(zhǎng)度為：ASL成功=查找不成功時(shí)，與表中各關(guān)鍵字的比較次數(shù)顯然是n+1次，從而順序查找不成功的平均查找長(zhǎng)度為ASL失敗=n+1。平均查找長(zhǎng)度為：ASL平均

=(ASL成功+ASL失敗)/2=(n+1)*3/47.2靜態(tài)查找算法順序查找1.無(wú)序表的順序查找缺點(diǎn)：順序查找的缺點(diǎn)是當(dāng)元素個(gè)數(shù)較大時(shí)，平均查找長(zhǎng)度較大，效率低，它的時(shí)間復(fù)雜度為O(n)。優(yōu)點(diǎn)：對(duì)數(shù)據(jù)元素的存儲(chǔ)沒(méi)有要求，順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)皆可。對(duì)表中數(shù)據(jù)元素關(guān)鍵字的大小有序也沒(méi)有要求，無(wú)論數(shù)據(jù)元素是否按關(guān)鍵字有序均可應(yīng)用。同時(shí)還需要注意，對(duì)線性鏈表只能進(jìn)行順序查找。7.2靜態(tài)查找算法順序查找2.有序順序表的順序查找如果在查找之前已知表是按關(guān)鍵字排序的，那么當(dāng)查找失敗時(shí)可以不必再比較到表的另一端就能返回查找失敗的信息，這樣能降低順序查找失敗的平均查找長(zhǎng)度。若表L是按關(guān)鍵字從小到大排列的，查找的順序是從前往后，待查找元素的關(guān)鍵字為key，當(dāng)查找到第i個(gè)元素時(shí)，發(fā)現(xiàn)第i個(gè)元素對(duì)應(yīng)的關(guān)鍵字小于key，但第i+1個(gè)元素對(duì)應(yīng)的關(guān)鍵字大于key，這時(shí)就可以返回查找失敗的信息了，因?yàn)榈趇個(gè)元素之后的元素的關(guān)鍵字均大于key，所以表中不存在關(guān)鍵字為key的元素。7.2靜態(tài)查找算法順序查找7.2靜態(tài)查找算法順序查找2.有序順序表的順序查找用如圖7.1所示的判定樹(shù)來(lái)描述有序順序表的順序查找過(guò)程。圖中的圓形節(jié)點(diǎn)表示有序順序表中存在的元素；樹(shù)中的矩形節(jié)點(diǎn)稱為失敗節(jié)點(diǎn)(若有n個(gè)查找成功節(jié)點(diǎn)，則相應(yīng)地有n+1個(gè)查找失敗的節(jié)點(diǎn))，它描述的是那些不在表中的數(shù)據(jù)值的集合。如果查找到失敗的節(jié)點(diǎn)，則說(shuō)明查找不成功。時(shí)間復(fù)雜度為O(n)。7.2靜態(tài)查找算法折半查找折半查找（BinarySearch）查找又稱為二分查找，它是一種效率較高的查找方法。但二分查找有一定的條件限制：要求線性表必須采用順序存儲(chǔ)結(jié)構(gòu)，且表中元素必須按關(guān)鍵字有序（升序或降序均可）。1.折半查找的基本思想在有序表中，取中間的記錄作為比較對(duì)象，如果要查找記錄的關(guān)鍵字等于中間記錄的關(guān)鍵字，則查找成功；若要查找記錄的關(guān)鍵字大于中間記錄的關(guān)鍵字，則在中間記錄的右半?yún)^(qū)繼續(xù)查找。不斷重述上述查找過(guò)程，直到查找成功，或有序表中沒(méi)有所要查找的記錄，查找失敗。7.2靜態(tài)查找算法折半查找2.折半查找的具體操作過(guò)程假設(shè)順序表ST是有序的。設(shè)兩個(gè)指針，一個(gè)是low，指示查找表第一個(gè)記錄的位置，low=0；另一個(gè)是high，指示查找表最后一個(gè)記錄的位置，high=ST.TableLen-1。設(shè)要查找的記錄的關(guān)鍵字為key。當(dāng)low<=high時(shí)，反復(fù)執(zhí)行以下步驟：(1)計(jì)算中間記錄的位置mid，mid=(low+high)/2；7.2靜態(tài)查找算法折半查找2.折半查找的具體操作過(guò)程(2)將待查記錄的關(guān)鍵字key和r[mid].key進(jìn)行比較：①若key=r[mid].key，查找成功，mid所指元素即為要查找的元素。②若key<r[mid].key，說(shuō)明若存在要查找的元素，該元素一定在查找表的前半部分。修改查找范圍的上界：high=mid-1，轉(zhuǎn)①；③若key>r[mid].key，說(shuō)明若存在要查找的元素，該元素一定在查找表的后半部分。修改查找范圍的下界：low=mid+1，轉(zhuǎn)①；(3)重復(fù)以上過(guò)程，當(dāng)low>high時(shí)，表示查找失敗。7.2靜態(tài)查找算法折半查找2.折半查找的具體操作過(guò)程【例7.1】已知由11個(gè)數(shù)據(jù)元素構(gòu)成的有序表(關(guān)鍵字即為數(shù)據(jù)元素的值)如下：{4，12，20，21，35，58，63，77，81，87，98}現(xiàn)要查找值為21和83的數(shù)據(jù)元素。假設(shè)指針low和high分別指示待檢查元素所在范圍的下界和上界，指針mid指示區(qū)間的中間位置，即mid=(low+high)/2=(0+10)/2=5。則在此例中，low和high的初值分別為0和10，即[0,10]為待檢查范圍。

7.2靜態(tài)查找算法折半查找2.折半查找的具體操作過(guò)程key=21時(shí)的查找過(guò)程01234567891041220

21

355863

77

81

8798↑low↑mid

↑high首先令查找范圍中間位置的數(shù)據(jù)元素的關(guān)鍵字ST.elem[mid].key與給定值key相比較，因?yàn)镾T.elem[mid].key>key，說(shuō)明待查找元素若存在，必在區(qū)間[low,mid-1]的范圍內(nèi)，則令指針high指向第mid-1個(gè)元素，重新求得mid=(0+4)/2=2。012345678910412

20

21

35586377

81

8798↑low

↑mid

↑high7.2靜態(tài)查找算法折半查找2.折半查找的具體操作過(guò)程key=21時(shí)的查找過(guò)程仍以ST.elem[mid].key和key相比，因?yàn)镾T.elem[mid].key<key，說(shuō)明待檢查元素若存在，必在[mid+1,high]范圍內(nèi)，則令指針low指向第mid+1個(gè)元素，求得mid的新值為3；若ST.elem[mid].key和key相等，則查找成功，所查元素在表中的序號(hào)等于指針mid的值。01234567891041220213558

63

77

818798

↑low↑high

↑mid7.2靜態(tài)查找算法折半查找3.折半查找算法intBinary_Search(SSTableL,ElemTypekey){

/*在有序表L中查找關(guān)鍵字為key的元素，若存在則返回其位置，不存在則返回-1*/

intlow=0,high=L.TableLen-1,mid; /*置區(qū)間初值*/

while(low<=high){

mid=(low+high)/2; /*取中間位置*/

if(L.elem[mid].key==key)returnmid; /*查找成功，返回所在位置*/7.2靜態(tài)查找算法折半查找3.折半查找算法

elseif(L.elem[mid].key>key)high=mid-1; /*從前半部分繼續(xù)查找*/

elselow=mid+1; /*從后半部分繼續(xù)查找*/

}

return-1; /*順序表中不存在待查元素*/}7.2靜態(tài)查找算法折半查找4.折半查找的性能分析7.2靜態(tài)查找算法折半查找4.折半查找的性能分析折半查找的過(guò)程可用如圖7.2所示的二叉樹(shù)來(lái)描述，圖中的長(zhǎng)方形節(jié)點(diǎn)為判定樹(shù)的外部節(jié)點(diǎn)(圓形節(jié)點(diǎn)為內(nèi)部節(jié)點(diǎn))，由判定樹(shù)中所有節(jié)點(diǎn)的空指針域上的指針指向它。圖中的每個(gè)圓形節(jié)點(diǎn)表示一個(gè)記錄，節(jié)點(diǎn)中的值為該記錄在表中的位置；圖中最下面的葉節(jié)點(diǎn)都是長(zhǎng)方形的，它表示查找不成功的情況。判定樹(shù)有一特點(diǎn)：它的中序序列是一個(gè)有序序列，即為二分查找的初始序列。在判定樹(shù)中，所有的根結(jié)點(diǎn)值大于左子樹(shù)而小于右子樹(shù)，因此在判定樹(shù)上查找很方便，與根結(jié)點(diǎn)比較時(shí)若相等則查找成功，若待找的值小于根結(jié)點(diǎn)，則進(jìn)入左子樹(shù)繼續(xù)查找，否則進(jìn)入右子樹(shù)查找，若找到葉子結(jié)點(diǎn)時(shí)還沒(méi)有找到所需元素，則查找失敗。7.2靜態(tài)查找算法折半查找從判定樹(shù)可以看出，查找成功時(shí)的查找長(zhǎng)度為從根節(jié)點(diǎn)到目的節(jié)點(diǎn)的路徑上的節(jié)點(diǎn)數(shù)，而查找失敗時(shí)的查找長(zhǎng)度為從根節(jié)點(diǎn)到對(duì)應(yīng)失敗節(jié)點(diǎn)的父節(jié)點(diǎn)的路徑上的節(jié)點(diǎn)數(shù)。故用折半查找法查找到給定值的比較次數(shù)最多不會(huì)超過(guò)樹(shù)的高度，時(shí)間復(fù)雜度為O(log2n)。折半查找的優(yōu)點(diǎn)是比較次數(shù)較順序查找要少，查找速度較快，執(zhí)行效率較高；缺點(diǎn)是表的存儲(chǔ)結(jié)構(gòu)只能為順序存儲(chǔ)，不能為鏈?zhǔn)酱鎯?chǔ)，且表中元素必須是有序的。7.3動(dòng)態(tài)查找表7.3動(dòng)態(tài)查找表二叉排序樹(shù)1.二叉排序樹(shù)的定義二叉排序樹(shù)(BinarySortTree)又稱二叉查找樹(shù)。定義：或者是一棵空樹(shù)，或者是具有如下特性的二叉樹(shù)：若它的左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；若它的右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；它的左、右子樹(shù)也分別是二叉排序樹(shù)。7.3動(dòng)態(tài)查找表二叉排序樹(shù)2.二叉排序樹(shù)的存儲(chǔ)定義二叉排序樹(shù)用二叉鏈表來(lái)存儲(chǔ)，其存儲(chǔ)結(jié)構(gòu)描述如下：typedefintKeyType;typedefstructBTNode{

KeyTypekey;/*關(guān)鍵字域*/

structBTNode*lchild,*rchild; /*左、右孩子指針*/}BTNode,*BiTree7.3動(dòng)態(tài)查找表二叉排序樹(shù)3.二叉排序樹(shù)的查找算法二叉排序樹(shù)的查找是從根節(jié)點(diǎn)開(kāi)始，沿某一個(gè)分支逐層向下進(jìn)行比較的過(guò)程（1）若查找樹(shù)為空，查找失敗，結(jié)束查找過(guò)程。（2）查找樹(shù)非空，將給定值key與查找樹(shù)的根結(jié)點(diǎn)關(guān)鍵字比較。（3）若相等，查找成功，結(jié)束查找過(guò)程，否則：①

當(dāng)key小于根結(jié)點(diǎn)關(guān)鍵字，查找將在以左孩子為根的子樹(shù)上繼續(xù)進(jìn)行，轉(zhuǎn)（1）②

當(dāng)key大于根結(jié)點(diǎn)關(guān)鍵字，查找將在以右孩子為根的子樹(shù)上繼續(xù)進(jìn)行，轉(zhuǎn)（1）7.3動(dòng)態(tài)查找表二叉排序樹(shù)3.二叉排序樹(shù)的查找算法算法7.3二叉排序樹(shù)的遞歸查找算法BiTreeSearchBST(BTNodeT,KeyTypekey)/*在根指針T所指二叉排序樹(shù)中查找某關(guān)鍵字等于key的數(shù)據(jù)元素，若查找成功，則返回指向該數(shù)據(jù)元素節(jié)點(diǎn)的指針，否則返回空指針*/{if(!T||key==T->key))return(T);elseif(key<T->key))return(SearchBST(T->lchild,key));elsereturn(SearchBST(T->rchild,key));}7.3動(dòng)態(tài)查找表二叉排序樹(shù)3.二叉排序樹(shù)的查找算法算法7.4改進(jìn)的二叉排序樹(shù)查找算法BTNode*SearchBST(BTNode*T,KeyTypekey,int*f)/*若查找成功，則返回該數(shù)據(jù)元素節(jié)點(diǎn)并使*f=1;否則返回查找路徑上訪問(wèn)的最后一節(jié)點(diǎn)并使*f=0*/{BTNode*p,*pre;

*f=0;if(!T){*f=0;returnT;}

p=T;pre=T;

/*pre指向p的雙親*/7.3動(dòng)態(tài)查找表二叉排序樹(shù)3.二叉排序樹(shù)的查找算法

while(p!=NULL&&key!=p->key)

{pre=p;

if(key<p->key)p=p->lchild; /*在左子樹(shù)中查找*/

elsep=p->rchild;/*在右子樹(shù)中查找*/

}

if(p!=NULL&&key==p->key){*f=1;returnp;} /*查找成功*/

else{*f=0;returnpre;}/*查找失敗*/}7.3動(dòng)態(tài)查找表二叉排序樹(shù)4.二叉排序樹(shù)的插入算法二叉排序樹(shù)是一種動(dòng)態(tài)查找表，樹(shù)的結(jié)構(gòu)通常不是一次生成的，而是在查找的過(guò)程中，當(dāng)樹(shù)中不存在關(guān)鍵字等于給定值的節(jié)點(diǎn)時(shí)再進(jìn)行插入。由于二叉排序樹(shù)是遞歸定義的，因此插入節(jié)點(diǎn)的過(guò)程是，若原二叉樹(shù)為空，則直接插入節(jié)點(diǎn)；否則，若關(guān)鍵字key小于根節(jié)點(diǎn)關(guān)鍵字，則插入到左子樹(shù)中，若關(guān)鍵字key大于根節(jié)點(diǎn)關(guān)鍵字，則插入到右子樹(shù)中。二叉排序樹(shù)的插入見(jiàn)算法7.5中的描述。7.3動(dòng)態(tài)查找表二叉排序樹(shù)4.二叉排序樹(shù)的插入算法算法7.3二叉排序樹(shù)的插入算法BTNode*InsertBST(BTNode*T,KeyTypekey)/*當(dāng)二叉排序樹(shù)T中不存在關(guān)鍵字等于key的數(shù)據(jù)元素時(shí)，插入key返回二叉排序樹(shù)的根結(jié)點(diǎn)。*/{BTNode*p,*s; intf=0; p=SearchBST(T,key,&f); if(!f)/*查找不成功*/ {s=(BTNode*)malloc(sizeof(BTNode)); s->key=key; s->lchild=s->rchild=NULL;7.3動(dòng)態(tài)查找表二叉排序樹(shù)4.二叉排序樹(shù)的插入算法算法7.3二叉排序樹(shù)的插入算法if(!p) returns;/*插入為根結(jié)點(diǎn)*/elseif(key<p->key) p->lchild=s; else p->rchild=s; } returnT;}7.3動(dòng)態(tài)查找表二叉排序樹(shù)5.二叉排序樹(shù)的查找分析二叉排序樹(shù)查找最壞的情況下，需要的查找時(shí)間取決于樹(shù)的深度，當(dāng)二叉排序樹(shù)接近于滿二叉樹(shù)時(shí)，其深度為O(log2n)+l，最壞情況下的查找時(shí)間為O(log2n)，與折半查找是同數(shù)量級(jí)的；當(dāng)二叉排序樹(shù)單枝樹(shù)時(shí)，其深度為n，最壞情況下查找時(shí)間為O(n)，與順序查找屬于同一數(shù)量級(jí)。為了保證二叉排序樹(shù)查找有較高的查找速度，希望該二叉樹(shù)接近于滿二叉樹(shù)，也即希望二叉樹(shù)的每一個(gè)結(jié)點(diǎn)的左、右子樹(shù)盡量相等。7.4哈希表7.4哈希表哈希表的定義哈希(Hash)法又稱為散列法、雜湊法或關(guān)鍵字地址計(jì)算法，相應(yīng)的表稱為哈希表、散列表或雜湊表等，哈希表是一種重要的查找技術(shù)，既適用于靜態(tài)查找，又適用于動(dòng)態(tài)查找，并且查找效率非常高。哈希表的構(gòu)造方法：對(duì)于存儲(chǔ)的m個(gè)數(shù)據(jù)元素，確定一個(gè)稱為哈希函數(shù)的函數(shù)H(key)，將要存儲(chǔ)元素的關(guān)鍵字key按照該函數(shù)進(jìn)行計(jì)算后得到該元素的存儲(chǔ)地址，并將該數(shù)據(jù)元素存儲(chǔ)到存儲(chǔ)地址對(duì)應(yīng)的內(nèi)存單元中。7.4哈希表哈希表的定義例如，假定數(shù)據(jù)元素集合為{25，6，1，20，22，27，10，13，41}，內(nèi)存長(zhǎng)度為100，此時(shí)可以取H(key)=k，此時(shí)，在100個(gè)內(nèi)存單元中只存放9個(gè)元素，存儲(chǔ)單元的利用率很低?？梢钥紤]適當(dāng)?shù)貙?nèi)存單元的個(gè)數(shù)減少為n，若取內(nèi)存單元的個(gè)數(shù)為11，取哈希函數(shù)H(key)=key%n，即用關(guān)鍵字key除以n得到的余數(shù)作為存儲(chǔ)地址，則有：H(25)=25%11=3，H(6)=6%11=6，H(1)=1%11=1，H(20)=20%11=9，H(22)=22%11=0，H(27)=27%11=5，H(10)=10%11=10，H(13)=13%11=2，H(41)=41%11=8數(shù)據(jù)元素在內(nèi)存中的存儲(chǔ)單元位置分別為3、6、1、9、0、5、10、2、8，提高了內(nèi)存單元的利用率。7.4哈希表哈希表的定義如果內(nèi)存單元的個(gè)數(shù)為10，仍取哈希函數(shù)H(key)=key%n，則有：H(25)=25%10=5，H(6)=6%10=6，H(1)=1%10=1，H(20)=20%10=0，H(22)=22%10=2，H(27)=27%10=7，H(10)=10%10=0，H(13)=13%10=3，H(41)=41%10=1此時(shí)，有H(1)=H(41)=1，H(20)=H(10)=0，產(chǎn)生了沖突。7.4哈希表哈希表的定義在構(gòu)造哈希表時(shí)，對(duì)于兩個(gè)不同的關(guān)鍵字key1≠key2，有H(key1)=H(key2)，即兩個(gè)不同記錄需要存放在同一個(gè)存儲(chǔ)位置中，這種現(xiàn)象稱為沖突(Collision)具有相同函數(shù)值的關(guān)鍵字對(duì)該哈希函數(shù)來(lái)說(shuō)稱作同義詞在構(gòu)造哈希表時(shí)，除了需要選擇一個(gè)盡可能少產(chǎn)生沖突的哈希函數(shù)之外，還需要找到一種處理沖突的方法7.4哈希表哈希函數(shù)的構(gòu)建1.構(gòu)造哈希函數(shù)的注意事項(xiàng)(1)哈希函數(shù)的定義必須包含全部需要存儲(chǔ)的關(guān)鍵字，而值域的范圍則依賴于哈希表的大小或地址范圍；(2)哈希函數(shù)計(jì)算出來(lái)的地址應(yīng)該能等概率地、均勻地分布在整個(gè)地址空間，從而減少?zèng)_突的發(fā)生；(3)哈希函數(shù)應(yīng)盡量簡(jiǎn)單，能夠在較短的時(shí)間內(nèi)計(jì)算出任一關(guān)鍵字對(duì)應(yīng)的哈希地址。7.4哈希表哈希函數(shù)的構(gòu)建2.常見(jiàn)的哈希函數(shù)(1)直接定址法直接取關(guān)鍵字的某個(gè)線性函數(shù)值為散列地址，散列函數(shù)為：H(key)=a×key+b(a、b為常數(shù))例如：關(guān)鍵字集合{10，20，40，50，60，90}，選取的哈希函數(shù)為H(key)=key/10，構(gòu)造的哈希表如圖7.5所示。0123456789

102040506090直接定址法的特點(diǎn)是計(jì)算簡(jiǎn)單，并且不會(huì)產(chǎn)生沖突。它適合關(guān)鍵字分布基本連續(xù)的情況，若關(guān)鍵字分布不連續(xù)，將造成存儲(chǔ)空間的浪費(fèi)。7.4哈希表哈希函數(shù)的構(gòu)建2.常見(jiàn)的哈希函數(shù)(2)除留取余法這是一種最簡(jiǎn)單、最常用的方法，假定哈希表表長(zhǎng)為m，取一個(gè)不大于m但最接近或等于m的質(zhì)數(shù)p，利用哈希函數(shù)H(key)=key%p把關(guān)鍵字轉(zhuǎn)換成哈希地址。這一方法的關(guān)鍵在于選取合適的p，如果p的選擇不合適，則容易產(chǎn)生同義詞。通常情況下，確定數(shù)據(jù)元素的個(gè)數(shù)m后，p選取不大于m的最大的質(zhì)數(shù)，可有效減少哈希沖突的發(fā)生。例如元素集合{78，7，99，24，25，53，59，19}，m=11，當(dāng)p取11時(shí)，不產(chǎn)生哈希沖突；但當(dāng)p取10時(shí)，就會(huì)產(chǎn)生2次哈希沖突。7.4哈希表哈希函數(shù)的構(gòu)建3.選用哈希函數(shù)要考慮的因素實(shí)際工作中需視不同的情況采用不同的哈希函數(shù)。通常，考慮的因素有：(1)計(jì)算哈希函數(shù)所需的時(shí)間(2)關(guān)鍵字的長(zhǎng)度(3)哈希表的大小(4)關(guān)鍵字的分布情況(5)記錄的查找頻率7.4哈希表處理沖突方法處理沖突是為產(chǎn)生沖突的地址尋找下一個(gè)哈希地址處理沖突方法開(kāi)放定址法、鏈地址法、再哈希法、建立公共溢出區(qū)1.開(kāi)放定址法為產(chǎn)生沖突的地址H(key)求得一個(gè)地址序列：

H1,H2,…,Hk

其中：1≤k≤m-1Hi=(H(key)+di)%m，其中：i=1,2,…,k H(key)為哈希函數(shù); m為哈希表長(zhǎng); di為增量序列；7.4哈希表處理沖突的方法1.開(kāi)放定址法開(kāi)放定址法對(duì)增量di的兩種取法(1)線性探測(cè)再散列當(dāng)di=1，2，…，m-1時(shí)稱為線性探測(cè)法沖突發(fā)生時(shí)，順序查看表的下一單元，當(dāng)探測(cè)到表尾地址m-1時(shí)，下一個(gè)探測(cè)地址是表首地址0，直到找出一個(gè)空閑單元或查遍全表。線性探測(cè)法可能會(huì)使第i個(gè)哈希地址的同義詞存入第i+1個(gè)哈希地址中，這樣本應(yīng)存入第i+1個(gè)哈希地址的元素就爭(zhēng)奪第i+2個(gè)哈希地址的元素的地址，以此類推，從而造成大量元素在相鄰的哈希地址上“聚集”(或堆積)起來(lái)，大大降低了查找效率。7.4哈希表處理沖突的方法1.開(kāi)放定址法(開(kāi)放定址法對(duì)增量di的兩種取法)(1)線性探測(cè)再散列例如，哈希表表長(zhǎng)m為10，以關(guān)鍵字的末尾數(shù)字作為哈希地址(即H(key)=key%10)，依次插入45、22、13、65、29、42、79、2共8個(gè)記錄。若發(fā)生沖突則采用線性探測(cè)法。H1=(H(65)+1)%10=6H2=(H(42)+2)%10=4H5=(H(2)+5)%10=77.4哈希表處理沖突的方法1.開(kāi)放定址法開(kāi)放定址法對(duì)增量di的兩種取法(2)平方探測(cè)再散列(二次探測(cè)法)di=12，-12，22，-22，…，k2，-k2，其中k≤m/2，m必須是一個(gè)可以表示成4k+3的質(zhì)數(shù)時(shí)，稱為平方探測(cè)法，又稱二次探測(cè)法。平方探測(cè)法是一種較好的處理沖突的方法，可以避免出現(xiàn)“堆積”問(wèn)題，它的缺點(diǎn)是不能探測(cè)到哈希表上的所有單元，但至少能探測(cè)到一半的單元。7.4哈希表處理沖突的方法1.開(kāi)放定址法開(kāi)放定址法對(duì)增量di的兩種取法(2)平方探測(cè)再散列(二次探測(cè)法)例如，若有關(guān)鍵字集合{47，7，29，11，16，92，22，8，3}，哈希表表長(zhǎng)m為11，哈希函數(shù)為H(key)=key%11，用二次探測(cè)法處理沖突。關(guān)鍵字3，H(3)