8.1

基本概念與術(shù)語

8.2靜態(tài)查找表8.3動(dòng)態(tài)查找表8.4哈希表查找8.5小結(jié)與習(xí)題第八章查找1本章主要內(nèi)容本章主要學(xué)習(xí)靜態(tài)查找和動(dòng)態(tài)查找方法。靜態(tài)查找包括順序查找、二分查找和分塊索引查找等，動(dòng)態(tài)查找包括二叉排序樹、B樹等。作為重點(diǎn)內(nèi)容本章還介紹了哈希查找及相關(guān)知識(shí)。查找是數(shù)據(jù)結(jié)構(gòu)中的重要操作，好的查找方法會(huì)大大提高執(zhí)行效率。通過本章學(xué)習(xí)，應(yīng)掌握以下內(nèi)容：

查找的有關(guān)概念；

靜態(tài)查找；

動(dòng)態(tài)查找；

哈希查找。

2查找就是指在給定的一組數(shù)據(jù)中對(duì)某個(gè)數(shù)值進(jìn)行查詢的過程。關(guān)鍵字是數(shù)據(jù)元素（或記錄）中某個(gè)項(xiàng)或組合項(xiàng)的數(shù)值，它可以標(biāo)識(shí)一個(gè)數(shù)據(jù)元素或記錄。主關(guān)鍵字將能唯一確定一個(gè)數(shù)據(jù)元素（或記錄）的關(guān)鍵字。查找表是由具有相同類型的數(shù)據(jù)元素（或記錄）組成的集合。分為靜態(tài)查找表和動(dòng)態(tài)查找表兩大類。如果查找表中能夠找到滿足條件的記錄，稱為查找成功，否則稱為查找不成功。8.1基本概念與術(shù)語3

靜態(tài)查找表：在對(duì)查找表進(jìn)行操作時(shí)，不改變表的結(jié)構(gòu)，只進(jìn)行查找操作；

動(dòng)態(tài)查找表：在對(duì)查找表進(jìn)行操作時(shí)，可以改變?cè)摬檎冶淼慕Y(jié)構(gòu)，既可以進(jìn)行查找操作，又可以進(jìn)行插入、刪除等操作。8.2靜態(tài)查找表8.2.1靜態(tài)查找表結(jié)構(gòu)靜態(tài)查找表是由數(shù)據(jù)元素組成的線性表。其存儲(chǔ)結(jié)構(gòu)分為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種?？梢杂庙樞虮砘蚓€性鏈表來表示靜態(tài)查找表。48.2.1靜態(tài)查找表結(jié)構(gòu)

typedefintKeyType;typedefstruct{KeyTypekey;………}ElemType;typedefstruct{ElemTypeelem[MAXSIZE+1]；intlength；}SST；

typedefstructNODE{ElemTypedata；/*結(jié)點(diǎn)的數(shù)據(jù)域*/

structNODE*next；/*指針域*/

}NodeType；靜態(tài)查找表的順序存儲(chǔ)結(jié)構(gòu)定義靜態(tài)查找表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)定義58.2.2順序查找

順序查找又稱線性查找，它思路簡單、容易實(shí)現(xiàn)，是一種最基本的查找方法。其查找過程為：從查找表的一端開始，逐個(gè)進(jìn)行關(guān)鍵字與查找值的比較，若某個(gè)記錄的關(guān)鍵字值與給定值相等，則查找成功，給出數(shù)據(jù)元素在查找表中的位置；若將整個(gè)表查找完，仍未找到與給定值相同的關(guān)鍵字，則查找失敗，給出提示信息。6【算法8.1】順序查找intSearch_Seq(SSTST，KeyTypex){

ST.elem[0].key=x;/*設(shè)置監(jiān)護(hù)哨*/

i=ST.length;while(ST.elem[i].key!=x)i--;/*返回找到記錄的下標(biāo)或者0(查找不成功)*/

returni;}/*Search_Seq*/將查找過程中給定值和關(guān)鍵字比較的次數(shù)稱為查找長度。通常用平均查找長度ASL來衡量查找算法的優(yōu)劣。算法分析：7

平均查找長度：在查找成功時(shí)，平均查找長度ASL是指為確定數(shù)據(jù)元素在表中位置所進(jìn)行關(guān)鍵字比較次數(shù)的期望值。對(duì)一個(gè)含n個(gè)數(shù)據(jù)元素的表，查找成功時(shí)

