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

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

m/2

棵子樹(shù)；所有的非終端結(jié)點(diǎn)中包含下列信息數(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)為指向子樹(shù)根結(jié)點(diǎn)的指針，且指針Ai-1所指子樹(shù)中所有結(jié)點(diǎn)的關(guān)鍵字均小于Ki

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

m/2

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

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

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

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

m/2

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

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

m/2)

l?1個(gè)結(jié)點(diǎn)，而l+1層的結(jié)點(diǎn)為葉子結(jié)點(diǎn)。若m階B-樹(shù)中具有N個(gè)關(guān)鍵字，則葉子結(jié)點(diǎn)即查找不成功的結(jié)點(diǎn)為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個(gè)關(guān)鍵字的B-樹(shù)上進(jìn)行查找時(shí)，從根結(jié)點(diǎn)到關(guān)鍵字所在結(jié)點(diǎn)的路徑上涉及的結(jié)點(diǎn)數(shù)不超過(guò)log

m/2

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

m/2

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

m/2

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

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

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

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

(m+1)/2

和

(m+1)/2

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

m/2

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

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

H(Shanghai)=19

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

H(key)=key

或H(key)=a·key+b

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

分析：

只取8

只取1

只取3、4

只取2、7、5

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

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

一個(gè)數(shù)平方后的中間幾位數(shù)和數(shù)的每一位都相關(guān)，由此使隨機(jī)分布的關(guān)鍵字得到的哈希地址也是隨機(jī)的。適用于在選定哈希函數(shù)時(shí)不一定能知道關(guān)鍵字的全部情況，取其中哪幾位也不一定合適的情況。數(shù)據(jù)結(jié)構(gòu)31常用的構(gòu)造哈希函數(shù)的方法折疊法將關(guān)鍵字分割成位數(shù)相同的幾部分(最后一部分的位數(shù)可以不同)，然后取這幾部分的疊加和(舍去進(jìn)位)作為哈希地址。數(shù)位疊加有移位疊加和間界疊加兩種。移位疊加：將分割后的每一部分的最低位對(duì)齊相加；間界疊加：從一端到另一端沿分割界來(lái)回折疊，然后對(duì)齊相加。適用于關(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)鍵字被某個(gè)不大于哈希表表長(zhǎng)m的數(shù)p除后所得余數(shù)為哈希地址，即：

H(key)=keyMODp，(p

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

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

di為第i次探測(cè)時(shí)的增量序列；

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

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

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

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

H1=(5+12)MOD11=6

沖突

H2=(5-12)MOD11=4

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

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

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

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

其中，RHi

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

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

的記錄都插入到頭指針為ChainHash[i]的鏈表中，插入位置可以在表頭或表尾，或按關(guān)鍵字排序插入。優(yōu)點(diǎn)：不易產(chǎn)生沖突的“聚集”；刪除記錄也很簡(jiǎ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^^^^^^^^^^^沖突處理的方法建立一個(gè)公共溢出區(qū)在基本哈希表之外，另外設(shè)立一個(gè)溢出表保存與基本表中記錄沖突的所有記錄。所有關(guān)鍵字和基本表中關(guān)鍵字為同義詞的記錄，不管它們由哈希函數(shù)得到的哈希地址是什么，一旦發(fā)生沖突，都填入溢出表。例：已知一組關(guān)鍵字(15,4,18,7,37,47)，哈希表長(zhǎng)度為7，哈希函數(shù)為：H(key)=key

MOD

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

012345

6

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

0123456

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

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

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

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

121

1

1

14不成：21321654321