- 1 Trie树简介
- 2 比较
- 2.1 HashMap
- 2.2 ElasticSearch
- 3 实现Trie树
- 4 使用DoubleArrayTrie降低空间复杂度
Trie又称前缀树或字典树，有如下特性：
- 除根节点为空外，其每个节点都表示一个字符
- 一个节点的所有子孙都有相同的前缀
- 从根节点出发，到某一end节点，则表示一个字符串
一下是一个简单的例子：在trie树中插入多个子串[she, he, her, this, his, is]
蓝色的节点表示end节点，即从root出发到end节点表示一个子串。
当我们要查找主串sherthis，是否存在一个从首字符起前缀相同的子串时（如果是查找子串，则需要为trie加上fail指针，即AC自动机，这里不讲），我们便可以在trie上以O(n)的时间复杂度完成查找。
从上边的例子中，我们可以看到在前缀匹配中，trie拥有不俗查找效率外，还能够对公共前缀进行空间上的压缩。
Trie树主要可以应用在各种字符串前缀匹配的场景下，如搜索提示、词频统计等。
看完后依然不明白，可以手动实现一遍LeetCode208题。
2 比较 2.1 HashMapHashMap可以在O(1)的时间复杂度和O(n)的时间复杂度内，完成对字符串的匹配。
但其只能使用在字符串精确匹配，而无法应对前缀匹配场景。
2.2 ElasticSearch除了自己实现数据结构去应对业务场景外，同样可以考虑借助一些中间件帮助我们干活。
ElasticSearch作为一款分布式搜索引擎，是否能够实现高效的前缀匹配呢？
ES提供有prefix前缀查询功能，可以支持前缀匹配功能。以匹配W1前缀为例，工作流程如下：
- 扫描词列表并查找第一个以W1开始词
- 搜集关联的文档ID
- 移动到下一个词
- 如果这个词也是以W1开头，查询跳回到第二步再重复执行，直到下一词不以W1为止
但官方文档中同时也建议要小心使用该功能，避免搜索过大的词集合（换句话说，也就是输入的前缀能够匹配上的词越少，效率越高）。
prefix 查询或过滤对于一些特定的匹配是有效的，但使用方式还是应当注意。当字段中词的集合很小时，可以放心使用，但是它的伸缩性并不好，会对我们的集群带来很多压力。可以使用较长的前缀来限制这种影响，减少需要访问的量。
所以可以看到ElasticSearch可以解决前缀匹配的问题，但是要考虑前缀串的特性，并且要依赖中间件。
3 实现Trie树这里就不贴实现了，网上的代码有很多。
如果你思考过如何实现Trie树，或则尝试解决了LeetCode208题，你或许发现可以使用HashMap或则数组去存储父子节点关系。
但不幸的是，在特定的业务场景和数据量比较小的情况，它们能够正确的运行。但数据量太大的话，这两种实现恐怕就无法胜任工作了。
使用HashMap需要new大量的对象，对GC并不友好，并且hashMap自身的数据结构对内存的占用较高。
使用数组则不够灵活，因为插入的字符可不一定是26个英文字符，数组大小难以估算，并且哪怕是只有一个子节点，也需要开辟一个完整的数组。
那有没有一种在O(1)时间复杂度下，能以更小的空间复杂度实现父子节点关系的存储呢？
有，它便是双数组（DoubleArrayTrie）。
4 使用DoubleArrayTrie降低空间复杂度简单的说，DoubleArrayTrie本质是一个确定有限状态自动机（DFA），使用两个线性数组（base数组和check数组）来表示Trie树，对Trie的结构进行了空间上的压缩，但同时不降低查询速度。
在这里不做更多DoubleArrayTrie构建和查找原理上的介绍，感兴趣这里贴几篇高质量的文章（让我写并不会写得比他们更好），足够让你理解DoubleArrayTrie的原理和实现了。
《DoubleArrayTrie的Java实现》
《最好懂的DoubleArrayTrie构建与遍历流程》
《计算的本质：深入剖析程序和计算机》3.1节 确定性有限自动机
