常用字典数据结构如下所示

字典树又称单词查找树， Trie 树，是一种树形结构，是一种哈希树的变种

典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），经常被搜索引擎系统用于文本词频统计

优点

• 利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较
• 查询效率比哈希树高

Trie 的核心思想是空间换时间，利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的

基本性质

• 根节点不包含字符，除根节点外每一个节点都只包含一个字符
• 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串
• 每个节点的所有子节点包含的字符都不相同

对于中文的字典树，每个节点的子节点用一个哈希表存储，这样就不用浪费太大的空间，而且查询速度上可以保留哈希的复杂度 O(1)