《數(shù)據(jù)結(jié)構(gòu)與算法》第7章 查找

第7章查找7.1查找的基本概念

7.2順序表的查找

7.3樹表的查找

7.4哈希表及其查找7.1查找的基本概念查找 假定k1,k2,…,kn是互不相同的關(guān)鍵字值，有一個集合T，其中有n個記錄，形式如下：(k1，I1)，(k2，I2)，…，(kn，In)其中Ij是與關(guān)鍵字值kj相關(guān)的信息，1≤j≤n。給定一個特定的關(guān)鍵字值K，查找問題是在T中確定記錄（kj，Ij），使得kj

=K。查找表是記錄的集合，每個記錄至少包含一個關(guān)鍵字。查找實際上就是根據(jù)給定的關(guān)鍵字值，在查找表中找出一個記錄，該記錄的關(guān)鍵字值恰好等于給定的值。根據(jù)關(guān)鍵字匹配的情況，查找有兩種可能的結(jié)果：一種是找到了相應(yīng)的記錄，即找到至少一個關(guān)鍵字值為kj

的記錄使得kj=K，此稱為成功查找；一種是找不到相應(yīng)的記錄，稱為不成功查找。一般地，查找還分精確匹配查詢和范圍查詢兩種。所謂精確匹配查詢是指檢索關(guān)鍵字值完全匹配特定值的記錄。范圍查詢是指檢索關(guān)鍵字值在某個指定關(guān)鍵字值范圍的所有記錄。有的關(guān)鍵字，它的值一旦指定，就可以唯一地對應(yīng)著一條記錄，這種能夠唯一確定一條記錄的關(guān)鍵字稱為主關(guān)鍵字。所有主關(guān)鍵字的值均不相同，它們與記錄一一對應(yīng)。有些關(guān)鍵字的值指定以后，不能唯一地對應(yīng)一個記錄，而是可能對應(yīng)很多記錄，這樣的關(guān)鍵字稱為次關(guān)鍵字。根據(jù)數(shù)據(jù)存儲介質(zhì)的不同，查找又分為兩種類型。當數(shù)據(jù)量非常大，需要借助于外存存儲數(shù)據(jù)時，相應(yīng)的查找稱為外部查找。反之，全部數(shù)據(jù)都可以存放在內(nèi)存中時，相應(yīng)的查找稱為內(nèi)部查找。目前有三類檢索算法：分別是順序和列表方法、根據(jù)關(guān)鍵字值直接訪問和樹索引方法。順序和列表方法一般基于順序表，依據(jù)順序表中關(guān)鍵字的排列不同，又分為順序查找、折半查找及索引順序查找。根據(jù)關(guān)鍵字值直接訪問方法即哈希方法，又稱散列方法。樹索引方法包括二叉排序樹、B-樹等查找方法。7.2順序表的查找所謂順序表，其邏輯結(jié)構(gòu)即是線性表，存儲結(jié)構(gòu)多采用靜態(tài)存儲，也可以采用鏈表方式存儲。 采用數(shù)組存儲時，順序表的類定義如下：

template<classKeyType>searchList; //向前聲明

template<classKeyType> //節(jié)點類的定義

classElemType{

public:

friendclasssearchList<KeyType>; //聲明searchList類為節(jié)點類的友類

ElemType();

~ElemType();

private:

KeyTypekey;

};

template<classKeyType> //被檢索數(shù)據(jù)表類的定義

classsearchList{

public:

searchList();

~searchList();

int

search(KeyTypetarget); //檢索關(guān)鍵字為target的記錄

private:

ElemType<KeyType>*element;

int

MaxSize,CurrentSize;

}; 用鏈表表示順序表時，定義類如下：

template<classKeyType> //節(jié)點類的定義

classElemType{

public:

friendclasssearchList<KeyType>; //聲明友類

ElemType();

~ElemType();

private:

KeyTypekey;

ElemType<KeyType>*next;

}; template<classKeyType> //被檢索數(shù)據(jù)表類的定義

classsearchList{

public:

searchList();

~searchList();

ElemType<KeyType>*search(KeyType&target);

private:

ElemType<KeyType>*element;

int

CurrentSize;

};7.2.1順序查找順序查找是最簡單、最自然的查找方法，它的基本思想是用給定的關(guān)鍵字值與表中各個記錄的關(guān)鍵字值逐個進行比較。初始時，給定的關(guān)鍵字與表中第一個記錄的關(guān)鍵字相比較，若兩個值相等表示找到目標，查找成功；否則將關(guān)鍵字與表中下一個記錄的關(guān)鍵字繼續(xù)比較并判斷是否相等。如此循環(huán)。如果直到比較到最后一個記錄的關(guān)鍵字時兩個值都不相等，表明所存儲的數(shù)據(jù)中沒有要查找的數(shù)據(jù)，查找不成功。這種查找方法對順序存儲和鏈式存儲都是適用的。 順序查找算法如下：

template<classKeyType>

int

searchList<KeyType>::search(KeyTypetarget){ //成功，返回記錄所在下標，否則返回0

element[0].key=target; //下標為0的記錄為監(jiān)視哨

inti=CurrentSize;

while(element[i].key!=target){ //對記錄號從大到小，逐個查找

i--;

}

returni; //返回查找結(jié)果

};這個順序查找方法也適用于關(guān)鍵字值有重復(fù)的情況。當關(guān)鍵字值出現(xiàn)重復(fù)時，從while循環(huán)中退出后，i記錄的是查找目標在順序表中最后一次出現(xiàn)的位置。 當采用鏈表表示順序表時，順序查找方法如下：

template<classKeyType>

ElemType<KeyType>*searchList<KeyType>::search(KeyType&target){

//返回的是指向所查找節(jié)點的指針，若不成功，則為NULL

ElemType<KeyType>*p=element,q=NULL;

while(p!=NULL){

if(p->key!=target){

q=p;

p=p->next;

}

else{

break;

}

}

returnp;

};順序查找的效率如何呢？它在空間方面只要求一個記錄大小的輔助空間（即element[0]），自然是微不足道的。對于它的時間復(fù)雜度的分析，需要建立一個評價標準。這就是平均查找長度（AverageSearchLength）的概念。對于一個給定的關(guān)鍵字k值，在具有n個記錄的查找表中進行查找，最好的可能是經(jīng)過一次比較就能查到。在順序查找的情況下，最壞的可能是要經(jīng)過n次比較才能查到。為了表示在平均意義下的查找次數(shù)，定義平均查找長度為： 其中，n為表中記錄個數(shù)，Pi為查找第i個記錄的查找概率，Ci為查到第i個記錄時的比較次數(shù)。在我們給出的順序查找的算法中，Ci=n-i+1。假設(shè)查找表中每個記錄的概率相等，那么 。此時

這就是說，成功查找的平均查找長度為(n+1)/2。顯然，不成功查找的查找次數(shù)為n+1。這個結(jié)果表明：順序查找的平均查找長度與表中的記錄個數(shù)成正比，無論成功查找還是不成功查找，皆可記為O(n)。當所有關(guān)鍵字的出現(xiàn)頻率不一樣時，還可以進一步改進順序查找方法，使用關(guān)鍵字出現(xiàn)的頻率信息來組織記錄的排列：按照查找頻率從高到低排列記錄，先放置查找頻率最高的記錄，接下來是查找頻率次高的記錄，依此類推。這樣組織的表稱為自組織線性表。