ASL=Pi*Ci

n∑i=1

Pi為表中第i個(gè)數(shù)據(jù)元素的查找概率，Ci為表中第i個(gè)數(shù)據(jù)元素的關(guān)鍵字與給定值x相等時(shí)，需要比較的次數(shù)。設(shè)查找表長度為n，查找元素x和表中第i個(gè)元素關(guān)鍵字相等時(shí)，需要比較的次數(shù)為n-i+1，則平均查找長度為：ASL=Pi*（n-i+1）n∑i=18

設(shè)查找表中各元素的查找概率相等，即Pi=1/n，則上面的式子表示為：

n∑i=1ASL=（n-i+1）=１─ｎｎ＋１───

２當(dāng)查找成功時(shí)，順序查找的時(shí)間復(fù)雜度就是O(n)。

當(dāng)查找失敗時(shí)，關(guān)鍵字與給定值的比較次數(shù)總是n+1次。8.2.3二分查找

二分查找，也稱為折半查找，是對(duì)有序表進(jìn)行的一種高效率的線性查找。有序表是指數(shù)據(jù)元素按給定的關(guān)鍵字已經(jīng)是升序（或者是降序）的查找表。9

假設(shè)各記錄的關(guān)鍵字是由小到大排序的，算法的實(shí)現(xiàn)過程為：在待查找的有序表中，將中間元素首先與給定值進(jìn)行比較，若相等，則表示查找成功；若給定值小于中間元素的關(guān)鍵字，則在左邊的區(qū)域中繼續(xù)查找；若給定值大于中間元素的關(guān)鍵字，則在右邊的區(qū)域中繼續(xù)查找。重復(fù)上述過程，直到查找成功或者查找失敗，查找的過程隨之結(jié)束。例在給定的序列A={6，13，17，20，24，28，30，36，39，44，48，51，55}中查找給定值13和52這兩個(gè)數(shù)據(jù)。⑴查找關(guān)鍵字為13的過程10

6131720242830363944485155第一次

low=1

mid=7high=13因x<30，下一步繼續(xù)在左半?yún)^(qū)查找，即：

012345678910111213第二次

low=1mid=3high=6因x<17，下一步繼續(xù)在左半?yún)^(qū)查找，即：

012345678910111213

6131720242830363944485155

613172024283036394448515511因x>6，下一步繼續(xù)在右半?yún)^(qū)查找。此時(shí)，low=2,high=2,mid=(2+2)/2=2。由于x=13,查找成功，所找到的記錄序號(hào)為2。

⑵查找關(guān)鍵字為52的過程第一次

low=1

mid=7high=13因x>30，下一步繼續(xù)在右半?yún)^(qū)查找，即：

012345678910111213第二次

low=8

mid=10high=13因x>44，下一步繼續(xù)在右半?yún)^(qū)查找，即：

012345678910111213

6131720242830363944485155

613172024283036394448515512第三次

low=11high=13mid=12因x>51，下一步繼續(xù)在右半?yún)^(qū)查找，即：

012345678910111213

第四次

low=mid=high=13因x<55，下一步繼續(xù)在左半?yún)^(qū)查找，此時(shí)，low=13,high=12，因?yàn)閘ow>high，所以查找失敗。

012345678910111213

6131720242830363944485155

