靜態(tài)索引結(jié)構(gòu)動(dòng)態(tài)索引結(jié)構(gòu)散列可擴(kuò)充散列.ppt

靜態(tài)索引結(jié)構(gòu) 動(dòng)態(tài)索引結(jié)構(gòu) 散列 可擴(kuò)充散列,第十章 索引與散列,靜態(tài)索引結(jié)構(gòu),示例：有一個(gè)存放職工信息的數(shù)據(jù)表, 每一 個(gè)職工對(duì)象有近 1k 字節(jié)的信息, 正好占據(jù)一 個(gè)頁(yè)塊的存儲(chǔ)空間。,當(dāng)數(shù)據(jù)對(duì)象個(gè)數(shù) n 很大時(shí), 如果用無(wú)序表形式的靜態(tài)搜索結(jié)構(gòu)存儲(chǔ), 采用順序搜索, 則搜索效率極低。如果采用有序表存儲(chǔ)形式的靜態(tài)搜索結(jié)構(gòu), 則插入新記錄進(jìn)行排序, 時(shí)間開(kāi)銷也很可觀。這時(shí)可采用索引方法來(lái)實(shí)現(xiàn)存儲(chǔ)和搜索。,線性索引 (Linear Index List),100 140 180 220 260 300 340 380,key addr 03 180 08 140 17 340 24 260 47 300 51 380 83 100 95 220,職工號(hào) 姓名 性別 職務(wù) 婚否 83 張珊 女 教師 已婚 08 李斯 男 教師 已婚 . 03 王魯 男 教務(wù)員 已婚 . 95 劉琪 女 實(shí)驗(yàn)員 未婚 . 24 岳跋 男 教師 已婚 . 47 周斌 男 教師 已婚 . 17 胡江 男 實(shí)驗(yàn)員 未婚 . 51 林青 女 教師 未婚 .,索引表,數(shù)據(jù)表,假設(shè)內(nèi)存工作區(qū)僅能容納 64k 字節(jié)的數(shù)據(jù), 在某一時(shí)刻內(nèi)存最多可容納 64 個(gè)對(duì)象以供搜索。 如果對(duì)象總數(shù)有 14400 個(gè), 不可能把所有對(duì)象的數(shù)據(jù)一次都讀入內(nèi)存。無(wú)論是順序搜索或折半搜索, 都需要多次讀取外存記錄。 如果在索引表中每一個(gè)索引項(xiàng)占4個(gè)字節(jié), 每個(gè)索引項(xiàng)索引一個(gè)職工對(duì)象, 則 14400 個(gè)索引項(xiàng)需要 56.25k 字節(jié), 在內(nèi)存中可以容納所有的索引項(xiàng)。,這樣只需從外存中把索引表讀入內(nèi)存, 經(jīng)過(guò)搜索索引后確定了職工對(duì)象的存儲(chǔ)地址, 再經(jīng)過(guò) 1 次讀取對(duì)象操作就可以完成搜索。 稠密索引：一個(gè)索引項(xiàng)對(duì)應(yīng)數(shù)據(jù)表中一個(gè)對(duì)象的索引結(jié)構(gòu)。當(dāng)對(duì)象在外存中按加入順序存放而不是按關(guān)鍵碼有序存放時(shí)必須采用稠密索引結(jié)構(gòu)，這時(shí)的索引結(jié)構(gòu)叫做索引非順序結(jié)構(gòu)。 稀疏索引：當(dāng)對(duì)象在外存中有序存放時(shí)，可以把所有 n 個(gè)對(duì)象分為 b 個(gè)子表(塊)存放，一個(gè)索引項(xiàng)對(duì)應(yīng)數(shù)據(jù)表中一組對(duì)象(子表)。,在子表中, 所有對(duì)象可能按關(guān)鍵碼有序地存放, 也可能無(wú)序地存放。但所有這些子表必須分塊有序, 后一個(gè)子表中所有對(duì)象的關(guān)鍵碼均大于前一個(gè)子表中所有對(duì)象的關(guān)鍵碼。它們都存放在數(shù)據(jù)區(qū)中。 另外建立一個(gè)索引表。索引表中每一表目叫做索引項(xiàng)，它記錄了子表中最大關(guān)鍵碼max _key以及該子表在數(shù)據(jù)區(qū)中的起始位置obj _ addr。 第 i 個(gè)索引項(xiàng)是第 i 個(gè)子表的索引項(xiàng), i = 0, 1, , n-1。這樣的索引結(jié)構(gòu)叫做索引順序結(jié)構(gòu)。,對(duì)索引順序結(jié)構(gòu)進(jìn)行搜索時(shí)，一般分為兩級(jí)搜索: 先在索引表 ID 中搜索給定值 K, 確定滿足 IDi-1.max_key K IDi.max_key,22 12 13 30 29 33,36 42 44 48 39 40,60 74 56 79 80 66,92 82 88 98 94,子表1,子表2,子表3,子表4,數(shù)據(jù)區(qū),33 48 80 98,索引表,1 2 3 4,max_ max_ key addr,的 i 值, 即待查對(duì)象可能在的子表的序號(hào)。 然后再在第 i 個(gè)子表中按給定值搜索要求的對(duì)象。 索引表是按max_key有序的, 且長(zhǎng)度也不大,可以折半搜索，也可以順序搜索。 各子表內(nèi)各個(gè)對(duì)象如果也按對(duì)象關(guān)鍵碼有序, 可以采用折半搜索或順序搜索; 如果不是按對(duì)象關(guān)鍵碼有序, 只能順序搜索。,索引順序搜索的搜索成功時(shí)的平均搜索長(zhǎng)度 ASLIndexSeq = ASLIndex + ASLSubList 其中, ASLIndex 是在索引表中搜索子表位置的平均搜索長(zhǎng)度，ASLSubList 是在子表內(nèi)搜索對(duì)象位置的搜索成功的平均搜索長(zhǎng)度。 設(shè)把長(zhǎng)度為 n 的表分成均等的 b 個(gè)子表，每個(gè)子表 s 個(gè)對(duì)象，則 b = n/s。又設(shè)表中每個(gè)對(duì)象的搜索概率相等，則每個(gè)子表的搜索概率為1/b，子表內(nèi)各對(duì)象的搜索概率為 1/s。 若對(duì)索引表和子表都用順序搜索，則索引順序搜索的搜索成功時(shí)的平均搜索長(zhǎng)度為 ASLIndexSeq = (b+1)/2+(s+1)/2 = (b+s)/2 +1,索引順序搜索的平均搜索長(zhǎng)度與表中的對(duì)象個(gè)數(shù) n 有關(guān)，與每個(gè)子表中的對(duì)象個(gè)數(shù) s 有關(guān)。在給定 n 的情況下，s 應(yīng)選擇多大？ 用數(shù)學(xué)方法可導(dǎo)出, 當(dāng) s = 時(shí), ASLIndexSeq取極小值 +1。這個(gè)值比順序搜索強(qiáng)，但比折半搜索差。但如果子表存放在外存時(shí)，還要受到頁(yè)塊大小的制約。 若采用折半搜索確定對(duì)象所在的子表, 則搜索成功時(shí)的平均搜索長(zhǎng)度為 ASLIndexSeq = ASLIndex + ASLSubList log2 (b+1)-1 + (s+1)/2 log2(1+n / s ) + s/2,倒排表 (Inverted Index List),對(duì)包含有大量數(shù)據(jù)對(duì)象的數(shù)據(jù)表或文件進(jìn)行搜索時(shí)，最常用的是針對(duì)對(duì)象的主關(guān)鍵碼建立索引。主關(guān)鍵碼可以唯一地標(biāo)識(shí)該對(duì)象。用主關(guān)鍵碼建立的索引叫做主索引。 主索引的每個(gè)索引項(xiàng)給出對(duì)象的關(guān)鍵碼和對(duì)象在表或文件中的存放地址。 但在實(shí)際應(yīng)用中有時(shí)需要針對(duì)其它屬性進(jìn)行搜索。例如，查詢?nèi)缦碌穆毠ば畔ⅲ?(1) 列出所有教師的名單；,對(duì)象關(guān)鍵碼 key 對(duì)象存放地址 addr,(2) 已婚的女性職工有哪些人？ 這些信息在數(shù)據(jù)表或文件中都存在，但都不是關(guān)鍵碼，為回答以上問(wèn)題，只能到表或文件中去順序搜索，搜索效率極低。 因此，除主關(guān)鍵碼外，可以把一些經(jīng)常搜索的屬性設(shè)定為次關(guān)鍵碼，并針對(duì)每一個(gè)作為次關(guān)鍵碼的屬性，建立次索引。 在次索引中，列出該屬性的所有取值，并對(duì)每一個(gè)取值建立有序鏈表，把所有具有相同屬性值的對(duì)象按存放地址遞增的順序或按主關(guān)鍵碼遞增的順序鏈接在一起。,次索引的索引項(xiàng)由次關(guān)鍵碼、鏈表長(zhǎng)度和鏈表本身等三部分組成。 例如，為了回答上述的查詢，我們可以分別建立“性別”、“婚否”和“職務(wù)”次索引。,性別次索引,次關(guān)鍵碼 男 女 計(jì) 數(shù) 5 3 地址指針,指針 03 08 17 24 47 51 83 95,婚否次索引,次關(guān)鍵碼 已婚 未婚 計(jì) 數(shù) 5 3 地址指針,指針 03 08 24 47 83 17 51 95,職務(wù)次索引,次關(guān)鍵碼 教師 教務(wù)員 實(shí)驗(yàn)員 計(jì) 數(shù) 5 1 2 地址指針,指針 08 24 47 51 83 03 17 95,(1) 列出所有教師的名單； (2) 已婚的女性職工有哪些人？ 通過(guò)順序訪問(wèn)“職務(wù)”次索引中的“教師”鏈，可以回答上面的查詢(1)。 通過(guò)對(duì)“性別”和“婚否”次索引中的“女性”鏈和“已婚”鏈進(jìn)行求“交”運(yùn)算，就能夠找到所有既是女性又已婚的職工對(duì)象，從而回答上面的查詢(2)。 倒排表是次索引的一種實(shí)現(xiàn)。在表中所有次關(guān)鍵碼的鏈都保存在次索引中，僅通過(guò)搜索次索引就能找到所有具有相同屬性值的對(duì)象。,在次索引中記錄對(duì)象存放位置的指針可以用主關(guān)鍵碼表示: 可通過(guò)搜索次索引確定該對(duì)象的主關(guān)鍵碼, 再通過(guò)搜索主索引確定對(duì)象的存放地址。 在倒排表中各個(gè)屬性鏈表的長(zhǎng)度大小不一,管理比較困難。為此引入單元式倒排表。 在單元式倒排表中, 索引項(xiàng)中不存放對(duì)象的存儲(chǔ)地址, 存放該對(duì)象所在硬件區(qū)域的標(biāo)識(shí)。 硬件區(qū)域可以是磁盤柱面、磁道或一個(gè)頁(yè)塊, 以一次 I / O 操作能存取的存儲(chǔ)空間作為硬件區(qū)域?yàn)樽詈谩?為使索引空間最小, 在索引中標(biāo)識(shí)這個(gè)硬件區(qū)域時(shí)可以使用一個(gè)能轉(zhuǎn)換成地址的二進(jìn)制數(shù),整個(gè)次索引形成一個(gè)(二進(jìn)制數(shù)的) 位矩陣。 例如, 對(duì)于記錄學(xué)生信息的文件, 次索引可以是如圖所示的結(jié)構(gòu)。二進(jìn)位的值為 1 的硬件區(qū)域包含具有該次關(guān)鍵碼的對(duì)象。 如果在硬件區(qū)域1，中有要求的對(duì)象。然后將硬件區(qū)域1，等讀入內(nèi)存，在其中進(jìn)行檢索，確定就可取出所需對(duì)象。,單元式倒排表結(jié)構(gòu),m 路靜態(tài)搜索樹(shù),當(dāng)數(shù)據(jù)對(duì)象數(shù)目特別大，索引表本身也很大，在內(nèi)存中放不下，需要分批多次讀取外存才能把索引表搜索一遍。 此時(shí), 可以建立索引的索引(二級(jí)索引)。二級(jí)索引可以常駐內(nèi)存，二級(jí)索引中一個(gè)索引項(xiàng)對(duì)應(yīng)一個(gè)索引塊，登記該索引塊的最大關(guān)鍵碼及該索引塊的存儲(chǔ)地址。,如果二級(jí)索引在內(nèi)存中也放不下，需要分為許多塊多次從外存讀入?？梢越⒍?jí)索引的索引(三級(jí)索引)。這時(shí)，訪問(wèn)外存次數(shù)等于讀入索引次數(shù)再加上1次讀取對(duì)象。,02 06,11 15,18 23,29 32,38 41,45 49,52 60,77 95,(06, ) (15, ) (23, ),(06, ) (15, ) (23, ),(32, ) (41, ) (49, ),(60, ) (95, ),(23, ) (41, ) (95, ),root,head,必要時(shí), 還可以有4級(jí)索引, 5極索引, 。 這種多級(jí)索引結(jié)構(gòu)形成一種 m 叉樹(shù)。樹(shù)中每一個(gè)分支結(jié)點(diǎn)表示一個(gè)索引塊, 它最多存放 m 個(gè)索引項(xiàng), 每個(gè)索引項(xiàng)分別給出各子樹(shù)結(jié)點(diǎn) (低一級(jí)索引塊) 的最大關(guān)鍵碼和結(jié)點(diǎn)地址。 樹(shù)的葉結(jié)點(diǎn)中各索引項(xiàng)給出在數(shù)據(jù)表中存放的對(duì)象的關(guān)鍵碼和存放地址。這種m叉樹(shù)用來(lái)作為多級(jí)索引，就是m路搜索樹(shù)。 m路搜索樹(shù)可能是靜態(tài)索引結(jié)構(gòu)，即結(jié)構(gòu)在初始創(chuàng)建，數(shù)據(jù)裝入時(shí)就已經(jīng)定型，在整個(gè)運(yùn)行期間，樹(shù)的結(jié)構(gòu)不發(fā)生變化。,多級(jí)索引結(jié)構(gòu)形成 m 路搜索樹(shù),m路搜索樹(shù)還可能是動(dòng)態(tài)索引結(jié)構(gòu), 即在整個(gè)系統(tǒng)運(yùn)行期間, 樹(shù)的結(jié)構(gòu)隨數(shù)據(jù)的增刪及時(shí)調(diào)整, 以保持最佳的搜索效率。,數(shù)據(jù)區(qū),一級(jí)索引,二級(jí)索引,三級(jí)索引,四級(jí)索引,動(dòng)態(tài)搜索結(jié)構(gòu),現(xiàn)在我們所討論的 m 路搜索樹(shù)多為可以動(dòng)態(tài)調(diào)整的多路搜索樹(shù)，它的一般定義為： 一棵 m 路搜索樹(shù), 它或者是一棵空樹(shù), 或者是滿足如下性質(zhì)的樹(shù)： 根最多有 m 棵子樹(shù), 并具有如下的結(jié)構(gòu)： n, P0, ( K1, P1 ), ( K2, P2 ), , ( Kn, Pn ) 其中, Pi 是指向子樹(shù)的指針, 0 i n m; Ki 是關(guān)鍵碼, 1 i n m。 Ki Ki+1, 1 i n。,動(dòng)態(tài)的 m 路搜索樹(shù),在子樹(shù) Pi 中所有的關(guān)鍵碼都小于 Ki+1, 且大于 Ki，0 i n。 在子樹(shù) Pn 中所有的關(guān)鍵碼都大于Kn； 在子樹(shù) P0 中的所有關(guān)鍵碼都小于 K1。 子樹(shù) Pi 也是 m 路搜索樹(shù)，0 i n。,一棵3路搜索樹(shù)的示例,35,20 40,a,b,c,d,e,25 30,10 15,45 50,m 路搜索樹(shù)的類定義 template class Mtree /基類 public: Triple ,AVL樹(shù)是2路搜索樹(shù)。如果已知 m 路搜索樹(shù)的度 m 和它的高度 h, 則樹(shù)中的最大結(jié)點(diǎn)數(shù)為,(等比級(jí)數(shù)前 h 項(xiàng)求和),每個(gè)結(jié)點(diǎn)中最多有 m-1 個(gè)關(guān)鍵碼，在一棵高度為 h 的 m 路搜索樹(shù)中關(guān)鍵碼的最大個(gè)數(shù)為 mh+1-1。 高度 h=2 的二叉樹(shù), 關(guān)鍵碼最大個(gè)數(shù)為7； 高度 h=3 的3路搜索樹(shù), 關(guān)鍵碼最大個(gè)數(shù)為 34-1 = 80。,struct Triple Mnode * r; /結(jié)點(diǎn)地址指針 int i; int tag; /結(jié)點(diǎn)中關(guān)鍵碼序號(hào) i ; /tag=0,搜索成功；tag=1,搜索不成功,標(biāo)識(shí) m 路搜索樹(shù)搜索結(jié)果的三元組表示,m 路搜索樹(shù)上的搜索算法,在 m 路搜索樹(shù)上的搜索過(guò)程是一個(gè)在結(jié)點(diǎn)內(nèi)搜索和自根結(jié)點(diǎn)向下逐個(gè)結(jié)點(diǎn)搜索的交替的過(guò)程。,35,20 40,a,b,c,d,e,25 30,10 15,45 50,root,搜索35,template Triple ,q = p; p = p-ptri; /向下一層結(jié)點(diǎn)搜索 GetNode (p); /讀入該結(jié)點(diǎn) result.r = q; result.i = i; result.tag = 1; return result; /搜索失敗,返回插入位置 ,提高搜索樹(shù)的路數(shù) m, 可以改善樹(shù)的搜索性能。對(duì)于給定的關(guān)鍵碼數(shù) n，如果搜索樹(shù)是平衡的，可以使 m 路搜索樹(shù)的性能接近最佳。下面將討論一種稱之為B 樹(shù)的平衡的 m 路搜索樹(shù)。,B 樹(shù),一棵 m 階B 樹(shù)是一棵平衡的 m 路搜索樹(shù), 它或者是空樹(shù), 或者是滿足下列性質(zhì)的樹(shù)： 根結(jié)點(diǎn)至少有 2 個(gè)子女。 除根結(jié)點(diǎn)以外的所有結(jié)點(diǎn) (不包括失敗結(jié)點(diǎn))至少有 m/2 個(gè)子女。 所有的失敗結(jié)點(diǎn)都位于同一層。 在B 樹(shù)中的“失敗”結(jié)點(diǎn)是當(dāng)搜索值x不在樹(shù)中時(shí)才能到達(dá)的結(jié)點(diǎn)。 事實(shí)上，在B 樹(shù)的每個(gè)結(jié)點(diǎn)中還包含有一組指針Dm，指向?qū)嶋H對(duì)象的存放地址。,30,Ki與Di (1 i n m) 形成一個(gè)索引項(xiàng)(Ki, Di)，通過(guò)Ki可找到某個(gè)對(duì)象的存儲(chǔ)地址Di。 一棵B 樹(shù)是平衡的 m 路搜索樹(shù)，但一棵平衡的 m 路搜索樹(shù)不一定是B 樹(shù)。,35,20 40,25 30,10 15,45 50,root,45 50,35,40,20,root,10 15,25,非B 樹(shù) B 樹(shù),B 樹(shù)的類定義和B 樹(shù)結(jié)點(diǎn)類定義 template class Btree : public Mtree /繼承 m 路搜索樹(shù)的所有屬性和操作 public: int Insert ( const Type template class Mnode / B 樹(shù)結(jié)點(diǎn)類定義 private:,int n; /結(jié)點(diǎn)中關(guān)鍵碼個(gè)數(shù) Mnode *parent; /雙親指針 Type keym+1; /關(guān)鍵碼數(shù)組 1m-1 Mnode *ptrm+1; /子樹(shù)指針數(shù)組 ;,B 樹(shù)的搜索算法,B 樹(shù)的搜索算法繼承了 m 路搜索樹(shù)Mtree上的搜索算法。 B 樹(shù)的搜索過(guò)程是一個(gè)在結(jié)點(diǎn)內(nèi)搜索和循某一條路徑向下一層搜索交替進(jìn)行的過(guò)程。,B 樹(shù)的搜索時(shí)間與B 樹(shù)的階數(shù) m 和B 樹(shù)的高度h直接有關(guān), 必須加以權(quán)衡。 在B 樹(shù)上進(jìn)行搜索, 搜索成功所需的時(shí)間取決于關(guān)鍵碼所在的層次; 搜索不成功所需的時(shí)間取決于樹(shù)的高度。 如果定義B 樹(shù)的高度h 為失敗結(jié)點(diǎn)所在的層次，需要了解樹(shù)的高度h 與樹(shù)中的關(guān)鍵碼個(gè)數(shù) N 之間的關(guān)系。 如果讓B 樹(shù)每層結(jié)點(diǎn)個(gè)數(shù)達(dá)到最大，且設(shè)關(guān)鍵碼總數(shù)為N, 則樹(shù)的高度達(dá)到最?。?h = logm( N*(m-2)/(m-1)+1) -1,設(shè)在 m 階B 樹(shù)中每層結(jié)點(diǎn)個(gè)數(shù)達(dá)到最少, 則B 樹(shù)的高度可能達(dá)到最大。設(shè)樹(shù)中關(guān)鍵碼個(gè)數(shù)為 N，從B 樹(shù)的定義知： 0層 1 個(gè)結(jié)點(diǎn) 1層 至少 2 個(gè)結(jié)點(diǎn) 2層 至少 2 m / 2 個(gè)結(jié)點(diǎn) 3層 至少 2 m / 2 2 個(gè)結(jié)點(diǎn) 如此類推， h-1 層 至少有 2 m / 2 h-2 個(gè)結(jié)點(diǎn)。所有這些結(jié)點(diǎn)都不是失敗結(jié)點(diǎn)。,高度h與關(guān)鍵碼個(gè)數(shù)N之間的關(guān)系,若樹(shù)中關(guān)鍵碼有N個(gè), 則失敗結(jié)點(diǎn)數(shù)為N+1。這是因?yàn)槭?shù)據(jù)一般與已有關(guān)鍵碼交錯(cuò)排列。因此，有 N +1 = 失敗結(jié)點(diǎn)數(shù) = 位于第 h 層的結(jié)點(diǎn)數(shù) 2 m / 2 h-1 N 2 m / 2 h-1-1 h-1 log m / 2 ( (N +1) / 2 ) 所有的非失敗結(jié)點(diǎn)所在層次為0 h-1。 示例：若B 樹(shù)的階數(shù) m = 199, 關(guān)鍵碼總數(shù) N = 1999999，則B 樹(shù)的高度 h 不超過(guò) log100 1000000 +1= 4,m值的選擇,如果提高B 樹(shù)的階數(shù) m, 可以減少樹(shù)的高度, 從而減少讀入結(jié)點(diǎn)的次數(shù), 因而可減少讀磁盤的次數(shù)。 事實(shí)上，m 受到內(nèi)存可使用空間的限制。當(dāng) m 很大超出內(nèi)存工作區(qū)容量時(shí), 結(jié)點(diǎn)不能一次讀入到內(nèi)存, 增加了讀盤次數(shù), 也增加了結(jié)點(diǎn)內(nèi)搜索的難度。 m值的選擇 : 應(yīng)使得在B 樹(shù)中找到關(guān)鍵碼 x 的時(shí)間總量達(dá)到最小。 這個(gè)時(shí)間由兩部分組成：,從磁盤中讀入結(jié)點(diǎn)所用時(shí)間 在結(jié)點(diǎn)中搜索 x 所用時(shí)間 根據(jù)定義, B 樹(shù)的每個(gè)結(jié)點(diǎn)的大小都是固定的, 結(jié)點(diǎn)內(nèi)有 m-1 個(gè)索引項(xiàng) (Ki, Di, Pi), 1 i m。其中，Ki 所占字節(jié)數(shù)為，Di 和 Pi 所占字節(jié)數(shù)為，則結(jié)點(diǎn)大小近似為 m(+2) 個(gè)字節(jié)。讀入一個(gè)結(jié)點(diǎn)所用時(shí)間為： tseek + tlatency + m( + 2) ttran = a + bm,B 樹(shù)的插入,B 樹(shù)是從空樹(shù)起, 逐個(gè)插入關(guān)鍵碼而生成的。 在B 樹(shù)，每個(gè)非失敗結(jié)點(diǎn)的關(guān)鍵碼個(gè)數(shù)都在 m/2 -1, m-1 之間。 插入在某個(gè)葉結(jié)點(diǎn)開(kāi)始。如果在關(guān)鍵碼插入后結(jié)點(diǎn)中的關(guān)鍵碼個(gè)數(shù)超出了上界 m-1，則結(jié)點(diǎn)需要“分裂”，否則可以直接插入。 實(shí)現(xiàn)結(jié)點(diǎn)“分裂”的原則是： 設(shè)結(jié)點(diǎn) p 中已經(jīng)有 m-1 個(gè)關(guān)鍵碼，當(dāng)再插入一個(gè)關(guān)鍵碼后結(jié)點(diǎn)中的狀態(tài)為,( m, P0, K1, P1, K2, P2, , Km, Pm) 其中 Ki Ki+1, 1 i m 這時(shí)必須把結(jié)點(diǎn) p 分裂成兩個(gè)結(jié)點(diǎn) p 和 q，它們包含的信息分別為： 結(jié)點(diǎn) p： ( m/2 -1, P0, K1, P1, , Km/2 -1, Pm/2 -1) 結(jié)點(diǎn) q： (m-m/2, Pm/2, Km/2+1, Pm/2+1, , Km, Pm) 位于中間的關(guān)鍵碼 Km/2 與指向新結(jié)點(diǎn) q 的指針形成一個(gè)二元組 ( Km/2, q )，插入到這兩個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)中去。,結(jié)點(diǎn)“分裂”的示例,2 53 75,n P0 K1 P1 K2 P2,p,3 53 75 139,n P0 K1 P1 K2 P2 K3 P3,p,加入139, 結(jié)點(diǎn)溢出,1 75,n P0 K1 P1,1 53,n P0 K1 P1,1 139,n P0 K1 P1,結(jié)點(diǎn) 分裂,P,q,49 75,示例:從空樹(shù)開(kāi)始加入關(guān)鍵碼建立3階B 樹(shù),n=1 加入53,53,n=2 加入75,53 75,n=3 加入139,75,139,53,n=5 加入49,145,75,139 145,49 53,n=6 加入36,139 145,53,36,在插入新關(guān)鍵碼時(shí)，需要自底向上分裂結(jié)點(diǎn)，最壞情況下從被插關(guān)鍵碼所在葉結(jié)點(diǎn)到根的路徑上的所有結(jié)點(diǎn)都要分裂。,若設(shè)B 樹(shù)的 高度為h, 那么在自頂向下搜索到葉結(jié)點(diǎn)的過(guò)程中需要進(jìn)行 h 次讀盤。,n=7 加入101,49,53,36,139,145,101,75,B 樹(shù)的插入算法 template int Btree : Insert ( const Type /寫(xiě)出, /結(jié)點(diǎn)已滿,分裂 int s = (m+1)/2; /求 m/2 insertkey ( p, j, K, ap ); /(K,ap)插入 j后 q = new Mnode; /建立新結(jié)點(diǎn) move ( p, q, s, m ); /從 p向q 搬送 K = p-keys; ap = q; /分界碼上移 if ( p-parent != NULL ) /雙親不是根 t = p-parent; GetNode (t); /讀入雙親 j = 0; t-key(t-n)+1 = MAXKEY; while ( t-keyj+1 parent = p-parent; PutNode (p); PutNode (q);,p = t; /繼續(xù) while(1) 循環(huán),向上調(diào)整 else /雙親是根 root = new Mnode; /創(chuàng)建新根 root-n = 1; root-parent = NULL; root-key1 = K; root-ptr0 = p; root-ptr1 = ap; q-parent = p-parent = root; PutNode (p); PutNode (q); PutNode (root); return 1; /跳出返回 ,當(dāng)分裂一個(gè)非根的結(jié)點(diǎn)時(shí)需要向磁盤寫(xiě)出 2 個(gè)結(jié)點(diǎn), 當(dāng)分裂根結(jié)點(diǎn)時(shí)需要寫(xiě)出 3 個(gè)結(jié)點(diǎn)。 如果我們所用的內(nèi)存工作區(qū)足夠大, 使得在向下搜索時(shí), 讀入的結(jié)點(diǎn)在插入后向上分裂時(shí)不必再?gòu)拇疟P讀入, 那么, 在完成一次插入操作時(shí)需要讀寫(xiě)磁盤的次數(shù) = = 找插入結(jié)點(diǎn)向下讀盤次數(shù) + + 分裂非根結(jié)點(diǎn)時(shí)寫(xiě)盤次數(shù) + + 分裂根結(jié)點(diǎn)時(shí)寫(xiě)盤次數(shù) = = h+2(h-1)+3 = = 3h+1。,B 樹(shù)的刪除,在B 樹(shù)上刪除一個(gè)關(guān)鍵碼時(shí), 首先需要找到這個(gè)關(guān)鍵碼所在的結(jié)點(diǎn), 從中刪去這個(gè)關(guān)鍵碼。若該結(jié)點(diǎn)不是葉結(jié)點(diǎn), 且被刪關(guān)鍵碼為 Ki, 1 i n, 則在刪去該關(guān)鍵碼之后, 應(yīng)以該結(jié)點(diǎn) Pi 所指示子樹(shù)中的最小關(guān)鍵碼 x 來(lái)代替被刪關(guān)鍵碼 Ki 所在的位置, 然后在 x 所在的葉結(jié)點(diǎn)中刪除 x。 在葉結(jié)點(diǎn)上的刪除有 4 種情況。 被刪關(guān)鍵碼所在葉結(jié)點(diǎn)同時(shí)又是根結(jié)點(diǎn)且刪除前該結(jié)點(diǎn)中關(guān)鍵碼個(gè)數(shù) n 2，則直接刪去該關(guān)鍵碼并將修改后的結(jié)點(diǎn)寫(xiě)回磁盤。,被刪關(guān)鍵碼所在葉結(jié)點(diǎn)不是根結(jié)點(diǎn)且刪除前該結(jié)點(diǎn)中關(guān)鍵碼個(gè)數(shù) n m/2 , 則直接刪去該關(guān)鍵碼并將修改后的結(jié)點(diǎn)寫(xiě)回磁盤, 刪除結(jié)束。 被刪關(guān)鍵碼所在葉結(jié)點(diǎn)刪除前關(guān)鍵碼個(gè)數(shù) n = m/2 -1, 若這時(shí)與該結(jié)點(diǎn)相鄰的右兄弟 (或左兄弟) 結(jié)點(diǎn)的關(guān)鍵碼個(gè)數(shù) n m/2，則可按以下步驟調(diào)整該結(jié)點(diǎn)、右兄弟 (或左兄弟) 結(jié)點(diǎn)以及其雙親結(jié)點(diǎn)，以達(dá)到新的平衡。,36 49,m = 3,刪除36,49,55 58,刪除55,簡(jiǎn)單刪除,75 80,m = 3,刪除55,10,40,65,60 70,30,50,a,c,b,d,e,f,g,h,58,75 80,10,40,65,60 70,30,50,a,c,b,d,e,f,g,h,將雙親結(jié)點(diǎn)中剛剛大于 (或小于) 該被刪關(guān)鍵碼的關(guān)鍵碼 Ki (1 i n) 下移； 將右兄弟 (或左兄弟) 結(jié)點(diǎn)中的最小 (或最大)關(guān)鍵碼上移到雙親結(jié)點(diǎn)的 Ki 位置； 將右兄弟 (或左兄弟) 結(jié)點(diǎn)中的最左 (或最右) 子樹(shù)指針平移到被刪關(guān)鍵碼所在結(jié)點(diǎn)中最后 (或最前) 子樹(shù)指針位置； 在右兄弟 (或左兄弟) 結(jié)點(diǎn)中，將被移走的關(guān)鍵碼和指針位置用剩余的關(guān)鍵碼和指針填補(bǔ)、調(diào)整。再將結(jié)點(diǎn)中的關(guān)鍵碼個(gè)數(shù)減1。,結(jié)點(diǎn)聯(lián)合調(diào)整,55 58,75 80,m = 3,刪除65,10,40,65,60 70,30,50,a,c,b,d,e,f,g,h,55 58,80,10,40,70,60 75,30,50,a,c,b,d,e,f,g,h,調(diào)整g,c,h,刪除65,70,刪除70,55 58,80,m = 3,刪除70,10,40,60 75,30,50,a,c,b,d,e,f,g,h,55,80,10,40,60,58 75,30,50,a,c,b,d,e,f,g,h,調(diào)整f,c,g,結(jié)點(diǎn)聯(lián)合調(diào)整,被刪關(guān)鍵碼所在葉結(jié)點(diǎn)刪除前關(guān)鍵碼個(gè)數(shù) n = m/2 -1, 若這時(shí)與該結(jié)點(diǎn)相鄰的右兄弟 (或左兄弟) 結(jié)點(diǎn)的關(guān)鍵碼個(gè)數(shù) n = m/2 -1, 則必須按以下步驟合并這兩個(gè)結(jié)點(diǎn)。 將雙親結(jié)點(diǎn) p 中相應(yīng)關(guān)鍵碼下移到選定保留的結(jié)點(diǎn)中。若要合并 p 中的子樹(shù)指針 Pi 與 Pi+1 所指的結(jié)點(diǎn), 且保留 Pi 所指結(jié)點(diǎn),則把 p 中的關(guān)鍵碼 Ki+1下移到 Pi 所指的結(jié)點(diǎn)中。 把 p 中子樹(shù)指針 Pi+1 所指結(jié)點(diǎn)中的全部指針和關(guān)鍵碼都照搬到 Pi 所指結(jié)點(diǎn)的后面。刪去 Pi+1 所指的結(jié)點(diǎn)。,在結(jié)點(diǎn) p 中用后面剩余的關(guān)鍵碼和指針填補(bǔ)關(guān)鍵碼 Ki+1 和指針 Pi+1。 修改結(jié)點(diǎn) p 和選定保留結(jié)點(diǎn)的關(guān)鍵碼個(gè)數(shù)。 在合并結(jié)點(diǎn)的過(guò)程中, 雙親結(jié)點(diǎn)中的關(guān)鍵碼個(gè)數(shù)減少了。 若雙親結(jié)點(diǎn)是根結(jié)點(diǎn)且結(jié)點(diǎn)關(guān)鍵碼個(gè)數(shù)減到 0, 則將該雙親結(jié)點(diǎn)刪去, 合并后保留的結(jié)點(diǎn)成為新的根結(jié)點(diǎn); 否則將雙親結(jié)點(diǎn)與合并后保留的結(jié)點(diǎn)都寫(xiě)回磁盤, 刪除處理結(jié)束。 若雙親結(jié)點(diǎn)不是根結(jié)點(diǎn)且關(guān)鍵碼個(gè)數(shù)減到m/2 -2，又要與它自己的兄弟結(jié)點(diǎn)合并, 重復(fù)上面的合并步驟。最壞情況下這種結(jié)點(diǎn)合并處理要自下向上直到根結(jié)點(diǎn)。,55,刪除55,結(jié)點(diǎn)合并,80,m = 3,刪除55,10,40,60,58 75,30,50,a,c,b,d,e,f,g,h,合并f, g,58 60,80,10,40,75,30,50,a,c,b,d,e,f,h,80,55,刪除80,結(jié)點(diǎn)合并,m = 3,刪除80,10,40,60,58 75,30,50,a,c,b,d,e,f,g,h,合并g, h,60 75,55,10,40,58,30,50,a,c,b,d,e,f,h,55,非葉結(jié)點(diǎn)刪除,刪除50,刪除55,55 58,75 80,m = 3,刪除50,10,40,65,60 70,30,50,a,c,b,d,e,f,g,h,58,75 80,刪除55,10,40,65,60 70,30,a,c,b,d,e,f,g,h,用55取代,用58取代,58,75 80,10,40,65,60 70,30,a,c,b,d,e,f,g,h,合并f, g,58,75 80,10,40,60 65,70,30,a,c,b,d,e,f,h,結(jié)點(diǎn)合并與調(diào)整,刪除70,58,80,10,40,60 65,75,30,a,c,b,d,e,f,h,刪除70,用75取代,刪除75,58,10,40,60 65,80,30,a,c,b,d,e,f,h,刪除75,用80取代 調(diào)整f, c, h,58,80,10,40,60,65,30,a,c,b,d,e,f,h,刪除10,80,30 40,60,f,h,58 65,d,b,B 樹(shù)的關(guān)鍵碼刪除算法 template int Btree : Delete ( const Type /在葉結(jié)點(diǎn)刪除,p = q; /轉(zhuǎn)化為葉結(jié)點(diǎn)的刪除 else compress ( p, j ); /葉結(jié)點(diǎn),直接刪除 int d = (m+1)/2; /求 m/2 while (1) /調(diào)整或合并 if ( p-n parent; /找到雙親 GetNode (q); while ( j n ,p = q; /向上調(diào)整 if ( p = root ) break; else break; if ( !root-n ) /調(diào)整后根的n減到0 p = root-ptr0; delete root; root = p; /刪根 root-parent = NULL; /新根 ,B+樹(shù),一棵 m 階B+樹(shù)可以定義如下： 樹(shù)中每個(gè)非葉結(jié)點(diǎn)最多有 m 棵子樹(shù)； 根結(jié)點(diǎn)(非葉結(jié)點(diǎn))至少有 2 棵子樹(shù)。除根結(jié)點(diǎn)外, 其它的非葉結(jié)點(diǎn)至少有 m/2 棵子樹(shù); 有 n 棵子樹(shù)的非葉結(jié)點(diǎn)有 n-1 個(gè)關(guān)鍵碼。 所有葉結(jié)點(diǎn)都處于同一層次上, 包含了全部關(guān)鍵碼及指向相應(yīng)數(shù)據(jù)對(duì)象存放地址的指針, 且葉結(jié)點(diǎn)本身按關(guān)鍵碼從小到大順序鏈接；,葉結(jié)點(diǎn)的子樹(shù)棵數(shù) n 可以多于 m, 可以少于 m, 視關(guān)鍵碼字節(jié)數(shù)及對(duì)象地址指針字節(jié)數(shù)而定。若設(shè)結(jié)點(diǎn)可容納最大關(guān)鍵碼數(shù)為 m1, 則指向?qū)ο蟮牡刂分羔樢灿?m1 個(gè)。,10 15,18 20 22,23 31,33 45,48 52,18 23,33,33,葉結(jié)點(diǎn)中的子樹(shù)棵數(shù) n 應(yīng)滿足 n m1/2 , m1。 若根結(jié)點(diǎn)同時(shí)又是葉結(jié)點(diǎn), 則結(jié)點(diǎn)格式同葉結(jié)點(diǎn)。 所有的非葉結(jié)點(diǎn)可以看成是索引部分, 結(jié)點(diǎn)中關(guān)鍵碼 Ki 與指向子樹(shù)的指針 Pi 構(gòu)成對(duì)子樹(shù)(即下一層索引塊)的索引項(xiàng)( Ki, Pi )，Ki 是子樹(shù)中最小的關(guān)鍵碼。 特別地, 子樹(shù)指針 P0 所指子樹(shù)上所有關(guān)鍵碼均小于 K1。結(jié)點(diǎn)格式同B 樹(shù)。,葉結(jié)點(diǎn)中存放的是對(duì)實(shí)際數(shù)據(jù)對(duì)象的索引。,在B+樹(shù)中有兩個(gè)頭指針: 一個(gè)指向 B+ 樹(shù)的根結(jié)點(diǎn)，一個(gè)指向關(guān)鍵碼最小的葉結(jié)點(diǎn)。 可對(duì)B+樹(shù)進(jìn)行兩種搜索運(yùn)算： 循葉結(jié)點(diǎn)鏈順序搜索 另一種是從根結(jié)點(diǎn)開(kāi)始, 進(jìn)行自頂向下, 直至葉結(jié)點(diǎn)的隨機(jī)搜索。 在B+樹(shù)上進(jìn)行隨機(jī)搜索、插入和刪除的過(guò)程基本上與B 樹(shù)類似。只是在搜索過(guò)程中，如果非葉結(jié)點(diǎn)上的關(guān)鍵碼等于給定值，搜索并不停止，而是繼續(xù)沿右指針向下，一直查到葉結(jié)點(diǎn)上的這個(gè)關(guān)鍵碼。,B+樹(shù)的搜索分析類似于B 樹(shù)。 B+樹(shù)的插入僅在葉結(jié)點(diǎn)上進(jìn)行。 每插入一 個(gè)(關(guān)鍵碼-指針)索引項(xiàng)后都要判斷結(jié)點(diǎn)中的子樹(shù)棵數(shù)是否超出范圍。 當(dāng)插入后結(jié)點(diǎn)中的子樹(shù)棵數(shù) n m1 時(shí), 需要將葉結(jié)點(diǎn)分裂為兩個(gè)結(jié)點(diǎn), 它們的關(guān)鍵碼分別為 (m1+1)/2 和 (m1+1)/2。 它們的雙親結(jié)點(diǎn)中應(yīng)同時(shí)包含這兩個(gè)結(jié)點(diǎn)的最小關(guān)鍵碼和結(jié)點(diǎn)地址。此后, 問(wèn)題歸于在非葉結(jié)點(diǎn)中的插入了。,3個(gè)關(guān)鍵碼的B+樹(shù),10 12 23,加入關(guān)鍵碼33,結(jié)點(diǎn)分裂,10 12,23 33,23,10 12,18 20 22,23 33,18 23,加入更多的關(guān)鍵碼,在非葉結(jié)點(diǎn)中關(guān)鍵碼的插入與葉結(jié)點(diǎn)的插入類似, 但非葉結(jié)點(diǎn)中的子樹(shù)棵數(shù)的上限為 m, 超出這個(gè)范圍就需要進(jìn)行結(jié)點(diǎn)分裂。 在做根結(jié)點(diǎn)分裂時(shí), 因?yàn)闆](méi)有雙親結(jié)點(diǎn), 就必須創(chuàng)建新的雙親結(jié)點(diǎn), 作為樹(shù)的新根。這樣樹(shù)的高度就增加一層了。 B+樹(shù)的刪除僅在葉結(jié)點(diǎn)上進(jìn)行。當(dāng)在葉結(jié)點(diǎn)上刪除一個(gè)(關(guān)鍵碼-指針)索引項(xiàng)后, 結(jié)點(diǎn)中的子樹(shù)棵數(shù)仍然不少于 m1/2，這屬于簡(jiǎn)單刪除, 其上層索引可以不改變。,如果刪除的關(guān)鍵碼是該結(jié)點(diǎn)的最小關(guān)鍵碼, 但因在其上層的副本只是起了一個(gè)引導(dǎo)搜索的“分界關(guān)鍵碼”的作用, 所以上層的副本仍然可以保留。 如果在葉結(jié)點(diǎn)中刪除一個(gè)(關(guān)鍵碼-指針)索引項(xiàng)后，該結(jié)點(diǎn)中的子樹(shù)棵數(shù) n 小于結(jié)點(diǎn)子樹(shù)棵數(shù)的下限 m1/2，必須做結(jié)點(diǎn)的調(diào)整或合并工作。,刪除18,10 15,18 20 22,23 31,33 45,48 52,18 23,33,33,10 15,20 22,23 31,33 45,48 52,18 23,33,33,刪除關(guān)鍵碼18 上層索引不改,10 15,18 20 22,23 31,33 45,48 52,18 23,33,33,15 18,20 22,23 31,33 45,48 52,20 23,33,33,刪除關(guān)鍵碼10, 18移入結(jié)點(diǎn),索 引改20,刪除10,如果右兄弟結(jié)點(diǎn)的子樹(shù)棵數(shù)已達(dá)到下限m1/2，沒(méi)有多余的關(guān)鍵碼可以移入被刪關(guān)鍵碼所在的結(jié)點(diǎn), 必須進(jìn)行兩個(gè)結(jié)點(diǎn)的合并。將右兄弟結(jié)點(diǎn)中的所有(關(guān)鍵碼-指針)索引項(xiàng)移入被刪關(guān)鍵碼所在結(jié)點(diǎn)，再將右兄弟結(jié)點(diǎn)刪去。 結(jié)點(diǎn)的合并將導(dǎo)致雙親結(jié)點(diǎn)中“分界關(guān)鍵碼”的減少, 有可能減到非葉結(jié)點(diǎn)中子樹(shù)棵數(shù)的下限 m/2 以下。這樣將引起非葉結(jié)點(diǎn)的調(diào)整或合并。如果根結(jié)點(diǎn)的最后兩個(gè)子女結(jié)點(diǎn)合并，樹(shù)的層數(shù)就會(huì)減少一層。,10 15,18 20 22,23 31,33 45,48 52,18 23,33,33,15 18,20 22,23 31,20 23 45,刪除關(guān)鍵碼33, 右邊兩結(jié)點(diǎn)合并, 影響到非葉結(jié)點(diǎn)合并,可能直到根結(jié)點(diǎn),導(dǎo)致高度減少,刪除33,45 48 52,散列 (Hashing),在計(jì)算科學(xué)中把詞典當(dāng)作一種抽象數(shù)據(jù)類型。 在討論詞典抽象數(shù)據(jù)類型時(shí)，把詞典定義為 對(duì)的集合。,在現(xiàn)實(shí)中, 經(jīng)常遇到按給定的值進(jìn)行查詢的事例。為此, 必須在開(kāi)發(fā)相應(yīng)軟件時(shí)考慮在記錄的存放位置和用以標(biāo)識(shí)它的數(shù)據(jù)項(xiàng) (稱為關(guān)鍵碼)之間的對(duì)應(yīng)關(guān)系,從而選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu), 很方便地根據(jù)記錄的關(guān)鍵碼檢索到對(duì)應(yīng)記錄的信息。,詞典(Dictionary)的抽象數(shù)據(jù)類型,根據(jù)問(wèn)題的不同, 可以為名字和屬性賦予不同的含義。 例如, 在圖書(shū)館檢索目錄中, 名字是書(shū)名, 屬性是索書(shū)號(hào)及作者等信息; 在計(jì)算機(jī)活動(dòng)文件表中, 名字是文件名, 屬性是文件地址、大小等信息。,詞典的抽象數(shù)據(jù)類型 const int DefaultSize = 26; template class Dictionary public:,Dictionary ( int size = DefaultSize ); int IsIn ( Name name ); Attribute * Find ( Name name ); void Insert ( Name name, Attribute attr ); void Remove ( Name name ); ,在詞典的所有操作中，最基本的只有 3 種：Find (搜索)、Insert (插入)、Remove (刪除)。 在選擇詞典的表示時(shí)，必須確保這幾個(gè)操作的實(shí)現(xiàn)。,通常，用文件 (表格) 來(lái)表示實(shí)際的對(duì)象集合, 用文件記錄 (表格的表項(xiàng)) 來(lái)表示單個(gè)對(duì)象。這樣, 詞典中的對(duì)將被存于記錄 (表項(xiàng)) 中，通過(guò)表項(xiàng)的關(guān)鍵碼 ( 對(duì)的名字) 來(lái)標(biāo)識(shí)該表項(xiàng)。 表項(xiàng)的存放位置及其關(guān)鍵碼之間的對(duì)應(yīng)關(guān)系可以用一個(gè)二元組表示： ( 關(guān)鍵碼key，表項(xiàng)位置指針addr ) 這個(gè)二元組構(gòu)成搜索某一指定表項(xiàng)的索引項(xiàng)。 考慮到搜索效率, 可以用順序表方式、二叉搜索樹(shù)或多路搜索樹(shù)方式組織詞典。本節(jié)討論另一種組織詞典的方法, 即散列表結(jié)構(gòu)。,靜態(tài)散列方法,散列方法在表項(xiàng)存儲(chǔ)位置與其關(guān)鍵碼之間建立一個(gè)確定的對(duì)應(yīng)函數(shù)關(guān)系Hash( )，使每個(gè)關(guān)鍵碼與結(jié)構(gòu)中一個(gè)唯一存儲(chǔ)位置相對(duì)應(yīng)： Address Hash ( Rec.key ) 在搜索時(shí), 先對(duì)表項(xiàng)的關(guān)鍵碼進(jìn)行函數(shù)計(jì)算,把函數(shù)值當(dāng)做表項(xiàng)的存儲(chǔ)位置, 在結(jié)構(gòu)中按此位置取表項(xiàng)比較。若關(guān)鍵碼相等, 則搜索成功。在存放表項(xiàng)時(shí), 依相同函數(shù)計(jì)算存儲(chǔ)位置, 并按此位置存放。這種方法就是散列方法。,在散列方法中使用的轉(zhuǎn)換函數(shù)叫做散列函數(shù)。按此方法構(gòu)造出來(lái)的表或結(jié)構(gòu)就叫做散列表。 使用散列方法進(jìn)行搜索不必進(jìn)行多次關(guān)鍵碼的比較, 搜索速度比較快, 可以直接到達(dá)或逼近具有此關(guān)鍵碼的表項(xiàng)的實(shí)際存放地址。 散列函數(shù)是一個(gè)壓縮映象函數(shù)。關(guān)鍵碼集合比散列表地址集合大得多。因此有可能經(jīng)過(guò)散列函數(shù)的計(jì)算，把不同的關(guān)鍵碼映射到同一個(gè)散列地址上，這就產(chǎn)生了沖突。 示例：有一組表項(xiàng)，其關(guān)鍵碼分別是 12361, 07251, 03309, 30976,采用的散列函數(shù)是 hash(x) = x % 73 + 13420 其中，“%”是除法取余操作。 則有：hash(12361) = hash(07250) = hash(03309) = hash(30976) = 13444。就是說(shuō), 對(duì)不同的關(guān)鍵碼, 通過(guò)散列函數(shù)的計(jì)算, 得到了同一散列地址。我們稱這些產(chǎn)生沖突的散列地址相同的不同關(guān)鍵碼為同義詞。 由于關(guān)鍵碼集合比地址集合大得多, 沖突很難避免。所以對(duì)于散列方法, 需要討論以下兩個(gè)問(wèn)題：,構(gòu)造散列函數(shù)時(shí)的幾點(diǎn)要求： 散列函數(shù)應(yīng)是簡(jiǎn)單的，能在較短的時(shí)間內(nèi)計(jì) 算出結(jié)果。 散列函數(shù)的定義域必須包括需要存儲(chǔ)的全部 關(guān)鍵碼, 如果散列表允許有 m 個(gè)地址時(shí), 其 值域必須在 0 到 m-1 之間。,散列函數(shù),對(duì)于給定的一個(gè)關(guān)鍵碼集合, 選擇一個(gè)計(jì)算簡(jiǎn)單且地址分布比較均勻的散列函數(shù), 避免或盡量減少?zèng)_突； 擬訂解決沖突的方案。,直接定址法 此類函數(shù)取關(guān)鍵碼的某個(gè)線性函數(shù)值作為散列地址： Hash ( key ) a * key + b a, b為常數(shù) 這類散列函數(shù)是一對(duì)一的映射，一般不會(huì)產(chǎn)生沖突。但是，它要求散列地址空間的大小與關(guān)鍵碼集合的大小相同。,散列函數(shù)計(jì)算出來(lái)的地址應(yīng)能均勻分布在整 個(gè)地址空間中 : 若 key 是從關(guān)鍵碼集合中隨 機(jī)抽取的一個(gè)關(guān)鍵碼, 散列函數(shù)應(yīng)能以同等 概率取0 到 m-1 中的每一個(gè)值。,示例：有一組關(guān)鍵碼如下： 942148, 941269, 940527, 941630, 941805, 941558, 942047, 940001 。散列函數(shù)為 Hash (key) = key - 940000 Hash (942148) = 2148 Hash (941269) = 1269 Hash (940527) = 527 Hash (941630) = 1630 Hash (941805) = 1805 Hash (941558) = 1558 Hash (942047) = 2047 Hash (940001) = 1 可以按計(jì)算出的地址存放記錄。 數(shù)字分析法,設(shè)有 n 個(gè) d 位數(shù), 每一位可能有 r 種不同的符號(hào)。這 r 種不同的符號(hào)在各位上出現(xiàn)的頻率不一定相同。 可根據(jù)散列表的大小, 選取其中各種符號(hào)分布均勻的若干位作為散列地址。 計(jì)算各位數(shù)字中符號(hào)分布均勻度 k 的公式： 其中， 表示第 i 個(gè)符號(hào)在第 k 位上出現(xiàn)的次數(shù)，n/r 表示各種符號(hào)在 n 個(gè)數(shù)中均勻出現(xiàn)的期望值。計(jì)算出的 k 值越小，表明在該位 (第 k 位) 各種符號(hào)分布得越均勻。,9 4 2 1 4 8 位， 1 = 57.60 9 4 1 2 6 9 位， 2 = 57.60 9 4 0 5 2 7 位， 3 = 17.60 9 4 1 6 3 0 位， 4 = 5.60 9 4 1 8 0 5 位， 5 = 5.60 9 4 1 5 5 8 位， 6 = 5.60 9 4 2 0 4 7 9 4 0 0 0 1 ,若散列表地址范圍有 3 位數(shù)字, 取各關(guān)鍵碼的 位做為記錄的散列地址。也可以把第，, 和第位相加, 舍去進(jìn)位位, 變成一位數(shù), 與第, 位合起來(lái)作為散列地址。,數(shù)字分析法僅適用于事先明確知道表中所有關(guān)鍵碼每一位數(shù)值的分布情況，它完全依賴于關(guān)鍵碼集合。如果換一個(gè)關(guān)鍵碼集合，選擇哪幾位要重新決定。 除留余數(shù)法 設(shè)散列表中允許地址數(shù)為 m, 取一個(gè)不大于 m, 但最接近于或等于 m 的質(zhì)數(shù) p 作為除數(shù), 利用以下函數(shù)把關(guān)鍵碼轉(zhuǎn)換成散列地址： hash ( key ) = key % p p m 其中, “%”是整數(shù)除法取余的運(yùn)算，要求這時(shí)的質(zhì)數(shù) p 不是接近2的冪。,示例: 有一個(gè)關(guān)鍵碼 key = 962148, 散列表大小 m = 25, 即 HT25。取質(zhì)數(shù) p= 23。散列函數(shù) hash ( key ) = key % p。則散列地址為 hash ( 962148 ) = 962148 % 23 = 12。 可以按計(jì)算出的地址存放記錄。需要注意的是, 使用上面的散列函數(shù)計(jì)算出來(lái)的地址范圍是 0到 22, 因此, 從23到24這幾個(gè)散列地址實(shí)際上在一開(kāi)始是不可能用散列函數(shù)計(jì)算出來(lái)的, 只可能在處理溢出時(shí)達(dá)到這些地址。 平方取中法 此方法在詞典處理中使用十分廣泛。,它先計(jì)算構(gòu)成關(guān)鍵碼的標(biāo)識(shí)符的內(nèi)碼的平方, 然后按照散列表的大小取中間的若干位作為散列地址。 設(shè)標(biāo)識(shí)符可以用一個(gè)計(jì)算機(jī)字長(zhǎng)的內(nèi)碼表示。因?yàn)閮?nèi)碼平方數(shù)的中間幾位一般是由標(biāo)識(shí)符所有字符決定, 所以對(duì)不同的標(biāo)識(shí)符計(jì)算出的散列地址大多不相同, 即使其中有些字符相同。 在平方取中法中, 一般取散列地址為 2 的某次冪。例如, 若散列地址總數(shù)取為 m = 2r，則對(duì)內(nèi)碼的平方數(shù)取中間的 r 位。如果 r = 3，所取得的散列地址參看圖的最右一列。,標(biāo)識(shí)符 內(nèi)碼 內(nèi)碼的平方 散列地址 A 01 01 001 A1 0134 20420 042 A9 0144 23420 342 B 02 4 004 DMAX 04150130 21526443617100 443 DMAX1 0415013034 5264473522151420 352 AMAX 01150130 135423617100 236 AMAX1 0115013034 3454246522151420 652,標(biāo)識(shí)符的八進(jìn)制內(nèi)碼表示及其平方值,折疊法 此方法把關(guān)鍵碼自左到右分成位數(shù)相等的幾部分, 每一部分的位數(shù)應(yīng)與散列表地址位數(shù)相同, 只有最后一部分的位數(shù)可以短一些。 把這些部分的數(shù)據(jù)疊加起來(lái), 就可以得到具有該關(guān)鍵碼的記錄的散列地址。 有兩種疊加方法： 移位法 把各部分的最后一位對(duì)齊相加； 分界法 各部分不折斷, 沿各部分的分界來(lái)回折疊, 然后對(duì)齊相加, 將相加的結(jié)果當(dāng)做散列地址。,示例: 設(shè)給定的關(guān)鍵碼為 key = 23938587841, 若存儲(chǔ)空間限定 3 位, 則劃分結(jié)果為