數(shù)據(jù)結(jié)構(gòu)第九章查找

何謂查找表？

查找表是由同一類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合。第九章查找對(duì)查找表經(jīng)常進(jìn)行的操作:1）查詢某個(gè)“特定的”數(shù)據(jù)元素是否在查找表中；2）檢索某個(gè)“特定的”數(shù)據(jù)元素的各種屬性；3）在查找表中插入一個(gè)數(shù)據(jù)元素；4）從查找表中刪去某個(gè)數(shù)據(jù)元素。僅作查詢和檢索操作的查找表。靜態(tài)查找表有時(shí)在查詢之后，還需要將“查詢”結(jié)果為“不在查找表中”的數(shù)據(jù)元素插入到查找表中；或者，從查找表中刪除其“查詢”結(jié)果為“在查找表中”的數(shù)據(jù)元素。動(dòng)態(tài)查找表查找表可分為兩類:是數(shù)據(jù)元素（或記錄）中某個(gè)數(shù)據(jù)項(xiàng)的值，用以標(biāo)識(shí)（識(shí)別）一個(gè)數(shù)據(jù)元素（或記錄）。關(guān)鍵字

若此關(guān)鍵字可以識(shí)別唯一的一個(gè)記錄，則稱之謂“主關(guān)鍵字”。

若此關(guān)鍵字能識(shí)別若干記錄，則稱之謂“次關(guān)鍵字”。

根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素或（記錄）。

查找

若查找表中存在這樣一個(gè)記錄，則稱“查找成功”。查找結(jié)果給出整個(gè)記錄的信息，或指示該記錄在查找表中的位置；否則稱“查找不成功”。查找結(jié)果給出“空記錄”或“空指針”。

由于查找表中的數(shù)據(jù)元素之間不存在明顯的組織規(guī)律，因此不便于查找。為了提高查找的效率，需要在查找表中的元素之間人為地附加某種確定的關(guān)系，換句話說，