對這樣的線性表，它的查找仍然是從第一個位置開始順序進行。由于各記錄依查找概率從大到小依次排列，所以查找的平均比較次數(shù)比(n+1)/2要少，查找需要的預(yù)期比較數(shù)目是：Cn=1P1+2P2+…+nPn

其中Pi

是訪問第i個記錄的概率。目前有三個傳統(tǒng)的啟發(fā)式規(guī)則：保持一個根據(jù)頻率排序的線性表最顯然的方式是為每一個記錄保存一個訪問計數(shù)，而且一直按照這個順序維護計數(shù)。這種方法稱為計數(shù)方法。當訪問頻率變化較大時，重排記錄會花費較多的時間。當找到一個記錄時就把它放到線性表的最前端，而把其它記錄后退一個位置。這類似于“最近最少使用”緩沖池替代策略，稱為移至前端方法。把找到的記錄與它在線性表中的前一個記錄交換位置，這種啟發(fā)式規(guī)則稱為轉(zhuǎn)置。7.2.2折半查找在順序存儲的條件下，若各記錄是按其關(guān)鍵字值的大小依次存放的，則這個查找表稱為有序表。在有序表中可采用折半查找（或稱為二分查找）的方法進行查找。設(shè)各記錄在表中按關(guān)鍵字值由小到大依次存放。折半查找的基本思想是：先取表的中間位置記錄的關(guān)鍵字與給定關(guān)鍵字的值進行比較，如果給定值正好與該記錄的關(guān)鍵字值相等，則查找成功；如果給定值比該記錄的關(guān)鍵字值大，則要查找的記錄一定在表的后半部分；如果給定值比該記錄的關(guān)鍵字值小，則要查找的記錄一定在表的前半部分。這樣，當還沒有查到目標時，都是在表的長度縮小一半后繼續(xù)進行查找，依此反復(fù)進行。在最壞的情況下，當表的長度縮小為1時，若該位置記錄的關(guān)鍵字仍然不等于給定的值，則可以肯定表中不存在所要找的記錄，于是宣布查找不成功。例：有如下11個元素的有序表（其數(shù)據(jù)元素的關(guān)鍵字為整數(shù)），現(xiàn)在要查找關(guān)鍵字為24的數(shù)據(jù)元素。假設(shè)指針low和high分別指向待查元素所在區(qū)間的下界和上界，指針mid指向該區(qū)間的中間位置，即：。 初始狀態(tài)如圖7.1。圖7.1二分查找初始狀態(tài)查找過程如圖7.2所示圖7.2關(guān)鍵字為24的二分查找過程如果給定關(guān)鍵字值k=86，在同樣的有序表上再看一看查找過程，見圖7.3。圖7.3關(guān)鍵字為86二分查找過程如圖7.3所示，經(jīng)過三次比較之后，mid=10，該位置的關(guān)鍵字值89>86，按規(guī)定應(yīng)在前半?yún)^(qū)間[low,mid-1]繼續(xù)查找，但此時新的區(qū)間上界mid-1=9，它已小于下界low=10，即新的區(qū)間已不存在，這就意味著查找表中根本沒有關(guān)鍵字值為86的元素，應(yīng)宣布查找不成功。折半查找的具體算法//折半查找template<classKeyType>int

