試談哈希樹(HashTree)數(shù)據(jù)結(jié)構(gòu)分析

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

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

3、rch Length）。下面我們簡(jiǎn)單討論一下在含有個(gè)數(shù)據(jù)記錄的結(jié)構(gòu)中，各種查找算法的平均查找長(zhǎng)度。在等概率的情況下，順序查找的平均查找長(zhǎng)度為：對(duì)于折半查找（表要求是順序表），在比較大（）的時(shí)候，可有以下近似結(jié)果：在隨機(jī)情況下（二叉樹查找可能退化為順序查找），對(duì)于二叉樹，其平均查找長(zhǎng)度為： 在平衡二叉樹上進(jìn)行查找，其平均查找長(zhǎng)度為：，其中對(duì)于一顆階的樹，從根節(jié)點(diǎn)到關(guān)鍵字所在節(jié)點(diǎn)的路徑上涉及的節(jié)點(diǎn)數(shù)可以說是平均查找長(zhǎng)度的上限：總的來說，這些查找算法的效率都將隨著數(shù)據(jù)記錄數(shù)的增長(zhǎng)而下降。僅僅是有的比較快（時(shí)間復(fù)雜度為），有的比較慢（時(shí)間復(fù)雜度是）而已。這些查找算法的平均查找長(zhǎng)度是在一種比較理想的情況

4、下獲得的。在實(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)過任何比較，一次存取便能得到所查的記錄，那就必須在記的存儲(chǔ)位置和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系，使每個(gè)關(guān)鍵字和結(jié)構(gòu)中一個(gè)唯一的存儲(chǔ)位置相對(duì)應(yīng)。因而在查找時(shí)，只要根據(jù)這個(gè)對(duì)應(yīng)關(guān)系找到給定值的像。若結(jié)構(gòu)中存在關(guān)鍵字和相等的記錄，則必定在的存儲(chǔ)位置上，由此，不需要進(jìn)行比較便可直接取得所查記錄。在此，我們稱這個(gè)對(duì)應(yīng)關(guān)系為哈希（H

5、ash）函數(shù)，按這個(gè)思想建立的表為哈希表。在哈希表中對(duì)于不同的關(guān)鍵字可能得到同一哈希地址，即，而。這種現(xiàn)象稱做沖突（Collision）。在一般情況下，沖突只能盡可能地減少，而不能完全避免。因?yàn)楣：瘮?shù)是從關(guān)鍵字集合到地址集合的映像。通常關(guān)鍵字的集合比較大，它的元素包括所有可能的關(guān)鍵字，而地址集合的元素僅為哈希表中的地址值。假設(shè)標(biāo)識(shí)符可定義為以字符為首的8位字符，則關(guān)鍵字（標(biāo)識(shí)符）的集合大小為，而在一個(gè)源程序中出現(xiàn)的數(shù)據(jù)對(duì)象是有限的，設(shè)有10000個(gè)元素。地址集合中的元素為0到9999。因此在一般情況下，哈希函數(shù)是一個(gè)壓縮映像函數(shù)，這就不可避免的要產(chǎn)生沖突。二、哈希樹的理論基礎(chǔ)2.1質(zhì)數(shù)分辨定

6、理定理1：選取任意個(gè)互不相同的質(zhì)數(shù)：（），定義：設(shè)（），那么對(duì)于任意的，（）（）不可能總成立。證明：假設(shè)定理1的結(jié)論不正確，那么對(duì)于任意的，（）（）將總是成立。這個(gè)可以表達(dá)為：設(shè)：顯然，是一個(gè)合數(shù)，而且包含質(zhì)因素。根據(jù)質(zhì)數(shù)的定義和質(zhì)因素分解定理，可以表達(dá)為：而另外一方面，根據(jù)，可以得出：很明顯，這兩個(gè)結(jié)論是相互矛盾的。因此原定理1正確。這個(gè)定理可以簡(jiǎn)單的表述為：個(gè)不同的質(zhì)數(shù)可以“分辨”的連續(xù)整數(shù)的個(gè)數(shù)和他們的乘積相等?！胺直妗本褪侵高@些連續(xù)的整數(shù)不可能有完全相同的余數(shù)序列。這個(gè)為哈希樹的分辨方式奠定了理論基礎(chǔ)。顯然，這個(gè)定理的一個(gè)特殊情況就是為從2起的連續(xù)質(zhì)數(shù)。我們可以記為前個(gè)連續(xù)質(zhì)數(shù)的乘積。

