3个坑讲透ac路由器源码，面试必问不再慌

看了一堆教程还是不会写项目？别慌，问题不在你笨，而在没人带你啃源码。

很多应届生进厂写业务代码，感觉自己在搬砖。直到面试官甩出一句：“讲讲 ac路由器的核心路由匹配机制，为什么比暴力查找快？” 瞬间哑火。

这不是个例。这是面试必问的深水区。大家总以为路由就是查个表，其实 AcRouter 这种高性能实现，底层藏着不少门道。今天不整虚的，直接扒开源代码，带你把这块硬骨头嚼碎了咽下去。

入口定位：找到代码的“心脏”

要搞懂一个库，第一步不是看文档，是看入口。

我们在 GitHub 开源仓库里搜索 AcRouter，定位到核心包 core/router.go。别被几千行代码吓退，先找 NewRouter() 函数。这是所有路由器的构造函数，相当于汽车的发动机点火开关。

// core/router.go
type Router struct {tree *radixTree // 核心数据结构：基数树sync.RWMutex    // 读写锁，保证并发安全params         map[string]int // 参数名到索引的映射
}func NewRouter() *Router {r := &Router{tree:   newRadixTree(),params: make(map[string]int),}return r
}

逐行拆解：

tree *radixTree：这是灵魂。很多新手以为路由是用 map 存的，错了。map 查固定路径很快，但带参数（如 /user/:id）时，map 无能为力。这里用了基数树（Radix Tree），也叫压缩前缀树。它能把公共前缀合并，比如 /api/v1 和 /api/v2，只存 /api 节点，后面分叉。
sync.RWMutex：高并发场景下，多个 goroutine 同时注册路由或请求路由。不加锁？数据竞争直接崩溃。这里用读写锁，读多写少，性能最优。
params map[string]int：当匹配到 /user/:id 时，:id 这个参数名需要和实际值对应起来。这个 map 记录了参数在路径中的位置索引，方便后续提取。

看到没？入口很简单，但背后的 radixTree 才是大头。

核心片段：路由匹配的真实战场

接下来看最核心的 Lookup 函数。这是每次 HTTP 请求进来，路由器要做的第一件事：在树里找到对应的处理函数。

// core/router.go
func (r *Router) Lookup(method string, path string) (*Context, error) {r.RLock() // 加读锁defer r.RUnlock() // 函数结束自动释放锁node, ok := r.tree.search(method, path)if !ok {return nil, ErrNotFound // 没找到，返回404}ctx := &Context{Params: make(map[string]string),}// 遍历节点，提取动态参数for _, param := range node.params {value := path[param.start:param.end]ctx.Params[param.name] = value}ctx.handler = node.handlerreturn ctx, nil
}

逐行拆解：

r.RLock()：进入只读模式。如果这时候另一个 goroutine 在 AddRoute（写操作），它会被阻塞，直到 RLock 释放。这是 Go 并发安全的基石。
r.tree.search(method, path)：这里把 method（GET/POST）和 path 一起传入。在树的结构里，通常方法也是节点的一部分，或者作为节点的一个属性。基数树的 search 算法复杂度是 O(M)，M 是路径长度，而不是 O(N) 的 N 条路由数量。这就是为什么路由数量上万时，性能依然稳定。
path[param.start:param.end]：这是精华。在建树时，每个动态参数节点已经记录了它在原始路径中的起始和结束索引。匹配成功后，直接切片截取字符串，不用正则，不用解析，速度极快。
ctx.handler = node.handler：最后，把找到的处理函数挂载到上下文里，交给框架执行。

这段代码短小精悍，但涵盖了并发控制、高效查找、参数提取三个核心点。面试时，能讲清楚 start 和 end 索引是怎么来的，基本就稳了一半。

设计思想：为什么是基数树？

很多同学会问：用 map 不行吗？为什么非要搞个树？

来，做个对比实验。假设你有 1000 条路由，其中 900 条都是 /api/v1/user/... 开头。

方案 A：Map 你存 1000 个 key。查找 /api/v1/user/123 时，哈希计算，O(1) 找到。看似很快？但如果你要支持通配符 /api/v1/user/*，Map 就废了。你只能存一个特殊的 key，然后在 handler 里再写逻辑判断。代码混乱，性能下降。
方案 B：基数树 建树时，/api/v1/user 是一条公共路径。树里只存一个节点，指向一个子树。查找时，沿着 /api -> /v1 -> /user 走三步，直接到达目标。通配符节点也是一个特殊节点，匹配时直接截断剩余路径。

设计思想核心：

空间换时间：基数树存储的是压缩后的前缀，比散列在 map 里的完整 key 更省内存，且查找路径更短。
结构化匹配：把“静态路径”和“动态参数”在数据结构层面就分开处理。静态部分走树，动态部分走索引切片。
并发友好：树结构天然支持不可变节点（Immutable Node）。新增路由时，可以创建新节点链，旧请求继续用旧链，避免复杂的锁粒度问题。这就是 AcRouter 能扛住高并发的秘密。

记住这个思路：数据结构决定算法上限。选错数据结构，代码写得再漂亮也是徒劳。

手写简化版：别怕，其实就这么点事

理论懂了，手痒了？来，手写一个迷你版，感受下原理。

type Node struct {prefix     stringchildren   map[string]*NodeparamChild *Node // 专门放动态参数的子节点handler    http.HandlerFuncisParam    bool
}type MiniRouter struct {root *Node
}func (m *MiniRouter) AddRoute(path string, handler http.HandlerFunc) {node := m.rootparts := strings.Split(path, "/")for _, part := range parts {if part == "" {continue}if strings.HasPrefix(part, ":") {// 动态参数if node.paramChild == nil {node.paramChild = &Node{isParam: true}}node = node.paramChild} else {// 静态前缀if child, ok := node.children[part]; ok {node = child} else {newChild := &Node{prefix: part}node.children[part] = newChildnode = newChild}}}node.handler = handler
}func (m *MiniRouter) Lookup(path string) http.HandlerFunc {node := m.rootparts := strings.Split(path, "/")for _, part := range parts {if part == "" {continue}if node.paramChild != nil && (strings.HasPrefix(part, ":") || true) {// 简化逻辑：如果有参数子节点，且当前段是动态或需要匹配，则进入// 实际代码需更严谨的匹配逻辑if node.paramChild.isParam {node = node.paramChild} else if child, ok := node.children[part]; ok {node = child} else {return nil}} else if child, ok := node.children[part]; ok {node = child} else {return nil}}return node.handler
}

逐行拆解：

paramChild *Node：我们把动态参数节点单独拎出来，不和静态子节点混在一起。这样查找时，先查静态 children，查不到再查 paramChild。优先级清晰。
strings.Split(path, "/")：把路径拆分成段。虽然真实实现不会用 Split（性能开销大），但为了简化逻辑，这里先用 Split 理解结构。
strings.HasPrefix(part, ":")：判断是不是动态参数。如果是，就挂到 paramChild 下。
Lookup 中的逻辑：注意，这里为了简化，没做完整的参数值提取。真实场景中，进入 paramChild 后，需要记录 part 的值，并更新 Context。