這兩天在接觸Gin，對它的動態路由功能比較感興趣，特意做了筆記，順便跟SpringMVC作下對比。
1.簡介
Gin是使用Go/golang語言實現的HTTP Web框架。接口簡潔,性能極高。截止1.4.0版本,包含測試代碼,僅14K,其中測試代碼9K左右,也就是說框架源碼僅5K左右。SpringMVC不用過多介紹，Java市場的一把手。
Gin支持動態路由，簡單示例如下：
<code>import (
"github.com/gin-gonic/gin"
"net/http"
)
func main() {
r := gin.Default()
r.GET("/hello/:name", func(context *gin.Context) {
context.String(http.StatusOK, "Hello : "+context.Param("name"))
})
r.Run()
}
/<code>
對比SpringMVC的例子為：
<code>import org.springframework.web.bind.annotation.PathVariable;
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RestController;
@RestController
public class HelloWorldController {
@RequestMapping("/hello/{name}")
public String antUser (@PathVariable("name") String name) {
return "Hello : " + name;
}
}
/<code>
二者有相似的地方。
2.Gin
Gin使用Trie樹來實現動態路由。Trie樹,即字典樹,又稱單詞查找樹或鍵樹,是一種樹形結構,是一種哈希樹的變種。典型應用是用於統計和排序大量的字符串（但不僅限於字符串），所以經常被搜索引擎系統用於文本詞頻統計。它的優點是：最大限度地減少無謂的字符串比較，查詢效率比哈希表高。
Trie的核心思想是空間換時間。利用字符串的公共前綴來降低查詢時間的開銷以達到提高效率的目的。它有3個基本性質：
- 根節點不包含字符，除根節點外每一個節點都只包含一個字符。
- 從根節點到某一節點，路徑上經過的字符連接起來，為該節點對應的字符串。
- 每個節點的所有子節點包含的字符都不相同。
如上圖示，為一個保存了8個鍵的trie結構，"A", "to", "tea", "ted", "ten", "i", "in", "inn"。其中，鍵標註在節點中，值標註在節點之下。每一個完整的英文單詞對應一個特定的整數。Trie可以看作是一個確定有限狀態自動機，儘管邊上的符號一般是隱含在分支的順序中的。
Trie數的常見應用場景包括：
- 字符串檢索
- 詞頻統計
- 前綴檢索
- 前綴詞頻統計
- 對所有的字符串按照字典序排序
Gin的路由實現也是跟上面的例子類似，具體實現在tree.go文件裡，主要包括trie樹的構建和查找過程。
2.1. 建樹過程
先看node的定義
<code>type node struct {
path string // 當前節點相對路徑,即公共前綴
indices string // 所有孩子節點的path[0]組成的字符串，如果子節點有通配符，則為空
children []*node // 孩子節點
handlers HandlersChain // 當前節點的處理函數（包括中間件）
priority uint32 // 當前節點及子孫節點的實際路由數量
nType nodeType // 節點類型
maxParams uint8 // 子孫節點的最大參數數量
wildChild bool // 孩子節點是否有通配符（wildcard）
fullPath string // 完整的請求路徑，各中間節點也有
}
/<code>建樹過程主要由兩個方法來完成
<code>// 根據給定的路徑增加一個節點，主要用於處理公共前綴的分割
func (n *node) addRoute(path string, handlers HandlersChain) {}
// 主要用於處理新節點的插入
func (n *node) insertChild(numParams uint8, path string, fullPath string, handlers HandlersChain) {}
/<code>
流程如下：
使用addRoute方法從根節點添加一個新的路徑P，如果樹為空，則作為新節點直接插入，此時該節點為樹中的第一個節點(根節點)，path和fullPath值都為P。如果根節點存在子節點，則找到P跟根節點path的公共前綴，如果不存在公共前綴，則將新節點作為根節點的子節點加入，使用insertChild方法。如果存在公共前綴，則分裂當前節點，將根節點(當前節點)公共前綴後的內容獨立為一個子節點，並掛到當前節點下，更新indices；接著獲取P去掉公共前綴的第一個字符，判斷當前節點indices列表是否存在相同的字符，即判斷剩下的內容是要作為新節點加入，還是要繼續分裂，如果需要繼續分裂，則重複addRoute方法。
以下面這段代碼為例，
<code>r.GET("/q/query", func(context *gin.Context) {
context.String(http.StatusOK,"Hello "+context.Query("name"))
})
r.GET("/q/qaz/:name", func(context *gin.Context) {
context.String(http.StatusOK,"Hello "+context.Query("name"))
})
r.GET("/q/qaj/:name/l", func(context *gin.Context) {
context.String(http.StatusOK,"Hello "+context.Query("name"))
})
/<code>構建的trie樹為：
2.png
這裡需要指出的是，對於通配符，:xxxx或者*，會作為一個單獨的節點出現。
2.2. 查找過程
查找過程比較簡單，直接從根節點往下找，知道找到匹配的節點，過程如下：
3.SpringMVC
如下為一個簡單的示例：
<code>@RestController
public class HelloWorldController {
@RequestMapping("/hello/{name}")
public String antUser (@PathVariable("name") String name) {
return "hello : " + name;
}
}
/<code>
之前在介紹《SpringMVC加載流程》是說過，Spring MVC路由的加載是由RequestMappingHandlerMapping來處理的。該類會查找所有符合條件的Method上的註解，然後添加到父類AbstractHandlerMethodMapping的MappingRegistry中封裝為HandlerMethod進行緩存，直接以HashMap的方式。除了RequestMappingHandlerMapping外還有其他HandlerMapping,如SimpleUrlHandlerMapping,BeanNameUrlHandlerMapping等。
當查找符合的HandlerMethod時會遍歷所有的HandlerMapping，如果某HandlerMapping能夠處理，返回對應的HandlerExecutionChain,同時退出循環，由HandlerAdapter來執行具體的Method,Apdater會完成入參的注入。而RequestMappingHandler的動態路由則體現在HandlerMethod的查找上，該功能主要由AbstractHandlerMethodMapping的lookupHandlerMethod方法來實現。lookupHandlerMethod方法會遍歷MappingRegistry中的所有註冊對象，通過PatternsRequestCondition的getMatchingCondition來判斷，具體交由AntPathMatcher來實現。
AntPathMatcher主要用來做類URLs字符串匹配,可以匹配的規則如下：
- ？匹配一個字符
- *匹配0個或多個字符
- **匹配0個或多個目錄
具體實現在doMatch方法中。
即SpringMVC是通過遍歷所有註冊的Url，對每個Url應用AntPathMatcher來判斷當前請求的Url是否符合註冊的通配符寫法，從而找到對應的處理函數。
如下為簡單的示意圖：
4.參考
https://zh.wikipedia.org/wiki/Trie
閱讀更多 程序猿啊駝 的文章