7、連續(xù)10個(gè)質(zhì)數(shù)就可以分辨大約個(gè)數(shù)，已經(jīng)超過計(jì)算機(jī)中常用整數(shù)（32bit）的表達(dá)范圍。連續(xù)100個(gè)質(zhì)數(shù)就可以分辨大約。而按照目前的CPU水平，100次取余的整數(shù)除法操作幾乎不算什么難事。在實(shí)際應(yīng)用中，整體的操作速度往往取決于節(jié)點(diǎn)將關(guān)鍵字裝載內(nèi)存的次數(shù)和時(shí)間。一般來說，裝載的時(shí)間是由關(guān)鍵字的大小和硬件來決定的；在相同類型關(guān)鍵字和相同硬件條件下，實(shí)際的整體操作時(shí)間就主要取決于裝載的次數(shù)。他們之間是一個(gè)成正比的關(guān)系。2.2余數(shù)分辨定理在這里，我們對(duì)更為普遍的余數(shù)分辨方式做一個(gè)討論。定理2：選取任意個(gè)互不相同的自然數(shù)：（），定義LCM（Lease Common Multiple）為的最小公倍數(shù)。設(shè)（），

8、那么對(duì)于任意的，（）（）不可能總成立。證明：假設(shè)定理2的結(jié)論不正確，那么對(duì)于任意的，（）（）將總是成立。這個(gè)可以表達(dá)為：設(shè)：顯然，是一個(gè)合數(shù)，而且包含因素。根據(jù)最小公倍數(shù)的定義，可以表達(dá)為：而另外一方面，根據(jù)，可以得出：很明顯，這兩個(gè)結(jié)論是相互矛盾的。因此原定理2正確。這個(gè)定理2可以簡(jiǎn)單的表述為：個(gè)不同的數(shù)可以“分辨”的連續(xù)整數(shù)的個(gè)數(shù)不超過他們的最小公倍數(shù)。超過這個(gè)范圍就意味著沖突的概率會(huì)增加。定理1是定理2的一個(gè)特例。2.3分辨算法評(píng)價(jià)標(biāo)準(zhǔn)1. 狀態(tài)和特征分辨也即分辨不同的狀態(tài)。分辨一般是先定義一組不同的狀態(tài)，然后將這些狀態(tài)記錄下來形成特征。由這些特征所形成的空間是特征空間。特征空間的緯數(shù)是

9、特征數(shù)列的長(zhǎng)度。2. 分辨能力分辨能力D，也稱分辨范圍，就是指分辨算法可以分辨的最大連續(xù)空間大小。在這個(gè)范圍內(nèi)，分辨算法可以唯一確定被分辨數(shù)。即任何兩個(gè)在分辨范圍內(nèi)的數(shù)，不可能具有完全相同的特征數(shù)。這些特征數(shù)會(huì)以某種形式被記錄下來，或者以數(shù)據(jù)結(jié)構(gòu)的形式體現(xiàn)出來。對(duì)于兩個(gè)具有相同分辨能力的分辨算法，我們認(rèn)為他們是等價(jià)算法。當(dāng)?shù)臅r(shí)候，分辨算法的分辨能力最強(qiáng)。但是同時(shí)分辨算法所使用的特征空間也將是無窮大，我們不可能有足夠的空間來存放這些相關(guān)特征記錄。3. 沖突概率當(dāng)被分辨數(shù)之間的距離超出分辨范圍的時(shí)候，就有可能發(fā)生沖突，這種沖突的概率被定義為沖突概率：當(dāng)被分辨的數(shù)是隨機(jī)分布在整個(gè)數(shù)軸的時(shí)候，兩個(gè)數(shù)之

10、間的距離可能會(huì)超過分辨范圍。這個(gè)時(shí)候分辨算法不一定會(huì)完全失效。沖突概率就體現(xiàn)為衡量某種分辨算法在處理散列時(shí)候的特性。沖突概率越小，那么處理散列的能力就越強(qiáng)，對(duì)非連續(xù)空間的特征分辨能力就越高；反之，那么處理散列的能力就越弱，對(duì)非連續(xù)空間的特征分辨能力就越低。對(duì)于兩個(gè)具有相同沖突概率的分辨算法，我們也認(rèn)為他們是等價(jià)算法。4. 分辨效率根據(jù)分辨算法的特點(diǎn)，我們可以定義分辨效率：在由定理1和定理2可以得知：當(dāng)用于余數(shù)分辨的整數(shù)數(shù)列是某一個(gè)確定整數(shù)，或者互不相等的質(zhì)數(shù)數(shù)列的時(shí)候，或者是互相沒有公約數(shù)的整數(shù)數(shù)列，分辨效率；其他情況下，分辨效率都小于100%。5. 簡(jiǎn)化度在分辨算法中，我們定義數(shù)列的簡(jiǎn)化度為

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

