東南大學數(shù)據(jù)結(jié)構(gòu)-Lec012

第12講多路查找樹、哈希表B-樹和B+樹哈希表1數(shù)據(jù)結(jié)構(gòu)樹形索引表平衡二叉排序樹便于動態(tài)查找，因此用平衡二叉排序樹來組織索引表是一種可行的選擇。當用于大型數(shù)據(jù)庫時，所有數(shù)據(jù)及索引都存儲在外存，因此，涉及到內(nèi)、外存之間頻繁的數(shù)據(jù)交換，這種交換速度的快慢成為制約動態(tài)查找的瓶頸。若以二叉樹的結(jié)點作為內(nèi)、外存之間數(shù)據(jù)交換單位，則查找給定關(guān)鍵字時對磁盤平均進行(㏒2n)次訪問是不能容忍的，因此，必須選擇一種能盡可能降低磁盤I/O次數(shù)的索引組織方式。樹結(jié)點的大小盡可能地接近頁的大小。R.Bayer和E.McCreight在1972年提出了一種多路平衡查找樹，稱為B-樹(其變型體是B+樹)。數(shù)據(jù)結(jié)構(gòu)2B-樹的概念一棵m階的B-樹，或為空樹，或為滿足下列特性的m叉樹：樹中每個結(jié)點至多有m棵子樹；若根結(jié)點不是葉子結(jié)點，則至少有兩棵子樹；除根之外的所有非終端結(jié)點至少有

m/2

棵子樹；所有的非終端結(jié)點中包含下列信息數(shù)據(jù)(n,A0,K1,A1,K2,A2,…,Kn,An)

其中：Ki(1≤i≤n)為關(guān)鍵字，且Ki<Ki+1(1≤i≤n-1)；Ai(i=0,1,…,n)為指向子樹根結(jié)點的指針，且指針Ai-1所指子樹中所有結(jié)點的關(guān)鍵字均小于Ki

(1≤i≤n)，An所指子樹中所有結(jié)點的關(guān)鍵字均大于Kn；n(

m/2

-1≤n≤m-1)為關(guān)鍵字的個數(shù)（或n+1為子樹個數(shù)）。所有的葉子結(jié)點都出現(xiàn)在同一層次上，并且不帶信息。數(shù)據(jù)結(jié)構(gòu)3B-樹的結(jié)構(gòu)條件(1)和(3)使每個結(jié)點至少半滿；條件(2)使B-樹不至于一開始就偏向一邊；條件(4)結(jié)點中關(guān)鍵字遞增排列，使B-樹具有某種“中序”遞增性，可看成二叉排序樹的擴充，是一種平衡多叉排序樹；而子樹數(shù)比關(guān)鍵字個數(shù)多1，使得最終葉子數(shù)比樹中所含關(guān)鍵字數(shù)多1。條件(5)葉子都在同一層，使B-樹高度上平衡；而葉子不含關(guān)鍵字，表示葉子實際上是樹中并不存在的外部結(jié)點，且指向這些外部結(jié)點的指針為空；數(shù)據(jù)結(jié)構(gòu)4B-樹的結(jié)點類型定義根據(jù)m階B-樹的定義，結(jié)點類型定義如下：#defineM5/*根據(jù)實際需要定義B_樹的階數(shù)*/typedefstruct

BTNode{intkeynum; /*結(jié)點中關(guān)鍵字的個數(shù)*/KeyTypekey[M+1]; /*關(guān)鍵字向量,key[0]未用*/RecType*recptr[M+1];/*記錄指針向量，recptr[0]未用*/structBTNode*parent;/*指向父結(jié)點的指針*/structBTNode*ptr[M+1];/*子樹指針向量*/}BTNode;數(shù)據(jù)結(jié)構(gòu)5B-樹的查找過程數(shù)據(jù)結(jié)構(gòu)6在B-樹上進行查找的過程是一個順指針查找結(jié)點和在結(jié)點的關(guān)鍵字中進行查找交叉進行的過程。例：查找26查找100

