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

1.Hash樹

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

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

哈希樹的理論基礎

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

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

插入

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

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

2.Trie樹

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

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

 下面我們有and,as,at,cn,com這些關鍵詞，那么如何構建trie樹呢？

從上面的圖中，我們或多或少的可以發現一些好玩的特性。

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

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

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

參考文章：

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

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