試談哈希樹(hashtree)數(shù)據(jù)結(jié)構(gòu)分析(編輯修改稿)
2025-07-24 12:32 本頁面
【文章內(nèi)容簡介】 分段特征提取法就是將被分辨的數(shù)分成若干部分，每個(gè)部分有若干狀態(tài)。假設(shè)某個(gè)數(shù)可以被分成段，每段所有可能的狀態(tài)個(gè)數(shù)為（其中）。那么我們可以得出以下結(jié)論： 任何一個(gè)段的狀態(tài)至少是有兩個(gè)狀態(tài)，否則這種分段是毫無意義的?；蛘哒f這段是沒有任何特征的，對(duì)分辨算法來說是一種時(shí)間和空間的浪費(fèi)。 這種算法的分辨能力是： 其沖突概率： 這種算法的分辨效率，簡化度為： 總體評(píng)價(jià)： 這種算法可以做到在所有分辨算法中的簡化度最高，綜合評(píng)價(jià)也可以很高。但這種分辨算法的綜合評(píng)價(jià)并不總是最高的。 例如：當(dāng)我們?cè)诜直?2位整數(shù)的時(shí)候，使用這種分段特征分辨法，那么這種分辨方法的各項(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ì)于超長的字符串仍然不是十分容易處理。三、哈希樹的組織結(jié)構(gòu)使用不同的分辨算法都可以組織成哈希樹。一般來說：每層哈希樹的節(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ù)來到第二層子節(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è)數(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ù)組我們用nodes[i]來表示節(jié)點(diǎn)的第i個(gè)子節(jié)點(diǎn)的地址。第10個(gè)質(zhì)數(shù)為29，余數(shù)不可能大于32。這個(gè)數(shù)組的固定長度為可以設(shè)置為32，即。當(dāng)?shù)趇個(gè)子節(jié)點(diǎn)不存在時(shí)，nodes[i]=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。用level表示插入操作進(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 Prime[level]。3. 如果nodes[index] = NULL，那么創(chuàng)建子節(jié)點(diǎn)，將level加1，并重復(fù)第1步操作。4. 如果nodes[index]為一個(gè)子節(jié)點(diǎn)那么，將level加1，然后重復(fù)第1步操作。用偽碼來表示如下：void insert (HashNode entry, int level, Key key, Value value){ if ( = false) { = key。 = value。 = true。 return。 } int index = key mod Prime[level]。 if( nodes[index] = NULL) { nodes[index] = new
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1