路由表数据结构：哈希表、Trie树、基数树(Radix Tree)的原理与对比
路由表的核心，说白了就是「查得快、存得稳」。我做了这么多年网关，见过太多因为路由表设计不合理导致的性能事故。今天咱们就聊聊三种最常用的数据结构：哈希表、Trie树、基数树。
嗯，先别急着背概念。咱们从实际场景出发，看看每种结构到底解决了什么问题。
哈希表：简单粗暴，但有坑
哈希表大家都不陌生。把IP地址算个哈希值，然后直接定位到表项。时间复杂度O(1)，听起来很完美对吧？
但我在项目中遇到过一个大坑——哈希冲突。你想想看，几百万条路由条目，哈希冲突几乎是必然的。冲突一多，查找性能就从O(1)退化到O(n)。
哈希表的优点很明显：
- 查找速度快，平均O(1)
- 实现简单，代码量少
- 适合精确匹配场景
缺点也致命：
- 不支持前缀匹配（路由查找最常用的就是最长前缀匹配）
- 哈希冲突难以完全避免
- 扩容时性能抖动大
Trie树：天生的前缀匹配选手
Trie树，也叫字典树。它的设计思路很巧妙——把IP地址按bit位拆开，每个bit决定走左子树还是右子树。
举个例子，路由条目 192.168.1.0/24，在Trie树里就是一条从根节点出发，经过24次bit判断到达的路径。查找时，顺着bit一路往下走，最后停下的节点就是匹配结果。
我记得有一次做高性能网关选型，对比了多种方案。Trie树在路由条目少于10万条时表现不错，但条目一多，树的高度就成了瓶颈。IPv4地址32位，最坏情况要查32层，每次都要访问内存。
Trie树的优缺点：
- 支持最长前缀匹配，天生适合路由查找
- 插入和删除操作简单
- 但树的高度固定，IPv4是32层，IPv6是128层
- 内存占用大，每个节点只存一个bit
基数树(Radix Tree)：压缩的艺术
基数树是Trie树的优化版。它把连续相同的bit路径压缩成一个节点。说白了，就是「能合并的就合并，别浪费内存」。
举个例子，路由条目 192.168.0.0/16 和 192.168.1.0/24，在Trie树里前16个bit是重复的路径。基数树直接把这16个bit压缩成一个节点，查找时一次跳过。
我个人习惯用基数树做核心路由表。Linux内核的路由表用的就是LPC-trie，其实就是基数树的一种变体。为什么？因为它在内存和性能之间取得了很好的平衡。
基数树的优势：
- 节点合并，内存占用比Trie树少很多
- 查找时一次跳过多个bit，减少内存访问次数
- 支持高效的插入和删除
- 适合大规模路由表
当然也有代价：
- 实现复杂度高，代码容易出bug
- 压缩和解压需要额外计算
- 在某些极端场景下，性能不如精心优化的哈希表
三种结构的对比
咱们用一张表来总结，这样更直观：
| 特性 | 哈希表 | Trie树 | 基数树 |
|---|---|---|---|
| 查找时间复杂度 | O(1) 平均 | O(W) | O(W) 但常数更小 |
| 前缀匹配支持 | 不支持 | 支持 | 支持 |
| 内存占用 | 低 | 高 | 中 |
| 实现复杂度 | 低 | 中 | 高 |
| 适用场景 | 精确匹配、会话表 | 小规模路由表 | 大规模路由表 |
实战中的选择建议
说了这么多理论，到底该怎么选？我分享几个经验：
- 路由条目少于1万条：用Trie树就够了，实现简单，维护成本低。
- 路由条目在1万到100万之间：上基数树。Linux内核的选择不会错。
- 需要精确匹配的场景：比如五元组会话，用哈希表。但记得做好冲突处理。
- 混合使用：我见过的最佳实践是哈希表做缓存 + 基数树做主表。热点路由走缓存，冷门路由走基数树。
最后说一句，没有银弹。每种数据结构都有自己的适用场景。关键是要理解你的业务特点——路由条目的分布、查找的频率、对延迟的要求。搞清楚了这些，选型就水到渠成了。