613172024283036394448515513【算法8.2】二分查找intSearch_Bin(SSTST，KeyTypex){low=1；high=ST.length；while(low<=high)/*區(qū)間條件判斷*/{/*當(dāng)區(qū)間下限不高于上限時(shí)，進(jìn)行比較測試*/

mid=(low+high)/2；/*取中點(diǎn)*/

if(x<ST.elem[mid].key)

high=mid-1；/*查找區(qū)間縮小到左邊區(qū)域*/

elseif(x>ST.elem[mid].key)

low=mid+1；/*查找區(qū)間縮小到右邊區(qū)域*/

elsereturnmid;}returnERROR;}14算法分析：對(duì)于有序查找表，可采用建立二叉樹的方法：將表的中間元素作為二叉樹的根結(jié)點(diǎn)，比中間值小的所有結(jié)點(diǎn)全部在二叉樹的左子樹中，比中間值大的所有結(jié)點(diǎn)全部在二叉樹的右子樹中。按照這種思路建立的二叉樹稱為判定二叉樹。如圖所示。513928176445530244836132015時(shí)間復(fù)雜度：該算法的時(shí)間復(fù)雜度取決于該二叉樹中從根結(jié)點(diǎn)到該查找元素所在的結(jié)點(diǎn)的路徑上與中間結(jié)點(diǎn)的比較次數(shù)，即該元素結(jié)點(diǎn)在樹中的所在的層數(shù)。對(duì)于n個(gè)結(jié)點(diǎn)的判定樹，樹高為h，則有2h-1-1<n≤2h-1，即h-1<log2(n+1)≤h，所以h=int(log2(n+1))(int為取整函數(shù))。二分查找的平均查找長度（ASL）為：ASL=Pi*Ci

n∑i=1

=[1×20+2×21+…＋h×2h-1]=(n+1)n*log2(n+1)-1≈log2(n+1)-1所以，二分查找的時(shí)間復(fù)雜度為O(log2n)。168.2.4分塊查找二分查找適用于順序存儲(chǔ)的有序表查找，但并不是所有的查找表都是有序的。分塊查找又稱索引順序查找，其思想是先將查找表中的數(shù)據(jù)分成若干個(gè)塊，并為這若干個(gè)塊建立相應(yīng)的索引表，查找時(shí)通過將表分塊操作而提高效率。索引表的值包括兩個(gè)部分：關(guān)鍵字和指針，其中關(guān)鍵字部分存放的是某子表中的最大關(guān)鍵字值，指針部分存放的是對(duì)應(yīng)子表的起始位置，索引表中的表項(xiàng)必須以關(guān)鍵字字段有序排列。查找過程：首先查找索引表，確定關(guān)鍵字記錄所在的塊，然后在塊中順序查找。17【例8-2】設(shè)關(guān)鍵字集合為：96，40，12，33，81，4，58，45，39，64，18，85，17，57按關(guān)鍵字值33，58，96分為三個(gè)塊建立的查找表及其索引表。查找表索引表關(guān)鍵字字段

指針字段1335896611123341817405845395796816485說明：在分塊查找算法中，索引表中關(guān)鍵字的選取將對(duì)算法的優(yōu)劣度起到相當(dāng)大的作用，若能夠使各子表中紀(jì)錄個(gè)數(shù)基本項(xiàng)等，則可以提高算法效率。188.3動(dòng)態(tài)查找表動(dòng)態(tài)查找表將在查找的過程中對(duì)記錄的關(guān)鍵字進(jìn)行了插入或刪除等修改操作。8.3.1二叉排序樹

