:-: **常用字典結構的數據結構** | 數據結構 | 優缺點 | | --- | --- | | 排序列表Array/List | 使用二分法查找，不平衡。 | | HashMap/TreeMap | 性能高，內存消耗大，幾乎是原始數據的三倍。 | | Skip List | 跳躍表， 可快速查找詞語，在lucene、 redis、 Hbase等均有實現。相對于TreeMap等結構，特別適合高并發場景 。 | | Trie | 字典樹 。適合英文詞典， 如果系統中存在大量字符串且這些字符串基本沒有公共前級，則相應的trie樹將非常消耗內存。 | | Double Array Trie | 適合做中文詞典，內存占用小，很多分詞工具均采用此種算法 。 | | Ternary Search Tree | 三叉樹，每一個node有3個節點， 兼具省空間和查詢快的優點 。 | | Finite State Transducers (FST) | 一種有限狀態轉移機，Lucene 4有開源實現，并大量使用。 | 字典樹又稱單詞查找樹，Trie 樹，是一種樹形結構，是一種哈希樹的變種。典型應用是用于統計，排序和保存大量的字符串（但不僅限于字符串），所以經常被搜索引擎系統用于文本詞頻統計。 <br/> 它的優點是：利用字符串的公共前綴來減少查詢時間，最大限度地減少無謂的字符串比較，查詢效率比哈希樹高。 <br/> Trie 的核心思想是空間換時間，利用字符串的公共前綴來降低查詢時間的開銷以達到提高效率的目的。 它有 3 個基本性質: * 根節點不包含字符，除根節點外每一個節點都只包含一個字符。 * 從根節點到某一節點，路徑上經過的字符連接起來，為該節點對應的字符串。 * 每個節點的所有子節點包含的字符都不相同。 對于中文的字典樹，每個節點的子節點用一個哈希表存儲，這樣就不用浪費太大的空間，而且查詢速度上可以保留哈希的復雜度 O(1)。