大二上數(shù)據(jù)結(jié)構(gòu)教學ch9查找

CH9

查找引言查找的概念靜態(tài)查找表順序查找有序表的查找索引順序表的查找動態(tài)查找表二叉排序樹和平衡二叉樹哈希表何謂查找表？查找表是由同一類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合。由于“集合”中的數(shù)據(jù)元素之間存在著松散的關(guān)系，因此查找表是一種應用靈便的結(jié)構(gòu)。9.0查找的概念對查找表經(jīng)常進行的操作:1）查詢某個“特定的”數(shù)據(jù)元素是否在查找表中；2）檢索某個“特定的”數(shù)據(jù)元素的各種屬性；3）在查找表中插入一個數(shù)據(jù)元素；4）從查找表中刪去某個數(shù)據(jù)元素。9.0查找的概念靜態(tài)查找表僅作查詢和檢索操作的查找表。動態(tài)查找表有時在查詢之后，還需要將“查詢”結(jié)果為“不在查找表中”的數(shù)據(jù)元素插入到查找表中；或者，從查找表中刪除其“查詢”結(jié)果為“在查找表中”的數(shù)據(jù)元素查找表可分為兩類:關(guān)鍵字是數(shù)據(jù)元素（或記錄）中某個數(shù)據(jù)項的值，用以標識（識別）一個數(shù)據(jù)元素（或記錄）。若此關(guān)鍵字可以識別唯一的一個記錄，則稱之謂“主關(guān)鍵字”。若此關(guān)鍵字能識別若干記錄，則稱之謂“次關(guān)鍵字”。9.0查找的概念9.0查找的概念查找根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定值的數(shù)據(jù)元素或（記錄）查找結(jié)果:查找成功(table

中存在給定值的記錄)查找不成功(table

中不存在給定值的記錄)本章數(shù)據(jù)元素類型與比較運算的符號約定1）數(shù)據(jù)類型定義typedef

struct

{keytype

key;……}ElemType;

2）關(guān)鍵字比較的符號約定EQ(a,b)

((a)=

=(b))LT(a,b)

((a)<(b))LQ(a,b)

((a)<=(b))靜態(tài)查找表動態(tài)查找樹表哈希表9.1靜態(tài)查找表一、順序查找表二、有序查找表三、索引順序表以順序表或線性鏈表表示靜態(tài)查找表一、順序查找表假設靜態(tài)查找表的順序存儲結(jié)構(gòu)為typedef struct

{ElemType

*elem;//數(shù)據(jù)元素存儲空間基址，建表時//按實際長度分配，0號單元留空int

length;

//表的長度}

SSTable;數(shù)據(jù)元素類型的定義為:typedef

struct

{keyType

key;…

…//關(guān)鍵字域//其它屬性域;}

ElemType

,

TElemType

;2137881992056456807513回顧順序表的查找過程：k

kST.elem0

1

2

3

4

5

6

7

8

9

10

11ST.Length假設給定值e=64,要求ST.elem[k].key=e,

問:k=?int

location(

SqList

ST,

ElemType&

e)

{k

=

1;while(

k<=ST.length

&&ST.elem[k].key!=e))k++;if

(

k<=

ST.length)

return

k;else return

0;}

//locationiiST.elem602137881992056456807513i0

1

2

3

4

5

6

7

8

9

10

11key=64

ST.Length0

1

2

3

4

5

6

7

8

9

10

11key=60

ST.Lengthi642137881992056456807513如何消除比較：k<=L.lengthST.elemint

Search_Seq(SSTable

ST,KeyType

key)

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

key的數(shù)據(jù)元素。若找到，則函數(shù)值為//該元素在表中的位置，否則為0。ST.elem[0].key

=

key;//“哨兵”for

(i=ST.length;

ST.elem[i].key!=key;

--i);//從后往前找//找不到時，i為0return

i;}

//

Search_Seq其中:n為表長，Pi

