内容简介：在上一篇文章中，我们聊了聊在Golang中怎么实现一个Http服务器。但是在最后我们可以发现，固然由所以在这篇文章中，我们将分析
摘要
在上一篇文章中，我们聊了聊在Golang中怎么实现一个Http服务器。但是在最后我们可以发现，固然 DefaultServeMux 可以做路由分发的功能，但是他的功能同样是不完善的。
由 DefaultServeMux 做路由分发，是不能实现 RESTful 风格的API的，我们没有办法定义请求所需的方法，也没有办法在 API 路径中加入 query 参数。其次，我们也希望可以让路由查找的效率更高。
所以在这篇文章中，我们将分析 httprouter 这个包，从源码的层面研究他是如何实现我们上面提到的那些功能。并且，对于这个包中最重要的 前缀树 ，本文将以图文结合的方式来解释。
1 使用
我们同样以怎么使用作为开始，自顶向下的去研究 httprouter 。我们先来看看官方文档中的小例子：
package main
import (
"fmt"
"net/http"
"log"
"github.com/julienschmidt/httprouter"
)
func Index(w http.ResponseWriter, r *http.Request, _ httprouter.Params) {
fmt.Fprint(w, "Welcome!\n")
}
func Hello(w http.ResponseWriter, r *http.Request, ps httprouter.Params) {
fmt.Fprintf(w, "hello, %s!\n", ps.ByName("name"))
}
func main() {
router := httprouter.New()
router.GET("/", Index)
router.GET("/hello/:name", Hello)
log.Fatal(http.ListenAndServe(":8080", router))
}
其实我们可以发现，这里的做法和使用Golang自带的 net/http 包的做法是差不多的。都是先注册相应的URI和函数，换一句话来说就是将路由和处理器相匹配。
在注册的时候，使用 router.XXX 方法，来注册相对应的方法，比如 GET ， POST 等等。
注册完之后，使用 http.ListenAndServe 开始监听。
至于为什么，我们会在后面的章节详细介绍，现在只需要先了解做法即可。
2 创建
我们先来看看第一行代码，我们定义并声明了一个 Router 。下面来看看这个 Router 的结构，这里把与本文无关的其他属性省略：
type Router struct {
//这是前缀树，记录了相应的路由
trees map[string]*node
//记录了参数的最大数目
maxParams uint16
}
在创建了这个 Router 的结构后，我们就使用 router.XXX 方法来注册路由了。继续看看路由是怎么注册的：
func (r *Router) GET(path string, handle Handle) {
r.Handle(http.MethodGet, path, handle)
}
func (r *Router) POST(path string, handle Handle) {
r.Handle(http.MethodPost, path, handle)
}
...
在这里还有一长串的方法，他们都是一样的，调用了
r.Handle(http.MethodPost, path, handle)
这个方法。我们再来看看：
func (r *Router) Handle(method, path string, handle Handle) {
...
if r.trees == nil {
r.trees = make(map[string]*node)
}
root := r.trees[method]
if root == nil {
root = new(node)
r.trees[method] = root
r.globalAllowed = r.allowed("*", "")
}
root.addRoute(path, handle)
...
}
在这个方法里，同样省略了很多细节。我们只关注一下与本文有关的。我们可以看到，在这个方法中，如果 tree 还没有初始化，则先初始化这颗 前缀树 。
然后我们注意到，这颗树是一个 map 结构。也就是说，一个方法，对应了一颗树。然后，对应这棵树，调用 addRoute 方法，把 URI 和对应的 Handle 保存进去。
3 前缀树
3.1 定义
又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
简单的来讲，就是要查找什么，只要跟着这棵树的某一条路径找，就可以找得到。
比如在搜索引擎中，你输入了一个 蔡 ：
他会有这些联想，也可以理解为是一个前缀树。
再举个例子：
在这颗 GET 方法的前缀树中，包含了以下的路由：
- /wow/awesome
- /test
- /hello/world
- /hello/china
- /hello/chinese
说到这里你应该可以理解了，在构建这棵树的过程中， 任何两个节点，只要有了相同的前缀，相同的部分就会被合并成一个节点 。
3.2 图解构建
上面说的 addRoute 方法，就是这颗前缀树的插入方法。假设现在数为空，在这里我打算以图解的方式来说明这棵树的构建。
假设我们需要插入的三个路由分别为：
- /hello/world
- /hello/china
- /hello/chinese
（1）插入 /hello/world
因为此时树为空，所以可以直接插入：
(2)插入 /hello/china
此时，发现 /hello/world 和 /hello/china 有相同的前缀 /hello/ 。
那么要先将原来的 /hello/world 结点，拆分出来，然后将要插入的结点 /hello/china ，截去相同部分，作为 /hello/world 的子节点。
(3)插入 /hello/chinese
此时，我们需要插入 /hello/chinese ，但是发现， /hello/chinese 和结点 /hello/ 有公共的前缀 /hello/ ，所以我们去查看 /hello/ 这个结点的子节点。
注意，在结点中有一个属性，叫 indices 。它记录了这个结点的子节点的首字母，便于我们查找。比如这个 /hello/ 结点，他的 indices 值为 wc 。而我们要插入的结点是 /hello/chinese ，除去公共前缀后， chinese 的第一个字母也是 c ，所以我们进入 china 这个结点。
这时，有没有发现，情况回到了我们一开始插入 /hello/china 时候的局面。那个时候公共前缀是 /hello/ ，现在的公共前缀是 chin 。
所以，我们同样把 chin 截出来，作为一个结点，将 a 作为这个结点的子节点。并且，同样把 ese 也作为子节点。
3.3 总结构建算法
到这里，构建就已经结束了。我们来总结一下算法。
具体带注释的代码将在本文最末尾给出，如果想要了解的更深可以自行查看。在这里先理解这个过程：
（1）如果树为空，则直接插入
（2）否则，查找当前的结点是否与要插入的 URI 有公共前缀
（3）如果没有公共前缀，则直接插入
（4）如果有公共前缀，则判断是否需要分裂当前的结点
（5）如果需要分裂，则将公共部分作为父节点，其余的作为子节点
（6）如果不需要分裂，则寻找有无前缀相同的子节点
（7）如果有前缀相同的，则跳到(4)
（8）如果没有前缀相同的，直接插入
（9）在最后的结点，放入这条路由对应的 Handle
但是到了这里，有同学要问了： 怎么这里的路由，不带参数的呀？
其实只要你理解了上面的过程，带参数也是一样的。逻辑是这样的：在每次插入之前，会扫描当前要插入的结点的path是否带有参数（即扫描有没有 / 或者 * ）。如果带有参数的话，将当前结点的 wildChild 属性设置为 true ，然后将参数部分，设置为一个 新的子节点 。
4 监听
在讲完了路由的注册，我们来聊聊路由的监听。
在上一篇文章的内容中，我们有提到这个：
type serverHandler struct {
srv *Server
}
func (sh serverHandler) ServeHTTP(rw ResponseWriter, req *Request) {
handler := sh.srv.Handler
if handler == nil {
handler = DefaultServeMux
}
if req.RequestURI == "*" && req.Method == "OPTIONS" {
handler = globalOptionsHandler{}
}
handler.ServeHTTP(rw, req)
}
当时我们提到，如果我们不传入任何的 Handle 方法，Golang将使用默认的 DefaultServeMux 方法来处理请求。而现在我们传入了 router ，所以将会使用 router 来处理请求。
因此， router 也是实现了 ServeHTTP 方法的。我们来看看（同样省略了一些步骤）：
func (r *Router) ServeHTTP(w http.ResponseWriter, req *http.Request) {
...
path := req.URL.Path
if root := r.trees[req.Method]; root != nil {
if handle, ps, tsr := root.getValue(path, r.getParams); handle != nil {
if ps != nil {
handle(w, req, *ps)
r.putParams(ps)
} else {
handle(w, req, nil)
}
return
}
}
...
// Handle 404
if r.NotFound != nil {
r.NotFound.ServeHTTP(w, req)
} else {
http.NotFound(w, req)
}
}
在这里，我们选择 请求方法 所对应的 前缀树 ，调用了 getValue 方法。
简单解释一下这个方法：在这个方法中会不断的去匹配当前路径与结点中的 path ，直到找到最后找到这个路由对应的 Handle 方法。
注意，在这期间，如果路由是RESTful风格的，在路由中含有参数，将会被保存在 Param 中，这里的 Param 结构如下：
type Param struct {
Key string
Value string
}
如果未找到相对应的路由，则调用后面的404方法。
5 处理
到了这一步，其实和以前的内容几乎一样了。
在获取了该路由对应的 Handle 之后，调用这个函数。
唯一和之前使用 net/http 包中的 Handler 不一样的是，这里的 Handle ，封装了从API中获取的参数。
type Handle func(http.ResponseWriter, *http.Request, Params)
6 写在最后
谢谢你能看到这里~
至此，httprouter介绍完毕，最关键的也就是前缀树的构建了。在上面我用图文结合的方式，模拟了一次前缀树的构建过程，希望可以让你理解前缀树是怎么回事。当然，如果还有疑问，也可以留言或者在微信中与我交流~
当然，如果你不满足于此，可以看看 后面的附 录，有前缀树的 全代码注释 。
当然了，作者也是刚入门。所以，可能会有很多的疏漏。如果在阅读的过程中，有哪些解释不到位，或者理解出现了偏差，也请你留言指正。
再次感谢~
PS：如果有其他的问题，也可以在公众号找到作者。并且，所有文章第一时间会在公众号更新，欢迎来找作者玩~
7 源码阅读
7.1 树的结构
type node struct {
path string //当前结点的URI
indices string //子结点的首字母
wildChild bool //子节点是否为参数结点
nType nodeType //结点类型
priority uint32 //权重
children []*node //子节点
handle Handle //处理器
}
7.2 addRoute
func (n *node) addRoute(path string, handle Handle) {
fullPath := path
n.priority++
// 如果这是个空树，那么直接插入
if len(n.path) == 0 && len(n.indices) == 0 {
//这个方法其实是在n这个结点插入path，但是会处理参数
//详细实现在后文会给出
n.insertChild(path, fullPath, handle)
n.nType = root
return
}
//设置一个flag
walk:
for {
// 找到当前结点path和要插入的path中最长的前缀
// i为第一位不相同的下标
i := longestCommonPrefix(path, n.path)
// 此时相同的部分比这个结点记录的path短
// 也就是说需要把当前的结点分裂开
if i < len(n.path) {
child := node{
// 把不相同的部分设置为一个切片，作为子节点
path: n.path[i:],
wildChild: n.wildChild,
nType: static,
indices: n.indices,
children: n.children,
handle: n.handle,
priority: n.priority - 1,
}
// 将新的结点作为这个结点的子节点
n.children = []*node{&child}
// 把这个结点的首字母加入indices中
// 目的是查找更快
n.indices = string([]byte{n.path[i]})
n.path = path[:i]
n.handle = nil
n.wildChild = false
}
// 此时相同的部分只占了新URI的一部分
// 所以把path后面不相同的部分要设置成一个新的结点
if i < len(path) {
path = path[i:]
// 此时如果n的子节点是带参数的
if n.wildChild {
n = n.children[0]
n.priority++
// 判断是否会不合法
if len(path) >= len(n.path) && n.path == path[:len(n.path)] &&
n.nType != catchAll &&
(len(n.path) >= len(path) || path[len(n.path)] == '/') {
continue walk
} else {
pathSeg := path
if n.nType != catchAll {
pathSeg = strings.SplitN(pathSeg, "/", 2)[0]
}
prefix := fullPath[:strings.Index(fullPath, pathSeg)] + n.path
panic("'" + pathSeg +
"' in new path '" + fullPath +
"' conflicts with existing wildcard '" + n.path +
"' in existing prefix '" + prefix +
"'")
}
}
// 把截取的path的第一位记录下来
idxc := path[0]
// 如果此时n的子节点是带参数的
if n.nType == param && idxc == '/' && len(n.children) == 1 {
n = n.children[0]
n.priority++
continue walk
}
// 这一步是检查拆分出的path，是否应该被合并入子节点中
// 具体例子可看上文中的图解
// 如果是这样的话，把这个子节点设置为n，然后开始一轮新的循环
for i, c := range []byte(n.indices) {
if c == idxc {
// 这一部分是为了把权重更高的首字符调整到前面
i = n.incrementChildPrio(i)
n = n.children[i]
continue walk
}
}
// 如果这个结点不用被合并
if idxc != ':' && idxc != '*' {
// 把这个结点的首字母也加入n的indices中
n.indices += string([]byte{idxc})
child := &node{}
n.children = append(n.children, child)
n.incrementChildPrio(len(n.indices) - 1)
// 新建一个结点
n = child
}
// 对这个结点进行插入操作
n.insertChild(path, fullPath, handle)
return
}
// 直接插入到当前的结点
if n.handle != nil {
panic("a handle is already registered for path '" + fullPath + "'")
}
n.handle = handle
return
}
}
7.3 insertChild
func (n *node) insertChild(path, fullPath string, handle Handle) {
for {
// 这个方法是用来找这个path是否含有参数的
wildcard, i, valid := findWildcard(path)
// 如果不含参数，直接跳出循环，看最后两行
if i < 0 {
break
}
// 条件校验
if !valid {
panic("only one wildcard per path segment is allowed, has: '" +
wildcard + "' in path '" + fullPath + "'")
}
// 同样判断是否合法
if len(wildcard) < 2 {
panic("wildcards must be named with a non-empty name in path '" + fullPath + "'")
}
if len(n.children) > 0 {
panic("wildcard segment '" + wildcard +
"' conflicts with existing children in path '" + fullPath + "'")
}
// 如果参数的第一位是`:`，则说明这是一个参数类型
if wildcard[0] == ':' {
if i > 0 {
// 把当前的path设置为参数之前的那部分
n.path = path[:i]
// 准备把参数后面的部分作为一个新的结点
path = path[i:]
}
//然后把参数部分作为新的结点
n.wildChild = true
child := &node{
nType: param,
path: wildcard,
}
n.children = []*node{child}
n = child
n.priority++
// 这里的意思是，path在参数后面还没有结束
if len(wildcard) < len(path) {
// 把参数后面那部分再分出一个结点，continue继续处理
path = path[len(wildcard):]
child := &node{
priority: 1,
}
n.children = []*node{child}
n = child
continue
}
// 把处理器设置进去
n.handle = handle
return
} else { // 另外一种情况
if i+len(wildcard) != len(path) {
panic("catch-all routes are only allowed at the end of the path in path '" + fullPath + "'")
}
if len(n.path) > 0 && n.path[len(n.path)-1] == '/' {
panic("catch-all conflicts with existing handle for the path segment root in path '" + fullPath + "'")
}
// 判断在这之前有没有一个/
i--
if path[i] != '/' {
panic("no / before catch-all in path '" + fullPath + "'")
}
n.path = path[:i]
// 设置一个catchAll类型的子节点
child := &node{
wildChild: true,
nType: catchAll,
}
n.children = []*node{child}
n.indices = string('/')
n = child
n.priority++
// 把后面的参数部分设置为新节点
child = &node{
path: path[i:],
nType: catchAll,
handle: handle,
priority: 1,
}
n.children = []*node{child}
return
}
}
// 对应最开头的部分，如果这个path里面没有参数，直接设置
n.path = path
n.handle = handle
}
最关键的几个方法到这里就全部结束啦，先给看到这里的你鼓个掌！
这一部分理解会比较难，可能需要多看几遍。
如果还是有难以理解的地方，欢迎留言交流，或者直接来公众号找我~
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
Data Structures and Algorithms
Alfred V. Aho、Jeffrey D. Ullman、John E. Hopcroft / Addison Wesley / 1983-1-11 / USD 74.20
The authors' treatment of data structures in Data Structures and Algorithms is unified by an informal notion of "abstract data types," allowing readers to compare different implementations of the same......一起来看看 《Data Structures and Algorithms》 这本书的介绍吧!