用另外一種結(jié)構(gòu)來表示查找表。如何進(jìn)行查找？查找的方法取決于查找表的結(jié)構(gòu)。9.1靜態(tài)查找表9.2動(dòng)態(tài)查找樹表9.3哈希表9.1靜態(tài)查找表typedefstruct{

//數(shù)據(jù)元素存儲(chǔ)空間基址，建表時(shí)

//按實(shí)際長(zhǎng)度分配，0號(hào)單元留空

int

length;//表的長(zhǎng)度}SSTable;假設(shè)靜態(tài)查找表的順序存儲(chǔ)結(jié)構(gòu)為ElemType

*elem;數(shù)據(jù)元素類型的定義為:typedefstruct{

keyTypekey;//關(guān)鍵字域

……

//其它屬性域}ElemType;,TElemType;一、順序查找表二、有序查找表三、索引順序表

以順序表或線性鏈表表示靜態(tài)查找表一、順序查找表ST.elem順序表的查找過程：假設(shè)給定值e=64,要求ST.elem[k]=e,問:k=?kkintlocation(SqListL,ElemType&e,

Status(*compare)(ElemType,ElemType)){k=1;p=L.elem;

while(k<=L.length

&&

!(*compare)(*++p,e)))k++;if(k<=L.length)returnk;

elsereturn0;}有點(diǎn)費(fèi)時(shí)ST.elemiST.elemi60ikey=64key=60i64intSearch_Seq(SSTableST,

KeyTypekey){

//在順序表ST中順序查找其關(guān)鍵字等于

//key的數(shù)據(jù)元素。若找到，則函數(shù)值為

//該元素在表中的位置，否則為0。

ST.elem[0].key=key;

//“哨兵”

for(i=ST.length;ST.elem[i].key!=key;

--i);

//從后往前找

returni;

//找不到時(shí)，i為0}

定義：

查找算法的平均查找長(zhǎng)度

(AverageSearchLength)

為確定記錄在查找表中的位置，需和給定值

進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的期望值

其中:n為表長(zhǎng)，Pi

為查找表中第i個(gè)記錄的概率，且，Ci為找到該記錄時(shí)，曾和給定 值比較過的關(guān)鍵字的個(gè)數(shù)。分析順序查找的時(shí)間性能在等概率查找的情況下，

順序表查找的平均查找長(zhǎng)度為：對(duì)順序表而言，Ci=n-i+1ASL=nP1+(n-1)P2++2Pn-1+Pn

上述順序查找表的查找算法簡(jiǎn)單，但平均查找長(zhǎng)度較大，特別不適用于表長(zhǎng)較大的查找表。二、有序查找表

若以有序表表示靜態(tài)查找表，則查找過程可以基于“折半”進(jìn)行。ST.elemST.length例如:key=64

的查找過程如下：lowhighmidlow

mid

high

midlow

指示查找區(qū)間的下界high

指示查找區(qū)間的上界mid=(low+high)/2intSearch_Bin(SSTableST,KeyTypekey){

low=1;high=ST.length;//置區(qū)間初值

while(low<=high){mid=(low+high)/2;

if（EQ(key,ST.elem[mid].key))

returnmid;//找到待查元素

elseif(LT(key,ST.elem[mid].key))

high=mid-1;//繼續(xù)在前半?yún)^(qū)間進(jìn)行查找

else

low=mid+1;//繼續(xù)在后半?yún)^(qū)間進(jìn)行查找

}return0;//順序表中不存在待查元素}//Search_Bin21

先看一個(gè)具體的情況，假設(shè)：n=11分析折半查找的平均查找長(zhǎng)度391425781011判定樹122333344446比較次數(shù)折半查找優(yōu)劣：折半查找的效率比順序查找高，但只適用于有序表，而且限于順序存儲(chǔ)結(jié)構(gòu)，對(duì)線性鏈表無法進(jìn)行折半查找。在n>50時(shí)，可得近似結(jié)果

一般情況下，表長(zhǎng)為n的折半查找的判定樹的深度和含有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度相同。索引順序表的查找過程：1）由索引確定記錄所在區(qū)間；2）在順序表的某個(gè)區(qū)間內(nèi)進(jìn)行查找?？梢姡?/p>

索引順序查找，是一個(gè)“縮小區(qū)間”的查找過程。具體實(shí)現(xiàn)是分塊查找。例如：22121389203342443824486058744986531234567891011121314151617182248861713索引表最大關(guān)鍵字起始地址key=38ijkey=29ij索引順序查找的平均查找長(zhǎng)度ASLbs=

查找“索引”的平均查找長(zhǎng)度Lb

+查找“順序表”的平均查找長(zhǎng)度Lw設(shè):表的長(zhǎng)度：n均勻分成的塊數(shù)：b，每塊記錄個(gè)數(shù)：s若用順序查找確定所在的塊，則：ASLbs＝Lb＋Lw=當(dāng)s=時(shí)，ASLbs最小＝＋19.2動(dòng)態(tài)查找表一、二叉排序樹（二叉查找樹）二、二叉平衡樹三、B-樹四、B+樹五、哈希表一、二叉排序樹（二叉查找樹）1．定義2．查找算法3．插入算法4．刪除算法（1）若它的左子樹不空，則左子樹上

所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；1．定義：

二叉排序樹或者是一棵空樹；或者是具有如下特性的二叉樹：（3）它的左、右子樹也都分別是二叉排序樹。（2）若它的右子樹不空，則右子樹上

所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；503080209010854035252388例如:是二叉排序樹。66不

通常，取二叉鏈表作為二叉排序樹的存儲(chǔ)結(jié)構(gòu)typedefstruct

BiTNode

{//結(jié)點(diǎn)結(jié)構(gòu)

structBiTNode*lchild,*rchild;//左右孩子指針}BiTNode,*BiTree;TElemTypedata;2．二叉排序樹的查找算法：1）若給定值等于根結(jié)點(diǎn)的關(guān)鍵字，則查找成功；2）若給定值小于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在左子樹上進(jìn)行查找；3）若給定值大于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在右子樹上進(jìn)行查找。否則，若二叉排序樹為空，則查找不成功；50308020908540358832例如:二叉排序樹查找關(guān)鍵字==50,505035,503040355090,50809095,從上述查找過程可見，在查找過程中，生成了一條查找路徑：

從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支逐層向下直至關(guān)鍵字等于給定值的結(jié)點(diǎn);或者

從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支逐層向下直至指針指向空樹為止。

——查找成功

——查找不成功StatusSearchBST(BiTreeT,KeyTypekey,BiTreef,BiTree&p){在根指針T

所指二叉排序樹中遞歸地查找其關(guān)鍵字等于key的數(shù)據(jù)元素，若查找成功，則返回指針

p指向該數(shù)據(jù)元素的結(jié)點(diǎn)，并返回

函數(shù)值為TRUE;}//SearchBST

…………否則表明查找不成功，返回指針

p

指向查找路徑上訪問的最后一個(gè)結(jié)點(diǎn)，并返回函數(shù)值為FALSE,指針f指向當(dāng)前訪問的結(jié)點(diǎn)的雙親，其初始調(diào)用值為NULLif(!T)elseif

(EQ(key,T->data.key))

elseif

(LT(key,T->data.key))

else{p=f;returnFALSE;}//查找不成功{p=T;returnTRUE;}//查找成功SearchBST(T->lchild,key,T,p);

//在左子樹中繼續(xù)查找SearchBST(T->rchild,key,T,p);

//在右子樹中繼續(xù)查找30201040352523fT設(shè)key=48fTfT22pfTfTTTTfffp根據(jù)動(dòng)態(tài)查找表的定義，“插入”操作在查找不成功時(shí)才進(jìn)行；3．二叉排序樹的插入算法若二叉排序樹為空樹，則新插入的結(jié)點(diǎn)為新的根結(jié)點(diǎn)；否則，新插入的結(jié)點(diǎn)必為一個(gè)新的葉子結(jié)點(diǎn)，其插入位置由查找過程得到。StatusInsertBST(BiTree&T,ElemTypee)

{//當(dāng)二叉排序樹中不存在關(guān)鍵字等于e.key的//數(shù)據(jù)元素時(shí)，插入元素值為e的結(jié)點(diǎn)，并返//回TRUE;否則，不進(jìn)行插入并返回FALSE

if

(!SearchBST(T,e.key,NULL,p))

{

}elsereturnFALSE;}//InsertBST……s=(BiTree)malloc(sizeof(BiTNode));

//為新結(jié)點(diǎn)分配空間s->data=e;s->lchild=s->rchild=NULL;if(!p)T=s;//插入s為新的根結(jié)點(diǎn)elseif(LT(e.key,p->data.key))p->lchild=s;

//插入*s為*p的左孩子elsep->rchild=s;//插入*s為*p的右孩子returnTRUE;//插入成功（1）被刪除的結(jié)點(diǎn)是葉子；（2）被刪除的結(jié)點(diǎn)只有左子樹或者只有右子樹；（3）被刪除的結(jié)點(diǎn)既有左子樹，也有右子樹。4．二叉排序樹的刪除算法可分三種情況討論：

和插入相反，刪除在查找成功之后進(jìn)行，并且要求在刪除二叉排序樹上某個(gè)結(jié)點(diǎn)之后，仍然保持二叉排序樹的特性。50308020908540358832（1）被刪除的結(jié)點(diǎn)是葉子結(jié)點(diǎn)例如:被刪關(guān)鍵字=2088其雙親結(jié)點(diǎn)中相應(yīng)指針域的值改為“空”50308020908540358832（2）被刪除的結(jié)點(diǎn)只有左子樹或者只有右子樹

其雙親結(jié)點(diǎn)的相應(yīng)指針域的值改為“指向被刪除結(jié)點(diǎn)的左子樹或右子樹”。被刪關(guān)鍵字=408050308020908540358832（3）被刪除的結(jié)點(diǎn)既有左子樹，也有右子樹4040以其前驅(qū)替代之，然后再刪除該前驅(qū)結(jié)點(diǎn)被刪結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)被刪關(guān)鍵字=50Status

DeleteBST(BiTree&T,KeyTypekey)

{//若二叉排序樹T中存在其關(guān)鍵字等于key的

//數(shù)據(jù)元素，則刪除該數(shù)據(jù)元素結(jié)點(diǎn)，并返回

//函數(shù)值TRUE，否則返回函數(shù)值FALSE

if(!T)returnFALSE; //不存在關(guān)鍵字等于key的數(shù)據(jù)元素

else{}}//DeleteBST算法描述如下：……if(EQ(key,T->data.key))

//找到關(guān)鍵字等于key的數(shù)據(jù)元素elseif(LT(key,T->data.key))

else{Delete(T);returnTRUE;}

DeleteBST(T->lchild,key);

//繼續(xù)在左子樹中進(jìn)行查找DeleteBST(T->rchild,key);//繼續(xù)在右子樹中進(jìn)行查找voidDelete(BiTree&p){//從二叉排序樹中刪除結(jié)點(diǎn)p，

//并重接它的左子樹或右子樹

if

(!p->rchild)

{}

elseif

(!p->lchild)

{}

else{}}//Delete其中刪除操作過程如下所描述：………………//右子樹為空樹則只需重接它的左子樹q=p;p=p->lchild;free(q);ppqqpp//左子樹為空樹只需重接它的右子樹q=p;p=p->rchild;free(q);ppqqppq=p;s=p->lchild;while(s->rchild){q=s;s=s->rchild;}//s指向被刪結(jié)點(diǎn)的前驅(qū)//左右子樹均不空p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;//重接*q的左子樹free(s);pqs5．查找性能的分析

對(duì)于每一棵特定的二叉排序樹，均可按照平均查找長(zhǎng)度的定義來求它的ASL值，顯然，由值相同的n個(gè)關(guān)鍵字，構(gòu)造所得的不同形態(tài)的各棵二叉排序樹的平均查找長(zhǎng)度的值不同，甚至可能差別很大。由關(guān)鍵字序列3，1，2，5，4構(gòu)造而得的二叉排序樹，由關(guān)鍵字序列1，2，3，4，5構(gòu)造而得的二叉排序樹，例如：2134535412ASL=（1+2+3+4+5）/5=3ASL=（1+2+3+2+3）/5=2.2二、二叉平衡樹何謂“二叉平衡樹”？二叉平衡樹的查找性能分析如何構(gòu)造“二叉平衡樹”

二叉平衡樹是二叉查找樹的另一種形式，其特點(diǎn)為：

樹中每個(gè)結(jié)點(diǎn)的左、右子樹深度之差的絕對(duì)值不大于1。例如:548254821是平衡樹不是平衡樹結(jié)點(diǎn)的平衡因子：該結(jié)點(diǎn)的左子樹的深度減去

(-101)

右子樹的深度

構(gòu)造二叉平衡（查找）樹的方法是：在插入過程中，采用平衡旋轉(zhuǎn)技術(shù)。失去平衡后進(jìn)行調(diào)整的規(guī)律可歸納為下列4種情況：

假設(shè)由于在二叉排序樹上插入結(jié)點(diǎn)而失去平衡的最小子樹根結(jié)點(diǎn)為A，沿插入路徑取直接下兩層的結(jié)點(diǎn)為B和C，如果這三個(gè)結(jié)點(diǎn)處于一條直線上，則采用單旋轉(zhuǎn)進(jìn)行平衡化；如果這三個(gè)結(jié)點(diǎn)處于一條折線上，則采用雙旋轉(zhuǎn)進(jìn)行平衡化。

調(diào)整方法：以結(jié)點(diǎn)B為旋轉(zhuǎn)軸，將結(jié)點(diǎn)A向右旋轉(zhuǎn)成為B的右子樹，結(jié)點(diǎn)B代替原來A的位置，原來B的右子樹成為A的左子樹。

原因：在A

的左子樹根結(jié)點(diǎn)的左子樹上插入結(jié)點(diǎn)，A的平衡因子由1增至2，至使以A為根的子樹失去平衡。ABhChBRhAR插入結(jié)點(diǎn)（1）單向右旋平衡處理：(LLR)LLRABh+1ChBRhAR

調(diào)整方法：以結(jié)點(diǎn)B為旋轉(zhuǎn)軸，將結(jié)點(diǎn)A向左旋轉(zhuǎn)成為B的左子樹，結(jié)點(diǎn)B代替原來A的位置，原來B的左子樹成為A的右子樹。

原因：在A

的右子樹根結(jié)點(diǎn)的右子樹上插入結(jié)點(diǎn)，A的平衡因子由-1增至-2，至使以A為根的子樹失去平衡。ABhChBLhAL插入結(jié)點(diǎn)（2）單向左旋平衡處理：(RRL)RRLABh+1ChBLhAL

調(diào)整方法：先以C為旋轉(zhuǎn)軸，將結(jié)點(diǎn)B向左旋轉(zhuǎn)成為C的左子樹，結(jié)點(diǎn)C代替原來B的位置，原來C的左子樹成為B的右子樹。

原因：在A

的左子樹根結(jié)點(diǎn)的右子樹上插入結(jié)點(diǎn)，A的平衡因子由1增至2，至使以A為根的子樹失去平衡。（3）先左后右平衡處理：(LRLR)ABh-1CLh-1CRhAR插入結(jié)點(diǎn)ChBLBAhARhCLhBLCh-1CRBAhARhCLhBLCh-1CR

再以C為旋轉(zhuǎn)軸，將A向右旋轉(zhuǎn)成為C的右子樹，結(jié)點(diǎn)C代替原來A的位置，原來C的右子樹成為A的左子樹。LR

再以C為旋轉(zhuǎn)軸，將A向左旋轉(zhuǎn)成為C的左子樹，結(jié)點(diǎn)C代替原來A的位置，原來C的左子樹成為A的右子樹。

調(diào)整方法：先以C為旋轉(zhuǎn)軸，將結(jié)點(diǎn)B向右旋轉(zhuǎn)成為C的右子樹，結(jié)點(diǎn)C代替原來B的位置，原來C的右子樹成為B的左子樹。

原因：在A

的右子樹根結(jié)點(diǎn)的左子樹上插入結(jié)點(diǎn)，A的平衡因子由-1增至-2，至使以A為根的子樹失去平衡。（4）先右后左平衡處理：(RLRL)ABh-1CRh-1CLhAL插入結(jié)點(diǎn)ChBRBRAhALhCRhBCh-1CLBAhALhCRhBRCh-1CLRLABCABC例如:依次插入的關(guān)鍵字為5,4,2,8,6,95424258665842向右旋轉(zhuǎn)一次先向右旋轉(zhuǎn)再向左旋轉(zhuǎn)BCACBACBA426589642895向左旋轉(zhuǎn)一次繼續(xù)插入關(guān)鍵字9CAB在二叉平衡樹上進(jìn)行查找時(shí)，查找過程中和給定值進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)和log(n)