為查找表中第i個記錄的概率，值比較過的關(guān)鍵字的個數(shù)。n分析順序查找的時間性能定義：查找算法的平均查找長度(Average

Search

Length)為確定記錄在查找表中的位置，需和給定值進行比較的關(guān)鍵字個數(shù)的期望值ASL

=

PiCii=1ni=1且

Pi

=

1

，

Ci為找到該記錄時，曾和給定順序表查找成功的平均查找長度為：ni在等概率查找的情況下，P

=121n

+1(n

-

i

+1)

=nni=1ASLss

=對順序表而言，Ci

=

n-i+1ASL

=

nP1

+(n-1)P2

++2Pn-1+Pn任意關(guān)鍵字查找不成功的比較次數(shù)為n＋1，則平均查找長度為Pi=1/2n順序表的平均查找長度為：2=1

n

+1(n

-

i

+1)nASLss

=2n

i=1+=3/4(n+1)二、有序查找表上述順序查找表的查找算法簡單，但平均查找長度較大，特別不適用

于表長較大的查找表。若以有序表表示靜態(tài)查找表，則查找過程可以基于“折半”（二分查找）進行。0513192137566475808892ST.length例如:key=64

的查找過程如下：lowhighmidmidST.elem0

1

2

3

4

5

6

7

8

9

10

11low

highmidlow

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

指示查找區(qū)間的上界mid

=(low+high)/2int

Search_Bin

(

SSTable

ST,

KeyType

key

)

{//置區(qū)間初值low=1;

high

=ST.length;while(low<=high)

{mid=(low+high)/2;if

（EQ

(key

,

ST.elem[mid].key)

)return

mid;//找到待查元素else if

(

LT

(key

,ST.elem[mid].key))high

=mid

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

low=mid+1;//繼續(xù)在后半?yún)^(qū)間進行查找//順序表中不存在待查元素}return

0;}

//

Search_Bin先看一個具體的情況，假設：n=11分析折半查找的平均查找長度69425781011判定樹31i1234567891011Ci34234134234可以看出：n個結(jié)點的判定樹的深度和n個結(jié)點的完全二叉樹的深度相同；查找過程：從根到結(jié)點（或外部結(jié)點）走出的路徑；二叉樹第k層結(jié)點的查找次數(shù)各為k次(根結(jié)點為第1層)，而第k層結(jié)點數(shù)最多為2k－1個。設有序表的長度為n＝2h－1(即h=log2(n+1)),則折半查找的判定樹為深為h的滿二叉樹，并設每條記錄的查找概率(pi=1/n)相等，則查找成功時的平均查找長度：2

j

-1hi

=1

j

=1j1ni

inASL

bs

=

p

c

=2

2n=

n

+

1

log (

n

+

1)

-

1

?

log (

n

+

1)

-

1可見，折半查找的效率比順序查找高，但是，折半查找只適用于有序表，且限于用順序存儲結(jié)構(gòu)（對線性鏈表無法有效進行折半查找）索引表:按表中記錄的關(guān)鍵字分塊,R1,R2,…,RL要求:

第Rk

塊中的所有關(guān)鍵字<

Rk+1塊中的所有關(guān)鍵字k=1,2,…,L-1,

稱為“分塊有序”對每塊建立一個索引項,包含以兩項內(nèi)容:①關(guān)鍵字項:為該塊中最大關(guān)鍵字值;②指針項:為該塊第一個記錄在表中位置.所有索引項組成索引表三、索引順序表的查找(分塊查找)項

2248861713三、索引順序表的查找(分塊查找)例.查找表為:22,

12,

13,

8,

9,

20,

33,

42,

44,

38,

24,

48,

60,

58,

74,

49,

86,

53索引表為:關(guān)鍵字指針項22,

12,

13,

8,

9,

20,

33,

42,

44,

38,

24,

48,

60,

58,

74,

49,

86,

53關(guān)鍵字項指針項2248861

7

1322,

12,

13,

8,

9,

20,

33,

42,

44,

38,

24,

48,

60,

58,

74,

49,

86,

53查找分為兩步:確定待查記錄所在塊;

(可以用順序或折半查找)在塊內(nèi)順序查找.