searchList<KeyType>::BinSearch(KeyTypetarget){//若成功，返回記錄號，否則返回－1

intlow=1,high=CurrentSize; //置區(qū)間初值

intfound=0,mid; //置是否找到標記found為0（未找到）

while(low<=high&&!found){ //當區(qū)間下界未超過上界且未找到時，循環(huán)查找

mid=(low+high)/2; //求中點

if(element[mid].key==target){ found=1; //已找到，置標記found為1 }

else{ if(target>element[mid].key){ low=mid+1; //在后半?yún)^(qū)間繼續(xù)查找

} else{ high=mid-1; //在前半?yún)^(qū)間繼續(xù)查找

} } } if(found){ returnmid; //查找成功，返回找到的記錄的位置

} else{ return-1; //查找不成功，返回-1為標記

}};上述算法當成功查找時，能保證查找目標一定落在從low到high的區(qū)間內(nèi)，并不能保證找到的關(guān)鍵字值是有序表中的第一次出現(xiàn)。這個過程可用圖7.4表示：圖7.4二分查找過程示意修改程序中的while循環(huán)，得到如下實現(xiàn)：//修改后的折半查找template<classKeyType>int

searchList<KeyType>::BinSearch(KeyTypetarget){//若成功，返回記錄號，否則返回－1

intlow=1,high=CurrentSize; //置區(qū)間初值

intmid; while(low<high){ //當區(qū)間下界未超過上界時，循環(huán)查找

mid=(low+high)/2; //求中點

if(target>element[mid].key) low=mid+1; //在后半?yún)^(qū)間繼續(xù)查找

else high=mid; //在前半?yún)^(qū)間繼續(xù)查找

}; if(low==high) returnmid; //查找成功，返回找到的記錄的位置

else return-1; //查找不成功，返回-1為標記} //算法結(jié)束如果有序表中存在目標，則使用這個算法能夠得到目標在有序表中第一次出現(xiàn)的位置。這個過程如圖7.5所示。圖7.5折半查找過程示意折半查找的平均查找長度可以用二叉樹進行分析。我們?nèi)砸陨鲜龅木哂?1個元素的有序表為例，從折半查找過程可知，查到表中第6個位置僅需一次運算，找到第3和第9個位置各需要兩次運算，以此類推。查找過程如圖7.6所示。圖7.6用二叉樹分析折半查找性能6901113478125平均查找長度 設(shè)有序表的長度為n=2h-1，則描述折半查找過程的二叉樹為滿二叉樹，其深度h=log2(n+1)。在這棵二叉樹中，層次為1的結(jié)點有1個，層次為2的結(jié)點有2個，…，層次為h的結(jié)點有2h-1-1個?，F(xiàn)仍設(shè)表中每個記錄的查找概率相等，即Pi=1/n，則查找成功時折半查找的平均查找長度：由上式可見，當查找成功時折半查找的平均查找長度對n來說是對數(shù)級的。另外，當查找不成功時，折半查找算法必須從二叉樹的根走到葉才能知道，自然也是對數(shù)級的。當然，使用折半查找必須是在順序存儲方式下，且必須做到按記錄的關(guān)鍵字值排序才行。折半查找時的一個關(guān)鍵位置是查找區(qū)間的中間位置。修改這種方法，預(yù)先存儲記錄的關(guān)鍵字值的預(yù)期分布情況，查找時一般不從查找區(qū)間的中間位置開始，而是根據(jù)關(guān)鍵字值，預(yù)測出它的可能位置，然后再在該位置附近的小區(qū)間內(nèi)進行尋找。這種方法稱為字典檢索。7.2.3索引順序表的查找索引順序查找 又稱分塊查找，是順序查找方法的一種改進。改進辦法是將原來對所有n個記錄逐個查找，變?yōu)橄葘個記錄分成若干組，再建一個索引表。當給定一個關(guān)鍵字后，先通過查索引表確定應(yīng)在哪一組中查找，然后再在該組中順序查找，索引表必須按關(guān)鍵字有序?！鞍磯K有序” 各子表（塊）中第二塊中一切記錄的關(guān)鍵字必須大于第一塊中最大關(guān)鍵字，第三塊中一切記錄的關(guān)鍵字必須大于第二塊中最大關(guān)鍵字，依此類推，每塊內(nèi)部不要求按關(guān)鍵字有序。這種表的結(jié)構(gòu)如圖7.7所示。查找過程確定要找的記錄所在的塊（子表）在塊中順序查找圖7.7索引順序表的結(jié)構(gòu)示意圖平均查找長度 由于索引表是按關(guān)鍵字有序的，所以查索引表時可以用順序查找也可以用折半查找，而在子表內(nèi)只能用順序查找。分塊查找的平均查找長度也是這兩步平均查找長度之和，即為：ASL=Lb+Lw

其中Lb為查找索引表以確定所在塊的平均查找長度，Lw為在塊內(nèi)查找所要的記錄的平均查找長度。

現(xiàn)在的問題是如何分塊才能提高查找速度。我們假設(shè)對表中每個記錄的查找概率相等，并且假設(shè)分塊是均勻的。設(shè)有n個記錄，平均分為b塊，每塊含有s個記錄，即b=n/s。若查索引表和在塊內(nèi)查找均用順序查找，則

在n已確定的前提下，根據(jù)求一元函數(shù)最小值的方法，可以求出當s=時，ASL取最小值，且它的值為+1。7.3.1二叉排序樹二叉排序樹（binarysorttree）

它或是一棵空樹，或是具有下列性質(zhì)的二叉樹：若它的左子樹不空，則左子樹所有結(jié)點上記錄的關(guān)鍵字值均小于它的根結(jié)點上記錄的關(guān)鍵字值；若它的右子樹不空，則右子樹所有結(jié)點上記錄的關(guān)鍵字值均大于它的根結(jié)點上記錄的關(guān)鍵字值；它的左、右子樹也都是二叉排序樹。在圖7.8所示的兩棵樹都是二叉排序樹，在它們的結(jié)點上列出了所存記錄的關(guān)鍵字。(a)中關(guān)鍵字為整數(shù)，在(b)中關(guān)鍵字為字符串（姓氏的漢語拼音），這些關(guān)鍵字都是可以比較大小的。圖7.8二叉排序樹示例81213165610112371(a)(b)hanliuzhaoliduanfangduguochen二叉排序樹中的結(jié)點類說明如下：template<classKeyType>BST; //類的向前聲明template<classKeyType>classBstNode{ public: friendclassBST<KeyType>;

BstNode(); ~BstNode(); private:

KeyTypekey; //關(guān)鍵字值

BstNode<KeyType>*lchild,*rchild;//左右子樹指針};二叉排序樹的類的說明如下：template<classKeyType>classBST{ public: BST(); ~BST();

BstNode<KeyType>*search(KeyType

k,BstNode<KeyType>*ptr); private:

BstNode<DataType>*root;};二叉排序樹查找的基本思想

設(shè)要查找的目標為target，從根結(jié)點開始，如果根結(jié)點的關(guān)鍵字等于查找目標target，則查找成功，并返回指向目標的指針。如果目標target小于根結(jié)點的關(guān)鍵字值，則在它的左子樹繼續(xù)查找；如果目標target大于根結(jié)點的關(guān)鍵字值，則在它的右子樹繼續(xù)查找；依此類推。這個過程沿著從根到葉結(jié)點的一條路徑向下查找，查找過程中遇到空指針時表示查找失敗，二叉排序樹中不存在查找目標target。//二叉排序樹的查找template<classDataType>BstNode<KeyType>*BST<KeyType>::BstSearch(KeyType

target,BstNode<KeyType>*t){//返回指向所查找節(jié)點的指針，若不成功，則返回NULL

if((t==NULL)||(t->key==target)){ returnt; //當樹為空或者已經(jīng)找到節(jié)點時返回

} else{ if(t->key>target){ returnBstSearch(target,t->lchild);//搜索左子樹

} else{ returnBstSearch(target,t->rchild);//搜索右子樹

} }};template<classKeyType>BstNode<KeyType>*BST<KeyType>::Search(KeyTypetarget){

return(Search(target,root));};例：根據(jù)二叉排序樹的查找算法，在圖7.9所示的二叉排序樹中，分別查找關(guān)鍵字為61和37的結(jié)點。圖7.9二叉排序樹示例47569098153461875204135二叉排序樹的生成

二叉排序樹的生成就是從空樹開始依次將結(jié)點插入到樹中的過程。在一棵二叉排序樹中插入一個新結(jié)點的算法是：若二叉排序樹為空樹，則新結(jié)點為二叉排序樹的根結(jié)點；若二叉排序樹非空，則比較新結(jié)點的關(guān)鍵字值和根結(jié)點的關(guān)鍵字值，若新結(jié)點關(guān)鍵字小于根結(jié)點關(guān)鍵字，則新結(jié)點插入到根的左子樹中，否則插入到根的右子樹中。//二叉排序樹的插入算法template<classDataType>voidBST<KeyType>::BstInsert(KeyType

k,BstNode<KeyType>*t){ //插入結(jié)點的關(guān)鍵字為k，樹根為t

if(t==NULL){ t=newBstNode(); t->key=k; } else{ if(k<t->key){

BstInsert(k,t->lchild); } else{

BstInsert(k,t->rchild); } }}template<classKeyType>voidBST<KeyType>::Insert(KeyTypex){

BstInsert(x,root);}例：按照二叉排序樹的插入算法，在圖7.9所示的樹中依次插入關(guān)鍵字為58和17的兩個新結(jié)點。圖7.10二叉排序樹插入示例174756909815346187520413558若從空樹開始，依次插入關(guān)鍵字分別為e、b、d、f、a、c和g的結(jié)點，建立一棵二叉樹，則這棵樹的建立過程如圖7.11所示。圖7.11二叉排序樹的生成過程二叉排序樹的刪除 假設(shè)在二叉排序樹上要刪除的結(jié)點為x，它的雙親結(jié)點由指針f所指，不失一般性，設(shè)x為f的左孩子（若x為f的右孩子，刪除算法類似）。這時，分三種情況考慮：x為葉結(jié)點，此種情況最為簡單，刪除該結(jié)點后，只須令f的左孩子指針為空即可。即令f->lchild=NULL。這個過程如圖7.12所示。x只有左子樹LTree或只有右子樹RTree，刪除x結(jié)點后，只須令LTree或RTree直接成為其雙親結(jié)點f的左子樹即可。即令f->lchild=x->lchild，或f->lchild=x->rchild。x只有左子樹LTree的情況如圖7.13所示，x有右子樹Rtree的情況與此類似。圖7.12刪除二叉排序樹中的葉結(jié)點圖7.13刪除二叉排序樹中有一個孩子的分支結(jié)點x結(jié)點的左、右子樹均不空，這種情況比較復(fù)雜。因為刪除x所指的結(jié)點后，其左、右子樹不能全都連接在其雙親結(jié)點f的左孩子指針上，破壞了原來樹的結(jié)構(gòu)。必須找一個合適的方法，才能將LTree和RTree都安排妥當。為了保持樹的結(jié)構(gòu)，一般地是在樹中尋找另一個結(jié)點w來頂替被刪除的結(jié)點x，然后轉(zhuǎn)而刪除w。實際上，以w頂替x后，要保證滿足二叉排序樹的有序性。根據(jù)有序性，顯然只能由被刪結(jié)點的直接前趨或是直接后繼來頂替，以其余任何結(jié)點來頂替都會增加逆序?qū)Γ瑥亩荒軡M足有序性。

