Trie 空间占用太大时有哪些优化办法？
简化版
Trie 空间大，主要因为节点多、每个节点还要存孩子指针。
常见优化包括：用 Map 替代固定数组、压缩单孩子链、用位图加紧凑数组、共享后缀形成 DAWG、把字符串边压缩成片段、使用对象池减少分配开销。
面试回答时要先说清空间大的来源，再按「孩子表示」「路径压缩」「节点共享」「工程内存管理」几个方向展开。
详细版
Trie 的时间复杂度很漂亮，但空间常数不小。
| 问题来源 | 说明 |
|---|---|
| 节点数量多 | 每个字符可能对应一个节点 |
| 孩子槽位浪费 | 固定数组里很多空引用 |
| 对象开销 | 每个节点是独立对象 |
| 指针开销 | 引用本身占内存 |
优化思路：
稀疏孩子 -> Map / 位图
长单链 -> Radix Tree
重复后缀 -> DAWG
大量对象 -> 对象池 / 数组化存储不同优化会影响查询速度和实现复杂度，要结合场景取舍。
完整版教学
1. Trie 为什么容易吃内存
Trie 把字符串拆成字符路径。
如果有大量长字符串，就会产生很多节点。更麻烦的是，每个节点还要保存孩子结构、结束标记和可能的计数字段。
如果用固定数组：
children[26]哪怕一个节点只有 1 个孩子，也要保留 26 个槽位。
2. 优化方向一：孩子结构换成 Map
当节点很稀疏时，用 Map 只存真实存在的孩子。
| 孩子结构 | 适合场景 |
|---|---|
| 固定数组 | 小字符集、分支较密 |
| HashMap | 大字符集、分支稀疏 |
| TreeMap | 需要有序遍历 |
第一层优化通常就是别让每个节点都背着一大堆空孩子槽。
3. 优化方向二：路径压缩
很多 Trie 会出现长长的单孩子链。
例如：
c -> o -> m -> p -> u -> t -> e -> r如果中间没有分叉，可以把这段压缩成一条边：
"computer"这就是压缩 Trie、Radix Tree 的思想。它减少节点数量，但匹配时要比较字符串片段。
4. 优化方向三：位图加紧凑数组
对于固定字符集，可以用位图表示哪些孩子存在，再用紧凑数组保存真实孩子。
例如 26 个小写字母可以用一个整数位图：
bitmap = 000...10101
children = [nodeA, nodeC, nodeE]查找某个字符时，先看对应 bit 是否存在，再计算它在紧凑数组中的排名。
这种方案常数更复杂，但空间更紧。
5. 优化方向四：共享后缀
普通 Trie 主要共享前缀，不共享后缀。
如果很多单词有相同后缀，比如：
running
walking
talking后缀 ing 可能重复存储。
DAWG 这类结构会尝试合并等价后缀状态，从而进一步压缩空间。
6. 优化方向五：数组化和对象池
在 Java、JavaScript 等语言里，大量小对象会带来对象头和 GC 压力。
可以考虑：
- 用数组保存节点字段；
- 用整数下标代替对象引用；
- 使用对象池复用节点；
- 批量构建后转成只读紧凑结构。
这种优化更偏工程，适合大词典、只读索引、搜索提示等场景。
7. 取舍怎么说清楚
可以用表格回答：
| 优化 | 优点 | 代价 |
|---|---|---|
| Map 孩子 | 省空槽 | 哈希开销 |
| 路径压缩 | 少节点 | 边匹配更复杂 |
| 位图紧凑数组 | 空间紧凑 | 实现复杂 |
| DAWG | 共享后缀 | 构建复杂 |
| 数组化节点 | 缓存友好 | 可维护性下降 |
面试官真正想听的是：你知道 Trie 空间问题来自哪里，也知道优化不是免费的。
8. 常见误区与追问
- 误区：Trie 的空间复杂度只是
O(n)，所以不用管。 大 O 忽略了节点对象、指针和空槽这些高常数。 - 误区：把数组换成 Map 一定省空间。 小字符集且节点分支较密时，Map 的额外对象开销可能更大。
- 误区：压缩 Trie 查询一定更快。 节点少了，但每条边可能要比较字符串片段。
- 追问：只读词典怎么优化？ 可以批量构建后做数组化、压缩边和紧凑编码。
- 追问：中文词库为什么更需要优化？ 字符集大、固定数组不可行，通常要用 Map、压缩结构或专门索引。