試談哈希樹(shù)數(shù)據(jù)結(jié)構(gòu)分析(19頁(yè))(正式版)

1、哈希樹(shù)( HashTree)羅堃 吳朝宏從 2000年開(kāi)始，作者開(kāi)始研究基于 TCP/IP 的短信息傳輸技術(shù)。這種技術(shù)目 前在國(guó)際上的標(biāo)準(zhǔn)被成為 SMPP (Short Message Peer to Peer Protoc) SMPP協(xié) 議是一種支持異步傳輸模式(Asynchronized Transmission Mode)的信息傳輸方 式。這種異步方式主要體現(xiàn)在兩個(gè)地方： 傳遞信息和等待確認(rèn)。 在為電信運(yùn)營(yíng)商 編寫(xiě)軟件的過(guò)程當(dāng)中， 解決大容量 (百萬(wàn)用戶以上) 要求下的快速查找與匹配成 為實(shí)現(xiàn)這個(gè)系統(tǒng)的核心任務(wù)。作者在反復(fù)設(shè)計(jì)整個(gè)過(guò)程中曾經(jīng)嘗試過(guò)很多種方式和算法， 但都未能取得滿 意的效

2、果。 最終不得不自己開(kāi)始設(shè)計(jì)針對(duì)這種系統(tǒng)的特殊存儲(chǔ)模式。 并在這個(gè)過(guò) 程中，找到了一種比較理想的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)哈希樹(shù)( HashTree)。一、查找算法在各種數(shù)據(jù)結(jié)構(gòu)(線性表、樹(shù)等)中，記錄在結(jié)構(gòu)中的相對(duì)位置是隨機(jī)的， 和記錄的關(guān)鍵字之間不存在確定的關(guān)系。 因此在機(jī)構(gòu)中查找記錄的時(shí)需要進(jìn)行一 系列和關(guān)鍵字的比較。這一類的查找方法建立在“比較”的基礎(chǔ)上。在順序查找 時(shí)，比較的結(jié)果為“”與“”兩種可能。在折半查找、二叉排序樹(shù)查找和樹(shù)查找 時(shí)，比較的結(jié)果為“”、“”與“”三種可能。查找的效率依賴于查找過(guò)程中所進(jìn) 行的比較次數(shù)。為確定記錄在查找表中的位置， 需和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的期望值 成為查

