Hash樹(散列樹)和Trie樹(字典樹、前綴樹)-創(chuàng)新互聯(lián)

1.Hash樹

網(wǎng)站建設(shè)哪家好，找創(chuàng)新互聯(lián)！專注于網(wǎng)頁設(shè)計(jì)、網(wǎng)站建設(shè)、微信開發(fā)、微信平臺(tái)小程序開發(fā)、集團(tuán)企業(yè)網(wǎng)站建設(shè)等服務(wù)項(xiàng)目。為回饋新老客戶創(chuàng)新互聯(lián)還提供了澤庫免費(fèi)建站歡迎大家使用！

理想的情況是希望不經(jīng)過任何比較，一次存取便能得到所查的記錄， 那就必須在記的存儲(chǔ)位置和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系f，使每個(gè)關(guān)鍵字和一個(gè)唯一的存儲(chǔ)位置相對(duì)應(yīng)。因而在查找時(shí)，只要根據(jù)這個(gè)對(duì)應(yīng)關(guān)系f找到 給定值K的像f(K)。由此，不需要進(jìn)行比較便可直接取得所查記錄。在此，我們稱這個(gè)對(duì)應(yīng)關(guān)系為哈希（Hash）函數(shù)，按這個(gè)思想建立的表為哈希表。

在哈希表中對(duì)于不同的關(guān)鍵字可能得到同一哈希地址，這種現(xiàn)象稱做沖突。在一般情況下，沖突只能盡可能地減少，而不能完全避免。因?yàn)楣：瘮?shù)是從關(guān)鍵字集合 到地址集合的映像。通常關(guān)鍵字的集合比較大，它的元素包括所有可能的關(guān)鍵字，而地址集合的元素僅為哈希表中的地址值。在一般情況下，哈希函數(shù)是一個(gè)壓縮映像函數(shù)，這就不可避免的要產(chǎn)生沖突。

哈希樹的理論基礎(chǔ)

【質(zhì)數(shù)分辨定理】
簡(jiǎn)單地說就是：n個(gè)不同的質(zhì)數(shù)可以“分辨”的連續(xù)整數(shù)的個(gè)數(shù)和他們的乘積相等?！胺直妗本褪侵高@些連續(xù)的整數(shù)不可能有完全相同的余數(shù)序列。

例如：
從2起的連續(xù)質(zhì)數(shù)，連續(xù)10個(gè)質(zhì)數(shù)就可以分辨大約M(10) =2*3*5*7*11*13*17*19*23*29= 6464693230 個(gè)數(shù)，已經(jīng)超過計(jì)算機(jī)中常用整數(shù)（32bit）的表達(dá)范圍。連續(xù)100個(gè)質(zhì)數(shù)就可以分辨大約M(100) = 4.711930 乘以10的219次方。

插入

我們選擇質(zhì)數(shù)分辨算法來建立一棵哈希樹。
選擇從2開始的連續(xù)質(zhì)數(shù)來建立一個(gè)十層的哈希樹。第一層結(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)。
同一結(jié)點(diǎn)中的子結(jié)點(diǎn)，從左到右代表不同的余數(shù)結(jié)果。
例如：第二層結(jié)點(diǎn)下有三個(gè)子節(jié)點(diǎn)。那么從左到右分別代表：除3余0，除3余1，除3余2.
對(duì)質(zhì)數(shù)進(jìn)行取余操作得到的余數(shù)決定了處理的路徑。

下面我們以隨機(jī)的10個(gè)數(shù)的插入為例，來圖解HashTree的插入過程

2.Trie樹

 字典樹（Trie）可以保存一些字符串->值的對(duì)應(yīng)關(guān)系?；旧希?Java 的 HashMap 功能相同，都是 key-value 映射，只不過 Trie 的 key 只能是字符串。
Trie 的強(qiáng)大之處就在于它的時(shí)間復(fù)雜度。它的插入和查詢時(shí)間復(fù)雜度都為 O(k) ，其中 k 為 key 的長(zhǎng)度，與 Trie 中保存了多少個(gè)元素?zé)o關(guān)。Hash 表號(hào)稱是 O(1) 的，但在計(jì)算 hash 的時(shí)候就肯定會(huì)是 O(k) ，而且還有碰撞之類的問題；Trie 的缺點(diǎn)是空間消耗很高。
     Trie樹，又稱單詞查找樹或鍵樹，是一種樹形結(jié)構(gòu)，是一種哈希樹的變種。典型應(yīng)用是用于統(tǒng)計(jì)和排序大量的字符串（但不僅限于字符串），所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計(jì)。它的優(yōu)點(diǎn)是：大限度地減少無謂的字符串比較，查詢效率比哈希表高。
     Trie的核心思想是空間換時(shí)間。利用字符串的公共前綴來降低查詢時(shí)間的開銷以達(dá)到提高效率的目的。

以英文單詞構(gòu)建的字典樹為例，這棵Trie樹中每個(gè)結(jié)點(diǎn)包括26個(gè)孩子結(jié)點(diǎn)，因?yàn)榭偣灿?6個(gè)英文字母(假設(shè)單詞都是小寫字母組成)。

 下面我們有and,as,at,cn,com這些關(guān)鍵詞，那么如何構(gòu)建trie樹呢？

從上面的圖中，我們或多或少的可以發(fā)現(xiàn)一些好玩的特性。

   第一：根節(jié)點(diǎn)不包含字符，除根節(jié)點(diǎn)外的每一個(gè)子節(jié)點(diǎn)都包含一個(gè)字符。

   第二：從根節(jié)點(diǎn)到某一節(jié)點(diǎn)，路徑上經(jīng)過的字符連接起來，就是該節(jié)點(diǎn)對(duì)應(yīng)的字符串。

   第三：每個(gè)單詞的公共前綴作為一個(gè)字符節(jié)點(diǎn)保存。

參考文章：

    Trie樹：應(yīng)用于統(tǒng)計(jì)和排序   http://blog.csdn.net/hguisu/article/details/8131559

    圖文詳解HashTree（哈希樹）  http://blog.csdn.net/yang_yulei/article/details/46337405

           

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

網(wǎng)站名稱：Hash樹(散列樹)和Trie樹(字典樹、前綴樹)-創(chuàng)新互聯(lián)
分享地址：http://www.muchs.cn/article38/depssp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供企業(yè)網(wǎng)站制作、網(wǎng)站設(shè)計(jì)、云服務(wù)器、網(wǎng)站策劃、網(wǎng)站制作、手機(jī)網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)