西電初試專業(yè)課講義-數(shù)據(jù)結(jié)構(gòu)ch09search

第九章查找

在英漢字典中查找某個英文單詞的中文解釋；在新華字典中查找某個漢字的讀音、含義；在對數(shù)表、平方根表中查找某個數(shù)的對數(shù)、平方根；郵遞員送信件要按收件人的地址確定位置等等?？梢哉f查找是為了得到某個信息而常常進行的工作。

從計算機、計算機網(wǎng)絡(luò)中查找特定的信息，就需要在計算機中存儲包含該特定信息的表。查找是許多程序中最消耗時間的一部分。因而，一個好的查找方法會大大提高運行速度。由于計算機的特性，對數(shù)、平方根等可通過函數(shù)求解，無需存儲相應(yīng)的信息表。本章將討論的問題是“信息的存儲和查找”。第九章查找本章內(nèi)容9.1靜態(tài)查找表9.1.1順序表的查找9.1.2有序表的查找9.1.3靜態(tài)樹表的查找(不講)9.1.4索引順序表的查找9.2動態(tài)查找表9.2.1二叉排序樹和平衡二叉樹9.2.2B_樹和B+樹9.2.3鍵樹(不講)9.3哈希表9.1查找的基本概念1.數(shù)據(jù)項(也稱項或字段)

項是具有獨立含義的標(biāo)識單位，是數(shù)據(jù)不可分割的最小單位。如“學(xué)號”、“姓名”、“年齡”等。項有名和值之分，項名是一個項的標(biāo)識，用變量定義，而項值是它的一個可能取值，例如“03051123”是項“學(xué)號”的一個取值。項具有一定的類型，依項的取值類型而定。2.組合項由若干項、組合項構(gòu)成，例如“出生日期”，它由“年”、“月”、“日”三項組成。3.數(shù)據(jù)元素（記錄）數(shù)據(jù)元素是由若干項、組合項構(gòu)成的數(shù)據(jù)單位，是在某一問題中作為整體進行考慮和處理的基本單位。數(shù)據(jù)元素有型和值之分，表中項名的集合，也即表頭部分就是數(shù)據(jù)元素的類型；而一個學(xué)生對應(yīng)的一行數(shù)據(jù)就是一個數(shù)據(jù)元素的值，表中全體學(xué)生即為數(shù)據(jù)元素的集合。9.1查找的基本概念(續(xù))4.關(guān)鍵碼

關(guān)鍵碼是數(shù)據(jù)元素（記錄）中某個項或組合項的值，用它可以標(biāo)識一個數(shù)據(jù)元素（記錄）。能唯一確定一個數(shù)據(jù)元素（記錄）的關(guān)鍵碼，稱為主關(guān)鍵碼；而不能唯一確定一個數(shù)據(jù)元素（記錄）的關(guān)鍵碼，稱為次關(guān)鍵碼。表中“學(xué)號”即可看成主關(guān)鍵碼，“姓名”則應(yīng)視為次關(guān)鍵碼，因可能有同名同姓的學(xué)生。5.查找表

是由具有同一類型（屬性）的數(shù)據(jù)元素（記錄）組成的集合。分為靜態(tài)查找表和動態(tài)查找表兩類。9.1查找的基本概念(續(xù))

靜態(tài)查找表：僅進行查找操作而不改變表中的數(shù)據(jù)；

動態(tài)查找表：對查找表除進行查找操作外，還可能進行插入數(shù)據(jù)元素，或刪除表中數(shù)據(jù)元素的操作，即表中的數(shù)據(jù)是動態(tài)變化的。6.查找按給定的某個值kx，在查找表中查找關(guān)鍵碼為kx的數(shù)據(jù)元素（記錄）。關(guān)鍵碼是主關(guān)鍵碼時：查找結(jié)果唯一，一旦找到，查找成功，結(jié)束查找過程，并給出找到的數(shù)據(jù)元素（記錄）的信息，或指示該數(shù)據(jù)元素（記錄）的位置。若沒有找到，則查找失敗，此時，查找結(jié)果應(yīng)給出一個“空”記錄或“空”指針。關(guān)鍵碼是次關(guān)鍵碼時：需要查遍表中所有數(shù)據(jù)元素（記錄），或在可以肯定查找失敗時，才能結(jié)束查找過程。

