數(shù)據(jù)結(jié)構(gòu)（Java語言實(shí)現(xiàn)） 課件 第7章 查找

第7章查找結(jié)構(gòu)Java實(shí)據(jù)現(xiàn)數(shù)目錄CONTENTS7.1

查找的基本概念7.2靜態(tài)查找7.3動態(tài)查找7.6小結(jié)7.4B-樹和B+樹7.5哈希表7.1查找的基本概念1.查找表：是由同一種類型的數(shù)據(jù)元素構(gòu)成的集合。查找表中的數(shù)據(jù)元素是完全松散的，數(shù)據(jù)元素之間沒有直接的聯(lián)系。2.查找：根據(jù)關(guān)鍵字在特定的查找表中找到一個與給定關(guān)鍵字相同的數(shù)據(jù)元素的操作。如果在表中找到相應(yīng)的數(shù)據(jù)元素，則稱查找是成功的，否則稱查找是失敗的。。7.1查找的基本概念關(guān)鍵字與主關(guān)鍵字：數(shù)據(jù)元素中某個數(shù)據(jù)項(xiàng)的值。如果該關(guān)鍵字可以將所有的數(shù)據(jù)元素區(qū)別開來，也就是說可以唯一標(biāo)識一個數(shù)據(jù)元素，則該關(guān)鍵字被稱為主關(guān)鍵字，否則被稱為次關(guān)鍵字。靜態(tài)查找：指的是僅僅在數(shù)據(jù)元素集合中查找是否存在與關(guān)鍵字相等的數(shù)據(jù)元素。在靜態(tài)查找過程中的存儲結(jié)構(gòu)稱為靜態(tài)查找表。動態(tài)查找：在查找過程中，同時在數(shù)據(jù)元素集合中插入數(shù)據(jù)元素，或者在數(shù)據(jù)元素集合中刪除某個數(shù)據(jù)元素，這樣的查找稱為動態(tài)查找。動態(tài)查找過程中所使用的存儲結(jié)構(gòu)稱為動態(tài)查找表。7.1查找的基本概念學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力平均查找長度：是指在查找過程中，需要比較關(guān)鍵字的平均次數(shù)，它是衡量查找算法的效率標(biāo)準(zhǔn)。平均查找長度的數(shù)學(xué)定義為：ASL=。其中，Pi表示查找表中第i個數(shù)據(jù)元素的概率，Ci表示在找到第i個數(shù)據(jù)元素時，與關(guān)鍵字比較的次數(shù)。。7.2靜態(tài)查找學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力publicclassSSTable{DataTypelist[];intlength;finalintMAXSIZE=50;SSTable(intlength)

{list=newDataType[length+1];this.length=length;}}7.2.1順序表的查找順序表的查找是指從表的一端開始，逐個與關(guān)鍵字進(jìn)行比較，如果某個數(shù)據(jù)元素的關(guān)鍵字與給定的關(guān)鍵字相等，則查找成功，函數(shù)返回該數(shù)據(jù)元素所在的順序表的位置；否則查找失敗，返回0。7.2靜態(tài)查找學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力publicintSeqSearch(DataTypex)

//在順序表中查找關(guān)鍵字為x的元素，如果找到返回該元素在表中的位置，否則返回0

{

inti=1;

while(i<=length&&list[i].key!=x.key)//從順序表的第一個元素開始比較

i++;

if(i>length)

return0;

else

returni;

}7.2靜態(tài)查找publicintSeqSearch2(DataTypex)

//設(shè)置監(jiān)視哨list[0]，在順序表中查找關(guān)鍵字為x的元素，如果找到返回該元素在表中的位置，否則返回0

{

inti=length;

list[0]=x;//將關(guān)鍵字存放在第0號位置，防止越界

while(list[i].key!=x.key)//從順序表的最后一個元素開始向前比較

i--;

returni;

}7.2靜態(tài)查找假設(shè)表中有n個數(shù)據(jù)元素，且數(shù)據(jù)元素在表中出現(xiàn)的概率都相等即，則順序表在查找成功時的平均查找長度為：ASL成功===即查找成功時平均比較次數(shù)約為表長的一半。在查找失敗時，即要查找的元素沒有在表中，則每次比較都需要進(jìn)行n+1次。7.2靜態(tài)查找7.2.2有序順序表的查找對于有序順序表的查找有兩種方法：順序查找和折半查找。1.順序查找有序順序表的順序查找算法與順序表的查找算法類似。但是在通常情況下，不需要比較表中的所有元素。如果要查找的元素在表中，則返回該元素的序號，否則返回0。7.2靜態(tài)查找publicintSeqSearch3(DataTypex)