3、找算法在查找成功時(shí)的平均查找長(zhǎng)度(Average Search Length。下面我們簡(jiǎn)單討論一下在含有個(gè)數(shù)據(jù)記錄的結(jié)構(gòu)中，各種查找算法的平均查找長(zhǎng)度。在等概率的情況下，順序查找的平均查找長(zhǎng)度為：對(duì)于折半查找(表要求是順序表) ，在比較大()的時(shí)候，可有以下近似結(jié) 果：在隨機(jī)情況下(二叉樹(shù)查找可能退化為順序查找) ，對(duì)于二叉樹(shù)，其平均查找長(zhǎng)度為：ASLb =14 log n在平衡二叉樹(shù)上進(jìn)行查找，其平均查找長(zhǎng)度為：ASLbb = log ；,5(n 1) -2，其中:對(duì)于一顆m階的B樹(shù)，從根節(jié)點(diǎn)到關(guān)鍵字所在節(jié)點(diǎn)的路徑上涉及的節(jié)點(diǎn)數(shù) 可以說(shuō)是平均查找長(zhǎng)度的上限：n +1AS-,logm/2()1

4、總的來(lái)說(shuō)，這些查找算法的效率都將隨著數(shù)據(jù)記錄數(shù)的增長(zhǎng)而下降。僅僅是 有的比較快(時(shí)間復(fù)雜度為0(n),有的比較慢(時(shí)間復(fù)雜度是O(log n)而已。 這些查找算法的平均查找長(zhǎng)度是在一種比較理想的情況下獲得的。在實(shí)際應(yīng)用當(dāng)中，對(duì)數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)的頻繁增加和刪除將不斷地改變著數(shù)據(jù)的結(jié)構(gòu)。這些操作將可能導(dǎo)致某些數(shù)據(jù)結(jié)構(gòu)退化為鏈表結(jié)構(gòu)，那么其性能必然將下降。為了避免出 現(xiàn)這種情況而采取的調(diào)整措施，又不可避免的增加了程序的復(fù)雜程度以及操作的 額外時(shí)間。二、哈希表理想的情況是希望不經(jīng)過(guò)任何比較，一次存取便能得到所查的記錄，那就必須在記的存儲(chǔ)位置和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系f，使每個(gè)關(guān)鍵字和結(jié)構(gòu)中一

5、個(gè)唯一的存儲(chǔ)位置相對(duì)應(yīng)。因而在查找時(shí)，只要根據(jù)這個(gè)對(duì)應(yīng)關(guān)系f 找到給定值K的像f(K)。若結(jié)構(gòu)中存在關(guān)鍵字和K相等的記錄，則必定在f(K) 的存儲(chǔ)位置上，由此，不需要進(jìn)行比較便可直接取得所查記錄。在此，我們稱這 個(gè)對(duì)應(yīng)關(guān)系為哈希(Hash)函數(shù)，按這個(gè)思想建立的表為哈希表。在哈希表中對(duì)于不同的關(guān)鍵字可能得到同一哈希地址，即Q =K2，而f(KJ = f(K2)。這種現(xiàn)象稱做沖突(Collision)。在一般情況下，沖突只能盡可 能地減少，而不能完全避免。因?yàn)楣：瘮?shù)是從關(guān)鍵字集合到地址集合的映像。通常關(guān)鍵字的集合比較大，它的元素包括所有可能的關(guān)鍵字，而地址集合的元素 僅為哈希表中的地址值。假設(shè)

6、標(biāo)識(shí)符可定義為以字符為首的 8位字符，則關(guān)鍵字（標(biāo)識(shí)符）的集合大 小為C；6 C：6 7匕1.09338 1012，而在一個(gè)源程序中出現(xiàn)的數(shù)據(jù)對(duì)象是有限的， 設(shè)有10000個(gè)元素。地址集合中的元素為 0到9999。因此在一般情況下，哈希 函數(shù)是一個(gè)壓縮映像函數(shù)，這就不可避免的要產(chǎn)生沖突。二、哈希樹(shù)的理論基礎(chǔ)2.1質(zhì)數(shù)分辨定理定理 1 :選取任意n個(gè)互不相同的質(zhì)數(shù)：Pi ： P2 ：巳；Pn-1 ： Pn（n N），定義：nM 二：PP2 F3“一 Pni占設(shè) m _ k1 ： k2 ： m M （ m, & 人 N），那么對(duì)于任意的 i 1,n 1,（ kdm R ） =（k2 mod

7、 P ）不可能總成立。證明：假設(shè)定理1的結(jié)論不正確，那么對(duì)于任意的 r 1,n 1，（ k1 m R）=（k2 mod P ）將總是成立。這個(gè)可以表達(dá)為：k - S1i Pi ri， k = S2i Pi ri，其中創(chuàng)，S2i, A N設(shè)：K = k2 - « = S2i - S1iPi 0顯然，K是一個(gè)合數(shù)，而且包含質(zhì)因素Pi。根據(jù)質(zhì)數(shù)的定義和質(zhì)因素分解定 理，K可以表達(dá)為：K =P1 P2 P3Pn4 Pn S 一 M，其中 S N而另外一方面，根據(jù) m三k2 : m M，可以得出:0 : k2 - k： M很明顯，這兩個(gè)結(jié)論是相互矛盾的。因此原定理1正確。這個(gè)定理可以簡(jiǎn)單的表述

8、為：n個(gè)不同的質(zhì)數(shù)可以“分辨”的連續(xù)整數(shù)的個(gè) 數(shù)和他們的乘積相等?！胺直妗本褪侵高@些連續(xù)的整數(shù)不可能有完全相同的余數(shù) 序列。這個(gè)為哈希樹(shù)的分辨方式奠定了理論基礎(chǔ)。顯然，這個(gè)定理的一個(gè)特殊情況就是Pn(n N)為從2起的連續(xù)質(zhì)數(shù)。我們可 以記Mn為前n個(gè)連續(xù)質(zhì)數(shù)的乘積。連續(xù)10個(gè)質(zhì)數(shù)就可以分辨大約 Mio =6469693230個(gè)數(shù)，已經(jīng)超過(guò)計(jì)算機(jī)中常用整數(shù)(32bit)的表達(dá)范圍。連續(xù) 100 個(gè)質(zhì)數(shù)就可以分辨大約 M100 二 4.7119307999061875 10219。而按照目前的CPU水平，100次取余的整數(shù)除法操作幾乎不算什么難事。在實(shí)際應(yīng)用中，整體的操作速度往往取決于節(jié)點(diǎn)將關(guān)鍵

9、字裝載內(nèi)存的次數(shù)和時(shí)間。 一般來(lái)說(shuō)，裝載的時(shí)間是由關(guān)鍵字的大小和硬件來(lái)決定的；在相同類型關(guān)鍵字和相同硬件條件下，實(shí)際的整體操作時(shí)間就主要取決于裝載的次數(shù)。他們之間是一個(gè)成正比的關(guān)系。2.2余數(shù)分辨定理在這里，我們對(duì)更為普遍的余數(shù)分辨方式做一個(gè)討論。定理 2 :選取任意n個(gè)互不相同的自然數(shù)：h ： J ：丨3 ：ln-1 ： In(nN)，定義 LCM( Lease Com mon Multiple)為 11, D,丨3,，ln-1, I n 的最 小公倍數(shù)。設(shè) m 二 & : k2 : m LCM ( m, k1,k N )，那么對(duì)于任意的 i 1,n 丨，(k1 mod Ii ) =

10、 ( k2 mod h )不可能總成立。證明：假設(shè)定理2的結(jié)論不正確，那么對(duì)于任意的i 1, n 1，( k1 m I i )=(k2 mod I i)將總是成立。這個(gè)可以表達(dá)為：kS1iIi 仃，k2 二 S2iIi A，其中 S1i, S2i, r-N設(shè):K = k? -=S2i - Sii I i > 0顯然，K是一個(gè)合數(shù)，而且包含因素Ii。根據(jù)最小公倍數(shù)的定義，K可以表 達(dá)為：K =k2 -ki =S LCM - LCM，其中 S N而另外一方面，根據(jù) m乞ki ： k2 : m - LCM，可以得出：0 ： k2 - kj : LCM很明顯，這兩個(gè)結(jié)論是相互矛盾的。因此原定理

11、2正確。這個(gè)定理2可以簡(jiǎn)單的表述為：n個(gè)不同的數(shù)可以“分辨”的連續(xù)整數(shù)的個(gè) 數(shù)不超過(guò)他們的最小公倍數(shù)。超過(guò)這個(gè)范圍就意味著沖突的概率會(huì)增加。定理1是定理2的一個(gè)特例。2.3分辨算法評(píng)價(jià)標(biāo)準(zhǔn)1. 狀態(tài)和特征分辨也即分辨不同的狀態(tài)。分辨一般是先定義一組不同的狀態(tài)，然后將這些 狀態(tài)記錄下來(lái)形成特征。由這些特征所形成的空間是特征空間。 特征空間的緯數(shù) 是特征數(shù)列的長(zhǎng)度。2. 分辨能力分辨能力D,也稱分辨范圍，就是指分辨算法可以分辨的最大連續(xù)空間大小。 在這個(gè)范圍內(nèi)，分辨算法可以唯一確定被分辨數(shù)。即任何兩個(gè)在分辨范圍內(nèi)的數(shù)， 不可能具有完全相同的特征數(shù)。這些特征數(shù)會(huì)以某種形式被記錄下來(lái)， 或者以數(shù) 據(jù)結(jié)

12、構(gòu)的形式體現(xiàn)出來(lái)。對(duì)于兩個(gè)具有相同分辨能力的分辨算法，我們認(rèn)為他們是等價(jià)算法。當(dāng)D：的時(shí)候，分辨算法的分辨能力最強(qiáng)。但是同時(shí)分辨算法所使用的特 征空間也將是無(wú)窮大，我們不可能有足夠的空間來(lái)存放這些相關(guān)特征記錄。3. 沖突概率當(dāng)被分辨數(shù)之間的距離超出分辨范圍的時(shí)候，就有可能發(fā)生沖突，這種沖突 的概率被定義為沖突概率':、 10 1D當(dāng)被分辨的數(shù)是隨機(jī)分布在整個(gè)數(shù)軸的時(shí)候，兩個(gè)數(shù)之間的距離可能會(huì)超過(guò) 分辨范圍。這個(gè)時(shí)候分辨算法不一定會(huì)完全失效。沖突概率就體現(xiàn)為衡量某種 分辨算法在處理散列時(shí)候的特性。沖突概率越小，那么處理散列的能力就越強(qiáng)， 對(duì)非連續(xù)空間的特征分辨能力就越高； 反之，那么處理

13、散列的能力就越弱，對(duì)非 連續(xù)空間的特征分辨能力就越低。對(duì)于兩個(gè)具有相同沖突概率的分辨算法，我們也認(rèn)為他們是等價(jià)算法。4.分辨效率根據(jù)分辨算法的特點(diǎn)，我們可以定義分辨效率：0% :分辨能力所有用于分辨的特征個(gè)數(shù)的乘積100%=LCMM100% 空 100%在由定理1和定理2可以得知：當(dāng)用于余數(shù)分辨的整數(shù)數(shù)列是某一個(gè)確定整 數(shù)，或者互不相等的質(zhì)數(shù)數(shù)列的時(shí)候， 或者是互相沒(méi)有公約數(shù)的整數(shù)數(shù)列， 分辨 效率 =100% ;其他情況下，分辨效率都小于 100%。5.簡(jiǎn)化度在分辨算法中，我們定義數(shù)列的簡(jiǎn)化度一：為：0 :1所有用于分辨的特征個(gè)數(shù)的和所有用于分辨的特征個(gè)數(shù)的和，代表了分辨所需要的特征總數(shù)。特

14、征總數(shù)越 少，那么簡(jiǎn)化度就越高。分辨算法的簡(jiǎn)化度越高，說(shuō)明所用狀態(tài)數(shù)越少，分辨過(guò) 程將能更簡(jiǎn)單。這個(gè)評(píng)價(jià)標(biāo)準(zhǔn)有利于我們?nèi)コ哂嗵卣鞯牟糠?。定?3：在相同分辨范圍條件下的余數(shù)分辨算法中，所有分辨效率100%的分辨數(shù)列的簡(jiǎn)化度都小于分辨效率=100%的分辨數(shù)列的簡(jiǎn)化度證明：分辨效率 < 100%意味著用于分辨的整數(shù)數(shù)列中，肯定存在某兩個(gè)整數(shù)有約數(shù)（否則他們的乘積就是他們的最小公倍數(shù)，那么分辨效率=100%）GCD ( Greatest Common這個(gè)約數(shù)我們稱它為這兩個(gè)數(shù)之間的最大公約數(shù)Divisor ）。不妨設(shè)這兩個(gè)整數(shù)為：顯然如果用Qi代替Ii，將不會(huì)影響這些整數(shù)之間的最小公倍數(shù) L

15、CM。一方 面，這些整數(shù)的積得到了減少，分辨效率將有所提高；另外一方面，這些整數(shù)的 和得到了減少，簡(jiǎn)化度也因此而提到。通過(guò)反復(fù)簡(jiǎn)化操作這個(gè)數(shù)列的分辨效率總 可以達(dá)到100%1:分辨效率 <100%的分辨數(shù)列總可以簡(jiǎn)化，而且可以簡(jiǎn)化成分辨效率 =100%的分辨數(shù)列。6.綜合評(píng)價(jià)指標(biāo)我們定義分辨算法綜合評(píng)價(jià)指標(biāo)-:，J 特征空間緯數(shù)這個(gè)標(biāo)準(zhǔn)意味著：分辨范圍越大，簡(jiǎn)化度越高，那么這個(gè)算法的綜合性能就越好。例如：在余數(shù)分辨法中，如果我們選擇數(shù)列100,200,3001作為分辨數(shù)列, 那么采取這個(gè)數(shù)列的余數(shù)分辨算法各項(xiàng)指標(biāo)如下:D = LCM 二 60010.001667600V =100 200

16、 3001=0.00001LCM0.001667 100 200 300 小 D x P0.333333如果我們選擇數(shù)列'2,3,5,7,11 “乍為分辨數(shù)列，那么采取這個(gè)數(shù)列的余數(shù)分辨算法各項(xiàng)指標(biāo)如下:D = LCM =23104.32 10,23100.035712 3 5 7 11 八D汀16.5顯然后者在綜合評(píng)價(jià)方面要優(yōu)于前者。2.4線性分辨算法線性分辨算法是利用線性函數(shù)f (x)二ax b作為分辨算法的分辨算法，或者 稱為余數(shù)分辨算法。這種算法簡(jiǎn)單易行。上面所有的討論都是基于線性分辨算法 的。2.5非線性分辨算法非線性分辨算法是指在特征數(shù)的獲取過(guò)程中采用非線性函數(shù)的方法。 這

17、也就 是說(shuō)，可以完全使用非線性函數(shù)，或者非線性函數(shù)和線性函數(shù)混合使用。 但是只 要是使用了非線性函數(shù)，那么就被稱作非線性分辨。在這些算法里面，可以分成兩類：非線性函數(shù)特征法和分段特征提取法。1. 非線性函數(shù)特征法利用單值非線性函數(shù)(例如：f (x)- -x，f(x)-xn )來(lái)提取特征的方法就稱 為非線性特征法。很明顯這些函數(shù)的單值對(duì)應(yīng)性，并沒(méi)有改變分辨范圍的大小。 這些函數(shù)僅僅是將特征空間做了一個(gè)變形處理。 這種變形可能是平移、縮放等等。 但是分辨能力沒(méi)有擴(kuò)大，沖突概率也并沒(méi)有得到減少，簡(jiǎn)化度也沒(méi)有發(fā)生變化， 分辨算法的整體評(píng)價(jià)標(biāo)準(zhǔn)也沒(méi)有改變。2. 分段特征提取法分段特征提取法就是將被分辨的

18、數(shù)分成若干部分，每個(gè)部分有若干狀態(tài)。假 設(shè)某個(gè)數(shù)可以被分成n段，每段所有可能的狀態(tài)個(gè)數(shù)為 Si (其中代1, n】)。那 么我們可以得出以下結(jié)論：Sj N，且 Sj_2任何一個(gè)段的狀態(tài)至少是有兩個(gè)狀態(tài)，否則這種分段是毫無(wú)意義的。或者說(shuō) 這段是沒(méi)有任何特征的，對(duì)分辨算法來(lái)說(shuō)是一種時(shí)間和空間的浪費(fèi)。這種算法的分辨能力是:nD 二-Si =S1S2S3 Sn 2ni 4其沖突概率：-19-n=-2D這種算法的分辨效率 =100%，簡(jiǎn)化度為:、Sii z01 1< S1 S2 S3亠 Sn 2n總體評(píng)價(jià):II Sii=01 3 S2 S3 Sn n S S2 S3 亠亠 Sni =0這種算法可以

19、做到在所有分辨算法中的簡(jiǎn)化度最高，綜合評(píng)價(jià)也可以很高。但這種分辨算法的綜合評(píng)價(jià) 門(mén)并不總是最高的。例如：當(dāng)我們?cè)诜直?2位整數(shù)的時(shí)候，使用這種分段特征分辨法，那么這種分辨方法的各項(xiàng)指標(biāo)如下：32D = 2 =4294967276?；宀 1 ： 2.33 100D= 100%10.0156252 32八D漢0209715232如果在余數(shù)分辨算法中，我們選擇從2到29的連續(xù)10個(gè)質(zhì)數(shù)作為分辨數(shù)列,那么這個(gè)分辨方法的各項(xiàng)指標(biāo)如下:D = M10 二 646969323011.54 10J0D= 100%1 10.007752 3 5 7 11 13 17 19 23 29129D x P501522