9.1靜態(tài)查找表順序表的查找順序查找i12236994530512812345678下面假設(shè)元素的主關(guān)鍵碼是一個整數(shù)，存放在數(shù)組A中9.1.1順序查找intSq_search(intA[],intn,inte){

//在無序表中查找元素e，查找成功時，返回元素在表中的位置

//否則返回0i=n;while(i>0&&A[i]!=e)i--;returni;}12236994530512812345678i9.1.1(續(xù))順序查找無序表上的順序查找，設(shè)監(jiān)視哨12236994530512812345678i12236994530512812345678i監(jiān)視哨09.1.1(續(xù))無序表上的順序查找intSq_search(intA[],intn,inte){//在無序表中查找元素e，查找成功時，返回元素在表中的位置

//否則返回0i=n;A[0]=e;//監(jiān)視哨：下標(biāo)為0的位置存放待查找的元素

while(A[i]!=e)i--;returni;}12236994530512812345678i監(jiān)視哨0平均查找長度查找性能：平均查找長度（ASL）為確定記錄在查找表中的位置，需和給定值進行比較的關(guān)鍵字個數(shù)的期望值稱為查找算法在查找成功時的平均查找長度。其中，n是查找表中的長度，Pi為查找第i個元素的概率ci是找到表中其關(guān)鍵字與給定值相等的記錄時(第i個記錄)，和給定值已進行過比較的關(guān)鍵字的個數(shù)。9.1.1(續(xù))無序表上的順序查找intSq_search(intA[],intn,inte){//在無序表中查找元素e，查找成功時，返回元素在表中的位置

//否則返回0i=n;A[0]=e;while(A[i]!=e)i--;returni;}12236994530512812345678i監(jiān)視哨09.1.1(續(xù))有序表上的順序查找612232831455199123456780監(jiān)視哨例如：e=23成功時，與順序查找的平均查找長度（ASL）相同，失敗時無須與所有元素進行比較9.1.1(續(xù))有序表上的順序查找61223283145519912345678230監(jiān)視哨>e=23?9.1.1(續(xù))有序表上的順序查找61223283145519912345678230監(jiān)視哨>e=23?9.1.1(續(xù))有序表上的順序查找61223283145519912345678230監(jiān)視哨>e=23?9.1.1(續(xù))有序表上的順序查找61223283145519912345678230監(jiān)視哨>e=23?9.1.1(續(xù))有序表上的順序查找61223283145519912345678230監(jiān)視哨>e=23?9.1.1(續(xù))有序表上的順序查找61223283145519912345678230監(jiān)視哨>e=23?a[i]>e不成立，停止查找9.1.1(續(xù))有序表上的順序查找intSq_search(intA[],intn,inte){//在無序表中查找元素e，查找成功時，返回元素在表中的位置

//否則返回0i=n;A[0]=e;while(A[i]>e)i--;ifA[i]==ereturni;elsereturn0;}61223283145519912345678i監(jiān)視哨09.1.1(續(xù))有序表上的順序查找：失敗61223283145519912345678400監(jiān)視哨靜態(tài)查找表順序查找無序表的順序查找有序表的順序查找折半查找9.1.2有序順序表上的折半查找61223283145519912345678lowhighmid=[(low+high)/2]下標(biāo)9.1.2(續(xù))有序順序表上的折半查找61223283145519912345678lowhighmide<A[mid]‖239.1.2(續(xù))有序順序表上的折半查找61223283145519912345678lowhighmide>A[mid]e==23mid=[(low+high)/2]‖239.1.2(續(xù))有序順序表上的折半查找：成功61223283145519912345678lowhighmide等于A[mid]‖239.1.2(續(xù))有序順序表上的折半查找61223283145519912345678lowhighmide>A[mid]‖559.1.2(續(xù))有序順序表上的折半查找61223283145519912345678lowhighmide>A[mid]‖559.1.2(續(xù))有序順序表上的折半查找61223283145519912345678lowhighmide>A[mid]‖559.1.2(續(xù))有序順序表上的折半查找61223283145519912345678lowhighmide<A[mid]‖559.1.2(續(xù))有序順序表上的折半查找：失敗61223283145519912345678lowhigh?9.1.2(續(xù))有序順序表上的折半查找mid=[(low+high)/2];if(A[mid]==e)returnmid;//查找成功

elseif(e<A[mid])high=mid-1;//下一次到前半?yún)^(qū)間查找

elselow=mid+1;//下一次到后半?yún)^(qū)間查找

折半查找方法：先確定待查記錄所在的范圍(區(qū)間)，若待查記錄等于表中間位置上的記錄，則查找成功；否則，縮小查找范圍，即若待查記錄小于中間位置上的元素，則下一次到前半?yún)^(qū)間進行查找，若待查記錄大于中間位置上的元素，則下一次到后半?yún)^(qū)間進行查找。61223283145519912345678lowhighmid9.1.2(續(xù))折半查找算法intB_search(intA[],intn,inte){//在有序表中查找元素e，若查找成功，則返回元素在表中的位置

//

否則返回0

low=1;high=n;while(low<=high){mid=[(low+high)/2];if(A[mid]==e)returnmid;//查找成功

elseif(e<A[mid])high=mid-1;//下一次到前半?yún)^(qū)查找

elselow=mid+1;//下一次到后半?yún)^(qū)查找

}//endofwhile

return0;//查找失敗}//endofB_search9.1.2(續(xù))折半查找法問題：

若采用鏈表（單鏈表或雙向鏈表）作為查找表的存儲結(jié)構(gòu)，能否進行折半查找？9.1.2(續(xù))折半查找判定樹折半查找判定樹：描述折半查找過程的二叉樹有序順序表：a1，a2，a3，a4，a5，a6，a7，a8a4a2a6a1a3a5a7a89.1.2(續(xù))折半查找判定樹a4a2a6a1a3a5a7a8ASL成功=(1+2+2+3+3+3+3+4)/8

=21/8-------等概率查找9.1.2(續(xù))查找失敗若查找失敗，即表中不存在要查找的元素，平均查找長度又如何呢？9.1.2(續(xù))查找失敗

ASL失敗=

？a1a2a3a4a5a6a7a89.1.2(續(xù))折半查找判定樹a4a2a6a1a3a5a7a8比a1小的所有元素比a8大的所有元素大于a2而小于a3的所有元素大于a5而小于a6的所有元素9.1.2(續(xù))折半查找算法intB_search(intA[],intn,inte){//在有序表中查找元素e，若查找成功，則返回元素在表中的位置

//

否則返回0

low=1;high=n;while(low<=high){mid=[(low+high)/2];if(A[mid]==e)returnmid;//查找成功

elseif(e<A[mid])high=mid-1;//下一次到前半?yún)^(qū)查找

elselow=mid+1;//下一次到后半?yún)^(qū)查找

}//endofwhile

return0;//查找失?。簂ow>high}//endofB_search9.1.2(續(xù))折半查找判定樹a4a2a6a1a3a5a7a8

ASL失敗=(3*7+4*2)/9=29/99.1.2(續(xù))折半查找判定樹n=11a6a3a1a4a9a10a7a11a2a5a89.1.2(續(xù))折半查找判定樹n=11a6a3a1a4a9a10a7a11a2a5a89.1.2(續(xù))折半查找的效率分析如果查找表中有n個元素，那么對應(yīng)的折半查找判定樹又如何？查找成功和失敗的平均查找長度與有n個結(jié)點的完全二叉樹的高度相同。即：完全二叉樹9.1.2(續(xù))折半查找的效率分析設(shè)有序順序表中有n個元素，進行折半查找設(shè)n=2h-1，則描述折半查找的判定樹是高度為h的滿二叉樹設(shè)表中每個記錄的查找概率相等，即Pi=1/n9.1.2(續(xù))折半查找的效率分析則查找成功時折半查找的平均查找長度為：9.1.4索引順序表的查找元素分塊有序建立索引表1389203342443824486058744986532212B1B2B32214878613最大關(guān)鍵字起始地址(下標(biāo))索引表9.1.4(續(xù))索引順序表的查找：分塊查找在索引順序表中查找指定元素時，分兩步：先在索引表中確定元素所在的塊；再在塊中順序查找；1389203342443824486058744986532212B1B2B32214878613最大關(guān)鍵字起始地址(下標(biāo))索引表9.1.4(續(xù))索引順序表的查找：分塊查找在索引順序表中查找指定元素時，分兩步：先在索引表中確定元素所在的塊；再在塊中順序查找；9.1.4(續(xù))索引順序表的查找：分塊查找設(shè)查找表中的元素可均勻地分為b塊，每塊含有s個記錄若在索引表和塊內(nèi)都進行順序查找，則：實際上，在索引表中可進行折半查找。動態(tài)查找表完全二叉樹n=11return9.2動態(tài)查找表動態(tài)查找表的特點表結(jié)構(gòu)本身是在查找過程中動態(tài)生成的，即對于給定值key，若表中存在關(guān)鍵字等于key的記錄，則查找成功返回，否則插入關(guān)鍵字等于key的記錄。動態(tài)查找表的主要運算創(chuàng)建、銷毀查找、插入和刪除遍歷9.2.1二叉排序樹和平衡二叉樹1.二叉排序樹(二叉檢索樹、二叉查找樹)定義二叉排序樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：若其左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值；若其右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值其左、右子樹也分別為二叉排序樹BST舉例9.2.1(續(xù))二叉排序樹圖示45125333710090246178CAOZHAODINGCHENWANGLIXIADUMA(a)(b)BST查找運算9.2.1(續(xù))二叉排序樹的查找運算查找：查找鍵值等于key的記錄若二叉排序樹為空樹，則查找失敗，返回；若根結(jié)點的鍵值等于key，則查找成功，返回；若根結(jié)點的鍵值大于key，則到根的左子樹上繼續(xù)查找；否則，到根的右子樹上繼續(xù)查找；45125333710090246178查找性能分析9.2.1(續(xù))二叉排序樹的查找算法BiTreeSearchBST(BiTreeT,keyTypekey){//在T指向根的二叉排序樹中遞歸地查找關(guān)鍵字等于key的數(shù)據(jù)元素，//若找到，返回指向該結(jié)點的指針，否則返回null

if(T==NULL)returnNULL;elseif(T->data.key==key)returnT;elseif(T->data.key>key)returnSearchBST(T->lchild,key);elsereturnSearchBST(T->rchild,key);}//SearchBST45125333710090246178T二叉排序樹是動態(tài)查找表，當(dāng)找不到指定元素時應(yīng)插入該元素9.2.1(續(xù))二叉排序樹的插入運算插入：在二叉排序樹中插入鍵值等于key的記錄若二叉排序樹為空樹，則插入元素作為樹根結(jié)點；若根結(jié)點的鍵值等于key，則插入失??；若key小于根結(jié)點的鍵值，則插入到根的左子樹上；否則，插入到根的右子樹上；4512533371009024657860例如，插入鍵值為60的結(jié)點新插入的結(jié)點一定是個葉子結(jié)點9.2.1(續(xù))二叉排序樹的插入算法StatusInsertBST(BiTree&T,ElemTypee){//當(dāng)二叉排序樹中不存在關(guān)鍵字等于e.key的數(shù)據(jù)元素時，//插入元素e并返回true，否則返回false45125333710090246578if(p)//鍵值為e.key的結(jié)點已經(jīng)存在

returnfalse;s=newBiTnode;s->data=e;s->lchild=s->rchild=NULL;if(father==NULL)T=s;//新建結(jié)點為根結(jié)點elseif(e.key>father->data.key)father->rchild=s;elsefather->lchild=s;}//InsertBSTp=T;father=NULL;while(p&&p->data.key!=e.key){father=p;if(e.key>p->data.key)p=p->rchild;elsep=p->lchild;}//whileTfather60s9.2.1(續(xù))二叉排序樹的特點將一個無序序列的元素依次插入到一棵二叉排序樹上，然后進行中序遍歷，可得到一個有序序列。在二叉排序樹上插入元素時，總是將新元素作為葉子結(jié)點插入，插入過程中無須移動其他元素，僅需將一個空指針修改為非空。在二叉排序樹上刪除元素時，應(yīng)保持其中序遍歷序列有序的特點。9.2.1(續(xù))二叉排序樹的刪除運算若待刪除的結(jié)點*p是個葉子結(jié)點，則：若*p是*f的左孩子將*p的父結(jié)點*f的左孩子指針置空，若*p是*f的右孩子，則將*f的右孩子指針置空，示例若待刪除的結(jié)點*p是僅有一個孩子的非葉子結(jié)點，則將*p的左孩子(或右孩子)接為*p的父結(jié)點*f的左孩子(若*p是*f的左孩子)，或者將*p的左孩子(或右孩子)接為*p的父結(jié)點*f的右孩子(若*p是*f的右孩子)，示例9.2.1(續(xù))二叉排序樹的刪除運算若待刪除的結(jié)點*p的兩個子樹都不為空(一般結(jié)構(gòu))，則其一是令*p的直接前驅(qū)(或直接后繼)代替*p，然后再刪除其直接前驅(qū)(或直接后繼)，示例其二是令*p的左子樹為*f的左子樹(若*p是*f的左孩子)，而*p的右子樹為*s的右子樹(*s是對*p的左子樹進行中序遍歷的最后一個結(jié)點)；示例，或者，令*p的右子樹為*f的右子樹(若*p是*f的右孩子)，而*p的左子樹為*s的左子樹(*s是對*p的右子樹進行中序遍歷的第一個結(jié)點)；關(guān)于查找9.2.1(續(xù))二叉排序樹的刪除運算4512533371009024657860刪除2445125333710090657860fpf->lchild=NULL;deletep;return9.2.1(續(xù))二叉排序樹的刪除運算4512533371009024657860刪除6545125333710090607824p令*p的直接前驅(qū)*s代替*p，然后刪除*ssnextexample9.2.1(續(xù))二叉排序樹的刪除運算4512533371009024657860刪除6545125333710090782460ps令*p的直接后繼*s代替*p，然后刪除*sreturn9.2.1(續(xù))二叉排序樹的刪除運算4512533371009024657860刪除65s令*p的左子樹為*f的左子樹(*p是*f的左子樹)pf令*p的右子樹為*s的右子樹，然后刪除*preturn451253337100906024789.2.1(續(xù))二叉排序樹的刪除運算4512533371009024657860刪除3745125332410090657860f->rchild=p->lchild;deletep;fpnextexample9.2.1(續(xù))二叉排序樹的刪除運算4512533371009040657860刪除3745125334010090657860f->rchild=p->rchild;deletep;fpreturn9.2.1(續(xù))二叉排序樹的刪除運算4512533371009010657860刪除3451253103710090657860f->lchild=p->rchild;deletep;fpreturn9.2.1(續(xù))刪除兩個子樹均不空的*p結(jié)點pFPfPLPR(a)cFPfPR(b)CpCLQQLSSLqs*p的直接前驅(qū)在其左子樹上最右下方的結(jié)點，設(shè)為*s繼續(xù)9.2.1(續(xù))刪除兩個子樹均不空的*p結(jié)點FCf(d)刪除*p之后，以PR作為*s的右子樹cCLSSLsPRcFPfPR(b)刪除*p之前CpCLQQLSSLqscFSfPR(c)刪除*p之后，以*s代替*pCpCLQQLSLqreturn9.2.1(續(xù))二叉排序樹的查找性能若查找成功，則走了一條從根結(jié)點到某結(jié)點的路徑，若查找失敗，則走到一棵空的子樹時為止。因此，最壞情況下，其平均查找長度不會超過樹的高度。4512533371009024617855ASL成功=(1+2*2+3*3+4*2+5*2+6*1)/11=38/11查找性能(續(xù))9.2.1(續(xù))二叉排序樹的查找性能(續(xù))ASL失敗=(2+3*4+4*2+5*3+6*2)/12=49/124512533371009024617855大于90且小于100的數(shù)大于100的數(shù)大于12且小于24的數(shù)9.2.1(續(xù))二叉排序樹的查找性能(續(xù))若查找成功，則走了一條從根結(jié)點到某結(jié)點的路徑，若查找失敗，則走到一棵空的子樹時為止。因此，最壞情況下，其平均查找長度不會超過樹的高度。具有n個結(jié)點的二叉樹的高度取決于其形態(tài)。45125333710090246178559.2.1(續(xù))二叉排序樹的形態(tài)關(guān)鍵字序列為(45,24,53,12,37,93)所構(gòu)造的二叉排序樹如圖(a)所示452453123793關(guān)鍵字序列為(12,24,37,45,53,93)所構(gòu)造的二叉排序樹如圖(b)所示(a)122437455393(b)單枝樹9.2.1(續(xù))二叉排序樹的形態(tài)(續(xù))關(guān)鍵字序列為(12,93,24,53,37,45)所構(gòu)造的二叉排序樹如圖(c)所示129324533745(c)單枝樹如果根據(jù)關(guān)鍵字的輸入序列構(gòu)造的二叉樹為單枝樹，則其平均查找長度與順序查找相同，因此在構(gòu)造二叉排序樹的過程中需要進行處理，使得樹中結(jié)點的分布比較均勻平衡二叉樹和B樹Adelson-Velskii,Landis(阿德爾森-維爾斯和蘭迪斯)于1962年首先提出了平衡二叉樹(AVL樹)。9.3哈希表（散列表）9.3.1基本概念

1.散列

也稱為雜湊或哈希。它既是一種查找方法，又是一種存貯方法，稱為散列存貯。散列存貯的內(nèi)存存放形式也稱為哈希表或散列表。

散列查找，與前面介紹的查找方法完全不同，前面介紹的所有查找都是基于待查關(guān)鍵字與表中元素進行比較而實現(xiàn)的查找方法，而散列查找是通過計算哈希函數(shù)來得到待查關(guān)鍵字的地址，理論上講，在哈希表中查找元素?zé)o須進行關(guān)鍵字間的比較。例如，要找關(guān)鍵字為k的元素，則只需求出函數(shù)值H(k)，H為給定的哈希函數(shù)，H(k)代表關(guān)鍵字k在存貯區(qū)中的地址。

假設(shè)有一批關(guān)鍵字序列18,75,60,43,54,90,46，給定哈希函數(shù)H(k)=k%13，存貯區(qū)的內(nèi)存地址從0到15，則可以得到每個關(guān)鍵字的散列地址為：

H(18)=18%13=5H(75)=75%13=10H(60)=60%13=8H(43)=43%13=4H(54)=54%13=2H(90)=90%13=12H(46)=46%13=7

于是，根據(jù)散列地址，可以將上述7個關(guān)鍵字序列存貯到一個一維數(shù)組HT（哈希表或散列表）中，具體表示為：

HT0123456789101112

54

43184660

75

90131415

例如：9.3.1哈希表基本概念

因此，一個散列結(jié)構(gòu)是一塊地址連續(xù)的存儲空間，它與一個稱為散列函數(shù)的函數(shù)相關(guān)聯(lián)，該函數(shù)是數(shù)據(jù)記錄的關(guān)鍵字到地址空間的映射。這種存儲空間的使用方式，使得存儲記錄時，通過散列函數(shù)計算出記錄的存儲位置并按此存儲位置存儲記錄記錄位置＝Hash(記錄的關(guān)鍵字)Hash：關(guān)鍵字→地址(2)訪問記錄時，同樣利用散列函數(shù)計算存儲位置，然后根據(jù)所計算出的存儲位置訪問記錄9.3.1哈希表基本概念2.散列技術(shù)中的主要問題

表面上看，設(shè)置了散列函數(shù)后，只需作簡單的函數(shù)計算就可以實現(xiàn)元素的定位及查找操作，但事實上沒有這么簡單，概括起來，主要有以下兩個問題：沖突

一般情況下，設(shè)計出的散列函數(shù)很難是單射的，即不同的關(guān)鍵字對應(yīng)到同一個存儲位置，這樣就造成了沖突(碰撞)。此時，發(fā)生沖突的關(guān)鍵字互為同義詞。(2)散列函數(shù)的設(shè)計

設(shè)計一個簡單、均勻、存儲空間利用率高、沖突少的散列函數(shù)是關(guān)鍵。9.3.1哈希表基本概念3.散列過程

散列的一般使用方法是，首先根據(jù)具體問題的特點(數(shù)據(jù)集的特點、存儲空間的限制等)設(shè)計散列函數(shù)和解決沖突的方法，然后執(zhí)行以下過程：提取需要插入或訪問的記錄的關(guān)鍵字，用散列函數(shù)計算出存儲位置addr。(2)如果是存儲(插入)記錄，且addr處已被其他記錄占用(插入沖突)則轉(zhuǎn)(4)；否則將記錄存入該位置，結(jié)束。(3)如果是訪問(查找、刪除、修改等)記錄，則檢查addr處的記錄是否為要訪問的記錄，若不是(定位沖突)，則轉(zhuǎn)(4)；否則讀取該記錄進行相應(yīng)的處理，結(jié)束。9.3.1哈希表基本概念提取需要插入或訪問的記錄的關(guān)鍵字，用散列函數(shù)計算出存儲位置addr。(2)如果是存儲(插入)記錄，且addr處已被其他記錄占用(插入沖突)，則轉(zhuǎn)(4)；否則將記錄存入該位置，結(jié)束。(3)如果是訪問(查找、刪除、修改等)記錄，則檢查addr處的記錄是否為要訪問的記錄，若不是(定位沖突)，則轉(zhuǎn)(4)；否則讀取該記錄進行相應(yīng)的處理，結(jié)束。(4)按既定的沖突處理策略處理沖突。若是插入沖突，則沖突處理是要找一個空閑位置以插入記錄；若是定位沖突，則沖突處理是繼續(xù)查找所要求的記錄，確定記錄是否在散列結(jié)構(gòu)中，若是則返回該元素的位置信息，否則返回特殊標(biāo)志。3.散列過程

9.3哈希表（散列表）9.3.2散列函數(shù)的構(gòu)造方法“好”的散列函數(shù)是指：對于關(guān)鍵字集合中的任意一個關(guān)鍵字，經(jīng)散列函數(shù)映像到地址集合中任意一個地址的概率是相等的，稱此類散列函數(shù)為均勻的哈希函數(shù)。常用的散列函數(shù)構(gòu)造方法有：1．直接定址法可表示為H(key)=a*key+b，其中a、b均為常數(shù)。這種方法計算特別簡單，并且不會發(fā)生沖突，但當(dāng)關(guān)鍵字分布不連續(xù)時，會出現(xiàn)很多空閑單元，會將造成大量存貯單元的浪費。9.3哈希表（散列表）9.3.2散列函數(shù)的構(gòu)造方法

1．直接定址法2．?dāng)?shù)字分析法分析關(guān)鍵字的各個位的構(gòu)成，截取其中若干位作為散列函數(shù)值，盡可能使關(guān)鍵字具有大的敏感度。