二叉排序樹屬動(dòng)態(tài)查找方法?？筛鶕?jù)相應(yīng)的二叉排序樹，實(shí)現(xiàn)對(duì)結(jié)點(diǎn)的查找。1．二叉排序樹定義二叉排序樹又稱為二叉查找樹，其定義是一個(gè)遞歸過程：它或者是一棵空樹；或者是具有下列性質(zhì)定義的二叉樹：59409975986049578861919⑴若左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；若右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于或等于根結(jié)點(diǎn)的值。⑵左右子樹都分別是一棵二叉排序樹。5940997598604957886198.3.2二叉排序樹的建立1.二叉排序樹的建立：由空集為初始狀態(tài)，將結(jié)點(diǎn)按關(guān)鍵字依次插入到排序二叉樹中去。先將第一個(gè)結(jié)點(diǎn)作為二叉樹的根結(jié)點(diǎn)，插入其它結(jié)點(diǎn)時(shí)，若結(jié)點(diǎn)的值小于根結(jié)點(diǎn)的值，則插入左子樹，否則插入右子樹，該過程依次進(jìn)行，直到整個(gè)過程結(jié)束。202.二叉排序樹的操作二叉排序樹的主要操作包括插入、查找、刪除等。(1)插入結(jié)點(diǎn)二叉排序樹插入結(jié)點(diǎn)的過程和二叉樹的建立過程中各結(jié)點(diǎn)的插入相似，即將一個(gè)元素插入到二叉排序樹中。(2)查找結(jié)點(diǎn)根據(jù)前面的定義可知，二叉排序樹的查找是一個(gè)遞歸的過程，具體如下：①若二叉排序樹為空，則查找失敗，輸出相關(guān)信息。②若二叉查找樹不為空，將給定值x與查找樹的根結(jié)點(diǎn)關(guān)鍵字進(jìn)行比較。21否則，完成下面的判斷：(i)若給定的值x小于根結(jié)點(diǎn)關(guān)鍵字的值，查找將按照遞歸的方式在左子樹上進(jìn)行。(ii)若給定的值x大于根結(jié)點(diǎn)關(guān)鍵字的值，查找將按照遞歸的方式在右子樹上進(jìn)行。(iii)重復(fù)以上過程，直到查找結(jié)束（成功或者失敗）。③若比較結(jié)果為相等，則查找成功，整個(gè)查找結(jié)束。22(3)刪除結(jié)點(diǎn)：當(dāng)刪除一個(gè)結(jié)點(diǎn)之后，原二叉樹的結(jié)構(gòu)可能發(fā)生變化，需要將其進(jìn)行相應(yīng)的調(diào)整。使其保持二叉排序樹的性質(zhì)。設(shè)準(zhǔn)備刪除的結(jié)點(diǎn)為p，其雙親結(jié)點(diǎn)為f，以下分三種情況進(jìn)行討論。(1)若結(jié)點(diǎn)p為葉子結(jié)點(diǎn)，刪去葉子結(jié)點(diǎn)后不影響整棵樹的特性，所以，只需將被刪除結(jié)點(diǎn)的雙親結(jié)點(diǎn)相應(yīng)指針域改為空指針。fpf刪除的結(jié)點(diǎn)為葉子結(jié)點(diǎn)的情況23(2)若結(jié)點(diǎn)p為非葉子結(jié)點(diǎn)，假設(shè)只有右子樹pr或只有左子樹pl，此時(shí)，只需將pr或pl替換f結(jié)點(diǎn)的p結(jié)點(diǎn)即可。如圖8-5所示。fpfpl刪除的結(jié)點(diǎn)p只有左子樹plfpfpr刪除的結(jié)點(diǎn)p只有右子樹pr24(3)若結(jié)點(diǎn)p既有左子樹pl又有右子樹pr，可按中序遍歷保持有序的原則進(jìn)行調(diào)整。調(diào)整方法有：①直接令pl為*r相應(yīng)的子樹，以pr為pl中序遍歷的最后一個(gè)結(jié)點(diǎn)pk的右子樹；②令p結(jié)點(diǎn)的直接前驅(qū)pr或直接后繼（對(duì)pl子樹中序遍歷的最后一個(gè)結(jié)點(diǎn)pk）替換p結(jié)點(diǎn)，再按②的方法刪去pr或pk。

對(duì)給定序列建立二叉排序樹時(shí)，若左右子樹分布均勻，則能提高查找效率。因此，對(duì)均勻的二叉排序樹進(jìn)行插入或刪除結(jié)點(diǎn)后，應(yīng)對(duì)其進(jìn)行調(diào)整，使其依然保持均勻。25(a)fpplprclslqlsrfclplslqlprsr（3）若結(jié)點(diǎn)p既有左子樹pl又有右子樹pr，如圖（a）所示，可按照中序遍歷保持有序的原則進(jìn)行調(diào)整。調(diào)整方法有以下兩種：1）

直接使左子樹pl為f的左子樹，再使pr為子樹pl中序遍歷最后一個(gè)結(jié)點(diǎn)的右子樹，如圖（b）所示。2）

