Trie 节点用数组还是哈希表存孩子？怎么取舍？

简化版

Trie 节点的孩子可以用数组，也可以用哈希表。

如果字符集很小并且固定，比如只包含 a-z，数组更快，访问下标是 O(1)，但会浪费空间。如果字符集很大或很稀疏，比如 Unicode、路径、URL、英文大小写混合，哈希表更省空间，但访问有哈希开销。

所以选择标准不是绝对性能，而是字符集大小、节点稀疏程度、内存预算和实现复杂度。

详细版

数组写法通常是：

children[26]
index = char - 'a'

它的优点是定位快、实现直观；缺点是每个节点都分配固定长度数组。即使某个节点只有 1 个孩子，也要占 26 个槽位。

哈希表写法通常是：

children: Map<char, TrieNode>

它只存真实存在的边，更适合稀疏字符集。

方案	优点	缺点
数组	快、简单、缓存友好	字符集大时浪费空间
哈希表	节省稀疏空间、字符集灵活	哈希开销、实现稍重

面试回答时可以先说：小字符集优先数组，大字符集或稀疏数据优先 Map。

完整版教学

1. Trie 节点到底要存什么

Trie 的每个节点代表一个前缀。

为了从当前前缀走到下一个前缀，节点需要保存「某个字符对应哪个子节点」。

例如单词 cat 的路径是：

root --c--> c --a--> ca --t--> cat

因此节点孩子结构的本质就是一个映射：

char -> childNode

数组和哈希表只是这个映射的两种实现。

2. 数组方案为什么快

如果字符集固定为小写英文字母，可以把字符直接转成数组下标。

idx = ch - 'a'
node.children[idx]

这不需要哈希，也不需要比较 key，访问路径非常直接。

当字符集又小又固定时，数组 Trie 的常数通常更好。

3. 数组方案为什么浪费空间

数组方案的问题是每个节点都要准备完整孩子槽位。

假设有 100000 个节点，每个节点放 26 个引用，就有：

100000 * 26 = 2600000

个引用槽。

但很多节点实际上只有 1 个或 2 个孩子，空槽位会很多。

4. 哈希表方案为什么更灵活

哈希表只为存在的边分配空间。

如果当前节点只有字符 a 和 z 两个孩子，Map 里就只有两条记录。

这对以下场景很有用：

场景	原因
Unicode 文本	字符集巨大
URL 路径	字符范围不固定
文件路径	分隔符和字符混杂
稀疏词典	大量节点孩子很少

缺点是哈希表对象本身也有额外开销，小数据量下未必省。

5. 还有没有折中方案

有。

常见折中包括：

小数组保存少量孩子，超过阈值再转 Map。
用排序数组保存 (char, child)，查找时二分。
用位图记录哪些字符存在，再配合紧凑数组。
对热门层使用数组，对深层稀疏节点使用 Map。

这些都是在时间和空间之间做更细的平衡。

6. 面试里怎么回答取舍

可以从 4 个维度说：

维度	数组更适合	Map 更适合
字符集	小且固定	大或动态
节点分支	分支较多	分支稀疏
性能	极致查找速度	内存更敏感
实现	简单	灵活

这样回答比只说「数组快、Map 省空间」更完整。

7. 一个小代码骨架

数组版本：

class Node {
    Node[] children = new Node[26];
    boolean end;
}

Map 版本：

class Node {
    Map<Character, Node> children = new HashMap<>();
    boolean end;
}

如果题目限定小写字母，数组是最常见写法；如果题目没有限定字符集，Map 更稳。

8. 常见误区与追问

误区：数组一定比 Map 更好。 数组访问快，但在大字符集和稀疏节点下会浪费大量空间。
误区：Map 一定更省内存。 小字符集、小数据量下，Map 对象和哈希桶也有额外开销。
误区：Trie 的复杂度只看单词长度。 还要考虑节点孩子结构带来的常数和内存成本。
追问：如果字符集是 ASCII 怎么选？ 可以用 128 或 256 长度数组，但要评估节点数量和空间预算。
追问：如果是中文词典怎么办？ 更常用 Map、压缩 Trie 或其他紧凑结构，固定大数组通常不合适。

简化版

详细版