通過對上述關(guān)鍵字序列分析，發(fā)現(xiàn)第4、5、6位的敏感度較大，于是有：H(99346532)＝465H(99372242)＝722H(99387433)＝874H(99301367)＝013H(99322817)＝228例如：key1:99346532key2:99372242key3:99387433key4:99301367key5:99322817．．．．．．9.3哈希表（散列表）9.3.2散列函數(shù)的構(gòu)造方法

1．直接定址法

2．?dāng)?shù)字分析法3．平方取中法這種方法是先求關(guān)鍵字的平方值，然后在平方值中取中間幾位為散列函數(shù)的值。因為一個數(shù)平方后的中間幾位和原數(shù)的每一位都相關(guān)，因此，使用隨機分布的關(guān)鍵字得到的記錄的存儲位置也是隨機的。

關(guān)鍵字

（關(guān)鍵字）2

函數(shù)地址

0100

0010000010

1100

1210000210

1200

1440000440

1160

1370400370

2061

4310541310

利用平方取中法得到散列函數(shù)地址

9.3哈希表（散列表）9.3.2散列函數(shù)的構(gòu)造方法

1．直接定址法

2．?dāng)?shù)字分析法

3．平方取中法4．折疊法

將關(guān)鍵字分割成位數(shù)相同的幾部分(最后一部分的位數(shù)可以不同)，然后取這幾部分的疊加和(舍去進位)作為散列函數(shù)的值，稱為折疊法。