類似二叉排序樹的查找root50157184382026435662788996B-樹查找分析兩種基本操作在B-樹中找結(jié)點B-樹通常存儲在磁盤上，第1步查找操作在磁盤上進行。在結(jié)點中找關(guān)鍵字在磁盤上找到指針p所指結(jié)點后，先將結(jié)點中的信息讀入內(nèi)存，因此，第2步查找操作在內(nèi)存中進行；然后再利用順序查找或折半查找查詢等于給定值的關(guān)鍵字。由于訪外（磁盤）耗時，在磁盤上進行查找的次數(shù)，即待查關(guān)鍵字所在結(jié)點在B-樹上的層次數(shù)，是決定B-樹查找效率的首要因素。數(shù)據(jù)結(jié)構(gòu)7B-樹查找分析考慮最壞的情況，即待查結(jié)點在B-樹的最大層次上。含N個關(guān)鍵字的m階B-樹的最大深度是多少？

根據(jù)B-樹的定義：第一層至少有1個結(jié)點；第二層至少有2個結(jié)點；由于除根之外的每個非終端結(jié)點至少有

m/2

棵子樹，則第三層至少有2(

m/2)個結(jié)點；…；依次類推，第l+1層至少有2(

m/2)

l?1個結(jié)點，而l+1層的結(jié)點為葉子結(jié)點。若m階B-樹中具有N個關(guān)鍵字，則葉子結(jié)點即查找不成功的結(jié)點為N+1，由此有：N+l≥2*(

m/2)

l?1

反之

l≤log

m/2

((N+1)/2)+1數(shù)據(jù)結(jié)構(gòu)8結(jié)論：在含有N個關(guān)鍵字的B-樹上進行查找時，從根結(jié)點到關(guān)鍵字所在結(jié)點的路徑上涉及的結(jié)點數(shù)不超過log

m/2

((N+1)/2)+1B-樹的插入操作每插入一個關(guān)鍵字不是在樹中添加一個葉子結(jié)點，而是首先在最低層的非終端結(jié)點中添加一個關(guān)鍵字。若該結(jié)點的關(guān)鍵字個數(shù)不超過m?1，則插入完成；否則要產(chǎn)生結(jié)點“分裂”，將位于中間的關(guān)鍵字提升到雙親結(jié)點，使分裂后的兩個結(jié)點大小相當，都約半滿；如果雙親結(jié)點原來也是滿的，則需要繼續(xù)分裂和提升。最壞的情況一直到根，若根也要分裂，由于它沒有雙親，就要另外建立一個新的根結(jié)點，整個B-樹增加一層。比較：二叉排序樹插入的結(jié)點可在任何層。數(shù)據(jù)結(jié)構(gòu)9B-樹的插入操作數(shù)據(jù)結(jié)構(gòu)10113階B-樹的生成B-樹的生成也是從空樹起，逐個插入關(guān)鍵字而得。數(shù)據(jù)結(jié)構(gòu)1253插入535375插入757513953插入139751391454953插入49,14549751391455336插入3649533613914510175插入101B-樹的刪除操作在B-樹上刪除一個關(guān)鍵字，首先應找到該關(guān)鍵字所在結(jié)點，并從中刪除之：若該結(jié)點為最下層的非終端結(jié)點，且其中的關(guān)鍵字數(shù)目不少于

m/2

，則刪除完成，否則要進行“合并”結(jié)點的操作；若所刪關(guān)鍵字為非終端結(jié)點中的Ki，則可以指針Ai所指子樹中的最小關(guān)鍵字Y代替Ki，然后在相應結(jié)點中刪去Y。討論刪除最下層非終端結(jié)點中的關(guān)鍵字的3種情形。數(shù)據(jù)結(jié)構(gòu)1355587580104065607030acbdefgh刪除55用后繼替換刪后繼14587580104060657030acbdefhB-樹的刪除操作被刪關(guān)鍵字所在結(jié)點中的關(guān)鍵字數(shù)目不小于

m/2