26將p結(jié)點(diǎn)的直接前驅(qū)（或直接后繼）替換結(jié)點(diǎn)p，然后再從二叉排序樹中刪除它的直接前驅(qū)（或直接后繼），如圖（c）所示。fsrprclplslql(c)27【例8-3】記錄的關(guān)鍵字序列為：60，94，74，57，69，41，99，85，13，48，59，則構(gòu)造一棵二叉排序樹的過程如圖所示。6060947494607494605774946057697494605769417494605769419974946035769859941749460576985991341419974946048578569135941997494604857856913φ28【算法8.3】二叉排序樹的查找BTNode*BST_search(BTNode*t,intx)/*二叉排序樹的查找*/{BTNode*p=t;/*t為根結(jié)點(diǎn)*/

f=NULL;while(p!=NULL){if(x==p->key)returnp;/*查找結(jié)束*/

elseif(x<p->key){f=p;p=p->lchild;}/*在左子樹上查找*/

else{f=p;p=p->rchild;}

}/*在右子樹上查找*/

returnNULL;}29【算法8.4】二叉排序樹的建立BTNode*BST_Insert(BTNode*t,intx)/*在二叉排序樹上執(zhí)行插入操作*/{BTNode*s,*p=BST_search(t,x);if(p==NULL){s=(BTNode*)malloc(sizeof(BTNode));s->key=x;s->lchild=s->rchild=NULL;if(t==NULL)t=s;elseif(x<f->key)

f->lchild=s;/*生成左孩子*/

elsef->rchild=s;/*生成右孩子*/

}

returnt;}308.3.3平衡二叉樹（AVL樹）平衡二叉樹(BalancedBinaryTree)指的是形態(tài)勻稱的二叉樹，其定義是一個(gè)遞歸過程：它或是一棵空樹，或者是具有下列性質(zhì)的二叉排序樹：它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹高度之差的絕對(duì)值不超過1220054854960770100031對(duì)于非平衡二叉排序樹，希望通過適當(dāng)調(diào)整，使其成為平衡二叉樹，設(shè)A結(jié)點(diǎn)為失去平衡的最小子樹根結(jié)點(diǎn)，對(duì)該子樹進(jìn)行平衡化調(diào)整歸納起來有以下四種情況：1.LL型平衡旋轉(zhuǎn)當(dāng)在A的左子樹上插入結(jié)點(diǎn)，使A的平衡因子由1增至2而失去平衡，因此需要進(jìn)行一次順時(shí)針旋轉(zhuǎn)操作。如圖8-9(a)所示。AB1插入前，平衡AB2C插入結(jié)點(diǎn)，失去平衡AB0C順時(shí)針旋轉(zhuǎn)后，平衡322.RR型平衡旋轉(zhuǎn)由于在A的右子樹上插入結(jié)點(diǎn)，使A的平衡因子由-1增至-2而失去平衡，因此需要進(jìn)行一次逆時(shí)針旋轉(zhuǎn)操作。如圖所示。AB-1插入前平衡AB-2C插入結(jié)點(diǎn)失去平衡CB0A逆時(shí)針旋轉(zhuǎn)后平衡333.LR型平衡旋轉(zhuǎn)由于在A的左子樹的右子樹上插入結(jié)點(diǎn)，使A的平衡因子由1增至2而失去平衡，因此需要進(jìn)行兩次旋轉(zhuǎn)（先逆時(shí)針旋轉(zhuǎn)，再順時(shí)針旋轉(zhuǎn)）操作。如圖8-9(c)所示。AB1插入前平衡AC0B順時(shí)針旋轉(zhuǎn)使其平衡AB2C插入結(jié)點(diǎn)失去平衡AC2以C為軸逆時(shí)針旋轉(zhuǎn)B344.RL型平衡旋轉(zhuǎn)由于在A的右子樹的左子樹上插入結(jié)點(diǎn)，使A的平衡因子由-1增至-2而失去平衡，因此需要進(jìn)行兩次旋轉(zhuǎn)（先順時(shí)針旋轉(zhuǎn)，再逆時(shí)針旋轉(zhuǎn)）操作。如圖8-9(d)所示。-1插入前平衡ABAB-2CBC0A插入結(jié)點(diǎn)失去平衡逆時(shí)針旋轉(zhuǎn)使平衡AC-2以C為軸順時(shí)針旋轉(zhuǎn)B35【例8-4】設(shè)有數(shù)據(jù)序列{63，90，70，55，67，42，98}，試用這組數(shù)建立平衡二叉排序樹，如圖8-10所示。636390639070709063709063557090635567709063556742(e)

(f)