例如，假設(shè)關(guān)鍵字為某人身份證號碼430104681015355，則可以用4位為一組進行疊加，即有5355＋8101＋1046＋430＝14932，舍去高位，則有H(430104681015355)＝4932。9.3哈希表（散列表）9.3.2散列函數(shù)的構(gòu)造方法

1．直接定址法

2．?dāng)?shù)字分析法

3．平方取中法

4．折疊法5．除留余數(shù)法該方法的散列函數(shù)形式為：Hash(key)=key%p

其中，p為不大于散列表表長m的整數(shù)5．除留余數(shù)法(續(xù))

除留余數(shù)法計算簡單，適用范圍廣，是一種最常使用的方法。這種方法的關(guān)鍵是選取較理想的p值，使得每一個關(guān)鍵字通過該函數(shù)轉(zhuǎn)換后映射到散列空間上任一地址的概率都相等，從而盡可能減少發(fā)生沖突的可能性。一般情形下，取p為一個素數(shù)較理想。經(jīng)驗表明，p為1.1n～1.7n之間的一個素數(shù)較好，其中n為哈希表中待裝入的元素個數(shù)。6.隨機法選擇一個隨機函數(shù)，取關(guān)鍵值的隨機函數(shù)值為它的哈希地址，即

H(key)=random(key)9.3.2散列函數(shù)的構(gòu)造方法9.3哈希表（散列表）9.3.3解決沖突的方法一般情況下，由于關(guān)鍵字的復(fù)雜性和隨機性，很難有理想的散列函數(shù)存在，所以，沖突一般是難以避免的，因此需要設(shè)計合適的沖突解決方法。常用的沖突處理方法有：1．開放定址法開放定址法就是從發(fā)生沖突的那個單元開始，按照一定的次序，從哈希表中找出一個空閑的存儲單元，把發(fā)生沖突的待插入關(guān)鍵字存儲到該單元中，從而解決沖突。在哈希表未填滿時，處理沖突需要的“下一個”空地址在哈希表中解決。9.3哈希表（散列表）9.3.3解決沖突的方法