，則只需從該結(jié)點中刪去該關(guān)鍵字Ki和相應指針Ai，樹的其他部分不變。數(shù)據(jù)結(jié)構(gòu)1555587580m=310406560703050acbdefghad58758010406560703050cbefgh直接刪除55B-樹的刪除操作被刪關(guān)鍵字所在結(jié)點中的關(guān)鍵字數(shù)目等于

m/2-1，而與該結(jié)點相鄰的右兄弟(或左兄弟)結(jié)點中的關(guān)鍵字數(shù)目大于

m/2-1，則需將其兄弟結(jié)點中的最小(或最大)的關(guān)鍵字上移至雙親結(jié)點中，而將雙親結(jié)點中小于(或大于)且緊靠該上移關(guān)鍵字的關(guān)鍵字下移至被刪關(guān)鍵字所在結(jié)點中。數(shù)據(jù)結(jié)構(gòu)165558758010406560703050acbdefgh刪除6555588010407060753050acbdefgh移動B-樹的刪除操作被刪關(guān)鍵字所在結(jié)點和其相鄰的兄弟結(jié)點中的關(guān)鍵字數(shù)目均等于

m/2-1。假設(shè)該結(jié)點有右兄弟(Ai所指)，則在刪去關(guān)鍵字之后，它所在結(jié)點中剩余的關(guān)鍵字和指針，加上雙親結(jié)點中的關(guān)鍵字Ki一起，合并到Ai所指兄弟結(jié)點中。數(shù)據(jù)結(jié)構(gòu)17558010406058753050acbdefgh刪除5518合并5860801040753050acbdefhB-樹的刪除操作雙親拿出關(guān)鍵字后，雙親可能要合并，并可能一直傳播到根；如果根只一個關(guān)鍵字，則下移與兩孩子合并后，形成新根結(jié)點，整個樹減少一層。數(shù)據(jù)結(jié)構(gòu)1958801040606530acbdefh刪除1080304060fh5865dbB+樹的概念B+樹是應文件系統(tǒng)所需而出的一種B-樹的變型樹。一棵m階的B+樹和m階的B-樹的差異在于：有n棵子樹的結(jié)點中含有n個關(guān)鍵字；所有的葉子結(jié)點中包含了全部關(guān)鍵字的信息，及指向含這些關(guān)鍵字記錄的指針，且葉子結(jié)點本身依關(guān)鍵字的大小自小而大順序鏈接；所有的非終端結(jié)點可以看成是索引部分，結(jié)點中僅含有其子樹(根結(jié)點)中的最大(或最小)關(guān)鍵字。數(shù)據(jù)結(jié)構(gòu)20B+樹的結(jié)構(gòu)B+樹有兩個頭指針：一個指向根結(jié)點，另一個指向關(guān)鍵字最小的葉子結(jié)點。因此，可以對B+樹進行兩種查找運算：從最小關(guān)鍵字開始進行順序查找；從根結(jié)點開始進行隨機查找。數(shù)據(jù)結(jié)構(gòu)21B+樹的查找、插入和刪除對B+樹不僅可以從根結(jié)點開始按關(guān)鍵字隨機查找，而且可以從最小關(guān)鍵字起，按葉子結(jié)點的鏈接順序進行順序查找。在B+樹上進行隨機查找、插入、刪除的過程基本上和B-樹類似。查找時，若在非終端結(jié)點上找到，并不終止查找，而是繼續(xù)向下查找直至葉子。在B+樹中，不管查找成功與否，每次都是走了一條從根到葉結(jié)點的路徑。插入僅在葉結(jié)點上進行。當結(jié)點中的關(guān)鍵字個數(shù)大于m時要分裂成兩個結(jié)點，它們所含關(guān)鍵字的個數(shù)分別為

(m+1)/2

和

(m+1)/2

，并且，它們的雙親結(jié)點中應同時包含這兩個結(jié)點的最大關(guān)鍵字。刪除也僅在葉結(jié)點上進行。當葉子結(jié)點中的最大關(guān)鍵字被刪除時，其在非終端結(jié)點中的值可以作為一個“分界關(guān)鍵字”存在（即不必刪除）。若因刪除而使結(jié)點中關(guān)鍵字的個數(shù)少于

m/2