//在有序順序表中查找關(guān)鍵字為x的元素，監(jiān)視哨為list[0]，如果找到返回該元素在表中的位置，否則返回0

{

inti=length;

list[0]=x;//將關(guān)鍵字存放在第0號位置，防止越界

while(list[i].key>x.key)//從有序順序表的最后一個元素開始向前比較

i--;

returni;

}7.2靜態(tài)查找假設(shè)表中有n個元素且要查找的數(shù)據(jù)元素在數(shù)據(jù)元素集合中出現(xiàn)的概率相等，查找成功時查找失敗時7.2靜態(tài)查找2.折半查找折半查找的前提條件是表中的數(shù)據(jù)元素有序排列。依次與表中間的元素進(jìn)行比較，如果找到與關(guān)鍵字相等的元素，則說明查找成功，否則利用中間位置將表分成兩段。如果查找關(guān)鍵字小于中間位置的元素值，則進(jìn)一步與前一個子表的中間位置元素比較；否則與后一個子表的中間位置元素進(jìn)行比較。重復(fù)以上操作，直到找到與關(guān)鍵字相等的元素，表明查找成功。如果子表為空表，表明查找失敗。折半查找又稱為二分查找。7.2靜態(tài)查找例如，一個有序順序表為(9,23,26,32,36,47,56,63,79,81)，如果要查找56。7.2靜態(tài)查找publicintBinarySearch(DataTypex)

//在有序順序表中折半查找關(guān)鍵字為x的元素，如果找到返回該元素在表中的位置，否則返回0

{

intlow=1;//設(shè)置待查找元素范圍的下界（左邊界）

inthigh=length;//設(shè)置待查找元素范圍的上界（右邊界）

while(low<=high){

intmid=(low+high)/2;

if(list[mid].key==x.key)//如果找到元素，則返回該元素所在的位置

returnmid;

elseif(list[mid].key<x.key)//如果mid所指示的元素小于關(guān)鍵字，則修改low指針

low=mid+1;

elseif(list[mid].key>x.key)//如果mid所指示的元素大于關(guān)鍵字，則修改high指針

high=mid-1;

}

return0;

}7.2靜態(tài)查找查找過程可以用圖7.2所示的二叉判定樹來表示。對于具有n個結(jié)點(diǎn)的有序表剛好能夠構(gòu)成一個深度為h的滿二叉樹，則有h=

。二叉樹中第i層的結(jié)點(diǎn)個數(shù)是2i-1，假設(shè)表中每個元素的查找概率相等，7.2靜態(tài)查找7.2.3索引順序表的查找通常將為順序表提供索引的表稱為索引表，索引表分為兩個部分：一個用來存儲順序表中每個單元的最大的關(guān)鍵字，另一個用來存儲順序表中每個單元的第一個元素的下標(biāo)。一個索引順序表如圖7.3所示。7.2靜態(tài)查找假設(shè)主表中的元素個數(shù)為n，并將該主表平均分為b個單元，且每個單元有s個元素，即b=n/s。如果表中的元素查找概率相等，則每個單元中元素的查找概率就是1/s，主表中每個單元的查找概率是1/b。如果用順序查找法查找索引表中的元素，則索引順序表查找成功時的平均查找長度為：7.2靜態(tài)查找如果主表中每個單元中的元素個數(shù)不相等的時候，就需要在索引表中增加一項(xiàng)，即用來存儲主表中每個單元元素的個數(shù)。將這種利用索引表示的順序表稱為不等長索引順序表。例如，一個不等長的索引表如圖7.4所示。7.3動態(tài)查找二叉排序樹也稱為二叉查找樹。二叉排序樹的查找是一種常用的動態(tài)查找方法。1.二叉排序樹的定義與查找所謂二叉排序樹，或者是一棵空二叉樹，或者二叉樹具有以下性質(zhì)：（1）如果二叉樹的左子樹不為空，則左子樹上的每一個結(jié)點(diǎn)的值都小于其對應(yīng)根結(jié)點(diǎn)的值；（2）如果二叉樹的右子樹不為空，則右子樹上的每一個結(jié)點(diǎn)的值都大于其對應(yīng)根結(jié)點(diǎn)的值；（3）該二叉樹的左子樹和右子樹也滿足性質(zhì)（1）和（2），即左子樹和右子樹也是一棵二叉排序樹。7.3.1二叉排序樹7.3動態(tài)查找圖7.5所示為一棵二叉排序樹。圖中的每個結(jié)點(diǎn)是對應(yīng)元素關(guān)鍵字的值。采用二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)，二叉排序樹的類型定義如下：classBTNode{intdata;BTNodelchild,rchild;BTNode(intdata)

{this.data=data;this.lchild=this.rchild=null;}BTNode()

{}}7.3動態(tài)查找publicBTNodeBSTSearch(intx)

