网站建设少用控件,网站主页设计注意点,国外创意网站设计欣赏,新媒体 网站建设 管理规范前言#xff1a;路由原理———压缩字典
这边简单讲一下gin非常重要的一个基点#xff0c;也就是他作为go web框架的一个亮点
也就是Trie树和压缩字典算法
gin 通过树来存储路由#xff0c;讲路由的字符拆解为一个个的结点#xff0c;在获取handler函数时#xff0c;会…前言路由原理———压缩字典
这边简单讲一下gin非常重要的一个基点也就是他作为go web框架的一个亮点
也就是Trie树和压缩字典算法
gin 通过树来存储路由讲路由的字符拆解为一个个的结点在获取handler函数时会根据路由来获取对应的结点结点中包含了handler函数根据结点来获取对应的handler函数
主要就是压缩字典算法
正常的trie树的存储单个结点一个结点一个字符这样是非常耗空间的但是如果使用压缩字典算法则是通过先找到共同公共前缀再去找子结点如此重复以上两个步骤期间会对结点进行切分和重组形成新的结点极大的节省了存储空间 比如上图没有使用压缩字典树算法路由 /acd /at /bee 形成的树形结构每个字母的父亲节点就是它的前一个字母
Trie树的三个性质 根节点不包含字符除根节点外每一个节点都只包含一个字符 从根节点到某一节点路径上经过的字符连接起来为该节点对应的字符串 每个节点的所有子节点包含的字符都不相同
那么有了这样的一颗树查找单词就变得很简单从根节点开始向下匹配如果匹配到单词的前缀就沿着该节点接着往下匹配直到完全匹配到单词。
但是trie树的每个节点只能存储一个字符这意味着面对较长的字符串仍然要向下探寻多个节点这存在着浪费因此就有了压缩字典树
压缩字典树是trie树的一种也称单词查找树、前缀树善于进行字符串的检索、取字符串最长公共前缀、以及排序常应用在搜索引擎中例如百度输入某个字可能自动弹出能匹配到的单词出来。
以下分别是Trie树和压缩字典树 显而易见的相同路径下结点数量便少了很多
压缩字典树的特质使得其用于单词前缀查找时更快。这也恰巧就是一个高性能的路由匹配算法需要的。因此Gin使用其作为路由算法。
type node struct {path string // 存储着节点的字符串indices string // 存储着下级子节点的前缀索引 这边是作为数组切片用按照子结点顺序抽取其所有子结点首字符放入这里wildChild bool //进行模糊匹配例如有些是/user/:pid 这类的url存储的结点遍历到/:pid时候就会判断是不是模糊匹配//如果你的url是user/1234 那么就会根据这个参数进行模糊匹配也就是 将1234填补:pid的位置nType nodeType
// nType 节点类型
// static nodeType iota // default默认类型
// root 根节点
// param 参数例如:id这样的通配符
// catchAll 全匹配priority uint32 // 优先级 这个树的结点有权重比一般是越上面的结点权重越高具体看实现children []*node // 子节点, 至少有一个 :param 类型的节点会在列表的末尾handlers HandlersChain // 匹配该节点的路由的处理函数 一个结点可以有多个handle函数也就是其名字带chain的意义fullPath string // 从根节点到该节点的完整路径 relativePath
} 下面通过引用一个博主的流程图直观解释添加结点的流程
插入操作 图解一串子串插入压缩trie过程/,/serach,/support,/blog , 在httprouter上截的一段例子我们只插到/blog 插入/serach 插入/support 插入/blog
同第二步查询后直接插入blog
——查询操作——
1、先找共同前缀。 2、再找目录。 3、循环上面两步直到当前path相等。
gin中还根据不同的请求方法分为不同的树例如getpost等方法都有各自独立的树但是都同属于同一个根节点