20、60710在分辨以2進(jìn)制為基礎(chǔ)的連續(xù)整數(shù)的時(shí)候，這種算法有著明顯的優(yōu)勢(shì)。但是 在分辨散列的時(shí)候，例如：以字符為基礎(chǔ)的字符串的時(shí)候，其特征緯數(shù)和者特征 數(shù)將會(huì)迅速增加。過(guò)多的特征緯數(shù)和特征數(shù)意味者，對(duì)于特征空間的浪費(fèi)、更多的初始化時(shí)間以及更多比較次數(shù)和比較時(shí)間。為了仍然能夠使用這種分辨方法， 普遍采用對(duì)字符串壓縮編碼轉(zhuǎn)換成整數(shù)后，再使用該分辨算法。但是即使是采取 轉(zhuǎn)換手段，對(duì)于超長(zhǎng)的字符串仍然不是十分容易處理。三、哈希樹(shù)的組織結(jié)構(gòu)使用不同的分辨算法都可以組織成哈希樹(shù)。一般來(lái)說(shuō)：每層哈希樹(shù)的節(jié)點(diǎn)下 的子節(jié)點(diǎn)數(shù)是和分辨數(shù)列一致的。哈希樹(shù)的最大深度和特征空間的緯數(shù)是一致 的。為了研究的方便，我們選擇質(zhì)

