一.前言
看了百度团队在 infoq 上发表的一篇【如何在秒级完成词表匹配】(https://xie.infoq.cn/article/97b2df7e41456335627ce4cd4)的文章，文章业务背景介绍的很清楚，里面有提到字典树，看到结构图我能明白工作原理，但是总感觉自己处于一种懂与不懂的半懂状态，希望通过写这篇文章我能彻底将字典树闹明白。
二.介绍
概念
字典树是一个存储字符串的树，一个节点的最大子节点数等于字母表的大小。支持在 O(L)时间内的搜索，插入和删除操作，L 是键的长度。
应用场景
1.可以在 O(L)时间内插入和查找字符串，其中 L 表示单个单词的长度。
2.可以轻松地按字母顺序打印所有单词。
3.可以使用字典树完成前缀搜索，这也是字典书叫前缀树的原因之一。
字典树样式
拥有字段：
（图有些问题，讲 i 视作右边最后一个节点）
b|bcd|abc|abd|abcd|efg|hi
总结
根据字典树特性，我们可以发现在敏感词场景中用字典树确实是一个很合理的选择，它采用空间换时间，保证用户可以在极短时间内获取字符串是否安全的结论，具体流程如下图所示：
针对百度的图，有以下两种情况
1.china，由于二级没有任何匹配的节点，所以安全
2.abd，在左边，有 abd 到有效节点 d，所以属于不安全
三.实现
了解了字典树的应用和特性，我们下一步要做的就是字典树的实现了,以下是我按照个人理解实现的源码，如有疑问欢迎沟通
3.1 字典树实现
type Trie struct {
valid bool //判断是否是有效节点
value interface{
} //节点的值
childMap map[interface{
}]int //子节点下是否有这个节点的map记录
childNodes []*Trie //包含的所有节点
}
func NewTrie() *Trie {
t := &Trie{
}
return t
}
//新增数据时间复杂度是O(L),L是新增字符串的长度
func (this *Trie) AddWord(word []byte) {
if len(word) < 1 {
return
}
length := len(word)
if this.childNodes == nil {
//不存在子级，需要重新创建
this.childNodes = append(this.childNodes, &Trie{
valid: length == 1,
value: word[0],
childNodes: nil,
})
this.childMap = make(map[interface{
}]int)
this.childMap[word[0]] = 1
this.childNodes[0].AddWord(word[1:])
} else {
index := this.childMap[word[0]]
if index > 0 {
//子级里面以及有这个值了
if len(word) == 1 && this.childNodes[index-