//二叉排序樹的查找，如果找到元素x，則返回指向結(jié)點(diǎn)的指針，否則返回null

{

BTNodep=root;

if(root!=null)//如果二叉排序樹不為空

p=root;

while(p!=null){

if(p.data==x)//如果找到，則返回指向該結(jié)點(diǎn)的指針

returnp;

elseif(x<p.data)//如果關(guān)鍵字小于p指向的結(jié)點(diǎn)的值，則在左子樹中查找

p=p.lchild;

else

p=p.rchild;//如果關(guān)鍵字大于p指向的結(jié)點(diǎn)的值，則在右子樹中查找

}

returnnull;

}7.3.1二叉排序樹的查找7.3動態(tài)查找左邊的圖的平均查找長度為ASL成功=1/7×(1+2×2+4×3)=17/7，右邊的圖的平均查找長度為ASL成功=1/7×(1+2+3+4+5+6+7)=28/7圖7.6所示為兩棵二叉排序樹，其元素的關(guān)鍵字序列分別是{57,21,71,12,51,67,76}和{12,21,51,57,67,71,76}。7.3動態(tài)查找假設(shè)當(dāng)前結(jié)點(diǎn)指針cur為空，則說明查找失敗，需要插入結(jié)點(diǎn)。如果parent.data小于要插入的結(jié)點(diǎn)x，則需要將parent的左指針指向x，使x成為parent的左孩子結(jié)點(diǎn)。如果parent.data大于要插入的結(jié)點(diǎn)x，則需要將parent的右指針指向x，使x成為parent的右孩子結(jié)點(diǎn)。如果二叉排序樹為空樹，則使當(dāng)前結(jié)點(diǎn)成為根結(jié)點(diǎn)。插入操作都是在葉子結(jié)點(diǎn)處進(jìn)行的。2.二叉排序樹的插入操作7.3動態(tài)查找對于一個關(guān)鍵字序列{37,32,35,62,82,95,73,12,5}，二叉樹的創(chuàng)建過程如下2.二叉排序樹的插入操作7.3動態(tài)查找publicvoidBSTInsert2(intx)

//叉排序樹的插入操作，如果樹中不存在元素x，則將x插入到正確的位置