12、。一方面，這些整數(shù)的積得到了減少，分辨效率將有所提高；另外一方面，這些整數(shù)的和得到了減少，簡(jiǎn)化度也因此而提到。通過反復(fù)簡(jiǎn)化操作這個(gè)數(shù)列的分辨效率總可以達(dá)到100%1：分辨效率的分辨數(shù)列總可以簡(jiǎn)化，而且可以簡(jiǎn)化成分辨效率的分辨數(shù)列。6. 綜合評(píng)價(jià)指標(biāo)我們定義分辨算法綜合評(píng)價(jià)指標(biāo)：這個(gè)標(biāo)準(zhǔn)意味著：分辨范圍越大，簡(jiǎn)化度越高，那么這個(gè)算法的綜合性能就越好。例如：在余數(shù)分辨法中，如果我們選擇數(shù)列作為分辨數(shù)列，那么采取這個(gè)數(shù)列的余數(shù)分辨算法各項(xiàng)指標(biāo)如下：如果我們選擇數(shù)列作為分辨數(shù)列，那么采取這個(gè)數(shù)列的余數(shù)分辨算法各項(xiàng)指標(biāo)如下：顯然后者在綜合評(píng)價(jià)方面要優(yōu)于前者。2.4線性分辨算法線性分辨算法是利用線性函數(shù)作

13、為分辨算法的分辨算法，或者稱為余數(shù)分辨算法。這種算法簡(jiǎn)單易行。上面所有的討論都是基于線性分辨算法的。2.5非線性分辨算法非線性分辨算法是指在特征數(shù)的獲取過程中采用非線性函數(shù)的方法。這也就是說，可以完全使用非線性函數(shù)，或者非線性函數(shù)和線性函數(shù)混合使用。但是只要是使用了非線性函數(shù)，那么就被稱作非線性分辨。在這些算法里面，可以分成兩類：非線性函數(shù)特征法和分段特征提取法。1. 非線性函數(shù)特征法利用單值非線性函數(shù)（例如：）來提取特征的方法就稱為非線性特征法。很明顯這些函數(shù)的單值對(duì)應(yīng)性，并沒有改變分辨范圍的大小。這些函數(shù)僅僅是將特征空間做了一個(gè)變形處理。這種變形可能是平移、縮放等等。但是分辨能力沒有擴(kuò)大，

14、沖突概率也并沒有得到減少，簡(jiǎn)化度也沒有發(fā)生變化，分辨算法的整體評(píng)價(jià)標(biāo)準(zhǔn)也沒有改變。2. 分段特征提取法分段特征提取法就是將被分辨的數(shù)分成若干部分，每個(gè)部分有若干狀態(tài)。假設(shè)某個(gè)數(shù)可以被分成段，每段所有可能的狀態(tài)個(gè)數(shù)為（其中）。那么我們可以得出以下結(jié)論：任何一個(gè)段的狀態(tài)至少是有兩個(gè)狀態(tài)，否則這種分段是毫無意義的。或者說這段是沒有任何特征的，對(duì)分辨算法來說是一種時(shí)間和空間的浪費(fèi)。這種算法的分辨能力是：其沖突概率：這種算法的分辨效率，簡(jiǎn)化度為：總體評(píng)價(jià)：這種算法可以做到在所有分辨算法中的簡(jiǎn)化度最高，綜合評(píng)價(jià)也可以很高。但這種分辨算法的綜合評(píng)價(jià)并不總是最高的。例如：當(dāng)我們?cè)诜直?2位整數(shù)的時(shí)候，使用這種

15、分段特征分辨法，那么這種分辨方法的各項(xiàng)指標(biāo)如下：如果在余數(shù)分辨算法中，我們選擇從2到29的連續(xù)10個(gè)質(zhì)數(shù)作為分辨數(shù)列，那么這個(gè)分辨方法的各項(xiàng)指標(biāo)如下：在分辨以2進(jìn)制為基礎(chǔ)的連續(xù)整數(shù)的時(shí)候，這種算法有著明顯的優(yōu)勢(shì)。但是在分辨散列的時(shí)候，例如：以字符為基礎(chǔ)的字符串的時(shí)候，其特征緯數(shù)和者特征數(shù)將會(huì)迅速增加。過多的特征緯數(shù)和特征數(shù)意味者，對(duì)于特征空間的浪費(fèi)、更多的初始化時(shí)間以及更多比較次數(shù)和比較時(shí)間。為了仍然能夠使用這種分辨方法，普遍采用對(duì)字符串壓縮編碼轉(zhuǎn)換成整數(shù)后，再使用該分辨算法。但是即使是采取轉(zhuǎn)換手段，對(duì)于超長(zhǎng)的字符串仍然不是十分容易處理。三、哈希樹的組織結(jié)構(gòu)使用不同的分辨算法都可以組織成哈希樹

