數(shù)據(jù)結構查找演示文稿當前第1頁\共有78頁\編于星期五\0點優(yōu)選數(shù)據(jù)結構查找Ppt當前第2頁\共有78頁\編于星期五\0點術語：查找(檢索)——根據(jù)給定的某個值，在表中確定一個關鍵字等于給定值的記錄或數(shù)據(jù)元素

關鍵字——是記錄某個數(shù)據(jù)項的值，它可以唯一標識一個記錄。

次關鍵字——不能唯一的確定一個記錄，但能確定表的一個子表。子表的元素個數(shù)應遠少于表中元素數(shù)。為簡化問題，將表中元素看成簡單的整型數(shù)據(jù)，理解為關鍵字部分。當前第3頁\共有78頁\編于星期五\0點8.1靜態(tài)查找表

1、順序表的順序查找

應用范圍：順序表或線性鏈表表示的表，表內(nèi)元素之間無序。查找過程：從表的一端開始逐個進行記錄的關鍵字和給定值的比較。

search(st,key，n)//在有n個數(shù)據(jù)的表st中找key{i=n-1;while(i>=0&&st[i]!=key)i--;if(i<0)return-1;//查找不成功返回-1

elsereturni;//查找成功返回下標號}算法主要時間在循環(huán)，為減少判定，n個數(shù)據(jù)用容量為n+1的一維數(shù)組表示。st[1]到st[n]存儲數(shù)據(jù)，st[0]作為監(jiān)視哨

search1(st,key，n){st[0]=key;i=n;while(st[i]!=key)i--;returni;//查找返回序號，0為不成功}當前第4頁\共有78頁\編于星期五\0點順序查找的平均時間為表長的一半。2、順序有序表的查找———二分（折半）查找查找過程：每次將待查記錄所在區(qū)間縮小一半適用條件：采用順序存儲結構的有序表算法實現(xiàn)設表長為n，low、high和mid分別指向待查元素所在區(qū)間的上界、下界和中點,k為給定的待查值初始時，令low=1,high=n,mid=(low+high)/2讓k與mid指向的記錄比較：若k=r[mid]，查找成功，結束若k<r[mid]，則high=mid-1若k>r[mid]，則low=mid+1重復上述操作，直至low>high時，查找失敗highmidlow當前第5頁\共有78頁\編于星期五\0點bin_search(st[],key,n){low=0;high=n-1;while(low<=high){mid=(low+high)/2;

if(st[mid]==key)returnmid;elseif(st[mid]>key)high=mid-1;elselow=mid+1;}return-1;}mid=(low+high)>>1;遞歸：bin_search(st[],key,l,h){if(l<=h){mid=(l+h)>>1;if(st[mid]==key)returnmid;elseif(st[mid]>key)returnbin_search(st,key,l,mid-1);elsereturnbin_search(st,key,mid+1,h)}elsereturn-1;}平均查找時間當前第6頁\共有78頁\編于星期五\0點3、分塊查找數(shù)據(jù)組織：將表分成幾塊，塊內(nèi)無序，塊間有序；先確定待查記錄所在塊，再在塊內(nèi)查找（1）用數(shù)組存放待查記錄,（2）建立索引表，由每塊中最大（?。┑年P鍵字及所屬塊位置的信息組成。當前第7頁\共有78頁\編于星期五\0點12345678910111213141516171822121389203342443824486058745786532248861713索引表查38當索引表較大時，可以采用二分查找在數(shù)據(jù)量極大時，索引可能很多，可考慮建立索引表的索引，即二級索引，原則上索引不超過三級當前第8頁\共有78頁\編于星期五\0點分塊查找方法評價由上面的公式，在n一定時，可以通過選擇s使ASL盡可能小可以證明，當時，對于（1）ASL最小。當前第9頁\共有78頁\編于星期五\0點小結：時間：順序查找最差，二分最好，分塊介于兩者之間空間：分塊最大，需要增加索引數(shù)據(jù)的空間特點：1）順序查找對表沒有特殊要求2）分塊時數(shù)據(jù)塊之間在物理上可不連續(xù)。所以可以達到插入、刪除數(shù)據(jù)只涉及對應的塊；另外，增加了索引的維護。3）二分查找要求表有序，所以若表的元素的插入與刪除很頻繁，維持表有序的工作量極大。4）在表不大時，一般直接使用順序查找。當前第10頁\共有78頁\編于星期五\0點二分查找的C/C++接口stdlib.hvoid*bsearch(void*key,void*base,intnelement,intsize,int(*fcmp)(constvoid*,constvoid*))其中：fcmp規(guī)定：第一個數(shù)據(jù)小于第二個，返回小于0的數(shù)第一個數(shù)據(jù)等于第二個，返回0第一個數(shù)據(jù)大于第二個，返回大于0的數(shù)當前第11頁\共有78頁\編于星期五\0點#include<iostream.h>#include<stdlib.h>cmp(constvoid*a,constvoid*b){ if(*(int*)a<*(int*)b)return-1; elseif(*(int*)a==*(int*)b)return0; elsereturn1;}voidmain(){ intar[]={-2,3,6,9,10,21,22,34,56}; int*p; intt; t=9; p=(int*)bsearch(&t,ar,sizeof(ar)/sizeof(int),sizeof(int),cmp); if(p!=NULL)cout<<*p<<endl;}當前第12頁\共有78頁\編于星期五\0點8.2動態(tài)查找8.2.1二叉排序樹和二叉平衡樹一、二叉排序樹1