{

BTNodep,cur,parent=null;

cur=root;

while(cur!=null){

if(cur.data==x)

return;

parent=cur;

if(x<cur.data)//如果關(guān)鍵字x小于cur指向的結(jié)點(diǎn)的值，則在左子樹中查找

cur=cur.lchild;

else//如果關(guān)鍵字x大于cur指向的結(jié)點(diǎn)的值，則在右子樹中查找

cur=cur.rchild;}

p=newBTNode(x);

if(parent==null)

root=p;

elseif(x<parent.data)

parent.lchild=p;

else

parent.rchild=p;

}7.3動態(tài)查找二叉排序樹的各種刪除情形如圖7.8所示。（1）如果s指向的結(jié)點(diǎn)為葉子結(jié)點(diǎn)，其左子樹和右子樹為空，刪除葉子結(jié)點(diǎn)不會影響到樹的結(jié)構(gòu)特性，因此只需要修改p的指向即可。（2）如果s指向的結(jié)點(diǎn)只有左子樹或只有右子樹，在刪除了結(jié)點(diǎn)*s后，只需要將s的左子樹sL或右子樹sR作為f的左孩子即p.lchild=s.lchild或p.lchid=s.rchild。（3）如果s左子樹和右子樹都存在，在刪除結(jié)點(diǎn)S之前，二叉排序樹的中序序列為{…QLQ…XLXYLYSSRP…}，因此，在刪除了結(jié)點(diǎn)S之后，有兩種方法調(diào)整使該二叉樹仍然保持原來的性質(zhì)不變。3.二叉排序樹的刪除操作7.3動態(tài)查找3.二叉排序樹的刪除操作7.3動態(tài)查找【例7.1】給定一組元素序列{37,32,35,62,82,95,73,12,5}，利用二叉排序樹的插入算法創(chuàng)建一棵二叉排序樹，然后查找元素值為32的元素，并刪除該元素，然后以中序序列輸出該元素序列。中序遍歷二叉排序樹得到的序列為：51232353762738295請輸入要查找的元素：32二叉排序樹查找，關(guān)鍵字32存在！刪除32后，二叉樹排序樹元素序列：5123537627382957.3動態(tài)查找1.平衡二叉樹的定義平衡二叉樹或者是一棵空二叉樹，或者是具有以下性質(zhì)的二叉樹：平衡二叉樹的左子樹和右子樹的深度之差的絕對值小于等于1，且左子樹和右子樹也是平衡二叉樹。平衡二叉樹也稱為AVL樹。7.3.2平衡二叉樹7.3動態(tài)查找失去平衡的二叉排序樹類型及調(diào)整方法可以歸納為以下四種情形。（1）LL型。LL型是指在離插入點(diǎn)最近的失衡結(jié)點(diǎn)的左子樹的左子樹中插入結(jié)點(diǎn)，導(dǎo)致二叉排序樹失去平衡。如圖7.13所示。可以使結(jié)點(diǎn)A作為結(jié)點(diǎn)B的右子樹，結(jié)點(diǎn)B的右子樹作為結(jié)點(diǎn)A的左子樹。這樣就恢復(fù)了該二叉排序樹的平衡，這相當(dāng)于以結(jié)點(diǎn)B為軸，對結(jié)點(diǎn)A進(jìn)行順時針旋轉(zhuǎn)。7.3.2二叉排序樹的平衡化處理7.3動態(tài)查找（2）LR型。LR型是指在離插入點(diǎn)最近的失衡結(jié)點(diǎn)的左子樹的右子樹中插入結(jié)點(diǎn)，導(dǎo)致二叉排序樹失去平衡。如圖7.14所示。使結(jié)點(diǎn)B作為結(jié)點(diǎn)C的左子樹，結(jié)點(diǎn)C的左子樹作為結(jié)點(diǎn)B的右子樹。將結(jié)點(diǎn)C作為新的根結(jié)點(diǎn)，結(jié)點(diǎn)A作為C的右子樹的根結(jié)點(diǎn)，結(jié)點(diǎn)C的右子樹作為A的左子樹。這相當(dāng)于以結(jié)點(diǎn)B為軸，對結(jié)點(diǎn)C先做了一次逆時針旋轉(zhuǎn)；然后以結(jié)點(diǎn)C為軸對結(jié)點(diǎn)A做了一次順時針旋轉(zhuǎn)。7.3動態(tài)查找（3）RL型。RL型是指在離插入點(diǎn)最近的失衡結(jié)點(diǎn)的右子樹的左子樹中插入結(jié)點(diǎn)，導(dǎo)致二叉排序樹失去平衡。如圖7.15所示。7.3動態(tài)查找（4）RR型。RR型是指在離插入點(diǎn)最近的失衡結(jié)點(diǎn)的右子樹的右子樹中插入結(jié)點(diǎn)，導(dǎo)致二叉排序樹失去平衡。如圖7.16所示。為了使二叉樹恢復(fù)平衡且保持二叉排序樹的性質(zhì)不變，可以使結(jié)點(diǎn)結(jié)點(diǎn)A作為B的左子樹的根結(jié)點(diǎn)，結(jié)點(diǎn)B的左子樹作為A的右子樹。這樣就恢復(fù)了該二叉排序樹的平衡。這相當(dāng)于以結(jié)點(diǎn)B為軸，對結(jié)點(diǎn)A做了一次逆時針旋轉(zhuǎn)。7.3動態(tài)查找1．紅黑樹的定義紅黑樹是一棵具有以下特點(diǎn)的二叉查找樹：（1）每個結(jié)點(diǎn)不是紅色，就是黑色；（2）根結(jié)點(diǎn)的顏色為黑色；（3）葉子結(jié)點(diǎn)是空節(jié)點(diǎn)且為黑色；（4）若一個結(jié)點(diǎn)是紅色的，則孩子結(jié)點(diǎn)一定是黑色的，即從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑中，不存在連續(xù)的紅色結(jié)點(diǎn)；（5）從任何一個結(jié)點(diǎn)出發(fā)到葉子結(jié)點(diǎn)的路徑上，包含相同數(shù)目的黑色結(jié)點(diǎn)。7.3動態(tài)查找1）紅黑樹的插入