(只能用順序查找)例如:k=38第1步:k=38

的記錄只可能在塊2中;第2步:從r[7]開始,直到k=r[i].key

或i>12為止.三、索引順序表的查找(分塊查找)分塊查找表的平均查找長度ASL=Lb+Lw其中:Lb為查索引表確定所在塊的平均查找長度;Lw為在塊內(nèi)查找記錄的平均查找長度;.性能分析設長度為n的表均勻地分為b塊，每塊有s個記錄，且表中每個記錄的查找概率相等，則：三、索引順序表的查找(分塊查找)1）若順序查找確定所在塊：2

2

2

2

s?

n

+

1=

b

+

1

+

s

+

1

=

1

(b

+

s

)

+

1

=

1

(

n

+

s

)

+

1sb+

ASLASL

=

ASLsj

+

1

ib=

1

j

=1

i

=1wbbs2）若折半查找確定所在塊：1222s

2isswbbs(

n

+

1)

+

ss

2=

log (

n

+

1)

+

s

+

1

?

log?

log (

b

+

1)

-

1

++

ASLASL

=

ASLi

=1小結(jié)：靜態(tài)查找表三種查找方法的比較順序查找折半查找分塊查找平均查找長度最大最小介于二者之間表結(jié)構(gòu)有序/無序表有序表表中元素逐段有序存儲結(jié)構(gòu)順序/鏈式存儲順序存儲順序/鏈式存儲9.2動態(tài)查找表動態(tài)查找表的特點：

表結(jié)構(gòu)本身是在查找過程中動態(tài)生成的，即對于給定值key,若表中存在其關(guān)鍵字等于key的記錄，則查找成功返回，否則插入關(guān)鍵字等于key的記錄。一、二叉排序樹（二叉查找樹）二、二叉平衡樹三、B-樹和B+樹一、二叉排序樹（二叉查找樹）定義查找算法插入算法刪除算法查找性能的分析1．定義：二叉排序樹或者是一棵空樹；或者是具有如下特性的二叉樹：若它的左子樹不空，則左子樹上

所有結(jié)點的值均小于根結(jié)點的值；若它的右子樹不空，則右子樹上

所有結(jié)點的值均大于根結(jié)點的值；它的左、右子樹也都分別是二叉排序樹。5030802090854010

25

352388例如:66不是二叉排序樹。通常，取二叉鏈表作為二叉排序樹的存儲結(jié)構(gòu)typedef

struct

BiTNode