時，要和該結(jié)點的兄弟結(jié)點進行合并。數(shù)據(jù)結(jié)構(gòu)22第12講多路查找樹、哈希表B-樹和B+樹哈希表23數(shù)據(jù)結(jié)構(gòu)引言記錄在線性表、樹等結(jié)構(gòu)中的相對位置是隨機的，和記錄的關(guān)鍵字之間不存在確定的關(guān)系，因此，在結(jié)構(gòu)中查找記錄時需進行一系列和關(guān)鍵字的比較。這一類查找方法建立在“比較”的基礎(chǔ)上。查找效率依賴于查找過程中進行比較的次數(shù)。在順序查找時，比較的結(jié)果為“=”與“≠”兩種可能；在折半查找、二叉排序樹查找和B-樹查找時，比較的結(jié)果為“<”、“=”和“>”3種可能。是否可以不作比較就直接得到記錄的存儲地址，從而找到所要的結(jié)點呢？回答是肯定的，這就是散列技術(shù)?；舅枷耄涸谟涗浀拇鎯Φ刂泛退年P(guān)鍵字之間建立一個確定的對應關(guān)系；不經(jīng)過任何比較，一次存取便能得到所查記錄。數(shù)據(jù)結(jié)構(gòu)24什么是哈希表在記錄的存儲位置和它的關(guān)鍵字之間建立一個確定的對應關(guān)系f，使每個關(guān)鍵字和結(jié)構(gòu)中一個惟一的存儲位置相對應。在查找時，只要根據(jù)這個關(guān)系f找到給定值K的像f(K)。若結(jié)構(gòu)中存在關(guān)鍵字和K相等的記錄，則必定在f(K)的存儲位置上。稱這個對應關(guān)系f為哈希(Hash)函數(shù)，按這個思想建立的表為哈希表。對于不同的關(guān)鍵字可能得到同一哈希地址，即key1≠key2，而f(key1)=f(key2)，這種現(xiàn)象稱沖突。具有相同函數(shù)值的關(guān)鍵字對該哈希函數(shù)來說稱做同義詞。根據(jù)設(shè)定的哈希函數(shù)H(key)和處理沖突的方法將一組關(guān)鍵字映像到一個有限的連續(xù)的地址集(區(qū)間)上，并以關(guān)鍵字在地址集中的“像”作為記錄在表中的存儲位置，這種表便稱為哈希表，這一映像過程稱為哈希造表或散列，所得存儲位置稱哈希地址或散列地址。數(shù)據(jù)結(jié)構(gòu)25一個哈希表的簡單例子數(shù)據(jù)結(jié)構(gòu)2630個地區(qū)的各民族人口統(tǒng)計表以編號作關(guān)鍵字；構(gòu)造哈希函數(shù)：H(key)=key

H(1)=1，H(2)=2以地區(qū)名稱作關(guān)鍵字；取地區(qū)名稱第1個拼音字母的序號作哈希函數(shù)：H(Beijing)=2

H(Shanghai)=19

H(Shenyang)=19編號省、市(區(qū))總?cè)丝跐h族回族…...1北京2上海…...…...哈希表的建造在一般情況下，哈希函數(shù)是一種壓縮映象，不可避免產(chǎn)生沖突，只能盡量減少。因此，建造哈希表主要解決兩個問題：哈希函數(shù)的構(gòu)造和沖突的處理。設(shè)計一個哈希表應包括：哈希表的空間范圍，即確定哈希函數(shù)的值域；構(gòu)造合適的哈希函數(shù)，使得對于所有可能的元素(記錄的關(guān)鍵字)，函數(shù)值均在哈希表的地址空間范圍內(nèi)，且出現(xiàn)沖突的可能盡量??；處理沖突的方法，即當沖突出現(xiàn)時如何解決。數(shù)據(jù)結(jié)構(gòu)27哈希函數(shù)的構(gòu)造方法哈希函數(shù)是一個映像，其設(shè)定很靈活，只要使得任何關(guān)鍵字由此所得的哈希函數(shù)值都落在表長允許范圍之內(nèi)即可。哈希函數(shù)“好壞”的主要評價因素：函數(shù)的構(gòu)造簡單；能“均勻”地將哈希表中的關(guān)鍵字映射到地址空間。若對于關(guān)鍵字集合中的任一個關(guān)鍵字，經(jīng)哈希函數(shù)映像到地址集合中任何一個地址的概率是相等的，則稱此類哈希函數(shù)為均勻的哈希函數(shù)，有助于減少沖突。數(shù)據(jù)結(jié)構(gòu)28常用的構(gòu)造哈希函數(shù)的方法直接定址法取關(guān)鍵字或關(guān)鍵字的某個線性函數(shù)值為哈希地址。即：

