:-: **常用字典结构的数据结构** | 数据结构 | 优缺点 | | --- | --- | | 排序列表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)。