{

//結(jié)點結(jié)構(gòu)TElemType

data;struct

BiTNode

*lchild,

*rchild;//左右孩子指針}

BiTNode,

*BiTree;1）若給定值等于根結(jié)點的關(guān)鍵字，則查找成功；2）若給定值小于根結(jié)點的關(guān)鍵字，則繼續(xù)在左子樹上進行查找；3）若給定值大于根結(jié)點的關(guān)鍵字，則繼續(xù)在右子樹上進行查找。2．二叉排序樹的查找算法：若二叉排序樹為空，則查找不成功；否則，858832例如:

二叉排序樹335555003020

40809900查找關(guān)鍵字==50

,

35

,

90

,

95

,從上述查找過程可見，在查找過程中，生成了一條查找路徑：從根結(jié)點出發(fā)，沿著左分支或右分支逐層向下直至關(guān)鍵字等于給定值的結(jié)點;或者

——查找成功從根結(jié)點出發(fā)，沿著左分支或右分支逐層向下直至指針指向空樹為止?！檎也怀晒Σ檎疫^程算法9.5-a

遞歸過程BiTree

SearchBST(BiTree

T,KeyType

key){if

(!T)

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

return

T;else

if

LT(key,T->data.key)return(SearchBST(T->lchild,key));elsereturn(SearchBST(T->rchild,key));}//

SearchBST算法描述如下：Status

SearchBST

(BiTree

T,

KeyType

key,BiTree

f,

BiTree

&p

)

{//在根指針T

所指二叉排序樹中遞歸地查找其//關(guān)鍵字等于key

的數(shù)據(jù)元素，若查找成功，//則返回指針p

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

函數(shù)值為TRUE;

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

指向查找路徑上訪問的最后一個結(jié)點，//并返回函數(shù)值為FALSE,指針f

指向當前訪問//的結(jié)點的雙親，其初始調(diào)用值為NULL…

…

…

…}

//

SearchBSTif

(!T){p=f;

return

FALSE;}

//查找不成功else if

(EQ(key,

T->data.key)

){p=T;

return

TRUE;}

//查找成功else if

(

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

(T->lchild,

key,

T,

p

);//在左子樹中繼續(xù)查找else

SearchBST

(T->rchild,

key,

T,

p

);//在右子樹中繼續(xù)查找3020104023fT48fTfT設key=22pfTfTTTTfff

25

35p3．二叉排序樹的插入算法根據(jù)動態(tài)查找表的定義，“插入”操作在查找不成功時才進行；新插入的結(jié)點必為一個新的葉子結(jié)點（若二叉排序樹為空樹，則新插入的結(jié)點為新的根結(jié)點）

，其插入位置由查找路徑上訪問最后一個結(jié)點的左孩子或右孩子。Status

Insert

BST(BiTree

&T,

ElemType

e

){//當二叉排序樹中不存在關(guān)鍵字等于e.key

的//數(shù)據(jù)元素時，插入元素值為e

的結(jié)點，并返//回TRUE;

否則，不進行插入并返回FALSEif

(!SearchBST

(

T,

e.key,

NULL,

p

))}else

return

FALSE;}

//

InsertBST{

…

…s

=

(BiTree)

malloc

(sizeof

(BiTNode));//為新結(jié)點分配空間s->data=e;s->lchild

=

s->rchild

=

NULL;if

(

!p

) T

=

s;//插入s

為新的根結(jié)點else if

(

LT(e.key,

p->data.key)

)p->lchild

=

s;else

p->rchild=s;//插入*s

為*p的左孩子//插入*s

為*p

的右孩子return

TRUE;//插入成功例：設BST為空，查找關(guān)鍵字序列為{45，24，53，45，12，24，90}，則經(jīng)過一系列查找插入操作后，生成的BST為：45245312904．二叉排序樹的刪除算法和插入相反，刪除在查找成功之后進行，并且要求在刪除二叉排序樹上某個結(jié)點之后，仍然保持二叉排序樹的特性?？煞秩N情況討論：（1）被刪除的結(jié)點是葉子；（2）被刪除的結(jié)點只有左子樹或者只有右子樹；（3）被刪除的結(jié)點既有左子樹，也有右子樹。503080209085403588（1）被刪除的結(jié)點是葉子結(jié)點例如:20被刪關(guān)鍵字=8832其雙親結(jié)點中相應指針域的值改為“空”30802090854035（2）被刪除的結(jié)點只有左子樹或者只有右子樹5032

88其雙親結(jié)點的相應指針域的值改為

“指向被刪除結(jié)點的左子樹或右子樹”。40被刪關(guān)鍵字=802090854035（3）被刪除的結(jié)點既有左子樹，也有右子樹4088以其前驅(qū)替代之，然后再刪除該前驅(qū)結(jié)點32前驅(qū)結(jié)點

被刪結(jié)點被刪關(guān)鍵字=50540030

80Status

DeleteBST

(BiTree

&T,

KeyType

key

)

{//若二叉排序樹T

中存在其關(guān)鍵字等于key

的//數(shù)據(jù)元素，則刪除該數(shù)據(jù)元素結(jié)點，并返回//函數(shù)值TRUE，否則返回函數(shù)值FALSEif

(!T)

return

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

{}}

//

DeleteBST算法描述如下：……if

(

EQ

(key,

T->data.key)

){ Delete(T);

return

TRUE;

}//找到關(guān)鍵字等于key的數(shù)據(jù)元素else

if

(

LT

(key,

T->data.key)

)DeleteBST

(

T->lchild,

key

);//繼續(xù)在左子樹中進行查找else

DeleteBST

(

T->rchild,

key

);//繼續(xù)在右子樹中進行查找}其中刪除操作過程如下所描述：void

Delete

(

BiTree

&p){//從二叉排序樹中刪除結(jié)點p，//并重接它的左子樹或右子樹if

(!p->rchild)

{

…

…

}…

…else

if

(!p->lchild)

{else{

…

…

}}//

Delete//右子樹為空樹則只需重接它的左子樹q

=

p; p

=

p->lchild;

free(q);pp//左子樹為空樹只需重接它的右子樹q

=

p; p

=

p->rchild;

free(q);pp//左右子樹均不空q=p; s

=p->lchild;while

(!s->rchild)

{

q

=

s; s=s->rchild;

}//s

指向被刪結(jié)點的前驅(qū)p->data=s->data;if

(q

!=p) q->rchild=s->lchild; //重接*q右子樹pqspqselse

q->lchild

=

s->lchild;//重接*q的左子樹free(s);5．查找性能的分析對于每一棵特定的二叉排序樹，均可按照平均查找長度的定義來求它的ASL

值，顯然，由值相同的n個關(guān)鍵字，構(gòu)造所得的不同形態(tài)的各棵二叉排序樹的平均查找長度的值不同，甚至可能差別很大。例如：2134535412由關(guān)鍵字序列1，2，3，4，5構(gòu)造而得的二叉排序樹，ASL

=（1+2+3+4+5）/

5=

3由關(guān)鍵字序列3，1，2，5，4構(gòu)造而得的二叉排序樹，ASL

=（1+2+3+2+3）/

5=

2.2二、二叉平衡樹何謂“二叉平衡樹”？如何構(gòu)造“二叉平衡樹”二叉平衡樹的查找性能分析二叉平衡樹是二叉查找樹的另一種形式，其特點為：樹中每個結(jié)點的左、右子樹深度之差的絕對值不大于1例如:hL

-hR

￡1

。548254821是平衡樹不是平衡樹構(gòu)造的二叉排序樹成為平衡樹的方法是：25868在插入過程中，采用平衡旋轉(zhuǎn)技術(shù)。例如:依次插入的關(guān)鍵字為5,4,2,8,6,95

4

44

2

2

6向右旋轉(zhuǎn)一次5先向右旋轉(zhuǎn)再向左旋轉(zhuǎn)42

65

89642895向左旋轉(zhuǎn)一次繼續(xù)插入關(guān)鍵字9ABDCEACDBEACEDB右單旋左單旋1.2.ABDCEhABDCFEGAEBDCFG左單旋右單旋ABDCFEhh-1G3.右單旋左單旋4.DACBEFhh-1GACBEFGDACBEFGD平衡樹的查找性能分析：在平衡樹上進行查找的過程和二叉排序樹相同，因此，查找過程中和給定值進行比較的關(guān)鍵字的個數(shù)不超過平衡樹的深度。問：含n個關(guān)鍵字的二叉平衡樹可能達到的最大深度是多少？n

=

0空樹最大深度為0n

=

1最大深度為1n

=

2最大深度為2n

=

4最大深度為3n

=

7最大深度為4先看幾個具體情況:反過來問，深度為h的二叉平衡樹中所含結(jié)點的最小值Nh

是多少？h

=

0

N0

=

0

h

=

1N1

=

1h

=

2

N2

=

2

h

=

3

N3

=

4一般情況下

Nh

=

Nh-1

+

Nh-2

+

1平衡樹上查找的時間復雜度：O(logn)9.2.2

B-樹和B+樹一、B-樹(多路搜索樹）1.定義：一棵m階的B-樹，或為一棵空樹，或為滿足下列條件的m叉樹：樹中每個結(jié)點至多m棵子樹；若根結(jié)點不是葉結(jié)點，則至少2棵子樹；除根以外的所有非終端結(jié)點至少有┌m/2┐棵子樹；所有非終端結(jié)點中包含下列信息數(shù)據(jù)：（n,A0,K1,A1,K2,A2,…，Kn,An)葉結(jié)點位于同一層次（外部結(jié)點/失敗點）351181784321112713916447533991FFFFFFFFFFFFbcdefgh2.示例（一棵4階B－樹及查找過程）Ta查找時間取決因素等于給定值的關(guān)鍵字所在結(jié)點的層次；結(jié)點中關(guān)鍵字的個數(shù)。（M=3）3階B-樹3.查找過程：順指針查找結(jié)點和在結(jié)點的關(guān)鍵字中順序查找交叉進行的過程。具體方法：從根結(jié)點開始，將key與根結(jié)點中的各個關(guān)鍵字k1,k2,……，kj進行比較，由于該關(guān)鍵字序列有序，可采用順序/二分查找方法。若key=ki,(1≤i≤j),則查找成功；若key<k1,則沿指針A0所指的子樹中繼續(xù)查找；若ki<key<ki+1,則沿指針Ai所指的子樹中繼續(xù)查找；若key>kj,則沿指針Aj所指的子樹中繼續(xù)查找。在自上向下的查找過程中，若直到葉結(jié)點也沒有找到值為key的關(guān)鍵字，則查找失敗。9.2.2

B-樹和B+樹B＋樹（B－的變型樹）

B+樹是B-樹的變體，也是一種多路搜索樹，其定義基本與B-樹同，除了：–

1）非葉子結(jié)點的子樹指針與關(guān)鍵字個數(shù)相同；

2）非葉子結(jié)點的子樹指針P[i]，指向關(guān)鍵字值屬于[K[i],K[i+1])的子樹（B-樹是開區(qū)間）；3）為所有葉子結(jié)點增加一個鏈指針；4）所有關(guān)鍵字都在葉子結(jié)點出現(xiàn)；（M=3）3階B+樹B+的搜索與B-樹也基本相同，區(qū)別是B+樹只有達到葉子結(jié)點才命中（B-樹可以在非葉子結(jié)點命中），其性能也等價于在關(guān)鍵字全集做一次二分查找；B+的特性：1.所有關(guān)鍵字都出現(xiàn)在葉子結(jié)點的鏈表中（稠密索引），且鏈表中的關(guān)鍵字恰好是有序的；2.不可能在非葉子結(jié)點命中；3.非葉子結(jié)點相當于是葉子結(jié)點的索引（稀疏索引），葉子結(jié)點相當于是存儲（關(guān)鍵字）數(shù)據(jù)的數(shù)據(jù)層；4.更適合文件索引系統(tǒng)；一、哈希表是什么？二、哈希函數(shù)的構(gòu)造方法三、處理沖突的方法四、哈希表的查找五、哈希表的刪除操作六、對靜態(tài)查找表，．．．9.3

哈

希

表一、哈希表是什么？以上兩節(jié)討論的表示查找表的各種結(jié)構(gòu)的共同特點：記錄在表中的位置和它的關(guān)鍵字之間不存在一個確定的關(guān)系，查找的過程為給定值依次和關(guān)鍵字集合中各個關(guān)鍵字進行比較，查找的效率取決于和給定值進行比較的關(guān)鍵字個數(shù)。用這類方法表示的查找表，其平均查找長度都不為零。不同的表示方法，其差別僅在于：

關(guān)鍵字和給定值進行比較的順序不同。對于頻繁使用的查找表，希望

ASL

=

0。只有一個辦法：預先知道所查關(guān)鍵字在表中的位置，即，要求：記錄在表中位置和其關(guān)鍵字之間存在一種確定的關(guān)系。例如：為每年招收的1000

名新生建立一張查找表，其關(guān)鍵字為學號，其值的范圍為xx000

~

xx999(前兩位為年份)。若以下標為000~999

的順序表表示之。則查找過程可以簡單進行：取給定值（學號）的后三位，不需要經(jīng)過比較便可直接從順序表中找到待查關(guān)鍵字。但是，對于動態(tài)查找表而言，表長不確定；在設計查找表時，只知道關(guān)鍵字所 屬范圍，而不知道確切的關(guān)鍵字。因此在一般情況下，需在關(guān)鍵字與記錄在表中的存儲位置之間建立一個函數(shù)關(guān)系，以f(key)作為關(guān)鍵字為key

的記錄在表中的位置，通常稱這個函數(shù)f(key)為哈希函數(shù)。例如：對于如下9

個關(guān)鍵字{Zhao,

Qian,Sun,

Li,

Wu,

Chen,Han,Ye,Dei}ChenDeiHanLiQianSunWuYe

Zhao設哈希函數(shù)f(key)=(Ord(第一個字母)-Ord('A')+1)/20

1

2

3

4

5

6

7

8

9

10

1

1

1

2

1

3問題:

若添加關(guān)鍵字

Zhou,怎么辦？能否找到另一個哈希函數(shù)？從這個例子可見：哈希函數(shù)是一個映象，即：將關(guān)鍵字的集合映射到某個地址集合上，它的設置很靈活，只要這個地址集合的

大小不超出允許范圍即可；由于哈希函數(shù)是一個壓縮映象，因此，在一般情況下，很容易產(chǎn)生“沖突”現(xiàn)象，即：

key1?

key2，而

f(key1)

=f(key2)。3)

很難找到一個不產(chǎn)生沖突的哈希函數(shù)。一般情況下，只能選擇恰當?shù)墓：瘮?shù)，使沖突盡可能少地產(chǎn)生。因此，在構(gòu)造這種特殊的“查找表”時，除了需要選擇一個“好”(盡可能少產(chǎn)生沖突)的哈希函數(shù)之外；還需要找到一種“處理沖突”的方法。哈希表的定義：根據(jù)設定的哈希函數(shù)H(key)和所選中的處理沖突的方法，將一組關(guān)鍵字映象到一個有限的、地址連續(xù)的地址集(區(qū)間)上，并以關(guān)鍵字在地址集中的“象”作為相應記錄在表中的存儲位置，如此構(gòu)造所得的查找表稱之為“哈希表”。二、構(gòu)造哈希函數(shù)的方法對數(shù)字的關(guān)鍵字可有下列構(gòu)造方法：若是非數(shù)字關(guān)鍵字，則需先對其進行數(shù)字化處理。折疊法除留余數(shù)法隨機數(shù)法直接定址法數(shù)字分析法平方取中法1.