21、數(shù)分辨算法來(lái)建立一顆哈希樹(shù)。選擇從2開(kāi)始的連續(xù)質(zhì)數(shù)來(lái)建立一個(gè)十層的哈希樹(shù) （因?yàn)镸10已經(jīng)超過(guò)了計(jì)算機(jī)中常用整數(shù)的 表達(dá)范圍）。第一層節(jié)點(diǎn)為根節(jié)點(diǎn)，根節(jié)點(diǎn)下有 2個(gè)節(jié)點(diǎn)；第二層的每個(gè)節(jié)點(diǎn)下 有3個(gè)節(jié)點(diǎn)；依此類推，即每層節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)目為連續(xù)的質(zhì)數(shù)。至U了第十層， 每個(gè)節(jié)點(diǎn)下有29個(gè)節(jié)點(diǎn)。同一節(jié)點(diǎn)中的子節(jié)點(diǎn)，從左到右代表不同的余數(shù)結(jié)果。例如：第二層節(jié)點(diǎn)下 有三個(gè)子節(jié)點(diǎn)。那么從左到右分別代表：除 3余0,除3余1和除3余2。對(duì)質(zhì)數(shù)的余數(shù)決定了處理的路徑。例如：某個(gè)數(shù)來(lái)到第二層子節(jié)點(diǎn)，那么它 要做取余操作，然后再?zèng)Q定從哪個(gè)子節(jié)點(diǎn)向下搜尋。如果這個(gè)數(shù)是12那么它需要從第一個(gè)子節(jié)點(diǎn)向下搜索；如果這個(gè)數(shù)是

