内容简介:路由功能是web框架中一个很重要的功能,它将不同的请求转发给不同的函数(handler)处理,很容易能想到,我们可以用一个字典保存它们之间的对应关系,字典的key存放path,value存放handler。当一个请求过来后,使用利用字典实现路由可以参考我的这篇文章:使用字典有一个问题,不支持动态路由。如果路由像这样呢?
路由功能是web框架中一个很重要的功能,它将不同的请求转发给不同的函数(handler)处理,很容易能想到,我们可以用一个字典保存它们之间的对应关系,字典的key存放path,value存放handler。当一个请求过来后,使用 routers.get(path, None) 就可以找到对应的handler。
利用字典实现路由可以参考我的这篇文章: 动手实现web框架 。
使用字典有一个问题,不支持动态路由。如果路由像这样呢?
/hello/:name/profile
name前面是通配符 : ,表示这是个动态的值。一个解决办法是使用前缀树trie。
前缀树
leetcode中有这个算法, 点这里 查看。
前缀树前缀树,首先是一棵树。不同的是树中一个节点的所有子孙都有相同的前缀。前缀树将单词中的每个字母依次插入树中,插入前首先确认该单词是否存在,不存在才创建新节点,如果一个单词已经全部插入,则将末尾单词设置为标志位。
type Node struct { isWord bool // 是否是单词结尾 next map[string]*Node // 子节点 } type Trie struct { root *Node }
以单词leetcode,leetd和code为例,首先一次插入leetcode中的每个单词,然后插入leetd的时候,leet在树中已经存在,跳过往下,现在要插入字母d,不存在,所以新建节点插入树中,并将该节点的isWord置位true,表明到了单词末尾。
最终插入结果为:
func (this *Trie) Insert(word string) { cur := this.root for _, w := range []rune(word) { c := string(w) if cur.next[c] == nil { cur.next[c] = &Node{next: make(map[string]*Node)} } cur = cur.next[c] } cur.isWord = true }
那么,当我们要搜索单词leetd的时候,从根节点开始查找,如果找到某条路径是leetd,并且末尾的d是单词标志位,则表示搜索成功。
func (this *Trie) Search(word string) bool { cur := this.root for _, w := range []rune(word) { c := string(w) if cur.next[c] == nil { return false } cur = cur.next[c] } return cur.isWord }
明白了前缀树的原理,我们来看看路由匹配是如何利用前缀树来实现的。
路由前缀树
go语言中gin框架的路由实现就是利用前缀树,可以看看它的源代码是如何实现的。
考虑一下,路由或者说路径的特点,是以 / 分隔的单词组成的,那我们将 / 的每一部分挂靠在前缀树上就可以了。如下图所示:
还有一点需要考虑,我们在用web框架定义路由的时候,常见的做法是根据不同的HTTP方法来定义。比如:
// 以 go 语言gin框架为例 g := gin.New() g.GET("/hello", Hello) g.POST("/form", Form)
对于同一个路径,可能有多个方法支持。所以我们要以不同HTTP方法为树根创建前缀树。当一个GET请求过来的时候,就从GET树上搜索,POST请求就从POST树上搜索。
除了为不同的HTTP方法定义树之外,还要给那些是通配符的节点增加一个标志位。所以,我们的路由前缀树结构看起来像这样:
type node struct { path string // 路由路径 part string // 路由中由'/'分隔的部分 children map[string]*node // 子节点 isWild bool // 是否是通配符节点 } type router struct { root map[string]*node // 路由树根节点 route map[string]HandlerFunc // 路由处理handler }
依照上面的前缀树算法的实现,照葫芦画瓢,我们可以写出插入路由和搜索路由的方法:
// addRoute 绑定路由到handler func (r *router) addRoute(method, path string, handler HandlerFunc) { parts := parsePath(path) if _, ok := r.root[method]; !ok { r.root[method] = &node{children: make(map[string]*node)} } root := r.root[method] key := method + "-" + path // 将parts插入到路由树 for _, part := range parts { if root.children[part] == nil { root.children[part] = &node{ part: part, children: make(map[string]*node), isWild: part[0] == ':' || part[0] == '*'} } root = root.children[part] } root.path = path // 绑定路由和handler r.route[key] = handler } // getRoute 获取路由树节点以及路由变量 func (r *router) getRoute(method, path string) (node *node, params map[string]string) { params = map[string]string{} searchParts := parsePath(path) // get method trie var ok bool if node, ok = r.root[method]; !ok { return nil, nil } // 在该方法的路由树上查找该路径 for i, part := range searchParts { var temp string // 查找child是否等于part for _, child := range node.children { if child.part == part || child.isWild { // 添加参数 if child.part[0] == '*' { params[child.part[1:]] = strings.Join(searchParts[i:], "/") } if child.part[0] == ':' { params[child.part[1:]] = part } temp = child.part } } // 遇到通配符*,直接返回 if temp[0] == '*' { return node.children[temp], params } node = node.children[temp] } return }
上面的代码是我自己实现的一个web框架 gaga 中路由前缀树相关的代码,有需要的可以去看看源代码。另外,欢迎 star 呀。
其中的 addRoute 用来将路由插入到对应method的路由树中,如果节点是通配符,将其设置为 isWild , 同时绑定路由和handler方法。
getRoute方法首先查找路由方法对应的路由前缀树,然后在树中查找是否存在该路径。
总结
前缀树trie算法不光可以用在路由的实现上,搜索引擎中自动补全的实现,拼写检查等等都是用trie实现的。trie树查找的时间和空间复杂度都是线性的,效率很高,很适合路由这种场景使用。
路由的实现上,go语言中 httpRouter 这个库除了使用前缀树之外,还加入了优先级,有兴趣的可以看看它的源码了解下。
我的blog: https://blog.shiniao.fun
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- Gin框架系列02:路由与参数
- 深入理解express框架的匹配路由
- React框架Umi实战(3)路由进阶
- 工具 | 滴滴开源的一套 Android 路由框架
- 美团外卖开源路由框架 WMRouter 源码分析
- Android点我达路由DRouter框架设计与解析
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
数据结构及应用算法教程
2011-5 / 45.00元
《数据结构及应用算法教程(修订版)》从数据类型的角度,分别讨论了四大类型的数据结构的逻辑特性、存储表示及其应用。此外,还专辟一章,以若干实例阐述以抽象数据类型为中心的程序设计方法。书中每一章后都配有适量的习题,以供读者复习提高之用。第1~9章还专门设有“解题指导与示例”一节内容,不仅给出答案,对大部分题目提供了详尽的解答注释;其中的一些算法题还给出了多种解法。书中主要算法和最后一章的实例中的全部程......一起来看看 《数据结构及应用算法教程》 这本书的介绍吧!