直接定址法哈希函數(shù)為關(guān)鍵字的線性函數(shù)H(key)=key

或者H(key)=a

·

key+b此法僅適合于：地址集合的大小==關(guān)鍵字集合的大小2.

數(shù)字分析法假設關(guān)鍵字集合中的每個關(guān)鍵字都是由s位數(shù)字組成(u1,u2,…,us)，分析關(guān)鍵字集中的全體，并從中提取分布均勻的若干位或它們的組合作為地址。此方法僅適合于：能預先估計出全體關(guān)鍵字的每一位上各種數(shù)字出現(xiàn)的頻度。3.

平方取中法以關(guān)鍵字的平方值的中間幾位作為存儲地址。求“關(guān)鍵字的平方值”的目的是“擴大差別”，同時平方值的中間各位又能受到整個關(guān)鍵字中各位的影響。此方法適合于:關(guān)鍵字中的每一位都有某些數(shù)字重復出現(xiàn)頻度很高的現(xiàn)象。4.

折疊法將關(guān)鍵字分割成若干部分，然后取它們的疊加和為哈希地址。有兩種疊加處理的方法：移位疊加和間界疊加。此方法適合于:關(guān)鍵字的數(shù)字位數(shù)特別多。5.

除留余數(shù)法設定哈希函數(shù)為:H(key)