22、7那么它需要從第二個(gè)子節(jié)點(diǎn)向下搜 索；如果這個(gè)數(shù)是32那么它需要從第三個(gè)子節(jié)點(diǎn)向下搜索。如果所有的節(jié)點(diǎn)都存在，并容納數(shù)據(jù)的話，那么可以容納的數(shù)據(jù)項(xiàng)目總數(shù)將比Mg要大一些：10M （10） = ' M i 6703028889 109i#如果在建立當(dāng)初就建立所有的節(jié)點(diǎn)，那么所消耗的計(jì)算時(shí)間和磁盤(pán)空間是巨 大的。在實(shí)際使用當(dāng)中，只需要初始化根節(jié)點(diǎn)就可以開(kāi)始工作。子節(jié)點(diǎn)的建立是在有更多的數(shù)據(jù)進(jìn)入到哈希樹(shù)中的時(shí)候建立的。因此可以說(shuō)哈希樹(shù)和其他樹(shù)一樣是一個(gè)動(dòng)態(tài)結(jié)構(gòu)。這些節(jié)點(diǎn)有以下基本元素：1. 節(jié)點(diǎn)的關(guān)鍵字我們用key來(lái)表示節(jié)點(diǎn)的關(guān)鍵字。在整個(gè)樹(shù)中這個(gè)數(shù)值是唯一的。當(dāng)節(jié) 點(diǎn)占據(jù)標(biāo)志位（occup