假設(shè)插入的結(jié)點(diǎn)為T，其雙親結(jié)點(diǎn)P為紅色的，則P的雙親結(jié)點(diǎn)是黑色的。（1）T的雙親結(jié)點(diǎn)P的兄弟結(jié)點(diǎn)U是黑色的情況以P為軸進(jìn)行一次順時針旋轉(zhuǎn)，使P成為G的雙親結(jié)點(diǎn)，G成為P的右孩子結(jié)點(diǎn)，并將P和G重新著色。7.3動態(tài)查找1）紅黑樹的插入對于LR型紅黑樹，以P為軸進(jìn)行逆時針旋轉(zhuǎn)，再以T為軸進(jìn)行順時針旋轉(zhuǎn)，使T成為P的雙親結(jié)點(diǎn)，P和G分別成為T的左、右孩子結(jié)點(diǎn)，將T和G重新著色，T著色為黑色，G著色為紅色7.3動態(tài)查找1）紅黑樹的插入（2）T的雙親結(jié)點(diǎn)P的兄弟結(jié)點(diǎn)U是紅色的情況7.3動態(tài)查找2）紅黑樹的刪除若刪除的結(jié)點(diǎn)D的左孩子結(jié)點(diǎn)DL或右孩子結(jié)點(diǎn)DR為紅色，在刪除D后，使DL或DR替換結(jié)點(diǎn)D的結(jié)點(diǎn)，并標(biāo)記為黑色結(jié)點(diǎn)。7.3動態(tài)查找2）紅黑樹的刪除若刪除的結(jié)點(diǎn)D為黑色結(jié)點(diǎn)，且其兄弟結(jié)點(diǎn)S也是黑色的。7.4B-樹與B+樹7.4.1B-樹1.B-樹的定義B-是一種平衡的排序樹，也稱為m路（階）查找樹。一棵m階B-樹或者是一棵空樹，或者是滿足以下性質(zhì)的m叉樹：（1）樹中的任何一個結(jié)點(diǎn)最多有m棵子樹。（2）如果根結(jié)點(diǎn)或者是葉子結(jié)點(diǎn)，或者至少有兩棵子樹。（3）除了根結(jié)點(diǎn)之外，所有的非葉子結(jié)點(diǎn)至少應(yīng)有棵子樹。（4）所有的葉子結(jié)點(diǎn)處于同一層次上，且不包括任何關(guān)鍵字信息。（5）所有的非葉子結(jié)點(diǎn)的結(jié)構(gòu)如下：7.4B-樹與B+樹例如，一棵深度為4的4階B-樹如圖7.17所示。7.4B-樹和B+樹3.B-樹的插入操作例如，圖7.18所示為一棵3階B-樹（省略了葉子結(jié)點(diǎn)），在該B-樹中依次插入關(guān)鍵字35、25、78和43。7.4B-樹和B+樹3.B-樹的插入操作插入關(guān)鍵字35：首先需要從根結(jié)點(diǎn)開始，確定關(guān)鍵字42應(yīng)插入的位置應(yīng)該是結(jié)點(diǎn)E。插入后B-樹如圖7.19所示。7.4B-樹和B+樹3.B-樹的插入操作插入關(guān)鍵字25：從根結(jié)點(diǎn)開始確定關(guān)鍵字25應(yīng)插入的位置為結(jié)點(diǎn)D。結(jié)點(diǎn)D分裂為兩個結(jié)點(diǎn)，關(guān)鍵字24被插入到雙親結(jié)點(diǎn)B中，關(guān)鍵字12被保留在結(jié)點(diǎn)D中，關(guān)鍵字25被插入到新生成的結(jié)點(diǎn)D’中，并使關(guān)鍵字24的右指針指向結(jié)點(diǎn)D’。7.4B-樹和B+樹4.B-樹的刪除操作B-樹的刪除操作有以下三種可能：（1）要刪除的關(guān)鍵字所在結(jié)點(diǎn)的關(guān)鍵字個數(shù)大于等于[m/2]

