Hash樹(散列樹)和Trie樹(字典樹、前綴樹)

1.Hash樹

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

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

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

【質(zhì)數(shù)分辨定理】
簡單地說就是：n個不同的質(zhì)數(shù)可以“分辨”的連續(xù)整數(shù)的個數(shù)和他們的乘積相等。“分辨”就是指這些連續(xù)的整數(shù)不可能有完全相同的余數(shù)序列。

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

插入

我們選擇質(zhì)數(shù)分辨算法來建立一棵哈希樹。
選擇從2開始的連續(xù)質(zhì)數(shù)來建立一個十層的哈希樹。第一層結(jié)點為根結(jié)點，根結(jié)點下有2個結(jié)點；第二層的每個結(jié)點下有3個結(jié)點；依此類推，即每層結(jié)點的子節(jié)點數(shù)目為連續(xù)的質(zhì)數(shù)。到第十層，每個結(jié)點下有29個結(jié)點。
同一結(jié)點中的子結(jié)點，從左到右代表不同的余數(shù)結(jié)果。
例如：第二層結(jié)點下有三個子節(jié)點。那么從左到右分別代表：除3余0，除3余1，除3余2.
對質(zhì)數(shù)進行取余操作得到的余數(shù)決定了處理的路徑。

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

2.Trie樹

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

以英文單詞構(gòu)建的字典樹為例，這棵Trie樹中每個結(jié)點包括26個孩子結(jié)點，因為總共有26個英文字母(假設單詞都是小寫字母組成)。

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

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

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

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

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

參考文章：

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

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