如果路由都只是 url 字符串完全匹配的，我可以用 hashmap ，理想情况 O(1) 复杂度。但是我想在 url 匹配中支持 通配符，那么最简单的实现方法，我就直接用正则了，但是匹配复杂度就变成 O（n）了，这样感觉不是很好。。。
如何解决这个问题
认证高级PHP讲师
为什么不用树来存路由的地址呢?如图,每一个方框都是一个 Map当你请求 /user/111/profile/books/222的时候先将 url 打散['/' , '111' , 'profile' , 'books' , '222']先搜索第一层有没有一个 / 节点然后搜索第二层有没有一个 111 节点 ,没有的话进入 * 节点然后所搜第三层有没有一个 profile 节点以此类推
https://github/bephp/router
这个项目没有使用正则，而是将URL按照"/"切割然后保存成为树形结构。
映射路由的时候，相当于对树进行遍历，复杂度为 O (log n)。
项目是PHP实现的，不过代码很少。应该很容易看明白的。
为什么不能维护一个路由Dict。值是key对应的func
正则在路由这块展示的灵活性是其他技术很难替代的。一样用正则，也可以把性能优化，原理很简单，合并正则，通过某种策略来依据正则匹配的结果来判断哪个
比如有
/user/{pid}/profile
/news
/product/{pid}
/product/{pid}/comment/{cid}
四个路由
用一个正则 #^(?|/user/(d+)/profile|/news|/product/(d+)()|/product/(d+)/comment/(d+)())$# 匹配#^(?|/user/(d+)/profile|/news|/product/(d+)()|/product/(d+)/comment/(d+)())$# 匹配
#^(?|/user/(d+)/profile|/news|/product/(d+)()|/product/(d+)/comment/(d+)())$#
当捕获结果分别有 1,0,2,3个组的时候，我们就知道分别匹配到了第1～4个路由。通过一些代码自动合并正则、分配捕获组数量=>路由的映射，就可以把多个正则合并到一起一次匹配
这里有个技巧是用(?|)
(?|)
为什么不用树来存路由的地址呢?
如图,每一个方框都是一个 Map
当你请求 /user/111/profile/books/222的时候先将 url 打散
['/' , '111' , 'profile' , 'books' , '222']
先搜索第一层有没有一个 / 节点
然后搜索第二层有没有一个 111 节点 ,没有的话进入 * 节点
然后所搜第三层有没有一个 profile 节点
以此类推
https://github/bephp/router
这个项目没有使用正则，而是将URL按照"/"切割然后保存成为树形结构。
映射路由的时候，相当于对树进行遍历，复杂度为 O (log n)。
项目是PHP实现的，不过代码很少。应该很容易看明白的。
为什么不能维护一个路由Dict。值是key对应的func
正则在路由这块展示的灵活性是其他技术很难替代的。一样用正则，也可以把性能优化，原理很简单，合并正则，通过某种策略来依据正则匹配的结果来判断哪个
比如有
/user/{pid}/profile
/news
/product/{pid}
/product/{pid}/comment/{cid}
四个路由
用一个正则
#^(?|/user/(d+)/profile|/news|/product/(d+)()|/product/(d+)/comment/(d+)())$#匹配#^(?|/user/(d+)/profile|/news|/product/(d+)()|/product/(d+)/comment/(d+)())$#匹配当捕获结果分别有 1,0,2,3个组的时候，我们就知道分别匹配到了第1～4个路由。通过一些代码自动合并正则、分配捕获组数量=>路由的映射，就可以把多个正则合并到一起一次匹配
这里有个技巧是用
当捕获结果分别有 1,0,2,3个组的时候，我们就知道分别匹配到了第1～4个路由。通过一些代码自动合并正则、分配捕获组数量=>路由的映射，就可以把多个正则合并到一起一次匹配(?|)
这里有个技巧是用(?|)来重置捕获组🎜 🎜参考 http://nikic.github.io/2014/0...🎜