數(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é)果是唯一的。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查找的基本概念

(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ù)雜度衡量查找算法的優(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=

其中：

n是查找表長(zhǎng)度；Pi是查找第i個(gè)數(shù)據(jù)元素的概率;Ci是找到第i個(gè)數(shù)據(jù)元素所需進(jìn)行的比較次數(shù)。7.1查找的基本概念5.查找結(jié)構(gòu)各種數(shù)據(jù)結(jié)構(gòu)都涉及查找操作，如線性表、隊(duì)列、棧、樹(shù)與圖等。為提高查找效率，需要專門為查找操作設(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)查找算法(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)查找算法(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)查找算法對(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)查找算法缺點(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)查找算法圓形節(jié)點(diǎn)表示有序順序表中存在的元素矩形節(jié)點(diǎn)稱為失敗節(jié)點(diǎn)7.2靜態(tài)查找算法折半查找折半查找(BinarySearch)查找又稱為二分查找，它的效率較高。但有一定的條件限制：要求線性表必須采用順序存儲(chǔ)結(jié)構(gòu)，且表中元素必須按關(guān)鍵字有序。1.折半查找的基本思想首先將給定值key與有序表中間位置元素的關(guān)鍵字相比較，若相等，則查找成功，返回該元素的存儲(chǔ)位置；若不等，則所需查找的元素只能在中間元素以外的前半部分或后半部分中，然后在縮小的范圍中繼續(xù)進(jìn)行同樣的查找，如此重復(fù)直到找到為止，或者確定表中沒(méi)有所需要查找的元素，查找不成功，返回查找失敗的信息。7.2靜態(tài)查找算法2.折半查找的具體操作過(guò)程假設(shè)順序表ST是有序的。設(shè)兩個(gè)指針，一個(gè)是low，指示查找表第一個(gè)記錄的位置；另一個(gè)是high，指示查找表最后一個(gè)記錄的位置。初始時(shí)low=0，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ā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)查找算法【例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的數(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)查找算法key=21時(shí)的查找過(guò)程01234567891041220

21

355863

77

81

8798↑low↑mid

↑high查找范圍中間位置的數(shù)據(jù)元素的關(guān)鍵字與給定值key相比較，因?yàn)榍罢叽?，說(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)查找算法仍以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;//置區(qū)間初值

intmid；

while(low<=high)

{

mid=(low+high)/2;/*取中間位置*/7.2靜態(tài)查找算法

if(L.elem[mid].key==key) returnmid;/*查找成功返回所在位置*/

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

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

}

return-1;/*順序表中不存在待查元素*/}7.2靜態(tài)查找算法4.折半查找的性能分析長(zhǎng)方形節(jié)點(diǎn)為判定樹(shù)外部節(jié)點(diǎn)，由判定樹(shù)中所有節(jié)點(diǎn)的空指針域上的指針指向它葉節(jié)點(diǎn)表示查找不成功的情況圓形節(jié)點(diǎn)表示一個(gè)記錄，節(jié)點(diǎn)中的值為該記錄在表中的位置7.2靜態(tài)查找算法4.折半查找的性能分析判定樹(shù)特點(diǎn)：中序序列是一個(gè)有序序列，為二分查找的初始序列，所有的根節(jié)點(diǎn)值大于左子樹(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í)的查找長(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)查找表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)查找表3.二叉排序樹(shù)的查找算法二叉排序樹(shù)的查找是從根節(jié)點(diǎn)開(kāi)始，沿某一個(gè)分支逐層向下進(jìn)行比較：（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)查找表3.二叉排序樹(shù)的查找算法算法7.3二叉排序樹(shù)的遞歸查找算法BiTreeSearchBST(BTNodeT,KeyTypekey)/*在二叉排序樹(shù)T中查找關(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)查找表算法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)查找表

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)查找表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)查找表算法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;7.3動(dòng)態(tài)查找表s->lchild=s->rchild=NULL;if(!p) returns;/*插入為根結(jié)點(diǎn)*/elseif(key<p->key)p->lchild=s; elsep->rchild=s; } returnT;}7.3動(dòng)態(tài)查找表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，取H(key)=k，在100個(gè)內(nèi)存單元中只存放9個(gè)元素，利用率很低。若將內(nèi)存單元的個(gè)數(shù)減少為11，取哈希函數(shù)H(key)=key%n，則有：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=801234567891022113252764120107.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哈希表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)造的哈希表：0123456789102040506090直接定址法計(jì)算簡(jiǎn)單，不會(huì)產(chǎn)生沖突，適合關(guān)鍵字分布基本連續(xù)的情況，若關(guān)鍵字分布不連續(xù)，將造成存儲(chǔ)空間的浪費(fèi)。7.4哈希表(2)除留取余法該方法是將關(guān)鍵字key除以一個(gè)不大于哈希表長(zhǎng)度的正整數(shù)p，將所得余數(shù)作為哈希表的地址。通常情況下，為了有效減少哈希沖突，確定哈希表長(zhǎng)度m后，p選取不大于m的最大的質(zhì)數(shù)，利用哈希函數(shù)H(key)=key%p把關(guān)鍵字轉(zhuǎn)換成哈希地址。例如，元素集合{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次哈希沖突；當(dāng)p取7時(shí)，就會(huì)產(chǎn)生3次沖突。7.4哈希表3.選用哈希函數(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)求地址序列：

H1,H2,…,Hk

其中：1≤k≤m-1Hi=(H(key)+di)%m，

其中：H(key)為哈希函數(shù); m為哈希表長(zhǎng);di為增量序列7.4哈希表開(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è)空閑單元，存放該關(guān)鍵字。線性探測(cè)法可能會(huì)使第i個(gè)哈希地址的同義詞存入第i+1個(gè)哈希地址中，這樣本應(yīng)存入第i+1個(gè)哈希地址的元素就爭(zhēng)奪第i+2個(gè)哈希地址的元素的地址，以此類推，從而造成大量元素在相鄰的哈希地址上“聚集”(或堆積)起來(lái)，大大降低了查找效率。7.4哈希表例如，哈希表表長(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=4H1=(H(79)+1)%10=0H5=(H(2)+5)%10=701234567892213456529427927.4哈希表(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哈希表例如，若有關(guān)鍵字集合{47，7，29，11，16，92，22，8，3}，哈希表表長(zhǎng)m為11，哈希函數(shù)為H(key)=key%11，用二次探測(cè)法處理沖突。012345678910114792167292283關(guān)鍵字3，H(3)=3，哈希地址發(fā)生沖突，有H1=(H(3)+12)%11=4，仍然沖突；H2=(H(3)-12)%11=2，找到空的哈希地址，將3存入。7.4哈希表2.鏈地址法鏈地址法是把具有相同散列地址的關(guān)鍵字(它們都是同義詞)記錄用一個(gè)單鏈表鏈在一起，組成同義詞鏈表