二叉排序樹定義

二叉排序樹（BinarySortTree）或者是一棵空樹；或者是具有下列性質(zhì)的二叉樹：（1）若左子樹不空，則左子樹中所有結點的值均小于它的根結點的值；（2）若右子樹不空，則右子樹中所有結點的值均大于它的根結點的值；（3）左、右子樹也分別為二叉排序樹；當前第13頁\共有78頁\編于星期五\0點45372453100619078312根據(jù)二叉排序樹的定義，對二叉樹進行LDR遍歷得到是遞增序列。當前第14頁\共有78頁\編于星期五\0點2、查找：步驟：若根結點的關鍵字值等于查找的關鍵字，成功。否則，若小于根結點的關鍵字值，遞歸查左子樹。若大于根結點的關鍵字值，遞歸查右子樹。若子樹為空，查找不成功。12225030011020099105230216

TreeNode*SearchBST(t,key)/*在二叉分類樹查找關鍵字之值為key的結點，找到返回該結點的地址，否則返回空。t為二叉分類樹的根結點的指針。*/{if(t==NULL||key==t->data)returnt;elseif（key<t->data)returnSearchBST(t->lchild,key);elsereturnSearchBST(t->rchild,key);}//SearchBST當前第15頁\共有78頁\編于星期五\0點3、插入算法：首先執(zhí)行查找算法，找出被插結點的父親結點。判斷被插結點是其父親結點的左、右兒子。將被插結點作為葉子結點插入。若二叉樹為空。則首先單獨生成根結點。

注意：新插入的結點總是葉子結點。例：將序列：122、99、250、110、300、280作為二叉排序樹的結點的關鍵字值，生成二叉排序樹。12299250300280110當前第16頁\共有78頁\編于星期五\0點voidInsertBST(*&t，key)//在二叉排序樹中插入查找關鍵字key{if(t==NULL){t=newBiTree;t->lchild=t->rchild=NULL;t->data=key;return;}if(key<t->data)InsertBST(t->lchild,key);elseInsertBST(t->rchild,key);}voidCreateBiTree(tree,d[],n）//n個數(shù)據(jù)在數(shù)組d中，tree為二叉排序樹根{tree=NULL;for(i=0;i<n;i++)InsertBST(tree,d[i]);}類C程序?qū)崿F(xiàn)：當前第17頁\共有78頁\編于星期五\0點4.二叉排序樹中一個結點的刪除在二叉排序樹中刪除結點的原則是：刪除結點后仍是二叉排序樹。

設在二叉排序樹被刪除結點是x，其雙親結點為f。情況討論：（1）x為葉子結點，則直接刪除（2）x只有左子樹xL或只有右子樹xR,則令xL或xR直接成為雙親結點f的子樹；ffxxLfxxRf當前第18頁\共有78頁\編于星期五\0點（3）x即有左子樹xL也有右子樹xRfxxRxL在xL中選值最大的代替x，該數(shù)據(jù)按二叉排序樹的性質(zhì)應在最右邊。qfxxRcscLqLsLfsxRcqcLqLsL當前第19頁\共有78頁\編于星期五\0點二叉排序樹的刪除操作例子

