java - 如何编写一个web 框架的 url 路由

Question

如果路由都只是 url 字符串完全匹配的，我可以用 hashmap ，理想情况 O(1) 复杂度。
但是我想在 url 匹配中支持 通配符，那么最简单的实现方法，我就直接用正则了，但是匹配复杂度就变成 O（n）了，这样感觉不是很好。。。

如何解决这个问题

Answer 1

為什麼不用樹來存路由的位址呢?
如圖,每一個方框都是一個Map
當你請求/user/111/profile/books/222的時候先將url 打散
['/' , '111' , 'profile' , 'books' , '222']
先搜尋第一層有沒有一個/ 節點
然後搜尋第二層有沒有一個111 節點,沒有的話進入* 節點
然後所搜第三層有沒有一個profile 節點
以此類推

Answer 2

https://github/bephp/router

這個項目沒有使用正規則，而是將URL依照"/"切割然後保存成為樹狀結構。

映射路由的時候，相當於對樹進行遍歷，複雜度為 O (log n)。

專案是PHP實現的，不過程式碼很少。應該很容易看懂的。

Answer 3

為什麼不能維護一個路由Dict。值是key對應的func

Answer 4

正則在路由這塊展示的彈性是其他技術很難取代的。一樣用正規，也可以把效能最佳化，原理很簡單，合併正規，透過某種策略來依據正規匹配的結果來判斷哪個

比如有

• /user/{pid}/profile

• /news

• /product/{pid}

• /product/{pid}/comment/{cid}

四個路由

用一個正規 #^(?|/user/(d+)/profile|/news|/product/(d+)()|/product/(d+)/comment/(d+)())$# 匹配

當捕獲結果分別有 1,0,2,3組的時候，我們就知道分別匹配到了第1～4個路由。透過一些程式碼自動合併正規、分配捕獲組數量=>路由的映射，就可以把多個正則合併到一起一次匹配

這裡有個技巧是用(?|)來重置捕獲組

參考 http://nikic.github.io/2014/0...