=key

MOD

p其中，

p≤m

(表長)

并且p應為不大于m的最大的素數(shù)或是不含20

以下的質(zhì)因子為什么要對p

加限制？例如：給定一組關(guān)鍵字為：12,

39,

18,

24,

33,

21，若取p=9,則他們對應的哈希函數(shù)值將為：

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

為偽隨機函數(shù)通常，此方法用于對長度不等的關(guān)鍵字構(gòu)造哈希函數(shù)。實際造表時，采用何種構(gòu)造哈希函數(shù)的方法取決于建表的關(guān)鍵字集合的情況(包括關(guān)鍵字的范圍和形態(tài))，總的原則是使產(chǎn)生沖突的可能性降到盡可能地小。190123145568118236811302053例如:

關(guān)鍵字集合{19,

01,

23,

14,

55,

68,

11,

82,

36},表長=11用除留余數(shù)法，構(gòu)造Hash函數(shù)?？稍OHash函數(shù)：H(key)=key

MOD

11keyH(key)三、處理沖突的方法“處理沖突”的實際含義是：為產(chǎn)生沖突的地址尋找下一個哈希地址。1.

開放定址法2.再哈希法3.

鏈地址法(拉鏈法）4.建立一個公共溢出區(qū)為產(chǎn)生沖突的地址H(key)求得一個地址序列：1≤

s≤m-1H0,

H1,

H2,

…,

Hs其中：H0

=H(key)Hi

=(

H(key)

+

di

)

MODmi=1,2,…,s1.

開放定址法對增量

di

有三種取法：1)