直接前趨和直接后繼 中序遍歷二叉樹時，左子樹上所有結(jié)點都位于根結(jié)點之前，右子樹上所有結(jié)點都位于根結(jié)點之后，而中序遍歷二叉排序樹時剛好得到一個有序的序列。這樣，根的左子樹中最后一個遍歷結(jié)點應(yīng)該是根的直接前趨，其右子樹中第一個遍歷結(jié)點應(yīng)該是根的直接后繼。任一結(jié)點的（中序遍歷的）直接前趨是其左子樹中的最后一個結(jié)點，即“右下角”，（中序遍歷的）直接后繼是其右子樹中的第一個結(jié)點，即“左下角”。根據(jù)剛才的分析，以w填充x的位置后，仍能保證二叉排序樹的特性。這樣刪除x就變?yōu)閯h除w。而w是x的直接前趨，它是x的左子樹中的右下角，它的右孩子指針為空，這意味著w的孩子結(jié)點個數(shù)最多為1。這種情況可以歸結(jié)為前述第一、二種情況。這個過程如圖7.14所示。圖7.14刪除二叉排序樹中有二個孩子的分支結(jié)點例：以7.10所示的二叉排序樹為例，分別刪除關(guān)鍵字35和90所在的結(jié)點。圖7.15二叉排序樹刪除示例二叉排序樹的刪除算法如下：template<classDataType>voidBST<KeyType>::BstDelete(KeyType

x,BstNode<KeyType>*&t){

BstNode<KeyType>*p,q;

if(t!=NULL) { if(t->key>x){

BstDelete(x,t->lchild); //搜索左子樹

} else{ if(t->key<x){

BstDelete(x,t->rchild); //搜索右子樹

} else{ if(t->lchild==NULL&&t->rchild==NULL){//左右子樹都為空

p=t; t=NULL; deletep; }

else{ if(t->lchild==NULL){//左子樹空，右子樹不為空，

p=t; t=t->rchild; deletep; } else{ if(t->rchild==NULL){//左子樹不空，右子樹為空

p=t; t=t->lchild; deletep; } else{ //左右子樹都不為空

p=t; q=t->lchild; //轉(zhuǎn)左子樹

while(q->rchild!=NULL){//向右到右下角

p=q; q=q->rchild; }

t->data=q->data;

if(p!=t){ p->rchild=q->lchild; //重新連接*p的右子樹

} else{ p->lchild=q->lchild; //重新連接*p的左子樹

} deleteq; //釋放結(jié)點

} } } } } }}template<classDataType>voidBST<KeyType>::BDelete(KeyTypek){

BstDelete(k,root);}查找效率

根據(jù)建樹的算法，當關(guān)鍵字個數(shù)一定時，所生成二叉排序樹的深度不僅與關(guān)鍵字個數(shù)有關(guān)，而且與這些關(guān)鍵字插入的次序有關(guān)。 二叉排序樹的深度不僅決定了查找中最大比較次數(shù)，也影響了平均查找長度?，F(xiàn)在仍假設(shè)對樹中7個關(guān)鍵字的查找概率相等，都是1/7，則圖7.11所示的樹的平均查找長度為

ASL(7.11)=(1+2+2+3+3+3+4)=18/7例：圖7.11所示的二叉排序樹中的關(guān)鍵字，如果關(guān)鍵字的插入次序改變了，會生成不同的二叉排序樹。圖7.16不同深度的二叉排序樹示例圖7.16(a)樹的平均查找長度為

ASL(7.16a)=(1+2+3+4+4+5+6)=25/7

實際上，圖7.11(b)樹已是單鏈形式，而圖7.11(c)更是退化為線性表，因此它們的平均查找長度與對順序表進行順序查找時的平均查找長度相同。一般來說，對于n個記錄，當它們的關(guān)鍵字隨機出現(xiàn)時，所構(gòu)成的二叉排序樹還是比較均衡的。可以證明，在這樣構(gòu)成的二叉排序樹上進行查找，其平均查找長度為O(log2n)。7.3.2平衡二叉樹1962年，Adel’son-Vel’skii和E.M.Landis提出了一種二叉樹結(jié)構(gòu)，這種二叉樹對于各級子樹的深度是比較平衡的，稱為平衡二叉樹、高平衡樹，又稱AVL樹。它滿足二叉排序樹的特性，樹型上也是比較平衡的，可以達到較高的查找效率。

平衡二叉樹

它或是一棵空樹，或是具有下列性質(zhì)的二叉排序樹：它的左子樹和右子樹的深度之差的絕對值不超過1；它的左、右子樹都是平衡二叉樹。平衡因子

該結(jié)點的左子樹的深度減去右子樹的深度。若某個結(jié)點的平衡因子出現(xiàn)大于1或小于-1的情況，說明平衡遭到破壞，需要將二叉排序樹進行調(diào)整，使之重新變?yōu)槠胶?。圖7.17所示的為平衡的二叉排序樹，圖7.18所示的為不平衡的二叉排序樹（'/'表示左子樹高1，'-'表示左右子樹等高，'\'表示右子樹高1）。圖7.17平衡的二叉排序樹圖7.18不平衡的二叉排序樹例：假設(shè)有一組關(guān)鍵字出現(xiàn)的次序為{k，m，u}，按照二叉排序樹的插入過程，從空樹開始，依次插入k，m，u三個關(guān)鍵字后，生成的樹如圖7.19(a)所示?；謴?fù)平衡后的二叉樹如圖7.19(b)所示。圖7.19平衡二叉排序樹的向左旋轉(zhuǎn)二叉平衡樹中結(jié)點的插入

假設(shè)由于在平衡二叉樹上插入一個結(jié)點以后，使得原來的二叉樹失去平衡，由上例可見，只須在局部調(diào)整某一子樹即可。設(shè)這棵失去平衡的最小子樹的根結(jié)點被指針root所指，對于這棵子樹可以分為四種情況進行調(diào)整。RR型 新結(jié)點插入在root結(jié)點右孩子的右子樹中，從而失去平衡。此時將root的右孩子right_tree上提為子樹的根結(jié)點，令root為right_tree的左孩子，right_tree的原右子樹T3保持不變，其左子樹T2變更為root的右子樹，根據(jù)二叉排序樹的特性，變換后的樹仍符合要求。這樣的調(diào)整稱為單旋轉(zhuǎn)，其調(diào)整過程如圖7.20所示。圖7.20AVL樹的單旋轉(zhuǎn)LL型