相當(dāng)。

一、哈希表是什么？二、哈希函數(shù)的構(gòu)造方法

三、處理沖突的方法

四、哈希表的查找

五、哈希表的刪除操作9.3哈希表

以上兩節(jié)討論的表示查找表的各種結(jié)構(gòu)的共同特點(diǎn)：記錄在表中的位置和它的關(guān)鍵字之間不存在一個(gè)確定的關(guān)系，一、哈希表是什么？

查找的過程為給定值依次和關(guān)鍵字集合中各個(gè)關(guān)鍵字進(jìn)行比較，

查找的效率取決于和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)。

用這類方法表示的查找表，其平均查找長(zhǎng)度都不為零。

不同的表示方法，其差別僅在于：關(guān)鍵字和給定值進(jìn)行比較的順序不同。

只有一個(gè)辦法：預(yù)先知道所查關(guān)鍵字在表中的位置，

對(duì)于頻繁使用的查找表，希望ASL=0。

即：記錄在表中位置和其關(guān)鍵字之間存在一種確定的關(guān)系。若以下標(biāo)為000~999的順序表表示之。例如：為每年招收的1000名新生建立一張查找表，其關(guān)鍵字為學(xué)號(hào)，其值的范圍為xx000~xx999(前兩位為年份)。則查找過程可以簡(jiǎn)單進(jìn)行：取給定值（學(xué)號(hào)）的后三位，不需要經(jīng)過比較便可直接從順序表中找到待查關(guān)鍵字。但是，對(duì)于動(dòng)態(tài)查找表而言，因此在一般情況下，需在關(guān)鍵字與記錄在表中的存儲(chǔ)位置之間建立一個(gè)函數(shù)關(guān)系，以f(key)作為關(guān)鍵字為key的記錄在表中的位置，通常稱這個(gè)函數(shù)f(key)為哈希函數(shù)。1)表長(zhǎng)不確定；2)在設(shè)計(jì)查找表時(shí)，只知道關(guān)鍵字所屬范圍，而不知道確切的關(guān)鍵字。{Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Dei}