1．開放定址法

開放定址法就是從發(fā)生沖突的那個單元開始，按照一定的次序，從哈希表中找出一個空閑的存儲單元，把發(fā)生沖突的待插入關(guān)鍵字存儲到該單元中，從而解決沖突。在哈希表未填滿時，處理沖突需要的“下一個”空地址在哈希表中解決。

開放定址法利用下列公式求“下一個”空地址

Hi=(H(key)+di)MODmi=1,2,…K(K<=m-1)

其中H(key)為散列函數(shù)，m為散列表長度，di為增量序列9.3哈希表（散列表）9.3.3解決沖突的方法

1．開放定址法

開放定址法利用下列公式求“下一個”空地址

Hi=(H(key)+di)MODmi=1,2,…K(K<=m-1)

其中H(key)為散列函數(shù)，m為散列表長度，di為增量序列根據(jù)di的取法，解決沖突時常使用下面一些方法：線性探測再散列二次探測再散列偽隨機探測再散列假設(shè)哈希表的地址為0~m-1，則哈希表的長度為m。若一個關(guān)鍵字在地址d處發(fā)生沖突，則依次探查d+1，d+2，…，當(dāng)達到表尾m-1時，又從0，1，2，….開始探查，直到找到一個空閑位置來存儲沖突的關(guān)鍵字，將這一種方法稱為線性探測再散列。