新結(jié)點插入在root結(jié)點的左孩子的左子樹中，從而失去平衡。此時將root的左孩子left_tree上提為子樹的根結(jié)點，令root為left_tree的右孩子，其余部分按二叉排序樹的要求進行相應(yīng)調(diào)整。LL型旋轉(zhuǎn)類似于RR型旋轉(zhuǎn)。RL型

新結(jié)點插入在root結(jié)點的右孩子的左子樹中，從而失去平衡。此時將root的右孩子right_tree的左孩子sub_tree提升為子樹的根結(jié)點，將root和right_tree分別作它的左、右孩子，其余部分按二叉排序樹的要求進行相應(yīng)調(diào)整。由二叉排序樹的特性可知，變換后的樹仍符合二叉排序樹的要求。這樣的變換稱為雙旋轉(zhuǎn)，其調(diào)整過程如圖7.21所示。圖7.21AVL樹的雙旋轉(zhuǎn)LR型 新結(jié)點插入在root結(jié)點的左孩子的右子樹中，從而失去平衡。此時將root的左孩子left_tree的右孩子sub_tree提升為子樹的根結(jié)點，將left_tree和root分別作為它的左、右孩子，其余部分按二叉排序樹的要求進行相應(yīng)調(diào)整。這個過程類似于RL旋轉(zhuǎn)。AVL樹中結(jié)點及樹的說明如下：//***********AVL樹**************///AVL樹結(jié)點的定義template<classKeyType>AVLTree;template<classKeyType>classAVLNode{public:

AVLNode(); ~AVLNode(); friendclassAVLTree<KeyType>; //聲明友類private:

KeyTypekey;

AVLNode*lchild,*rchild;

intbalance;};///AVL樹的定義template<classKeyType>classAVLTree{public:

AVLTree(); ~AVLTree();

int

Insert(KeyTypex); voidR_Rotate(); voidL_Rotate();private:

AVLNode*root;};AVL樹由失平衡到恢復(fù)平衡所進行的單旋轉(zhuǎn)操作如下，以RR型為例：///左單旋轉(zhuǎn)（RR型）template<classKeyType>voidAVLTree<KeyType>::L_Rotate(AVLNode*&Tree){

AVLNode*rightchild=Tree->rchild; Tree->rchild=rightchild->lchild;

rightchild->lchild=Tree; Tree->balance=0; //調(diào)整平衡因子

Tree=rightchild; //Tree指向新的根結(jié)點};AVL樹由失平衡到恢復(fù)平衡所進行的雙旋轉(zhuǎn)操作如下，以RL型為例：///雙旋轉(zhuǎn)（RL型）template<classKeyType>voidAVLTree<KeyType>::LeftBalance(AVLNode*&Tree){

AVLNode*leftchild=Tree->child;

AVLNode*rightchild;

switch(leftchild->balance){ //檢查左孩子的平衡因子

case1: //新插入結(jié)點在*leftchild的左子樹

Tree->balance=0; //調(diào)整平衡因子

leftchild->balance=0;

R_Rotate(Tree); //做右單旋轉(zhuǎn)

break; case-1://新插入結(jié)點在*leftchild的右子樹，要做雙旋轉(zhuǎn)

rightchild=leftchild->rchild;

switch(rightchild->balance){ //檢查*right的平衡因子以調(diào)整*Tree和*leftchild的平衡因子

case1: Tree->balance=-1;

leftchild->balance=0; break; case0: Tree->balance=0; leftchild.balance=0; break; case-1: Tree->balance=0;

leftchild->balance=1; break; }

rightchild->balance=0;

L_Rotate(Tree->lchild); //對*Tree的左子樹做左單旋轉(zhuǎn)

R_Rotate(root,root); //對*Tree做右單旋轉(zhuǎn)

}}在AVL樹中插入一個節(jié)點的實現(xiàn)如下：///AVL樹的插入template<classKeyType>int

AVLTree<KeyType>::Insert(AVLNode*&Tree,KeyType

x,int&taller){//在AVL樹Tree中插入關(guān)鍵字為x的結(jié)點，成功則返回1，否則返回0。//若因插入而使該AVL樹失去平衡，則作平衡旋轉(zhuǎn)處理。

intsuccess=0;

if(Tree==NULL){ //*Tree原為空樹或者某結(jié)點的空鏈域，插入新的結(jié)點。

Tree=newAVLNode(x); success=1; //插入成功標志

taller=1; //置taller為1，表示樹長高

} else{ if(x<Tree->key){ //應(yīng)該繼續(xù)在左樹中搜索插入位置

success=Insert(Tree->lchild,x,taller); if(success==0){ //未插入

returnsuccess; }

if(taller==1){ //已經(jīng)插入到左子樹，并且左子樹長高了

switch(Tree->balance){ //檢查*Tree的平衡因子

case1: //原先左子樹就比右子樹高，做平衡處理

LeftBalance(Tree); taller=0; //不長高

break; case0: //原左右子樹等高

Tree->balance=1; //改變平衡因子

taller=1; //長高

break; case-1: //原右子樹高，現(xiàn)在左右子樹等高

Tree->balance=0; //改變平衡因子

taller=0; //不長高

break; } } else{ if(x>Tree->key){ //在右子樹中搜索

success=Insert(Tree->rchild,x,taller); if(success==0){ //未插入

returnsuccess; }

if(taller==1){//已經(jīng)插入到右子樹，并且右子樹長高了

switch(Tree->balance){//檢查*Tree的平衡因子

case1: //原先左子樹高，現(xiàn)在左右子樹等高

Tree->balance=0;//改變平衡因子

taller=0; //不長高

break; case0: //原先左右子樹等高

Tree->balance=-1;//改變平衡因子

taller=1; //長高了

break; case-1://原先右子樹比較高，需要做平衡處理

RightBalance(Tree); taller=0; //不長高

break; } } } } } } returnsuccess; //返回是否成功的信息};例：在圖7.22(a)所示的平衡二叉樹中，插入結(jié)點65。圖7.22在平衡二叉樹中插入一個結(jié)點的變化過程二叉排序樹中的結(jié)點刪除

問題可以歸結(jié)為只需處理最多有一個孩子的結(jié)點的刪除問題，不失一般性，這里也僅討論AVL樹中最多有一個孩子的結(jié)點的刪除問題。如果要刪除有兩個孩子的結(jié)點，我們可以先用其直接前趨或是直接后繼結(jié)點頂替它，然后再刪除頂替它的這個結(jié)點。而這個結(jié)點最多只有一個孩子。 假設(shè)被刪除結(jié)點為x，樹根為root。以從x的父結(jié)點到root的路徑上的每個結(jié)點p為根的子樹的高度可能因刪除x而變矮，結(jié)點的平衡因子也會隨之改變，從而樹失平衡。為了標記這個變化，用一個邏輯變量shorter來標記當前子樹的樹高是否變小。依次處理從x的父結(jié)點到root的路徑上的每個結(jié)點p，如果以p為根的樹高變小，即shorter為TRUE，則分以下三種情況分別進行處理；如果樹高保持不變，shorter為FALSE時，則算法結(jié)束。第一種情況，p原來的平衡因子為0，根據(jù)x所在的子樹情況，相應(yīng)地修改p的平衡因子以適應(yīng)新的狀況。shorter為FALSE。如圖7.23所示。圖7.23刪除并不改變樹高第二種情況，p的平衡因子不是0，x位于p較高的子樹上，刪除x后，將p的平衡因為修改為0，shorter為TRUE，繼續(xù)處理p的父結(jié)點。如圖7.24所示。圖7.24在高子樹上刪除第三種情況，p的平衡因子不是0，x位于p較矮的子樹上，也就是說原來較矮的子樹更矮了，以p為根的子樹失平衡。此時需要進行旋轉(zhuǎn)來恢復(fù)平衡。設(shè)q為p較高子樹的根，分以下三種情況討論：q的平衡因子為0，此時進行單旋轉(zhuǎn)，q變?yōu)樽訕涞母?，而p變?yōu)閝的孩子結(jié)點，其他部分做相應(yīng)調(diào)整。shorter為FALSE。如圖7.25所示。圖7.25q的平衡因子為0q的平衡因子與p的平衡因子相等。此時進行單旋轉(zhuǎn)，q變?yōu)樽訕涞母?，而p變?yōu)閝的孩子結(jié)點，其他部分做相應(yīng)調(diào)整。shorter變?yōu)門RUE。如圖7.26所示。