H(key)=key

或H(key)=a·key+b

其中a和b為常數(shù)(這種哈希函數(shù)叫做自身函數(shù))。特點：直接定址法所得地址集合和關(guān)鍵字集合的大小相同；對于不同的關(guān)鍵字不會發(fā)生沖突；實際中能使用這種哈希函數(shù)的情況很少。數(shù)據(jù)結(jié)構(gòu)29常用的構(gòu)造哈希函數(shù)的方法數(shù)字分析法對關(guān)鍵字進行分析，取關(guān)鍵字的若干位或組合作為哈希地址。適用于關(guān)鍵字位數(shù)比哈希地址位數(shù)大，且可能出現(xiàn)的關(guān)鍵字事先知道的情況。數(shù)據(jù)結(jié)構(gòu)30例：設(shè)有80個記錄，關(guān)鍵字為8位十進制數(shù)，哈希地址為2位十進制數(shù)。┇8134653281372242813874228130136781322817813389678136853781419355

分析：

只取8

只取1

只取3、4

只取2、7、5

數(shù)字分布近乎隨機因此：取

任意兩位或兩位與另兩位的疊加作哈希地址常用的構(gòu)造哈希函數(shù)的方法平方取中法取關(guān)鍵字平方后的中間幾位作為哈希地址。

一個數(shù)平方后的中間幾位數(shù)和數(shù)的每一位都相關(guān)，由此使隨機分布的關(guān)鍵字得到的哈希地址也是隨機的。適用于在選定哈希函數(shù)時不一定能知道關(guān)鍵字的全部情況，取其中哪幾位也不一定合適的情況。數(shù)據(jù)結(jié)構(gòu)31常用的構(gòu)造哈希函數(shù)的方法折疊法將關(guān)鍵字分割成位數(shù)相同的幾部分(最后一部分的位數(shù)可以不同)，然后取這幾部分的疊加和(舍去進位)作為哈希地址。數(shù)位疊加有移位疊加和間界疊加兩種。移位疊加：將分割后的每一部分的最低位對齊相加；間界疊加：從一端到另一端沿分割界來回折疊，然后對齊相加。適用于關(guān)鍵字位數(shù)很多，而且關(guān)鍵字中每一位上數(shù)字分布大致均勻的情況。例：設(shè)關(guān)鍵字為0442205864，哈希地址位數(shù)為4。數(shù)據(jù)結(jié)構(gòu)32586442200410088H(key)=0088移位疊加5864022404

6092H(key)=6092間界疊加常用的構(gòu)造哈希函數(shù)的方法除留余數(shù)法取關(guān)鍵字被某個不大于哈希表表長m的數(shù)p除后所得余數(shù)為哈希地址，即：

H(key)=keyMODp，(p

m)一種最簡單、也最常用的構(gòu)造哈希函數(shù)的方法，可以對關(guān)鍵字直接取模(MOD)，也可在折疊、平方取中等運算之后取模。p的選擇很重要。若p選的不好，容易產(chǎn)生同義詞。選取p=2i：運算便于用移位來實現(xiàn)，但等于將關(guān)鍵字的高位忽略而僅留下低位二進制數(shù)，則高位不同而低位相同的關(guān)鍵字是同義詞。選取p=q