Hi=(H(key)+di)MODmi=1,2,…,k(k≤m-1)H(key)為關(guān)鍵字key的哈希函數(shù)值，di=1,2,3,…,m-19.3.3解決沖突的方法例如:

給定關(guān)鍵字序列如下，散列函數(shù)為H(k)=k%1319，14，23，1，68，20，84，27，55，11，10，79試用線性探測再散列法建立散列表。(1)線性探測再散列9.3.3解決沖突的方法例如:

給定關(guān)鍵字序列如下，散列函數(shù)為H(k)=k%1319，14，23，1，68，20，84，27，55，11，10，79試用線性探測再散列法建立散列表。(1)線性探測再散列12345678910111201919%13=614%13=11423%13=10231%13=1168%13=36820%13=72084%13=68427%13=12755%13=35511%13=111110%13=101079%13=179該方法規(guī)定，若在d地址發(fā)生沖突，下一次探查位置為d+12，d-12,d+22,d-22,…,直到找到一個空閑位置為止。9.3.3解決沖突的方法

開放地址法充分利用了哈希表的空間，但在解決一個沖突時，可能造成新的沖突(聚集)。另外，用開放地址法解決沖突不能隨便對結(jié)點進行刪除。(2)二次探測再散列法12345678910111201919%13=614%13=11423%13=10231%13=1168%13=36820%13=72084%13=68427%13=12755%13=35511%13=111110%13=101079%13=1

鏈地址法也稱拉鏈法，是把相互發(fā)生沖突的同義詞用一個單鏈表鏈接起來，若干組同義詞可以組成若干個單鏈表。9.3.3解決沖突的方法