例如：對(duì)于如下9個(gè)關(guān)鍵字設(shè)

哈希函數(shù)f(key)=

(Ord(第一個(gè)字母)-Ord('A')+1)/2ChenZhaoQianSunLiWuHanYeDei問題:

若添加關(guān)鍵字Zhou,怎么辦？能否找到另一個(gè)哈希函數(shù)？1)哈希函數(shù)是一個(gè)映象，即：

將關(guān)鍵字的集合映射到某個(gè)地址集合上，

它的設(shè)置很靈活，只要這個(gè)地址集合的大小不超出允許范圍即可；從這個(gè)例子可見：2)由于哈希函數(shù)是一個(gè)壓縮映象，因此，在一般情況下，很容易產(chǎn)生“沖突”現(xiàn)象，即：key1key2，而f(key1)=f(key2)。3)很難找到一個(gè)不產(chǎn)生沖突的哈希函數(shù)。一般情況下，只能選擇恰當(dāng)?shù)墓：瘮?shù)，使沖突盡可能少地產(chǎn)生。

因此，在構(gòu)造這種特殊的“查找表”時(shí)，除了需要選擇一個(gè)“好”(盡可能少產(chǎn)生沖突)的哈希函數(shù)之外；還需要找到一種“處理沖突”的方法。哈希表的定義：