，則只需要將關(guān)鍵字Ki和對應(yīng)的指針Pi從該結(jié)點(diǎn)中刪除即可。7.4B-樹和B+樹3.B-樹的刪除操作（2）要刪除的關(guān)鍵字所在結(jié)點(diǎn)的關(guān)鍵字個數(shù)等于-1，而與該結(jié)點(diǎn)相鄰的兄弟結(jié)點(diǎn)（左兄弟或右兄弟）中的關(guān)鍵字個數(shù)大于-1將關(guān)鍵字89刪除后，需要將關(guān)鍵字73向上移動到雙親結(jié)點(diǎn)C中，并將關(guān)鍵字83下移到結(jié)點(diǎn)H中，得到如圖7.28所示的B-樹。7.4B-樹和B+樹3.B-樹的刪除操作（3）要刪除的關(guān)鍵字所在結(jié)點(diǎn)的關(guān)鍵字個數(shù)等于-1，而與該結(jié)點(diǎn)相鄰的兄弟結(jié)點(diǎn)（左兄弟或右兄弟）中的關(guān)鍵字個數(shù)也等于-1將關(guān)鍵字83刪除后，需要將關(guān)鍵字83的左兄弟結(jié)點(diǎn)的關(guān)鍵字69與其雙親結(jié)點(diǎn)中的關(guān)鍵字73合并到一起，得到如圖7.29所示的B-樹。7.4B-樹和B+樹7.4.2B+樹B+樹是B-樹的一種變型。它與B-樹的主要區(qū)別在于：（1）如果一個結(jié)點(diǎn)有n棵子樹，則該結(jié)點(diǎn)也必有n個關(guān)鍵字，即關(guān)鍵字個數(shù)與結(jié)點(diǎn)的子樹個數(shù)相等。（2）所有的非葉子結(jié)點(diǎn)包含子樹的根結(jié)點(diǎn)的最大或者最小的關(guān)鍵字信息，因此所有的非葉子結(jié)點(diǎn)可以作為索引。（3）葉子結(jié)點(diǎn)包含所有關(guān)鍵字信息和關(guān)鍵字記錄的指針，所有葉子結(jié)點(diǎn)中的關(guān)鍵字按照從小到大的順序依次通過指針鏈接。7.5哈希表7.5.1哈希表的定義用key表示元素的關(guān)鍵字，f表示對應(yīng)關(guān)系，則f(key)表示元素的存儲地址，將這種對應(yīng)關(guān)系f稱為哈希（Hash）函數(shù)，利用哈希函數(shù)可以建立哈希表。哈希函數(shù)也稱為散列函數(shù)。7.5哈希表7.5.2哈希函數(shù)的構(gòu)造方法1.直接定址法直接定址法就是直接取關(guān)鍵字的線性函數(shù)值作為哈希函數(shù)的地址。直接定址法可以表示如下：h(key)=x*key+y其中x和y是常數(shù)。直接定址法的計(jì)算比較簡單且不會發(fā)生沖突。由于這種方法會使產(chǎn)生的哈希函數(shù)地址比較分散，造成內(nèi)存的大量浪費(fèi)。7.5哈希表7.5.2哈希函數(shù)的構(gòu)造方法2.平方取中法平方取中法就是將關(guān)鍵字的平方得到的值的其中幾位作為哈希函數(shù)的地址。3.折疊法折疊法是將關(guān)鍵字平均分割為若干等分，最后一個部分如果不夠可以空缺，然后將這幾個等分疊加求和作為哈希地址。4.除留余數(shù)法除留余數(shù)法主要是通過對關(guān)鍵字取余，將得到的余數(shù)作為哈希地址。其主要方法為：設(shè)哈希表長為m，p為小于等于m的數(shù)，則哈希函數(shù)為h(key)=key%p。除留余數(shù)法是一種常用的求哈希函數(shù)方法。7.5哈希表4.除留余數(shù)法例如，給定一組關(guān)鍵字{75,149,123,183,230,56,37,91}，設(shè)哈希表長m為14，取p=13，則這組關(guān)鍵字的哈希地址存儲情況為：p如果沒有明確給出，一般取小于等于表長的最大質(zhì)數(shù)。7.5哈希表7.5.3處理沖突的方法處理沖突的方法比較常用的主要有：開放定址法、再哈希法和鏈地址法。1.開放定址法開放定址法就是利用哈希表中的空地址存儲產(chǎn)生沖突的關(guān)鍵字。當(dāng)沖突發(fā)生時，按照下列公式處理沖突：hi=(h(key)+di)%m,其中i=1,2,…,m-1其中，h(key)為哈希函數(shù)，m為哈希表長，di為地址增量。（1）線性探測再散列：在沖突發(fā)生時，地址增量di依次取1,2,…,m-1自然數(shù)列，即di=1,2,…,m-1。（2）二次探測再散列：di=12,-12,22,-22,…,k2,-k2。（3）偽隨機(jī)數(shù)再散列。7.5哈希表1.開放定址法（1）線性探測再散列：在沖突發(fā)生時，地址增量di依次取1,2,…,m-1自然數(shù)列，即di=1,2,…,m-1。（2）二次探測再散列：在沖突發(fā)生時，地址增量di依次取自然數(shù)的平方，即di=12,-12,22,-22,…,k2,-k2。（3）偽隨機(jī)數(shù)再散列：在沖突發(fā)生時，地址增量di依次取隨機(jī)數(shù)序列。7.5哈希表1.開放定址法例如，在長度為14的哈希表中，在將關(guān)鍵字183、123、230、91存放在哈希表中的情況如圖7.31所示。插入關(guān)鍵字149時，h(149)=149%13=6，產(chǎn)生沖突，利用線性探測再散列法解決沖突，即h1=(6+1)%14=7，將149存儲在單元7中。7.5哈希表2.再哈希法再哈希法就是在沖突發(fā)生時，利用另外一個哈希函數(shù)再次求哈希函數(shù)的地址，直到?jīng)_突不再發(fā)生為止，即：hi=rehash(key)，i=1,2,…,n其中，rehash表示不同的哈希函數(shù)。7.5哈希表3.鏈地址法鏈地址法就是將具有相同散列地址的關(guān)鍵字用一個線性鏈表存儲起來。例如，一組關(guān)鍵字序列{23,35,12,56,123,39,342,90,78,110}，按照哈希函數(shù)h(key)=key%13和鏈地址法處理沖突，其哈希表如圖7.35所示。7.5哈希表【例7.2】設(shè)哈希表的長度為15，哈希函數(shù)為H(k)=k%13，散列地址空間為0~14，對關(guān)鍵字序列（19,5,21,24,45,20,68,27,70,11,10），按線性探測再散列解決沖突的方法構(gòu)造哈希表，畫出構(gòu)造后的哈希表，并求出等概率下查找成功和查找不成功時的平均查找長度。對于關(guān)鍵字19，H(19)=19%13=6對于關(guān)鍵字5，H(5)=5%13=5對于關(guān)鍵字21，H(21)=21%13=8對于關(guān)鍵字24，H(24)=24%13=11對于關(guān)鍵字45，H(45)=45%13=6，沖突；利用線性探測再散列法處理沖突，d1=1，H1=(H(19)+1)%15=7。7.5哈希表【例7.2】設(shè)哈希表的長度為15，哈希函數(shù)為H(k)=k%13，散列地址空間為0~14，對關(guān)鍵字序列（19,5,21,24,45,20,68,27,70,11,10），按線性探測再