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

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

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

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

4、總的來說，這些查找算法的效率都將隨著數(shù)據(jù)記錄數(shù)的增長而下降。僅僅是 有的比較快(時間復(fù)雜度為0(n),有的比較慢(時間復(fù)雜度是O(log n)而已。 這些查找算法的平均查找長度是在一種比較理想的情況下獲得的。在實際應(yīng)用當中，對數(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ù)雜程度以及操作的 額外時間。二、哈希表理想的情況是希望不經(jīng)過任何比較，一次存取便能得到所查的記錄，那就必須在記的存儲位置和它的關(guān)鍵字之間建立一個確定的對應(yīng)關(guān)系f，使每個關(guān)鍵字和結(jié)構(gòu)中一

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

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

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

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

9、字裝載內(nèi)存的次數(shù)和時間。 一般來說，裝載的時間是由關(guān)鍵字的大小和硬件來決定的；在相同類型關(guān)鍵字和相同硬件條件下，實際的整體操作時間就主要取決于裝載的次數(shù)。他們之間是一個成正比的關(guān)系。2.2余數(shù)分辨定理在這里，我們對更為普遍的余數(shù)分辨方式做一個討論。定理 2 :選取任意n個互不相同的自然數(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 )，那么對于任意的 i 1,n 丨，(k1 mod Ii ) =

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

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

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

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

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

15、CM。一方 面，這些整數(shù)的積得到了減少，分辨效率將有所提高；另外一方面，這些整數(shù)的 和得到了減少，簡化度也因此而提到。通過反復(fù)簡化操作這個數(shù)列的分辨效率總 可以達到100%1:分辨效率 <100%的分辨數(shù)列總可以簡化，而且可以簡化成分辨效率 =100%的分辨數(shù)列。6.綜合評價指標我們定義分辨算法綜合評價指標-:，J 特征空間緯數(shù)這個標準意味著：分辨范圍越大，簡化度越高，那么這個算法的綜合性能就越好。例如：在余數(shù)分辨法中，如果我們選擇數(shù)列100,200,3001作為分辨數(shù)列, 那么采取這個數(shù)列的余數(shù)分辨算法各項指標如下: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ù)列，那么采取這個數(shù)列的余數(shù)分辨算法各項指標如下:D = LCM =23104.32 10,23100.035712 3 5 7 11 八D汀16.5顯然后者在綜合評價方面要優(yōu)于前者。2.4線性分辨算法線性分辨算法是利用線性函數(shù)f (x)二ax b作為分辨算法的分辨算法，或者 稱為余數(shù)分辨算法。這種算法簡單易行。上面所有的討論都是基于線性分辨算法 的。2.5非線性分辨算法非線性分辨算法是指在特征數(shù)的獲取過程中采用非線性函數(shù)的方法。 這

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

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

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

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

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

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

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

24、到第幾層，level從0開始。Prime表為連續(xù)質(zhì)數(shù)表。插入過程從根節(jié)點開始執(zhí)行：1. 如果當前節(jié)點沒有被占據(jù)(occupied = false)，則設(shè)置該節(jié)點的key和 value，并設(shè)置占據(jù)標記為true，然后返回。2. 如果當前節(jié)點被占據(jù)( occupied = true)，則計算 index = key mod Primelevel。3. 如果nodesindex = NULL，那么創(chuàng)建子節(jié)點，將level加1,并重復(fù)第1 步操作。4. 如果nodesindex為一個子節(jié)點那么，將level加1，然后重復(fù)第1步操 作。用偽碼來表示如下：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表示插入進行到第幾層，

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

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è)需要刪除的關(guān)鍵字為key。用level表示插入進行到第幾

28、層，level從0開始。Prime 表為連續(xù)質(zhì)數(shù)表。插入過程從根節(jié)點開始執(zhí)行：1. 如果當前節(jié)點沒有被占據(jù)，則執(zhí)行第 5 步操作。2. 如果當前節(jié)點被占據(jù)，則讀取該節(jié)點的關(guān)鍵字，將它和 key進行比較。3. 如果相等，貝U設(shè)置該節(jié)點的占用標記為false，并返回刪除操作成功。4. 如果不等，則執(zhí)行第 5 步操作。5. 計算 index = key mod Primelevel。6. 如果 nodesindex = NULL ，那么則返回刪除失敗。7. 如果nodesindex為一個子節(jié)點那么，將level加1，然后重復(fù)第1步操 作。用偽碼來表示如下：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);七、哈希樹的特點7.1結(jié)構(gòu)簡單從哈希樹的結(jié)構(gòu)來說，非常的簡單。每層節(jié)點的子節(jié)點個數(shù)為連續(xù)的質(zhì)數(shù)。子節(jié)點可以隨時創(chuàng)建。因此哈希樹的結(jié)構(gòu)是動

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

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

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

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

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