23、ied）為真的時(shí)候，關(guān)鍵字才認(rèn)為是有效的，否則是無(wú) 效的。2. 節(jié)點(diǎn)是否被占據(jù)我們用occupied來(lái)表示節(jié)點(diǎn)是否被占據(jù)。如果節(jié)點(diǎn)的關(guān)鍵字（key）有效,那么occupied應(yīng)該設(shè)置位true,否則設(shè)置為false。3. 節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)組我們用nodesi來(lái)表示節(jié)點(diǎn)的第i個(gè)子節(jié)點(diǎn)的地址。第10個(gè)質(zhì)數(shù)為29, 余數(shù)不可能大于32。這個(gè)數(shù)組的固定長(zhǎng)度為可以設(shè)置為 32，即0 乞31。 當(dāng)?shù)趇個(gè)子節(jié)點(diǎn)不存在時(shí)，nodesi=NULL，否則為子節(jié)點(diǎn)的地址。4. 節(jié)點(diǎn)的數(shù)據(jù)對(duì)象我們用value來(lái)表示節(jié)點(diǎn)的數(shù)據(jù)對(duì)象。四、插入規(guī)則設(shè)需要插入的關(guān)鍵字和數(shù)據(jù)分別為key和value。用level表示插入操作進(jìn)行

24、到第幾層，level從0開(kāi)始。Prime表為連續(xù)質(zhì)數(shù)表。插入過(guò)程從根節(jié)點(diǎn)開(kāi)始執(zhí)行：1. 如果當(dāng)前節(jié)點(diǎn)沒(méi)有被占據(jù)(occupied = false)，則設(shè)置該節(jié)點(diǎn)的key和 value，并設(shè)置占據(jù)標(biāo)記為true，然后返回。2. 如果當(dāng)前節(jié)點(diǎn)被占據(jù)( occupied = true)，則計(jì)算 index = key mod Primelevel。3. 如果nodesindex = NULL，那么創(chuàng)建子節(jié)點(diǎn)，將level加1,并重復(fù)第1 步操作。4. 如果nodesindex為一個(gè)子節(jié)點(diǎn)那么，將level加1，然后重復(fù)第1步操 作。用偽碼來(lái)表示如下：void in sert (HashNode en

25、try, int level, Key key, Value value)if (this.occupied = false)this.key = key;this.value = value;this.occupied = true;return;int index = key mod Primelevel;if( nodesindex = NULL)nodesindex = new HashNode();level = level + 1; insert(nodesindex, level, key, value);五、查找操作設(shè)需要查找的關(guān)鍵字為key。用level表示插入進(jìn)行到第幾層，

