如何编写一个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