葉子結點：直接刪除。如：刪除數(shù)據(jù)為15、70的結點。15607030205060302050當前第20頁\共有78頁\編于星期五\0點12225030011020099105230216400450500若被刪結點的左兒子為空或者右兒子為空。如下圖所示，刪除結點的數(shù)據(jù)場為200的結點。刪除20012225030023021640045050011099105當前第21頁\共有78頁\編于星期五\0點被刪結點的左、右子樹皆不空1222503001102009910523021640045050011025030010520099230216400450500當前第22頁\共有78頁\編于星期五\0點voiddelete(*&p){if(p->rchild==NULL){q=p;p=p->lchild;deleteq;}elseif(p->lchild==NULL){q=p;p=p->rchild;deleteq;}else{q=p;s=p->lchild;while(s->rchild!=NULL){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;}deletes;}當前第23頁\共有78頁\編于星期五\0點voiddelete(*&p){

if(p->rchild==NULL){q=p;p=p->lchild;deleteq;}elseif(p->lchild==NULL){q=p;p=p->rchild;deleteq;}else{q=p;s=p->lchild;while(s->rchild!=NULL){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;}deletes;}pq當前第24頁\共有78頁\編于星期五\0點voiddelete(*&p){

if(p->rchild==NULL){q=p;p=p->lchild;deleteq;}elseif(p->lchild==NULL){q=p;p=p->rchild;deleteq;}else{q=p;s=p->lchild;while(s->rchild!=NULL){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;}deletes;}pq當前第25頁\共有78頁\編于星期五\0點voiddelete(*&p){

if(p->rchild==NULL){q=p;p=p->lchild;deleteq;}

elseif(p->lchild==NULL){q=p;p=p->rchild;deleteq;}else{q=p;s=p->lchild;while(s->rchild!=NULL){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;}deletes;}pq當前第26頁\共有78頁\編于星期五\0點voiddelete(*&p){

if(p->rchild==NULL){q=p;p=p->lchild;deleteq;}

elseif(p->lchild==NULL){q=p;p=p->rchild;deleteq;}else{q=p;s=p->lchild;while(s->rchild!=NULL){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;}deletes;}pq當前第27頁\共有78頁\編于星期五\0點voiddelete(*&p){

if(p->rchild==NULL){q=p;p=p->lchild;deleteq;}

elseif(p->lchild==NULL){q=p;p=p->rchild;deleteq;}else{q=p;s=p->lchild;while(s->rchild!=NULL){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;}deletes;}pqs當前第28頁\共有78頁\編于星期五\0點voiddelete(*&p){

if(p->rchild==NULL){q=p;p=p->lchild;deleteq;}

elseif(p->lchild==NULL){q=p;p=p->rchild;deleteq;}else{q=p;s=p->lchild;while(s->rchild!=NULL){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;}deletes;}psq當前第29頁\共有78頁\編于星期五\0點voiddelete(*&p){

if(p->rchild==NULL){q=p;p=p->lchild;deleteq;}

elseif(p->lchild==NULL){q=p;p=p->rchild;deleteq;}else{q=p;s=p->lchild;while(s->rchild!=NULL){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;}deletes;}psdq當前第30頁\共有78頁\編于星期五\0點voiddelete(*&p){

if(p->rchild==NULL){q=p;p=p->lchild;deleteq;}

elseif(p->lchild==NULL){q=p;p=p->rchild;deleteq;}else{q=p;s=p->lchild;while(s->rchild!=NULL){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;}deletes;}dpsdq當前第31頁\共有78頁\編于星期五\0點voiddelete(*&p){

if(p->rchild==NULL){q=p;p=p->lchild;deleteq;}

elseif(p->lchild==NULL){q=p;p=p->rchild;deleteq;}else{q=p;s=p->lchild;while(s->rchild!=NULL){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;}deletes;}dpsdq當前第32頁\共有78頁\編于星期五\0點voiddelete(*&p){

if(p->rchild==NULL){q=p;p=p->lchild;deleteq;}elseif(p->lchild==NULL){q=p;p=p->rchild;deleteq;}else{q=p;s=p->lchild;while(s->rchild!=NULL){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;}deletes;}p等于q的情況spxqsxqp當前第33頁\共有78頁\編于星期五\0點刪除一個結點：DeleteBST(*&t,key)//在根為t的排序二叉樹中刪去值為key的結點{

if(!t)returnelseif(t->data==key){delete(t);elseif(t->data>key)DeleteBST(t->lchild,key);elseDeleteBST(t->rchild,key);}當前第34頁\共有78頁\編于星期五\0點DABCFEG二、平衡二叉樹

起因：提高查找速度，避免最壞情況出現(xiàn)。如下圖單枝情況的出現(xiàn)。

平衡因子（平衡度）：結點的平衡因子是結點的左子樹的高度減去右子樹的高度。（或反之定義）

平衡二叉樹：每個結點的平衡因子都為1、－1、0的二叉排序樹?；蛘哒f每個結點的左右子樹的高度最多差1的二叉排序樹。1、概念與定義當前第35頁\共有78頁\編于星期五\0點例：014125392863536050171873011-1-1-100000000平衡二叉樹028181453963536050173012-1-100001-1非平衡二叉樹0當前第36頁\共有78頁\編于星期五\0點

2、平衡樹的平衡方法：在左圖所示的平衡樹中插入數(shù)據(jù)為2的結點。插入之后仍應保持平衡分類二叉樹的性質(zhì)不變。14125392863536050171873011-1-1-100000000平衡樹1412539286353605017187301-1-1-1000000002112原平衡度為0不平衡點解決：如何用最簡單、最有效的辦法保持平衡分類二叉樹的性質(zhì)2當前第37頁\共有78頁\編于星期五\0點141253928635360501718730+1+1-1-1-1000000002112原平衡度為0不平衡點Adelson解決思路：不涉及到不平衡點的雙親，即以不平衡點為根的子樹的高度應保持不變。新結點插入后，向根回溯找到第一個原平衡因子不為0的結點（如圖中9）。新插入的結點和第一個平衡因子不為0的結點之間的結點，其平衡因子原皆為0在調(diào)整中，僅涉及前面所提到的最小子樹（如：以9為根的子樹）仍應保持排序二叉樹的性質(zhì)不變。當前第38頁\共有78頁\編于星期五\0點3、平衡種類分析

左調(diào)整（新結點插入在左子樹上的調(diào)整）：1、LL情況：（插入在結點左子樹的左子樹上）LL旋轉(zhuǎn)旋轉(zhuǎn)前后：高度都為h+11h-10AB1h-12hh-1BRARBLBA0h0h-1h-1BRARBL當前第39頁\共有78頁\編于星期五\0點旋轉(zhuǎn)算法voidLL_rotate(BBSTNode*a){BBSTNode*b;b=a->Lchild;a->Lchild=b->Rchild;b->Rchild=a;a->Bfactor=b->Bfactor=0;a=b;}當前第40頁\共有78頁\編于星期五\0點2、LR情況：（新插入結點在左子樹的右子樹上）h-1旋轉(zhuǎn)前后高度仍然是h+1h-1CB0h-1BLARACRh-2CLh-1-10BLAB1h-102-1ARARCCRCLh-2h-101LR旋轉(zhuǎn)當前第41頁\共有78頁\編于星期五\0點旋轉(zhuǎn)算法voidLR_rotate(BBSTNode*a){BBSTNode*b,*c;b=a->Lchild;c=b->Rchild;/*初始化*/a->Lchild=c->Rchild;b->Rchild=c->Lchild;c->Lchild=b;c->Rchild=a;if(c->Bfactor==1){a->Bfactor=-1;b->Bfactor=0;}elseif(c->Bfactor==0)a->Bfactor=b->Bfactor=0;else{a->Bfactor=0;b->Bfactor=1;}}當前第42頁\共有78頁\編于星期五\0點

右調(diào)整（新結點插入在右子樹上進行的調(diào)整）1、RR情況：（插入在的右子樹的右子樹上）處理方法和LL對稱2、RL情況：（插入在右子樹的左子樹上）處理方法與LR對稱平衡樹建立方法：（1）按二叉排序樹插入結點（2）如引起結點平衡因子變?yōu)閨2|，則確定旋轉(zhuǎn)點，該點是離根最遠（或最接近于葉子的點）（3）確定平衡類型后進行平衡處理，平衡后以平衡點為根的子樹高不變當前第43頁\共有78頁\編于星期五\0點589162127431011二叉排序樹當前第44頁\共有78頁\編于星期五\0點二叉平衡樹811122371095614當前第45頁\共有78頁\編于星期五\0點采用B_樹和B+

樹目的應文件系統(tǒng)的要求而發(fā)展起來的，大量數(shù)據(jù)存放在外存中，通常存放在硬盤中。由于是海量數(shù)據(jù)，不可能一次調(diào)入內(nèi)存。因此，要多次訪問外存。但硬盤的驅(qū)動受機械運動的制約，速度慢。所以，主要矛盾變?yōu)闇p少訪外存次數(shù)。在1972年由R.Bayer和E.Macreight提出用B_樹作為索引組織文件。提高訪問速度、減少時間。 8.2.2B_樹和B+樹一、B_樹及其操作當前第46頁\共有78頁\編于星期五\0點1、m階B_樹定義：m階B_樹滿足或空，或為滿足下列性質(zhì)的m叉樹：(1)樹中每個結點最多有m棵子樹(2)根結點在不是葉子時，至少有兩棵子樹(3)除根外，所有非終端結點至少有m/2棵子樹(4)有s個子樹的非葉結點具有n=s-1個關鍵字，結點的信息組織為:(n,A0,K1,A1,K2,A2

…Kn，An）

這里：n:關鍵字的個數(shù)，ki（i=1,2,…,n)為關鍵字，且滿足Ki<Ki+1,，Ai(i=0,1,..n)為指向子樹的指針。(5)所有的葉子結點都出現(xiàn)在同一層上，不帶信息（可認為外部結點或失敗結點）。當前第47頁\共有78頁\編于星期五\0點例：4階B_樹。除根結點和葉子結點之外，每個結點的子樹個數(shù)至少為m/2=2個；結點的關鍵字個數(shù)至少為1。該B_樹的深度為4。葉子結點都在第4層上。藍色代表結點中關鍵字個數(shù)黑色代表結點中關鍵字第1層第2層第3層第4層133118243781111271391993475864FFFFFFFFFFFF當前第48頁\共有78頁\編于星期五\0點3、B_樹的查找：查找過程，類似于二叉樹的查找，關鍵字為key的記錄。從根開始在結點中順序或二分（當m較大時）查找，如果Ki=key則查找成功,

若Ki<key<Ki+1：順Ai指向的子樹重復查找若key<K1：順A0指向的子樹重復查找若key>Kn;：找順An指向的子樹重復查找若找到葉子，則查找失敗。當前第49頁\共有78頁\編于星期五\0點4、B_樹中結點的插入

m代表B_樹的階，插入總發(fā)生在最低層1）插入后關鍵字個數(shù)小于等于m-1,完成。2）插入后關鍵字個數(shù)等于m,結點分裂，以中點數(shù)據(jù)為界一分為二，中點數(shù)據(jù)放到雙親結點中。這樣就有可能使得雙親結點的數(shù)據(jù)個數(shù)為m,引起雙親結點的分裂，最壞情況下一直波及到根，引起根的分裂——B_樹長高。

122430457053902610039506185例：3階B_樹的插入操作。最多3棵子樹，2個數(shù)據(jù)；最少2棵子樹，1個數(shù)據(jù)。所以3階B_樹也稱為2-3樹。插入位置插入數(shù)據(jù)：33當前第50頁\共有78頁\編于星期五\0點31224304570539026100395061857243034570539026100395061851230324457053902610039506185127100303245390263950618512745707插入7當前第51頁\共有78頁\編于星期五\0點5、B_樹中結點的刪除*刪除發(fā)生在最底層（1）被刪關鍵字所在結點中的關鍵字數(shù)目大于等于m/2，直接刪除。（2）刪除后結點中數(shù)據(jù)為m/2-2，而相鄰的左（右）兄弟中數(shù)據(jù)大于m/2-1，此時左（右兄弟）中最大（?。┑臄?shù)據(jù)上移到雙親中，雙親中接（靠）在它后（前）面的數(shù)據(jù)移到被刪數(shù)據(jù)的結點中。32445539037100506170被刪關鍵字324456190371005370當前第52頁\共有78頁\編于星期五\0點(3)其左右兄弟結點中數(shù)據(jù)都是m/2-1，此時和左（右）兄弟合并，合并時連同雙親中相關的關鍵字。此時，雙親中少了一項，因此又可能引起雙親的合并，最壞一直到根，使B-樹降低一層。324459010061703244590371006170刪除3732445901006170當前第53頁\共有78頁\編于星期五\0點*刪除不在最底層在大于被刪數(shù)據(jù)中選最小的代替被刪數(shù)據(jù)，按B_樹性質(zhì)，其位置如下圖所示（x是要刪除的數(shù)據(jù)）xy用于代替x的數(shù)據(jù)問題轉(zhuǎn)換成在最底層的刪除當前第54頁\共有78頁\編于星期五\0點作業(yè)：試從空樹開始，畫出按以下次序向2-3樹中插入數(shù)據(jù)的建樹過程：20，30，50，52，60，68，70。如果以后刪除50和68，畫出每一步執(zhí)行后2-3樹的狀態(tài)。當前第55頁\共有78頁\編于星期五\0點二、B+樹在實際的文件系統(tǒng)中，用的是B+樹或其變形。有關性質(zhì)與操作類似與B_樹。1、差異：（1）有n棵子樹的結點中有n個關鍵字（2）所有葉子結點中包含全部關鍵字信息及對應記錄位置信息（3）所有非葉子為索引，只含關鍵字而且僅有子樹中最大或最小的信息。（4）非葉最底層順序聯(lián)結，這樣可以進行順序查找當前第56頁\共有78頁\編于星期五\0點59971544591015010203060910對應01的記錄當前第57頁\共有78頁\編于星期五\0點2．查找過程※在B+樹上，既可以進行縮小范圍的查找，也可以進行順序查找；※在進行縮小范圍的查找時，不管成功與否，都必須查到葉子結點才能結束；※若在結點內(nèi)查找時，給定值≤Ki，則應繼續(xù)在Ai所指子樹中進行查找3．插入和刪除的操作類似于B_樹進行，即必要時，也需要進行結點的“分裂”或“合并”。當前第58頁\共有78頁\編于星期五\0點8.3哈希表前面查找方法共同特點：通過將關鍵字值與給定值比較，來確定位置。效率取決比較次數(shù)。理想的方法是：不需要比較，根據(jù)給定值能直接定位記錄的存儲位置。這樣，需要在記錄的存儲位置與該記錄的關鍵字之間建立一種確定的對應關系，使每個記錄的關鍵字與一個存儲位置相對應。例1949-2000年某地區(qū)人口統(tǒng)計表可以按公式確定其人數(shù)：y年人數(shù)=表[y-1948]年份人數(shù)123…..5152194919501951……...19992000200021002200……...44004420當前第59頁\共有78頁\編于星期五\0點1.哈希（也稱為Hash、雜湊、散列）基本思想在記錄的存儲地址和它的關鍵字之間建立一個確定的對應關系；這樣，不經(jīng)過比較，一次存取就能得到元素。哈希函數(shù)——在記錄的關鍵字與記錄的存儲位置之間建立的一種對應關系。哈希函數(shù)是一種映象，是從關鍵字空間到存儲位置空間的一種映象。哈希函數(shù)可寫成：

addr(ai)=h(ki)ai是表中的一個元素addr(ai)是ai的存儲位置信息ki是ai的關鍵字當前第60頁\共有78頁\編于星期五\0點哈希表——應用哈希函數(shù)，由記錄的關鍵字確定記錄在表中的位置信息，并將記錄根據(jù)此信息放入表中，這樣構成的表叫哈希表。哈希查找——利用哈希函數(shù)進行查找的過程。除了特別簡單的應用，在大多數(shù)情況下，所構造出的哈希函數(shù)是多對一的（非單射函數(shù)）。即可能有多個不同的關鍵字，它們對應的哈希函數(shù)值是相同的，這意味著不同記錄由哈希函數(shù)確定的存儲位置是相同的。這種情況被稱為沖突。即：若key1不等于key2,而h(key1)=h(key2)

Hash查找適合于關鍵字可能出現(xiàn)的值的集合遠遠大于實際關鍵字集合的情形。根據(jù)抽屜原理，沖突是不可能完全避免的，所以，要解決：（1）構造一個性能好，沖突少的Hash函數(shù)（2）如何解決沖突當前第61頁\共有78頁\編于星期五\0點2、常用的哈希函數(shù)（1）直接定址法構造：取關鍵字或關鍵字的某個線性函數(shù)作哈希地址，即H(key)=key或H(key)=a·key+b特點：

直接定址法所得地址集合與關鍵字集合大小相等，不會發(fā)生沖突實際中能用這種哈希函數(shù)的情況很少。此法僅適合于：地址集合的大小==關鍵字集合的大小當前第62頁\共有78頁\編于星期五\0點(2)數(shù)字分析法構造：對關鍵字進行分析，取關鍵字的若干位或其組合作哈希地址。

例有80個記錄，關鍵字為8位十進制數(shù)，哈希地址為2位十進制數(shù)8134653281372242813874228130136781322817813389678136853781419355…..…..分析：只取8只取1只取3、4只取2、7、5數(shù)字分布近乎隨機所以：取任意兩位或兩位與另兩位的疊加作哈希地址當前第63頁\共有78頁\編于星期五\0點此方法僅適合于：能預先估計出全體關鍵字的每一位上各種數(shù)字出現(xiàn)的頻度。(2)數(shù)字分析法構造：對關鍵字進行分析，取關鍵字的若干位或其組合作哈希地址。

當前第64頁\共有78頁\編于星期五\0點以關鍵字的平方值的中間幾位作為存儲地址。求“關鍵字的平方值”的目的是“擴大差別”，同時平方值的中間各位又能受到整個關鍵字中各位的影響。（3）平方取中法當前第65頁\共有78頁\編于星期五\0點（4）折疊法構造：將關鍵字分割成位數(shù)相同的幾部分，然后取這幾部分的疊加和（舍去進位）做哈希地址。種類移位疊加：將分割后的幾部分低位對齊相加間界疊加：從一端沿分割界來回折送，然后對齊相加。例關鍵字為：0442205864，哈希地址位數(shù)為4586442200410088H(key)=0088移位疊加5864022404

6092H(key)=6092間界疊加當前第66頁\共有78頁\編于星期五\0點

此方法適合于:關鍵字的數(shù)字位數(shù)特別多，且每一位上數(shù)字分布大致均勻情況。（4）折疊法構造：將關鍵字分割成位數(shù)相同的幾部分，然后取這幾部分的疊加和（舍去進位）做哈希地址。種類移位疊加：將分割后的幾部分低位對齊相加間界疊加：從一端沿分割界來回折送，然后對齊相加。當前第67頁\共有78頁\編于星期五\0點（5）除留余數(shù)法構造：取關鍵字被某個不大于哈希表表長m的數(shù)p除后所得余數(shù)作哈希地址，即H(key)=key%p，pm特點：簡單、常用，可與上述幾種方法結合使用p的選取很重要；p選的不好，容易產(chǎn)生同義詞（6）隨機數(shù)法構造：取關鍵字的偽隨機函數(shù)值作哈希地址，即H(key)=random(key)適于關鍵字長度不等的情況說明：哈希函數(shù)構造不應太復雜不存在絕對好和壞的函數(shù)當前第68頁\共有78頁\編于星期五\0點3、沖突解決A)開放定址法方法：當沖突發(fā)生時，形成一個探查序列；沿此序列逐個地址探查，直到找到一個空位置（開放的地址），將發(fā)生沖突的記錄放到該地址中，即Hi=(H(key)+di)%m，i=1,2,……k(km-1)其中：H(key)——哈希函數(shù)

m——哈希表表長

di——增量序列分類線性探測再散列：di=1,2,3,……m-1二次探測再散列：di=12,-12,22,-22,32,……±k2(km/2)偽隨機探測再散列：di=偽隨機數(shù)序列當前第69頁\共有78頁\編于星期五\0點例已知一組關鍵字(19,14,23,1,68,20,84,27,55,11,10,79)哈希函數(shù)為：H(key)=key%13,哈希表長為m=16，

設每個記錄的查找概率相等用線性探測再散列處理沖突，即Hi=(H(key)+di)%mH(55)=3沖突->H1=(3+1)%16=4

沖突->H2=(3+2)%16=5H(79)=1沖突->H1=(1+1)%16=2

沖突->H2=(1+2)%16=3

沖突->H3=(1+3)%16=4

沖突->H4=(1+4)%16=5

沖突->H5=(1+5)%16=6

沖突->H6=(1+6)%16=7

沖突->H7=(1+7)%16=8

沖突->H8=(1+8)%16=9012345678910111213141514168275519208479231110H(19)=6H(14)=1H(23)=10H(1)=1沖突->H1=(1+1)%16=2H(68)=3H(20)=7H(84)=6沖突->H1=(6+1)%16=7

沖突->H2=(6+2)%16=8H(27)=1沖突->H1

=(1+1)%16=2

沖突->H2=(1+2)%16=3

沖突->H2=(1+3)%