圖7.26p與q的平衡因子相等

q的平衡因子與p的平衡因子相反。此時進行雙旋轉(zhuǎn)，第一次以q為軸旋轉(zhuǎn)，第二次以p為軸旋轉(zhuǎn)。其他部分做相應(yīng)調(diào)整。shorter變?yōu)門RUE。如圖7.27所示。圖7.27進行雙旋轉(zhuǎn)例：在圖7.28所示的AVL樹中，刪除p結(jié)點。圖7.28在AVL樹中刪除pp有兩個孩子，假設(shè)以其直接前趨o頂替它。m的右子樹如圖7.29所示。圖7.29m的右子樹從被刪結(jié)點o的父結(jié)點到根的路徑上有n、o和m三個結(jié)點，依次進行處理。對結(jié)點n，刪除的是它高子樹上的結(jié)點，修改n的平衡因子，shorter為true。對結(jié)點o，刪除是的它矮子樹上的結(jié)點，這是前述的3.2情況，以o為軸進行向左旋轉(zhuǎn)，shorter為true。調(diào)整后的樹如圖7.30所示。圖7.30左旋轉(zhuǎn)后的樹對結(jié)點m，刪除的是它矮子樹上的結(jié)點，并且它與左孩子的平衡因子相反，這是前述的3.3情況，先做一個以e為軸的向左旋轉(zhuǎn)，再做一個以m為軸的向右旋轉(zhuǎn)。最后得到的平衡的樹如圖7.31所示。圖7.31恢復(fù)平衡的AVL樹二叉平衡樹的查找效率

先分析深度為h的平衡二叉樹所含有的最少結(jié)點數(shù)。 設(shè)Nh表示深度為h的平衡二叉樹中含有的最少結(jié)點數(shù)，顯然N1=1，N2=2，并且Nh=Nh-1+Nh-2+1（h>2）?？梢宰C明，Nh約等于φh+2/-1，其中φ=（1+）/2。反之，令含有n個結(jié)點的平衡二叉樹的最大深度為h，根據(jù)Nh的近似表示，可以解出h=logφ((n+1))-2。 這說明在平衡二叉樹中，樹的深度h與結(jié)點總數(shù)n仍為對數(shù)關(guān)系。也就是說，在平衡二叉樹中進行查找的時間復(fù)雜度為O(logn)。這個結(jié)論雖與隨機形成的二叉排序樹的平均查找長度相同，但是平衡二叉樹從根本上避免了退化的可能性，因此它無疑地是對二叉排序樹的一種改進。7.3.3B-樹B-樹

1970年Bayer等人提出一種多叉平衡查找樹，稱為B-樹。一棵m階B-樹或者為空，或者為滿足下列性質(zhì)的m叉樹：樹中每個結(jié)點至多有m棵子樹；根結(jié)點至少有兩棵子樹；除根結(jié)點之外，每個結(jié)點至少有棵子樹；所有葉結(jié)點都出現(xiàn)在同一層上；所有結(jié)點都包含如下形式的數(shù)據(jù)：（n,A0,K1,A1,K2,A2,…,Kn,An） 其中n為關(guān)鍵字的個數(shù)，Ki（i=1,…,n）為關(guān)鍵字，且滿足K1<K2<…<Kn。Ai（i=0,1,…,n）為指向子樹根結(jié)點的指針，且對于i=1,2,…,n-1，Ai所指子樹上各結(jié)點的一切關(guān)鍵字均大于Ki，而小于Ki+1。A0所指子樹上各結(jié)點的一切關(guān)鍵字均小于K1，An所指子樹上各結(jié)點的一切關(guān)鍵字均大于Kn。對于葉結(jié)點，所有指針Ai皆為空。對于具有n個關(guān)鍵字的非葉結(jié)點，將有n+1棵子樹。 當n=3時，每個結(jié)點中最多包含兩個關(guān)鍵字、三個指針，最少時可以只含有一個關(guān)鍵字、兩個指針，所以3階B-樹又稱為2-3樹。下圖所示的是一棵5階（m=5）B-樹圖7.32一棵5階B-樹B-樹中元素的查找

B-樹的結(jié)構(gòu)保證了它是比較平衡的，限制了每個結(jié)點的子樹都不能過少，且從根到葉的路徑長度都相同，這對于提高查找效率顯然是有利的。具體的查找方法與在二叉排序樹中的查找方法類似。例如，在圖7.32所示的5階B-樹上查找關(guān)鍵字n的過程是：首先從根開始，由于e<n<p，則應(yīng)在位于e和p中間的指針所指的子樹上進行查找；然后，又由于l<n，則應(yīng)在l右邊的指針所指的子樹上進行查找；最后在含有m、n和o三個關(guān)鍵字的葉結(jié)點上查找成功。在m階B-樹上進行查找，其比較次數(shù)與兩個因素有關(guān)：結(jié)點中關(guān)鍵字的數(shù)目（最多m-1個，由于它們是有序的，當m較大時可以用折半查找方法）樹的深度現(xiàn)在假設(shè)共有N個關(guān)鍵字，且m是已確定的。可以證明，含N個關(guān)鍵字的m階B-樹的最大深度為:

B-樹中元素的插入

若要在m階B-樹上插入一個關(guān)鍵字，其尋找插入位置的過程與查找失敗的過程相同，待到在某個葉結(jié)點上找到相應(yīng)的空指針后，不能像二叉排序樹那樣向下“伸出”一個新的葉結(jié)點，而要將待插入的關(guān)鍵字按次序加到原來的葉結(jié)點中。若插入后該結(jié)點的關(guān)鍵字數(shù)目不超過m-1，則插入完成；否則需將這個結(jié)點“分裂”為兩個葉結(jié)點，并讓葉結(jié)點中中間位置的關(guān)鍵字提升到父結(jié)點中。如果因此而令父結(jié)點中關(guān)鍵字個數(shù)超限，則繼續(xù)這個結(jié)點分裂及關(guān)鍵字提升過程。在B-樹葉結(jié)點中插入關(guān)鍵字而不是新增加一個葉結(jié)點，是為了保證B-樹中的所有葉結(jié)點都必須在同一層上。例：一棵5階B-樹的生成過程如下圖所示。

