路由功能是 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 https://github.com/shiniao/gaga 中路由前缀树相关的代码, 有需要的可以去看看源代码. 另外, 欢迎 star 呀.
其中的 addRoute 用来将路由插入到对应 method 的路由树中, 如果节点是通配符, 将其设置为 isWild , 同时绑定路由和 handler 方法.
getRoute 方法首先查找路由方法对应的路由前缀树, 然后在树中查找是否存在该路径.
总结
前缀树 trie 算法不光可以用在路由的实现上, 搜索引擎中自动补全的实现, 拼写检查等等都是用 trie 实现的. trie 树查找的时间和空间复杂度都是线性的, 效率很高, 很适合路由这种场景使用.
路由的实现上, go 语言中 httpRouter 这个库除了使用前缀树之外, 还加入了优先级, 有兴趣的可以看看它的源码了解下.
我的 blog: https://blog.shiniao.fun/
来源: http://www.tuicool.com/articles/I3UjEbR