線

性

探

測

再

散

列di

=

c·

i最簡單的情況

c=12)

平

方

探

測

再

散

列di

=

12,

-12,

22,

-22,

…,3)

隨

機

探

測

再

散

列di

是一組偽隨機數(shù)列

或者di=i×H2(key)(又稱雙散列函數(shù)探測)例如:

關(guān)鍵字集合{

19,

01,

23,

14,

55,

68,

11,

82,

36

}設定哈希函數(shù)H(key)=key

MOD

11(表長=11)78

910若采用線性探測再散列處理沖突550123143682681911012345678910550123146811823619112136251若采用二次探測再散列處理沖突0

1

2

3

4

5

61

1

2

1

2

1

413ASL

=22/9ASL

=16/9H2(key)是另設定的一個哈希函數(shù)，它的函數(shù)值應和m

互為素數(shù)。230168141182551936若m

為素數(shù)，則H2(key)可以是1

至m-1之間的任意數(shù)；若m為2的冪次，則

H2(key)應是1

至m-1之間的任意奇數(shù)。例如，當m=11時，可設di=H2(key)=(3×key)MOD10+10

1

2

3

4

5

6

7

8

9

102

1

1

1

2

1

2

1

32.再哈希法基本思想：當發(fā)生沖突時，利用不同的哈希函數(shù)

