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

Question

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

如何解决这个问题

Answer 1

Why not use a tree to store routing addresses?
As shown in the figure, each box is a Map
When you request /user/111/profile/books/222, break up the url first
['/', '111', 'profile', 'books', '222']
First search if there is a / node on the first layer
Then search if there is a 111 node on the second layer, if not enter the * node
Then search the third layer Does the layer have a profile node
and so on

Answer 2

https://github/bephp/router

This project does not use regular expressions, but cuts the URL according to "/" and saves it into a tree structure.

When mapping routes, it is equivalent to traversing the tree, and the complexity is O (log n).

The project is implemented in PHP, but the code is very small. It should be easy to understand.

Answer 3

Why can't we maintain a routing Dict? The value is the func corresponding to the key

Answer 4

The flexibility shown by regex in routing is difficult to replace by other technologies. You can also use regular rules to optimize performance. The principle is very simple. Combine regular rules and use a certain strategy to determine which one is based on the regular matching results

For example, there is

• /user/{pid}/profile

• /news

• /product/{pid}

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

Four routes

Use a regular #^(?|/user/(d+)/profile|/news|/product/(d+)()|/product/(d+)/comment/(d+)())$# to match

When the capture results include 1, 0, 2, and 3 groups respectively, we know that the 1st to 4th routes have been matched respectively. By automatically merging regular expressions through some code and assigning the number of capture groups => routing mapping, multiple regular expressions can be merged together for one match

Here is a trick to use (?|) to reset the capture group

Reference http://nikic.github.io/2014/0...