26、level從0開(kāi)始。Prime 表為連續(xù)質(zhì)數(shù)表。插入過(guò)程從根節(jié)點(diǎn)開(kāi)始執(zhí)行：1. 如果當(dāng)前節(jié)點(diǎn)沒(méi)有被占據(jù)(occupied = false)，則執(zhí)行第5步操作。2. 如果當(dāng)前節(jié)點(diǎn)已經(jīng)被占據(jù)(occupied = true)，則讀取該節(jié)點(diǎn)的關(guān)鍵字， 將它和key進(jìn)行比較。3. 如果相等，則返回查找成功和該節(jié)點(diǎn)的value。4. 如果不等，則執(zhí)行第 5 步操作。5. 計(jì)算 index = key mod Primelevel。6. 如果 nodesindex = NULL ，那么則返回查找失敗。7. 如果nodesindex為一個(gè)子節(jié)點(diǎn)那么，將level加1，然后重復(fù)第1步操 作。用偽碼來(lái)表示如下：

27、Boolean search(HashNode entry, int level, Key key, Value value)if(this.occupied = true)if(this.key = key)value = this.value;return true;int index = key mod Primelevel;if( nodesindex = NULL)return false;level = level + 1;return search(nodesindex, level, key, value);六、刪除操作設(shè)需要?jiǎng)h除的關(guān)鍵字為key。用level表示插入進(jìn)行到第幾

28、層，level從0開(kāi)始。Prime 表為連續(xù)質(zhì)數(shù)表。插入過(guò)程從根節(jié)點(diǎn)開(kāi)始執(zhí)行：1. 如果當(dāng)前節(jié)點(diǎn)沒(méi)有被占據(jù)，則執(zhí)行第 5 步操作。2. 如果當(dāng)前節(jié)點(diǎn)被占據(jù)，則讀取該節(jié)點(diǎn)的關(guān)鍵字，將它和 key進(jìn)行比較。3. 如果相等，貝U設(shè)置該節(jié)點(diǎn)的占用標(biāo)記為false，并返回刪除操作成功。4. 如果不等，則執(zhí)行第 5 步操作。5. 計(jì)算 index = key mod Primelevel。6. 如果 nodesindex = NULL ，那么則返回刪除失敗。7. 如果nodesindex為一個(gè)子節(jié)點(diǎn)那么，將level加1，然后重復(fù)第1步操 作。用偽碼來(lái)表示如下：Boolean remove(HashNod

29、e entry, int level, Key key)if(this.occupied = true)if(this.key = key)this.occupied = false;return true;int in dex = key mod Primelevel;if( nodes in dex = NULL)return false;level = level + 1;return remove( no desi ndex, level, key);七、哈希樹(shù)的特點(diǎn)7.1結(jié)構(gòu)簡(jiǎn)單從哈希樹(shù)的結(jié)構(gòu)來(lái)說(shuō)，非常的簡(jiǎn)單。每層節(jié)點(diǎn)的子節(jié)點(diǎn)個(gè)數(shù)為連續(xù)的質(zhì)數(shù)。子節(jié)點(diǎn)可以隨時(shí)創(chuàng)建。因此哈希樹(shù)的結(jié)構(gòu)是動(dòng)

30、態(tài)的，也不像某些哈希算法那樣需 要長(zhǎng)時(shí)間的初始化過(guò)程。哈希樹(shù)也沒(méi)有必要為不存在的關(guān)鍵字提前分配空間。需要注意的是哈希樹(shù)是一個(gè)單向增加的結(jié)構(gòu)，即隨著所需要存儲(chǔ)的數(shù)據(jù)量增加而增大。即使數(shù)據(jù)量減少到原來(lái)的數(shù)量，但是哈希樹(shù)的總節(jié)點(diǎn)數(shù)不會(huì)減少。這 樣做的目的是為了避免結(jié)構(gòu)的調(diào)整帶來(lái)的額外消耗。7.2操作簡(jiǎn)單從上面所講述的操作過(guò)程來(lái)說(shuō)是相當(dāng)簡(jiǎn)單的。程序上特別容易實(shí)現(xiàn)，比起B(yǎng)-樹(shù)都更容易理解和實(shí)現(xiàn)。作者是通過(guò)實(shí)際中的應(yīng)用，將數(shù)據(jù)和代碼量減到了最低。 這種做法不僅提高了速度，而且編寫(xiě)起來(lái)更容易些。7.3 查找迅速?gòu)乃惴ㄟ^(guò)程我們可以看出， level 最多能增加到 10。因此最多只需要十次取 余和比較操作， 就