f(q、f都是質(zhì)因數(shù))：則所有含有q或f因子的關(guān)鍵字的哈希地址均是q或f的倍數(shù)。選取p為素數(shù)或不包含小于20的質(zhì)因數(shù)的合數(shù)：經(jīng)驗；常用的選取方法；能減少沖突出現(xiàn)的可能性。數(shù)據(jù)結(jié)構(gòu)33常用的構(gòu)造哈希函數(shù)的方法隨機數(shù)法選擇一個隨機函數(shù)，取關(guān)鍵字的隨機函數(shù)值為哈希地址，即H(key)=random(key)通常，當關(guān)鍵字長度不等時，采用此法較恰當。視不同的情況采用不同的哈希函數(shù)，考慮的因素有：計算哈希函數(shù)所需時間；關(guān)鍵字的長度；哈希表的大小（哈希地址范圍）；關(guān)鍵字的分布情況；記錄的查找頻率。數(shù)據(jù)結(jié)構(gòu)34沖突處理的方法沖突處理：當出現(xiàn)沖突時，為沖突元素找到另一個存儲位置。開放定址法基本方法：當沖突發(fā)生時，形成某個探測序列；按此序列逐個探測哈希表中的其他地址，直到找到給定關(guān)鍵字或一個空地址(開放的地址)為止，將發(fā)生沖突的記錄放到該地址中。哈希地址的計算公式是：Hi(key)=(H(key)+di)MODm，i=1,2,…,k(km-1)其中：H(key)為哈希函數(shù)；m為哈希表長；

di為第i次探測時的增量序列；

Hi(key)為經(jīng)第i次探測后得到的哈希地址。數(shù)據(jù)結(jié)構(gòu)35沖突處理的方法:開放定址法線性探測再散列增量序列為：di=1,2,3,…,m-1將哈希表T[0…m-1]看成循環(huán)向量。當發(fā)生沖突時，從初次發(fā)生沖突的位置依次向后探測其他地址。探測過程終止的情況是：探測到的地址為空：表中沒有記錄。若是查找則失??；若是插入則將記錄寫入到該地址；探測到的地址有給定的關(guān)鍵字。若是查找則成功；若是插入則失??；直到T[h]：仍未探測到空地址或給定的關(guān)鍵字，哈希表滿。數(shù)據(jù)結(jié)構(gòu)36沖突處理的方法:開放定址法數(shù)據(jù)結(jié)構(gòu)37例:(19,13,33,02,06,29,17,05)，取哈希表長12，線性探查。1913330205291706沖突因m＝12，故取p＝1119％11＝813％11＝233％11＝002％11＝206％11＝629％11＝717％11＝605％11＝501234567891011線性探測法的特點◆

優(yōu)點：只要哈希表未滿，總能找到一個不沖突的哈希地址；◆

缺點：每個產(chǎn)生沖突的記錄被散列到離沖突最近的空地址上，從而又增加了更多的沖突機會（這種現(xiàn)象稱為沖突的“聚集”）。沖突處理的方法:開放定址法二次探測再散列增量序列為：di=12,-12,22,-22,32,……±k2(k

m/2)二次探測法的特點◆優(yōu)點：探測序列跳躍式地散列到整個表中，不易產(chǎn)生沖突的“聚集”現(xiàn)象；◆缺點：不能保證探測到散列表的所有地址。偽隨機探測再散列增量序列使用一個偽隨機函數(shù)來產(chǎn)生一個落在閉區(qū)間[1,m-1]的隨機序列。數(shù)據(jù)結(jié)構(gòu)38沖突處理的方法:開放定址法例：表長為11的哈希表中已填有關(guān)鍵字17,60,29的記錄，哈希函數(shù)為H(key)=keyMOD11?，F(xiàn)有第4個記錄(關(guān)鍵字為38)，按三種處理沖突的方法，將它填入哈希表中。(1)H(38)=38MOD11=5

沖突

H1=(5+1)MOD11=6沖突

H2=(5+2)MOD11=7沖突

H3=(5+3)MOD11=8不沖突數(shù)據(jù)結(jié)構(gòu)3901234567891060172938沖突處理的方法:開放定址法(2)H(38)=38MOD11=5沖突

H1=(5+12)MOD11=6

沖突

H2=(5-12)MOD11=4