再求得一個新的地址，直到不出現(xiàn)沖突為止，即：Hi=RHi(key)

i=1,2,……，m其中:RHi

為一組不同的哈希函數(shù)。當?shù)谝淮伟l(fā)生沖突時，用RH1計算得到一個新的哈希地址H1

，如果仍然有沖突，又用RH2計算得到一個新的哈希地址H2

，……。依次類推，直到求得某個Hi

不再沖突為止。特點：這種方法一般不會產(chǎn)生“聚集”現(xiàn)象，但需要定義多個不同的哈希函數(shù)，并且增加了計算的時間。3.

鏈地址法

將所有哈希地址相同的記錄（拉鏈法）

都鏈接在同一鏈表中。0123456140136198223116855ASL=(6×1+2×2+3)/9=13/9例如:同前例的關(guān)鍵字，哈希函數(shù)為

H(key)=key

MOD

74.建立一個公共溢出區(qū)基本思想：在基本哈希表以外，另外設立一個溢出表，存放與基本表中記錄沖突的所有記錄。四、哈希表的查找查找過程和造表過程一致。假設采用開放定址處理沖突，則查找過程為：對于給定值K，計算哈希地址i=H(K)若

r[i]

=

NULL

則查找不成功若

r[i].key

=

K

則查找成功否則“求下一地址Hi”，直至r[Hi]=NULL

(查找不成功)或

r[Hi].key

=

K

(查找成功)

為止。TA[i]

為空？i=H（key)A[i].key==key?i＝下一個哈希存儲地址失敗成功TFF1.哈希查找法是一種直接計算地址的方法，在查找