對于一棵5階B-樹，每個結(jié)點中關(guān)鍵字個數(shù)最多為4個，最少為2個，相應(yīng)地指針個數(shù)最多為5個，最少為3個。圖請見下頁圖7.33在5階B-樹中插入關(guān)鍵字時的變化情況B-樹中元素的刪除

如果要刪除的關(guān)鍵字不在葉結(jié)點中，與二叉排序樹中刪除度為2的結(jié)點類似，找其直接前趨或是直接后繼來頂替它，然后再刪除這個直接前趨或是直接后繼，而這個關(guān)鍵字一定在葉結(jié)點中。因此我們只需討論刪除B-樹中葉結(jié)點中的關(guān)鍵字就可以了。分兩種情況處理。如果葉結(jié)點中含有的關(guān)鍵字個數(shù)多于最低限度，則直接刪除之。如果葉結(jié)點中含有的關(guān)鍵字個數(shù)正好等于最低限度，從中刪除一個關(guān)鍵字后，這個結(jié)點的關(guān)鍵字個數(shù)將少于最低限度，此時考察與其相鄰的兄弟結(jié)點。如果葉結(jié)點是其父結(jié)點的第一個或是最后一個孩子結(jié)點，則它只有一個相鄰的兄弟結(jié)點，否則會有兩個相鄰的兄弟結(jié)點。設(shè)葉結(jié)點為A，再分兩種情況考慮：如果至少有一個兄弟結(jié)點（設(shè)為B）中含有的關(guān)鍵字個數(shù)多于最低限度，則可以從B結(jié)點中“借”過一個關(guān)鍵字來。假設(shè)該兄弟結(jié)點B位于左側(cè)，則將B中最大的關(guān)鍵字移至A、B的父結(jié)點C中，C中指向A和B兩個指針之間的關(guān)鍵字下移到A中。對于B位于A之右側(cè)的情況與此類似，將B中最小關(guān)鍵字移至父結(jié)點C中，然后將C中相應(yīng)的關(guān)鍵字下移到A中。與A相鄰的兄弟結(jié)點中沒有多余的關(guān)鍵字可以借過來，即A和其兄弟結(jié)點中的關(guān)鍵字個數(shù)都達到最低限度，此時需要進行結(jié)點的合并。設(shè)將與A進行合并的兄弟結(jié)點為B，將A、B合并為一個結(jié)點D，同時，父結(jié)點C中分別指向A、B的兩個指針之間的關(guān)鍵字也下降到D中。C中關(guān)鍵字個數(shù)及指針個數(shù)同時減1。如果C中關(guān)鍵字個數(shù)也低于最低限度了，則再遞歸處理父結(jié)點的情況，考察C的兄弟，看是否能“借”關(guān)鍵字或是需要與其兄弟結(jié)點進行合并。如果每次都需要進行結(jié)點的合并，最終將根結(jié)點中的唯一一個關(guān)鍵字下降，則樹高減1。例：在一棵5階B-樹中，依次刪除多個關(guān)鍵字。刪除過程如圖7.34至7.37所示。圖7.34從5階B-樹中刪除關(guān)鍵字h、r圖7.35從5階B-樹中刪除關(guān)鍵字p圖7.36從5階B-樹中刪除關(guān)鍵字d圖7.37從5階B-樹中刪除關(guān)鍵字d后的結(jié)果7.4哈希表及其查找前面介紹的幾種查找方法，無論是順序查找、折半查找還是在樹表上進行查找，它們的共同特點是：為了找到表中某個記錄，都要對給定的關(guān)鍵字值進行一系列的比較，之后才能確定所找的記錄在表中的位置。而且其比較次數(shù)與表中記錄的個數(shù)n有關(guān)（O(n)或O(logn)）?，F(xiàn)在我們要介紹的方法是和以前完全不同的另一類重要的查找方法，它是通過對記錄的關(guān)鍵字值進行某種運算后，直接確定該記錄在表中的位置。因此，這種方法的平均查找長度將與表中記錄的個數(shù)無關(guān)，從而可以大大提高查找速度。7.4.1什么是哈希哈希

哈希一詞來自英文單詞hash的音譯，根據(jù)這個單詞的原意，哈希表也稱為雜湊表或散列表。相應(yīng)的技術(shù)稱為哈希技術(shù)、雜湊技術(shù)或散列技術(shù)，其主要特點是從關(guān)鍵字的值直接對應(yīng)到表中的地址。例：例7.8假設(shè)在某旅館中建立一個旅客管理—查詢系統(tǒng)，該旅館擁有一座大樓（樓層足夠高，樓的每層有足夠多的房間）供旅客居住，且假設(shè)每套客房只住一名旅客。為了便于管理和查詢，現(xiàn)以旅客姓名為關(guān)鍵字（設(shè)不超過三個漢字），以姓名的漢字筆劃數(shù)作為關(guān)鍵字的值，來決定他（她）所住的房間號。例如下面就是一張旅客姓名和所住房間號的對照表。表7.1旅客房間表旅客姓名房間號丁

一201于

立305王

方404田小華536劉力文624李中元744┆┆其中，姓的筆劃數(shù)決定樓層號，名字的筆劃數(shù)決定本層的房間號。用這種方法無論是安排旅客住宿（造表）還是查詢某旅客的居住房間，都是十分方便的。但是若有兩個旅客姓氏筆劃相同，就有一點問題。例如在表7.1中已住旅客的情況下，又來了一位名叫卞云的旅客，她的姓名編碼也是404，可是404號房間已經(jīng)住有旅客王方，不能再住第二個人了，這就叫發(fā)生“沖突”。這個問題怎么處理呢？當然處理的方法很多，最簡單的辦法是看下一個房間號405，若405號房間為空，則安排卞云住在該房間；若405號房間已住有旅客，則看406號房間是否為空，依此類推，直到找到一個空房間為止。在這種安排下，若要詢問卞云的住處，首先也要到404號房間查看，若此房間住的旅客不是卞云，則查下一個房間，依此類推，肯定能找到卞云住的房間。通過把關(guān)鍵字值映射到表中的一個位置來訪問記錄的過程稱為哈希，把關(guān)鍵字值映射到位置的函數(shù)稱為哈希函數(shù)，通常用h來表示。存放記錄的數(shù)組稱為哈希表，用T來表示。哈希表中的一個位置稱為一個槽。哈希表T中槽的數(shù)目用變量M來表示，槽從0到M-1編號。哈希方法使得對于任何關(guān)鍵字值K和某個哈希函數(shù)h，0≤h(K)≤M-1，得到：key(T(i))=K哈希方法概括如下： 對于某個問題可能出現(xiàn)的關(guān)鍵字，估計出它的總數(shù)，準備出略大于這一總數(shù)的空間（例如多出總數(shù)的20%—30%），以存放關(guān)鍵字。然后，設(shè)計一個哈希函數(shù)H，它將關(guān)鍵字k轉(zhuǎn)換成一個整數(shù)L，即H(k)=L。對于任何關(guān)鍵字，這個整數(shù)L都應(yīng)在所準備的空間地址（或表的位置）的范圍之內(nèi)。若有兩個不同的關(guān)鍵字k1、k2，即k1≠k2，但H(k1)=H(k2)=L，這就叫發(fā)生“沖突”。因此，對于哈希技術(shù)，主要研究兩個問題：如何設(shè)計哈希函數(shù)。發(fā)生沖突后如何解決。7.4.2哈希函數(shù)的構(gòu)造方法構(gòu)造哈希函數(shù)時通?？紤]的因素有：計算哈希函數(shù)所需的時間關(guān)鍵字的長度哈希表的大小關(guān)鍵字的分布情況記錄的查找頻率構(gòu)造哈希函數(shù)的基本原則是：算法簡單，運算量小；均勻分布，減少沖突。幾種常用的構(gòu)造哈希函數(shù)的方法直接定址法 這是一種計算最簡單、且沖突最少的方法，在某些適合的情況下應(yīng)盡量采用。這種哈希函數(shù)是關(guān)鍵字值的線性函數(shù)，即H(k)=k或H(k)=a*k+b，其中a、b為常數(shù)。