16、。一般來說：每層哈希樹的節(jié)點(diǎn)下的子節(jié)點(diǎn)數(shù)是和分辨數(shù)列一致的。哈希樹的最大深度和特征空間的緯數(shù)是一致的。為了研究的方便，我們選擇質(zhì)數(shù)分辨算法來建立一顆哈希樹。選擇從2開始的連續(xù)質(zhì)數(shù)來建立一個(gè)十層的哈希樹（因?yàn)橐呀?jīng)超過了計(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ù)。到了第十層，每個(gè)節(jié)點(diǎn)下有29個(gè)節(jié)點(diǎn)。圖1 哈希樹的組織結(jié)構(gòu)同一節(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ù)來到第

17、二層子節(jié)點(diǎn)，那么它要做取余操作，然后再?zèng)Q定從哪個(gè)子節(jié)點(diǎn)向下搜尋。如果這個(gè)數(shù)是12那么它需要從第一個(gè)子節(jié)點(diǎn)向下搜索；如果這個(gè)數(shù)是7那么它需要從第二個(gè)子節(jié)點(diǎn)向下搜索；如果這個(gè)數(shù)是32那么它需要從第三個(gè)子節(jié)點(diǎn)向下搜索。如果所有的節(jié)點(diǎn)都存在，并容納數(shù)據(jù)的話，那么可以容納的數(shù)據(jù)項(xiàng)目總數(shù)將比要大一些：如果在建立當(dāng)初就建立所有的節(jié)點(diǎn)，那么所消耗的計(jì)算時(shí)間和磁盤空間是巨大的。在實(shí)際使用當(dāng)中，只需要初始化根節(jié)點(diǎn)就可以開始工作。子節(jié)點(diǎn)的建立是在有更多的數(shù)據(jù)進(jìn)入到哈希樹中的時(shí)候建立的。因此可以說哈希樹和其他樹一樣是一個(gè)動(dòng)態(tài)結(jié)構(gòu)。這些節(jié)點(diǎn)有以下基本元素：1. 節(jié)點(diǎn)的關(guān)鍵字我們用key來表示節(jié)點(diǎn)的關(guān)鍵字。在整個(gè)樹中這個(gè)

18、數(shù)值是唯一的。當(dāng)節(jié)點(diǎn)占據(jù)標(biāo)志位（occupied）為真的時(shí)候，關(guān)鍵字才認(rèn)為是有效的，否則是無效的。2. 節(jié)點(diǎn)是否被占據(jù)我們用occupied來表示節(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來表示節(jié)點(diǎn)的第i個(gè)子節(jié)點(diǎn)的地址。第10個(gè)質(zhì)數(shù)為29，余數(shù)不可能大于32。這個(gè)數(shù)組的固定長(zhǎng)度為可以設(shè)置為32，即。當(dāng)?shù)趇個(gè)子節(jié)點(diǎn)不存在時(shí)，nodesi=NULL，否則為子節(jié)點(diǎn)的地址。4. 節(jié)點(diǎn)的數(shù)據(jù)對(duì)象我們用value來表示節(jié)點(diǎn)的數(shù)據(jù)對(duì)象。四、插入規(guī)則設(shè)需要插入的關(guān)鍵字和數(shù)據(jù)分別為key和value。用l