根據(jù)設(shè)定的哈希函數(shù)H(key)

和所選中的處理沖突的方法，將一組關(guān)鍵字映象到一個(gè)有限的、地址連續(xù)的地址集(區(qū)間)上，并以關(guān)鍵字在地址集中的“象”作為相應(yīng)記錄在表中的存儲(chǔ)位置，如此構(gòu)造所得的查找表稱之為“哈希表”。二、構(gòu)造哈希函數(shù)的方法

對(duì)數(shù)字的關(guān)鍵字可有下列構(gòu)造方法：

若是非數(shù)字關(guān)鍵字，則需先對(duì)其進(jìn)行數(shù)字化處理。1.

直接定址法3.平方取中法5.除留余數(shù)法4.折疊法6.隨機(jī)數(shù)法2.數(shù)字分析法哈希函數(shù)為關(guān)鍵字的線性函數(shù)

H(key)=key

或者

H(key)=akey+b1.

直接定址法此法僅適合于：地址集合的大小==關(guān)鍵字集合的大小此方法僅適合于：

能預(yù)先估計(jì)出全體關(guān)鍵字的每一位上各種數(shù)字出現(xiàn)的頻度。2.

數(shù)字分析法

假設(shè)關(guān)鍵字集合中的每個(gè)關(guān)鍵字都是由s位數(shù)字組成(u1,u2,…,us)，分析關(guān)鍵字集中的全體，并從中提取分布均勻的若干位或它們的組合作為地址。