例：設(shè)要統(tǒng)計某地區(qū)從1949年到2000年每年的出生人數(shù)，統(tǒng)計結(jié)果將列在一張表中，此時年份為關(guān)鍵字。因為共有2000-1949+1=52年，所以表中設(shè)有1至52個位置。如何將關(guān)鍵字值對應(yīng)到表中位置呢？只需取H(k)=k-1948即可，其中k為年份數(shù)。這樣的哈希表示意如下： 數(shù)據(jù)表完成后，若要查1949至2000之間任意年份M出生的人數(shù)，則在表的第M-1948個位置即可找到。12…52年份19491950…2000人數(shù)…………平方取中法 這是一種較常用的構(gòu)造哈希函數(shù)的方法。設(shè)關(guān)鍵字值的位數(shù)超出了空間地址的范圍，又不能簡單地截取其中的某幾位作為哈希函數(shù)值。為了能使關(guān)鍵字值的每一位都對計算的結(jié)果起作用，可以先將關(guān)鍵字值自乘，然后截取中間幾位對應(yīng)到空間地址。例7.9設(shè)有一組關(guān)鍵字ABC，BCD，CDE，DEF,……，其對應(yīng)的機內(nèi)代碼分別為010203，020304，030405，040506，……，假定地址空間大小為103，編號為0~999?，F(xiàn)在按平方取中法構(gòu)造哈希函數(shù)，則可取關(guān)鍵字機內(nèi)代碼平方后的中間三位作為存儲位置，計算過程如表7.2所列。關(guān)鍵字機內(nèi)代碼機內(nèi)代碼的平方數(shù)哈希地址ABCBCDCDEDEF┆010203020304030405040506┆0104101209041225241609244640251640739036┆101252464739┆折疊法 折疊法是另一類處理多位關(guān)鍵字的方法。當關(guān)鍵字的位數(shù)較多，遠超過空間地址的范圍時，可將關(guān)鍵字分割為位數(shù)相等的幾段，然后將各段疊加，疊加后將最高位的進位舍去，所得結(jié)果即為哈希地址。例：關(guān)鍵字值k=123203241712，哈希表長度為1000

(0~999)，則將k分為三位一段，共分成四段然后相加，去掉進位1之后得到哈希地址為279。這種方法的原理也是盡可能讓關(guān)鍵字的每一位都起作用，以達到使哈希函數(shù)值均勻分布的目的。同時采取幾位折疊，又避免了最后哈希地址太大，超出哈希表范圍?；鶖?shù)轉(zhuǎn)換法 這種方法是將關(guān)鍵字值先看成另一種進制的數(shù)，然后轉(zhuǎn)換成原來進制的數(shù)（例如十進制），再選其中的幾位作為哈希地址。例如現(xiàn)有十進制的關(guān)鍵字值210485，把它看成十三進制的數(shù)后，再轉(zhuǎn)換成十進制數(shù)，其過程是：21048513=2*135+1*134+0*133+4*132+8*13+5=77193210然后從中選幾位作為哈希地址即可。通常要求兩個基數(shù)互素，且新基數(shù)比原基數(shù)大。除留余數(shù)法 這是一種常用的方法，它是通過對關(guān)鍵字值進行取模運算得到的。設(shè)給出關(guān)鍵字值為k，哈希表長度為m，則設(shè)計哈希函數(shù)為：

H(k)=kmodp

其中p為小于m的某個正整數(shù)。顯然，哈希函數(shù)值在哈希表的長度范圍之內(nèi)。關(guān)于p的取法是很有講究的，理論分析和試驗結(jié)果均證明，p應(yīng)取小于表長m的最大素數(shù)，才能達到使哈希函數(shù)值均勻分布的目的。例如當m=1000時，p應(yīng)取997這個素數(shù)。這時對某些關(guān)鍵字可得結(jié)果如表7.3所示。表7.3關(guān)鍵字機內(nèi)代碼（k）H(k)=kmod997KEYAEYBAKEYBKEYABCDDCBA1105250111052502011105250211052501020304040302017567578648733733277.4.3處理沖突的幾種方法沖突

沖突就是不同的關(guān)鍵字對應(yīng)到相同的哈希地址。給定一個哈希函數(shù)h和兩個關(guān)鍵字k1、k2，如果h(k1)=b=h(k2)，其中b是表中的一個槽，那么我們就說k1和k2對于b在哈希函數(shù)h下有沖突。

若對于關(guān)鍵字集合中的任一個關(guān)鍵字，經(jīng)哈希函數(shù)映射到地址集合中任何一個地址的概率是相等的，則稱此類哈希函數(shù)是均勻的哈希函數(shù)。換句話說，就是使關(guān)鍵字經(jīng)過哈希函數(shù)得到一個“隨機的地址”，以便使一組關(guān)鍵字的哈希地址均勻分布在整個地址區(qū)間中，從而減少沖突。解決沖突的方法

基本上分為兩類：開放地址法（閉哈希法）

當發(fā)生沖突時，用某種方法形成一個探測下一地址的序列，沿著這個序列一個個地查找，直到找到一個空地址就將關(guān)鍵字所在的記錄存入。鏈地址法（開哈希法）

當發(fā)生沖突時，就拉出一條鏈，建立一個單鏈表，將具有相同哈希函數(shù)值的關(guān)鍵字所在的記錄依次存入這個鏈表中。下面分別介紹這兩類方法的具體實現(xiàn)方法。開放地址法

在這一類解決沖突的方法中又分為三種確定探測序列的方式：線性探測再散列；二次探測再散列；偽隨機數(shù)再散列。假設(shè)哈希表長度為m，編號為0～m-1，哈希函數(shù)為H(k)。用線性探測再散列法解決沖突，求下一地址的公式是：di+1=(di+j)modm(j=1,2,…,s)

其中d1=H(k)。這個方法的意思是從哈希地址

H(k)出發(fā)，以等距離j（j可取不同的值）依次

搜索，當?shù)奖砦矔r可以轉(zhuǎn)到表頭循環(huán)搜索，直

到找到空位置為止。用二次探測再散列法解決沖突，求下一地址的公式是：

d2i=(d1+i2)modm (i=1,2,…)d2i+1=(d1-i2)modm