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...