什么是http路由

撸过http框架的同学都知道，一个MVC模型的http框架肯定是少不了路由这一块的，那么什么是路由呢。

简而言之，http路由即是一条http请求的“向导”，根据URI上的路径，指引该条请求到对应的方法里去执行然后返回，中间可能会执行一些中间件。

路由的种类

  • 静态路由

框架/用户提前生成一个路由表，一般是map结构，key为URI上的path，value为代码执行点。

优点：只需要读取map，没有任何开销，速度奇快。

缺点：无法正则匹配路由，只能一一对应，模糊匹配的场景无法使用。

  • 动态路由

用户定义好路由匹配规则，框架匹配路由时，根据规则动态去规划路由。

优点：适应性强，解决了静态路由的缺点。

缺点：相比静态路由有开销，具体视算法和路由匹配规则而定。

gin框架路由实现原理

gin框架作为一个轻量级的快速框架，采用的是前缀树的方式实现的动态路由。

gin框架使用路由

我们以下面代码为例，去看看gin是如何实现路由的。

/user/:name/user/:name/user/user//user/allen/abc

接下来我们跟着源码去探究gin是如何实现的。

初始化框架

r := gin.New()EngineEngineHandlers HandlersChaintrees methodTrees

定义路由

r.GET("/user/:name", routeUser)GET/user/:name

步骤1：

routergroup.go=>group.calculateAbsolutePath()
/user/:name

步骤2：

routergroup.go=>group.combineHandlers()
handlersChainmath.MaxInt8 / 2handlersChain

步骤3：

routergroup.go=>group.engine.addRoute()
engine.trees

步骤4：

返回当前对象，达到能使用链式操作的目的。

访问路由

localhost:8080/user/abcServeHTTP()handleHTTPRequest()engine.tress
gin.go=>handleHTTPRequest()
tree.go=>getValue()

前缀树算法

前缀树的本质就是一棵查找树，有别于普通查找树，它适用于一些特殊场合，比如用于字符串的查找。比如一个在路由的场景中，有1W个路由字符串，每个字符串长度不等，我们可以使用数组来储存，查找的时间复杂度是O(n)，可以用map来储存，查找的复杂度是O(1)，但是都没法解决动态匹配的问题，如果用前缀树时间复杂度是O(logn)，也可以解决动态匹配参数的问题。

cat
crootarootcacatat

同理，在路由中，前缀树可以规划成如下：

具体查找方法和上面一致。