19、evel表示插入操作進(jìn)行到第幾層，level從0開始。Prime表為連續(xù)質(zhì)數(shù)表。插入過程從根節(jié)點(diǎn)開始執(zhí)行：1. 如果當(dāng)前節(jié)點(diǎn)沒有被占據(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步操作。用偽碼來表示如下：void insert (HashN

20、ode entry, 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)行

21、到第幾層，level從0開始。Prime表為連續(xù)質(zhì)數(shù)表。插入過程從根節(jié)點(diǎn)開始執(zhí)行：1. 如果當(dāng)前節(jié)點(diǎn)沒有被占據(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步操作。用偽碼來表示如下：Boo

22、lean 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)行到第幾層，l

23、evel從0開始。Prime表為連續(xù)質(zhì)數(shù)表。插入過程從根節(jié)點(diǎn)開始執(zhí)行：1. 如果當(dāng)前節(jié)點(diǎn)沒有被占據(jù)，則執(zhí)行第5步操作。2. 如果當(dāng)前節(jié)點(diǎn)被占據(jù)，則讀取該節(jié)點(diǎn)的關(guān)鍵字，將它和key進(jìn)行比較。3. 如果相等，則設(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步操作。用偽碼來表示如下：Boolean remove(HashNode entry, int l

24、evel, Key key)if(this.occupied = true)if(this.key = key)this.occupied = false;return true;int index = key mod Primelevel;if( nodesindex = NULL)return false;level = level + 1;return remove(nodesindex, level, key);七、哈希樹的特點(diǎn)7.1結(jié)構(gòu)簡(jiǎn)單從哈希樹的結(jié)構(gòu)來說，非常的簡(jiǎn)單。每層節(jié)點(diǎn)的子節(jié)點(diǎn)個(gè)數(shù)為連續(xù)的質(zhì)數(shù)。子節(jié)點(diǎn)可以隨時(shí)創(chuàng)建。因此哈希樹的結(jié)構(gòu)是動(dòng)態(tài)的，也不像某些哈希算法那樣需要長(zhǎng)時(shí)間的

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

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

27、時(shí)間。7.5非排序性哈希樹不支持排序，沒有順序特性。就好比你可以使用select * where id = 12345的SQL選擇語(yǔ)句，但是不可以使用select * where id > 12345的SQL語(yǔ)句。如果在此基礎(chǔ)上不做任何改進(jìn)的話并試圖通過遍歷來實(shí)現(xiàn)排序，那么操作效率將遠(yuǎn)遠(yuǎn)低于其他類型的數(shù)據(jù)結(jié)構(gòu)。八、沖突處理從定理1中我們可以知道，這個(gè)定理只保證了個(gè)連續(xù)的整數(shù)是可以被“分辨”的。如果在使用中，有兩個(gè)整數(shù)之間的距離超過，那么就可能會(huì)出現(xiàn)沖突。解決沖突的辦法有兩種：一種是主動(dòng)解決這種沖突，另外一種是被動(dòng)的。所謂主動(dòng)解決沖突，就是我們可以選擇更大的質(zhì)數(shù)序列來組織哈希樹，只到這些質(zhì)

28、數(shù)的乘積可以覆蓋所有可能的范圍?；蛘哌x擇更多的質(zhì)數(shù)，只到他們的乘積可以覆蓋所有可能的范圍。另外一個(gè)方面如果這種沖突發(fā)生的概率很低，那么可以讓哈希樹被動(dòng)適應(yīng)這種變化。沖突對(duì)哈希樹來說并非不可以被接納。無非是增加了哈希樹的層數(shù)，或者說增加了所需要比較和取余的次數(shù)。但是為了容納過多的沖突將會(huì)導(dǎo)致哈希樹的嚴(yán)重退化，最終將退化一個(gè)鏈表結(jié)構(gòu)。這些能產(chǎn)生沖突的數(shù)值之間的距離必須滿足：因此任何兩個(gè)重復(fù)的數(shù)之間的距離必須為，而非簡(jiǎn)單成倍關(guān)系。即與不會(huì)導(dǎo)致哈希樹的退化。九、字符串關(guān)鍵字的處理字符串是由字符組成，字符都具有某種具體的編碼方式。由這種編碼方式最終都可以轉(zhuǎn)換成字節(jié)數(shù)組的形式。因此我們可以簡(jiǎn)單的將字符串看

29、作是256進(jìn)制的數(shù)。例如：“abc”可以轉(zhuǎn)換成字節(jié)數(shù)組0x616263，可以看作是十進(jìn)制的6382179。那么一個(gè)20個(gè)字符的字符串將是一個(gè)很大的數(shù)。我們不能簡(jiǎn)單地使用計(jì)算機(jī)的整數(shù)來做除法，而是使用程序模擬人工的除法方式來做除法并獲得余數(shù)。一個(gè)簡(jiǎn)單的例子如下：int hash(String string, int prime)byte bytes = string.getBytes();int residual = 0;for(int i = bytes.length;i > 0;i -)residual = residual * 256 + bytesi 1residual = residual mod primereturn residual;雖然多做了幾次基本的加、減、乘、除運(yùn)算。但是因?yàn)槎际钦麛?shù)計(jì)算，對(duì)于目前的CPU水平來說，幾乎不算什么難事。而且還可以通過移位運(yùn)算代替乘法運(yùn)算，這樣能更快些。而且除法的除數(shù)和被除數(shù)都不會(huì)太大，計(jì)算起來也不會(huì)有太多的CP