資源描述:
《試談哈希樹HashTree)數(shù)據(jù)結(jié)構(gòu)解析.doc》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、哈希樹(HashTree)羅堃吳朝宏從2000年開始,作者開始研究基于TCP/IP的短信息傳輸技術(shù)。這種技術(shù)目前在國(guó)際上的標(biāo)準(zhǔn)被成為SMPP(ShortMessagePeertoPeerProtocol)。SMPP協(xié)議是一種支持異步傳輸模式(AsynchronizedTransmissionMode)的信息傳輸方式。這種異步方式主要體現(xiàn)在兩個(gè)地方:傳遞信息和等待確認(rèn)。在為電信運(yùn)營(yíng)商編寫軟件的過(guò)程當(dāng)中,解決大容量(百萬(wàn)用戶以上)要求下的快速查找與匹配成為實(shí)現(xiàn)這個(gè)系統(tǒng)的核心任務(wù)。作者在反復(fù)設(shè)計(jì)整個(gè)過(guò)程中曾經(jīng)嘗試過(guò)很多種方式和算法,但
2、都未能取得滿意的效果。最終不得不自己開始設(shè)計(jì)針對(duì)這種系統(tǒng)的特殊存儲(chǔ)模式。并在這個(gè)過(guò)程中,找到了一種比較理想的數(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é)果為“”、“”與“”三種可能。查找的效率依賴于查找過(guò)程中所進(jìn)行的比較次數(shù)。為確定記
3、錄在查找表中的位置,需和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的期望值成為查找算法在查找成功時(shí)的平均查找長(zhǎng)度(AverageSearchLength)。下面我們簡(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ù)可以說(shuō)是平均查找長(zhǎng)度的
4、上限:總的來(lái)說(shuō),這些查找算法的效率都將隨著數(shù)據(jù)記錄數(shù)的增長(zhǎng)而下降。僅僅是有的比較快(時(shí)間復(fù)雜度為),有的比較慢(時(shí)間復(fù)雜度是)而已。這些查找算法的平均查找長(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)鍵字之間建立
5、一個(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)系為哈希(Hash)函數(shù),按這個(gè)思想建立的表為哈希表。在哈希表中對(duì)于不同的關(guān)鍵字可能得到同一哈希地址,即,而。這種現(xiàn)象稱做沖突(Collision)。在一般情況下,沖突只能盡可能地減少,而不能完全避免。因?yàn)楣:瘮?shù)是從關(guān)鍵字集合到地址集合的映像。通常關(guān)鍵字的集合比較大,它的元素包括所有可能的關(guān)鍵字,
6、而地址集合的元素僅為哈希表中的地址值。假設(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ù)分辨定理定理1:選取任意個(gè)互不相同的質(zhì)數(shù):(),定義:設(shè)(),那么對(duì)于任意的,()=()不可能總成立。證明:假設(shè)定理1的結(jié)論不正確,那么對(duì)于任意的,()=()將總是成立。這個(gè)可以表達(dá)為:設(shè):顯然,是一個(gè)合數(shù),而且包含質(zhì)因素。根據(jù)
7、質(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ù)的乘積。連續(xù)10個(gè)質(zhì)數(shù)就可以分辨大約個(gè)數(shù),已經(jīng)超過(guò)計(jì)算機(jī)中常用整數(shù)(32bit)的表達(dá)范圍。連續(xù)100個(gè)質(zhì)數(shù)就可以分辨大約。而按照目前的CPU水平,100次取余
8、的整數(shù)除法操作幾乎不算什么難事。在實(shí)際應(yīng)用中,整體的操作速度往往取決于節(jié)點(diǎn)將關(guān)鍵字裝載內(nèi)存的次數(shù)和時(shí)間。一般來(lái)說(shuō),裝載的時(shí)間是由關(guān)鍵字的大小和硬件來(lái)決定的;在相同類型關(guān)鍵字和相同硬件條件下,實(shí)際的整體操作時(shí)間就主要取決于裝載的次數(shù)。他們之間是一個(gè)成正比的關(guān)系。2