以關(guān)鍵字的平方值的中間幾位作為存儲(chǔ)地址。求“關(guān)鍵字的平方值”的目的是“擴(kuò)大差別”，同時(shí)平方值的中間各位又能受到整個(gè)關(guān)鍵字中各位的影響。3.平方取中法

此方法適合于:

關(guān)鍵字中的每一位都有某些數(shù)字重復(fù)出現(xiàn)頻度很高的現(xiàn)象。

將關(guān)鍵字分割成若干部分，然后取它們的疊加和為哈希地址。有兩種疊加處理的方法：移位疊加和間界疊加。4.折疊法

此方法適合于:

關(guān)鍵字的數(shù)字位數(shù)特別多。5.除留余數(shù)法

設(shè)定哈希函數(shù)為:H(key)=keyMODp其中，

p≤m(表長(zhǎng))并且

p

應(yīng)為不大于m的素?cái)?shù)或是不含20以下的質(zhì)因子

給定一組關(guān)鍵字為：12,39,18,24,33,21，若取p=9,則他們對(duì)應(yīng)的哈希函數(shù)值將為：3,3,0,6,6,3例如：為什么要對(duì)p加限制？

可見，若p中含質(zhì)因子3，則所有含質(zhì)因子3的關(guān)鍵字均映射到“3的倍數(shù)”的地址上，從而增加了“沖突”的可能。6.隨機(jī)數(shù)法設(shè)定哈希函數(shù)為:H(key)=Random(key)其中，Random為偽隨機(jī)函數(shù)

通常，此方法用于對(duì)長(zhǎng)度不等的關(guān)鍵字構(gòu)造哈希函數(shù)。

