gin源碼分析（路由）

為什麼gin路由用樹結構存儲，而不是hash map？

gin路由是字首樹存儲的，看到樹就下意識是性能的優化。可是想想不對勁，map性能才是最高的，map的時間複雜度O(1)，而樹結構的時間複雜度明顯是大于O(1)。其實不使用map的原因是，map無法實作動态參數，比如

/user/:id

，用map存儲無法對比，

/user/1

!=

/user/:id

，是以隻能把uri拆開進行對比處理，比如[

user

,

:id

]（當然也有可能拆成

u

,

ser

,

:id

,主要看有沒有共同的字首）。拆開之後，能實作動态參數了，這時候才是性能的考慮，當拆開來之後，如果還是簡單的使用數組存儲這些關鍵字的話，性能就降低很多。假設有n條路由，每條路由拆成m個項，那麼時間複雜度就是O(n·m)，用樹結構明顯小于O(n·m)

gin對路由做的一些優化

gin中的節點

type node struct {
	path      string
	indices   string
	wildChild bool
	nType     nodeType
	priority  uint32  // 自己和子孫路由的總數
	children  []*node
	handlers  HandlersChain
	fullPath  string
}
           

priority

是優先的意思，也是自己和子孫路由的總數，gin會把priority大的節點放在小的節點前面，這樣每次比對路由的時候大機率會先比對上，提高了性能。