(g)失去平衡36(h)調(diào)整平衡(i)結(jié)束67906355704267906355704298平衡二叉樹的查找分析：在查找過程中將給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)不超過樹的深度。因此，在平衡樹上進(jìn)行查找的時(shí)間復(fù)雜度為O(log2n)。(等概率的提前下進(jìn)行的)378.3.4B樹如果查找需要在外存儲(chǔ)器上進(jìn)行，需要使用外部查找方法。1.B樹的定義一棵m階的B樹，或者為空樹，或?yàn)闈M足下列特性的m叉樹：⑴樹中每個(gè)結(jié)點(diǎn)至多有m棵子樹；⑵除非根結(jié)點(diǎn)為葉子結(jié)點(diǎn)，否則至少有兩棵子樹；⑶除根結(jié)點(diǎn)之外的所有非終端結(jié)點(diǎn)至少有m/2

棵子樹；⑷所有的非終端結(jié)點(diǎn)中包含以下信息數(shù)據(jù)：（n，A0，K1，A1，K2，…，Kn，An）38

其中：Ki（i=1,2,…,n）為關(guān)鍵字，且Ki<Ki+1，Ai為指向子樹根結(jié)點(diǎn)的指針(i=0,1,…,n)，且指針Ai-1所指子樹中所有結(jié)點(diǎn)的關(guān)鍵字均小于Ki(i=1,2,…,n)，An所指子樹中所有結(jié)點(diǎn)的關(guān)鍵字均大于Kn，m/2

1≤n≤m1，n為關(guān)鍵字的個(gè)數(shù)。⑸所有的葉子結(jié)點(diǎn)都出現(xiàn)在同一層次上，并且不帶信息。1L2DG3OSW3∧A∧B∧C∧2∧E∧F∧2∧H∧K∧2∧M∧N∧3∧P∧Q∧R∧3∧T∧U∧V∧3∧X∧Y∧Z∧圖8-11一棵5階的B-樹392．B樹基本操作

B樹的基本操作也是查找、插入和刪除等操作。現(xiàn)以B樹查找為例做簡單介紹。B樹的查找類似二叉排序樹的查找，所不同的是B樹每個(gè)結(jié)點(diǎn)上是多關(guān)鍵字的有序表，在到達(dá)某個(gè)結(jié)點(diǎn)時(shí)，先在有序表中查找，若找到，則查找成功；否則，按照對(duì)應(yīng)的指針信息指向的子樹中去查找，當(dāng)?shù)竭_(dá)葉子結(jié)點(diǎn)時(shí)，則說明樹中沒有對(duì)應(yīng)的關(guān)鍵字，查找失敗?？梢?，B樹上進(jìn)行查找的過程是一個(gè)順指針查找結(jié)點(diǎn)和在結(jié)點(diǎn)的關(guān)鍵字中進(jìn)行查找交叉進(jìn)行的過程。408.4哈希表查找8.4.1哈希表與哈希方法前面介紹的查找算法基本上都是建立在“比較”的基礎(chǔ)上。而數(shù)據(jù)元素的存儲(chǔ)位置與關(guān)鍵字之間不存在確定的關(guān)系，查找效率由每次比較縮小的查找范圍決定。哈希表（Hash）是由哈希函數(shù)生成的表示關(guān)鍵字與存儲(chǔ)位置之間關(guān)系的表。哈希函數(shù)是一個(gè)以關(guān)鍵字值為自變量，在關(guān)鍵字值與記錄存儲(chǔ)位置之間建立確定關(guān)系的函數(shù)。哈希函數(shù)的值，就是指定關(guān)鍵字對(duì)應(yīng)的存儲(chǔ)地址。41【例8-5】設(shè)有11個(gè)記錄的關(guān)鍵字，其值分別為6，37，12，21，69，31，16，33，41，13，51。選取關(guān)鍵字與記錄位置間的函數(shù)為Hash(key)=key%11建立的哈希查找表如下：331213693716651413121對(duì)于n個(gè)數(shù)據(jù)元素的集合，總能找到關(guān)鍵字與存放地址一一對(duì)應(yīng)的函數(shù)。但當(dāng)key1≠key2，而Hash(key1)=Hash(key2)時(shí)，即將不同的關(guān)鍵字映射到同一個(gè)哈希地址上，這種現(xiàn)象稱為沖突，映射到同一哈希地址上的關(guān)鍵字稱為同義詞?？梢哉f，沖突是不可能避免的，只能盡可能減少。因此選取適當(dāng)?shù)墓：瘮?shù)很關(guān)鍵。428.4.2常用的哈希函數(shù)1.直接定址法