實(shí)際造表時(shí)，采用何種構(gòu)造哈希函數(shù)的方法取決于建表的關(guān)鍵字集合的情況(包括關(guān)鍵字的范圍和形態(tài))，總的原則是使產(chǎn)生沖突的可能性降到盡可能地小。三、處理沖突的方法

“處理沖突”的實(shí)際含義是：為產(chǎn)生沖突的地址尋找下一個(gè)哈希地址。1.開放定址法2.鏈地址法

為產(chǎn)生沖突的地址H(key)求得一個(gè)地址序列：

H0,H1,H2,…,Hs

1≤s≤m-1其中：H0=H(key)Hi=(H(key)+di

)MODm

i=1,2,…,s1.開放定址法對(duì)增量

di

有三種取法：1)線性探測(cè)再散列

di=ci

最簡(jiǎn)單的情況c=12)平方探測(cè)再散列

di=12,-12,22,-22,…,3)隨機(jī)探測(cè)再散列

di

是一組偽隨機(jī)數(shù)列或者

di=i×H2(key)(又稱雙散列函數(shù)探測(cè))即：產(chǎn)生的Hi

均不相同，且所產(chǎn)生的

s(m-1)個(gè)Hi

值能覆蓋哈希表中所有地址。則要求：

注意：增量di

應(yīng)具有“完備性”※

隨機(jī)探測(cè)時(shí)的m

和di沒有公因子?！?/p>

平方探測(cè)時(shí)的表長(zhǎng)

m

必為形如4j+3

的素?cái)?shù)（如:7,11,19,23,…等）；例如:

關(guān)鍵字集合

{19,01,23,14,55,68,11,82,36}設(shè)定哈希函數(shù)H(key)=keyMOD11(表長(zhǎng)=11)1901231455681901231468若采用線性探測(cè)再散列處理沖突若采用二次探測(cè)再散列處理沖突11823655118236112136251H2(key)是另設(shè)定的一個(gè)哈希函數(shù)，它的函數(shù)值應(yīng)和m

互為素?cái)?shù)。若m

為素?cái)?shù)，則H2(key)

可以是1

至m-1

之間的任意數(shù)；

若m

為2的冪次，則H2(key)

應(yīng)是1

至m-1

之間的任意奇數(shù)。例如，當(dāng)m=11時(shí)，可設(shè)H2(key)=(3key)MOD10+1190123145568118236211121213{19,01,23,14,55,68,11,82,36}將所有哈希地址相同的記錄都鏈接在同一鏈表中。

2.鏈地址法0123456140136198223116855ASL=(6×1+2×2+3)/9=13/9例如:同前例的關(guān)鍵字，哈希函數(shù)為H(key)=keyMOD7

查找過程和造表過程一致。假設(shè)采用開放定址處理沖突，則查找過程為：

四、哈希表的查找

對(duì)于給定值K，計(jì)算哈希地址i=H(K)若r[i]=NULL

則查找不成功若

r[i].key=K

則查找成功否則“求下一地址Hi”，直至

r[Hi]=NULL(查找不成功)

或

r[Hi].key=K(查找成功)為止。inthashsize[]={997,...};typedefstruct{ElemType*elem;

intcount;//當(dāng)前數(shù)據(jù)元素個(gè)數(shù)

intsizeindex;//hashsize[sizeindex]為當(dāng)前容量}HashTable;#defineSUCCESS1#defineUNSUCCESS0#defineDUPLICATE-1//---開放定址哈希表的存儲(chǔ)結(jié)構(gòu)---StatusSearchHash(HashTableH,KeyTypeK,

int&p,int&c){//在開放定址哈希表H中查找關(guān)鍵碼為K的記錄}//SearchHashp=Hash(K);//求得哈希地址while(H.elem[p].key!=NULLKEY&&

!EQ(K,H.elem[p].key)）

collision(p,++c);//求得下一探查地址pif(EQ(K,H.elem[p].key))returnSUCCESS;//查找成功，返回待查數(shù)據(jù)元素位置pelsereturnUNSUCCESS;//查找不成功StatusInsertHash(HashTable&H,Elemtypee){

}//InsertHashc=0;if(HashSearch(H,e.key,p,c)==SUCCESS)returnDUPLICATE;