31、可以知道這個(gè)對(duì)象是否存在。 這個(gè)在算法邏輯上決定了哈希樹(shù) 的優(yōu)越性。一般的樹(shù)狀結(jié)構(gòu)， 往往隨著層次和層次中節(jié)點(diǎn)數(shù)的增加而導(dǎo)致更多的比較操 作。操作次數(shù)可以說(shuō)無(wú)法準(zhǔn)確確定上限。 而哈希樹(shù)的查找次數(shù)和元素個(gè)數(shù)沒(méi)有關(guān) 系。如果元素的連續(xù)關(guān)鍵字總個(gè)數(shù)在計(jì)算機(jī)的整數(shù)（32bit）所能表達(dá)的最大范圍 內(nèi)，那么比較次數(shù)就最多不會(huì)超過(guò) 10 次，通常低于這個(gè)數(shù)值。7.4 結(jié)構(gòu)不變從刪除算法中可以看出，哈希樹(shù)在刪除的時(shí)候，并不做任何結(jié)構(gòu)調(diào)整。這個(gè) 也是它的一個(gè)非常好的優(yōu)點(diǎn)。 常規(guī)樹(shù)結(jié)構(gòu)在增加元素和刪除元素的時(shí)候都要做一 定的結(jié)構(gòu)調(diào)整， 否則他們將可能退化為鏈表結(jié)構(gòu)， 而導(dǎo)致查找效率的降低。 哈希 樹(shù)采取的是一種

32、“見(jiàn)縫插針”的算法，從來(lái)不用擔(dān)心退化的問(wèn)題。也不必為優(yōu)化 結(jié)構(gòu)而采取額外的操作，因?yàn)榇蟠蠊?jié)約了操作時(shí)間。7.5 非排序性哈希樹(shù)不支持排序，沒(méi)有順序特性。就好比你可以使用 select * where id = 12345的SQL選擇語(yǔ)句，但是不可以使用select * where id > 12345的SQL語(yǔ)句。 如果在此基礎(chǔ)上不做任何改進(jìn)的話并試圖通過(guò)遍歷來(lái)實(shí)現(xiàn)排序， 那么操作效率將 遠(yuǎn)遠(yuǎn)低于其他類型的數(shù)據(jù)結(jié)構(gòu)。八、沖突處理從定理 1 中我們可以知道，這個(gè)定理只保證了 M 10個(gè)連續(xù)的整數(shù)是可以被“分 辨”的。如果在使用中，有兩個(gè)整數(shù)之間的距離超過(guò) M 10 ，那么就可能會(huì)出現(xiàn)沖 突

33、。解決沖突的辦法有兩種：一種是主動(dòng)解決這種沖突，另外一種是被動(dòng)的。所謂主動(dòng)解決沖突，就是我們可以選擇更大的質(zhì)數(shù)序列來(lái)組織哈希樹(shù)，只到 這些質(zhì)數(shù)的乘積可以覆蓋所有可能的范圍?；蛘哌x擇更多的質(zhì)數(shù)，只到他們的乘積可以覆蓋所有可能的范圍。另外一個(gè)方面如果這種沖突發(fā)生的概率很低，那么可以讓哈希樹(shù)被動(dòng)適應(yīng)這 種變化。沖突對(duì)哈希樹(shù)來(lái)說(shuō)并非不可以被接納。無(wú)非是增加了哈希樹(shù)的層數(shù)，或者說(shuō)增加了所需要比較和取余的次數(shù)。但是為了容納過(guò)多的沖突將會(huì)導(dǎo)致哈希樹(shù) 的嚴(yán)重退化，最終將退化一個(gè)鏈表結(jié)構(gòu)。這些能產(chǎn)生沖突的數(shù)值之間的距離 Dis tan ce必須滿足：Dis tan ce = S M 10，其中 S N因此任何兩

34、個(gè)重復(fù)的數(shù)之間的距離必須為Mi。，而非簡(jiǎn)單成倍關(guān)系。即k與n k n N,且n k =M 10不會(huì)導(dǎo)致哈希樹(shù)的退化。九、字符串關(guān)鍵字的處理字符串是由字符組成，字符都具有某種具體的編碼方式。由這種編碼方式最 終都可以轉(zhuǎn)換成字節(jié)數(shù)組的形式。因此我們可以簡(jiǎn)單的將字符串看作是 256進(jìn)制 的數(shù)。例如：“abc”可以轉(zhuǎn)換成字節(jié)數(shù)組0x616263,可以看作是十進(jìn)制的6382179。那么一個(gè)20個(gè)字符的字符串將是一個(gè)很大的數(shù)。我們不能簡(jiǎn)單地使用計(jì)算 機(jī)的整數(shù)來(lái)做除法，而是使用程序模擬人工的除法方式來(lái)做除法并獲得余數(shù)。一 個(gè)簡(jiǎn)單的例子如下：int hash(Stri ng stri ng, int prime)byte bytes = stri ng.getBytes();int residual = 0;for(int i = bytes.length;i > 0;i -)residual = residual * 256 + bytesi Tresidual = residual mod primereturn residual;雖然多做了幾次基本的