不沖突(3)H(38)=38MOD11=5

沖突設(shè)偽隨機數(shù)序列為9，則H1=(5+9)MOD11=3

不沖突數(shù)據(jù)結(jié)構(gòu)400123456789106017293838012345678910601729383838沖突處理的方法再哈希法構(gòu)造若干個哈希函數(shù)，在同義詞產(chǎn)生地址沖突時，利用不同的哈希函數(shù)計算另一個哈希函數(shù)地址，直到?jīng)_突不再發(fā)生。即：

Hi=RHi(key)i=1,2,…,k

其中，RHi

均是不同的哈希函數(shù)。第一次發(fā)生沖突時，用RH1計算，第二次發(fā)生沖突時，用RH2計算，依此類推直到得到的某個Hi不再沖突為止。◆優(yōu)點：不易產(chǎn)生沖突的“聚集”現(xiàn)象；◆缺點：計算時間增加。數(shù)據(jù)結(jié)構(gòu)41沖突處理的方法鏈地址法將所有關(guān)鍵字為同義詞(哈希地址相同)的記錄存儲在同一線性鏈表中，并用一維數(shù)組存放鏈表的頭指針。假設(shè)哈希表長為m，設(shè)立一個一維指針數(shù)組：

ChainChainHash[m];其每個分量的初始狀態(tài)都是空指針。凡哈希地址為i

的記錄都插入到頭指針為ChainHash[i]的鏈表中，插入位置可以在表頭或表尾，或按關(guān)鍵字排序插入。優(yōu)點：不易產(chǎn)生沖突的“聚集”；刪除記錄也很簡單。數(shù)據(jù)結(jié)構(gòu)42沖突處理的方法:鏈地址法例：(19,13,33,02,06,29,17,05)，

H(key)=key

%11，

尾插建表數(shù)據(jù)結(jié)構(gòu)432105438761093319％11＝813％11＝233％11＝002％11＝206％11＝629％11＝717％11＝605％11＝513052919020617^^^^^^^^^^^沖突處理的方法建立一個公共溢出區(qū)在基本哈希表之外，另外設(shè)立一個溢出表保存與基本表中記錄沖突的所有記錄。所有關(guān)鍵字和基本表中關(guān)鍵字為同義詞的記錄，不管它們由哈希函數(shù)得到的哈希地址是什么，一旦發(fā)生沖突，都填入溢出表。例：已知一組關(guān)鍵字(15,4,18,7,37,47)，哈希表長度為7，哈希函數(shù)為：H(key)=key

MOD

7，用建立公共溢出區(qū)法處理沖突。數(shù)據(jù)結(jié)構(gòu)44Hashtable表：散列地址

012345

6

關(guān)鍵字71537447OverTable表：溢出地址

0123456

關(guān)鍵字18哈希查找過程哈希表的主要目的是用于快速查找，且插入和刪除操作都要用到查找。由于散列表的特殊組織形式，其查找有特殊的方法。設(shè)散列為HT[0…m-1]，散列函數(shù)為H(key)，解決沖突的方法為R(x,i)，則在散列表上查找給定值K的記錄的過程如右圖所示。數(shù)據(jù)結(jié)構(gòu)45給定k值計算H(k)此地址為空?關(guān)鍵字==k?查找失敗查找成功按處理沖突方法計算HiNYYN哈希查找分析從哈希查找過程可見：盡管哈希表在關(guān)鍵字與記錄的存儲地址之間建立了直接映象，但由于“沖突”，查找過程仍是一個給定值與關(guān)鍵字進行比較的過程，評價哈希查找效率仍要用ASL。哈希查找時關(guān)鍵字與給定值比較的次數(shù)取決于：哈希函數(shù)；處理沖突的方法；哈希表的填滿因子

。數(shù)據(jù)結(jié)構(gòu)46表中填入的記錄數(shù)哈希表長度

=例：(19,13,33,02,06,29,17,05)，

H(K)＝K％11，線性探測19133302172956找17，17％11＝6不成功11109876543210比較4次成功：1

121

1

1

14不成：21321654321