Hash(key)=a*key+b(a、b為常數(shù))直接地址法取關(guān)鍵字的某個(gè)線性函數(shù)值為哈希地址?！纠?-6】

解放后，某農(nóng)作物年產(chǎn)量(單位：噸)序列為下表：1950年1951年1952年1953年1954年1955年……160萬240萬360萬540萬810萬1006萬……若選取哈希函數(shù)：

Hash(key)=key-1950，其中key取“年份”，則建立的哈希查找表如下：012345……195019511952195319541955……1602403605408101006……432.除留余數(shù)法

Hash(key)=key%p(p是一個(gè)整數(shù))即取關(guān)鍵字除以p的余數(shù)作為哈希地址。使用除留余數(shù)法，選取合適的p很重要，若哈希表表長為m，一般選取p≤m的質(zhì)數(shù)?！纠?-7】關(guān)鍵字集合為{34，21，78，52，16，46，33}，構(gòu)造哈希函數(shù)。選取哈希函數(shù)為Hash(key)=key%7，則存放如下：21781652463334

0123456443.數(shù)字分析法設(shè)關(guān)鍵字集合中，每個(gè)關(guān)鍵字均由m位組成，每位上可能有r種不同的符號(hào)。數(shù)字分析法根據(jù)r種不同的符號(hào)，在各位上的分布情況，選取某幾位，組合成哈希地址。所選的位應(yīng)使各種符號(hào)在該位上出現(xiàn)的頻率大致相同。【例8-8】有一組關(guān)鍵字如下：

2

7

40364

2

7

61487

2

7

52496

2

7

55470

2

7

57305分析：第1、2位均是“2和7”，第3位也只有“4、5、6”，因此，這幾位不能用，余下四位分布較均勻，可作為哈希地址選用。454.平方取中法對(duì)關(guān)鍵字平方后，按哈希表大小，取中間的若干位作為哈希地址。【例8-9】設(shè)有如下關(guān)鍵字序列{0100，0110，1010，1001，0111}，采用平方取中法建立哈希表。關(guān)鍵字平方取值0100001000010001100012100121101010201002011001100200102001110012321123則該關(guān)鍵字序列對(duì)應(yīng)的地址值分別為{100，121，201，020，123}。468.4.3處理沖突的方法1.開放定址法：當(dāng)由關(guān)鍵字得到的哈希地址發(fā)生了沖突，即該地址已經(jīng)存放了某數(shù)據(jù)元素時(shí)，就自動(dòng)尋找下一個(gè)空的內(nèi)存地址，只要哈希表足夠大，總能找到一個(gè)位置，將數(shù)據(jù)元素存入。

(1)線性探測法

Hi=(Hash(key)+di)%m(1≤i<m)其中：Hash(key)為哈希函數(shù)，m為哈希表長度，di

為增量序列1，2，……，m-1，且di=i【例8-11】關(guān)鍵字集為{47，7，29，11，16，92，22，8，3}，哈希表表長為11，

Hash(key)=key%11，用線性探測法處理沖突，如下所示：0123456789101122

47921637298

47存儲(chǔ)元素47、7后，再存儲(chǔ)29時(shí)，Hash(29)=7，哈希地址上沖突，由H1=(Hash(29)+1)%11=8，哈希地址8為空，將29存入；線性探測法可能使第i個(gè)哈希地址的同義詞存入第i+1個(gè)哈希地址，這樣本應(yīng)存入第i+1個(gè)哈希地址的元素變成了第i+2個(gè)哈希地址的同義詞，……，因此，可能出現(xiàn)很多元素在相鄰的哈希地址上“堆積”起來，大大降低了查找效率?？刹捎枚翁綔y法，或雙哈希函數(shù)探測法，以改善“堆積”問題。0123456789101122

47921637298

48

(2)二次探測法

Hi=(Hash(key)±di)modm其中：Hash(key)為哈希函數(shù)，m為哈希表長度，通常取m為4k+3的質(zhì)數(shù)，di

為增量序列12，-12，22，-22，……，q2，-q2且q≤(m-1)/2

當(dāng)對(duì)例8-11使用二次探測法處理沖突時(shí)，如果已經(jīng)將前8個(gè)數(shù)都存入相應(yīng)的位置，