第七届“四川工匠杯“职业技能大赛
2026/10/14 9:11:16
Q：好，那么我们来看tries了！你看了ppt，先给我讲一个intro，关于什么是tries（这看起来像try的复数！），为什么要有tries，tries大概怎么做，不需要深入，只要直白明了，注意保持专业，不要类比
A：Tries（读作“try”，不是“tries”），来自“retrieval”这个词，但为了和“tree”区分，发音改成“try”。
机制：
红黑树存储字符串
红黑树是一个二叉搜索树。每个节点存一个键（字符串）和一个值。
查找时，从根节点开始，把要查找的键和当前节点的键做
compareTo比较。
String.compareTo的物理动作：从两个字符串的第一个字符开始，逐个比较。如果字符相同，继续比较下一个；如果不同，返回差值；如果其中一个字符串先结束，按长度决定。所以，每次比较两个字符串，最坏情况下要扫描整个较短字符串的所有字符。如果树中有 N 个节点，查找路径长度约 log N，那么每次查找要做 log N 次
compareTo，每次compareTo可能扫描 L 个字符。总字符访问次数约 L × log N。如果很多字符串共享长前缀（比如 URL 都以
"http://www."开头），每次compareTo都要重复扫描这些前缀。这些前缀被反复比较了 log N 次。哈希表存储字符串
哈希表用
hashCode()计算键的哈希值，然后映射到数组索引。
String.hashCode()的物理动作：遍历字符串的每个字符，用h = 31 * h + c计算。必须遍历整个字符串，一个字符都不能少。如果键长度为 L，每次
put或get都要扫描 L 个字符来计算哈希值。然后可能还要在链表或开放地址中比较键（用equals），equals也要逐字符比较，直到找到不同或结束。所以，哈希表的查找命中需要扫描 L 个字符（计算哈希），加上可能的比较。查找未命中也需要扫描 L 个字符（计算哈希）。
为什么要有 Tries
之前学的符号表（红黑树、哈希表）有一个共同问题：它们需要检查整个键才能确定键是否存在。
红黑树：每次比较调用
compareTo，从第一个字符开始逐个比较，直到找到不同。如果两个键共享长前缀，每次比较都要扫描那些前缀。哈希表：必须遍历整个键来计算哈希值。即使键的第一个字符就足以区分，它也要读完所有字符。
如果键是字符串，而且很多字符串共享前缀（比如 URL、单词、IP 地址），这种“检查整个键”的动作是浪费的。
Tries 的核心思想：把字符存在节点里，而不是把键存在节点里。每个节点有 R 个子节点，对应字母表中的每个字符。查找时沿着键的每个字符走一步，不需要比较整个键。
物理结构
一个 Trie 是一棵树。根节点不存字符。从根出发，每条边对应一个字符。从根走到某个节点的路径上的字符序列，就是那个节点对应的键。
每个节点包含：
一个值（value），存这个键对应的数据。
一个长度为 R 的子节点数组，每个槽位存一个指向子节点的引用（或者 null）。
以字母表 R=26（小写字母）为例，每个节点有 26 个槽位，分别对应 'a' 到 'z'。当你在查找键 "sea" 时：
从根出发，取第一个字符 's'，走根节点的第 's'-'a' 个槽位。
到达下一个节点，取第二个字符 'e'，走该节点的第 'e'-'a' 个槽位。
到达下一个节点，取第三个字符 'a'，走该节点的第 'a'-'a' 个槽位。
到达节点后，检查该节点的值是否非空。非空则命中，返回该值；空则未命中。
字符不存储在节点里，而是隐式地由“走的是第几个槽位”来表示。节点本身只存值和子节点数组。
查找的物理动作
命中：沿着键的每个字符走一步，最后到达的节点有非空值，返回该值。
未命中：中途遇到 null 链接（说明没有这个前缀的键），或者走到最后节点但它的值为 null（说明这个前缀存在，但不是一个完整的键）。
关键物理优势：
未命中往往很快。如果键的第一个字符在根节点就没有对应链接，直接返回 null。不需要检查整个键。这是次线性的（sublinear）——只检查了少数几个字符。
命中需要检查所有 L 个字符，因为你要沿着整条路径走到终点。
空间代价
每个节点有 R 个槽位。如果 R=256（扩展 ASCII），每个节点就有 256 个引用，每个引用 8 字节，仅子节点数组就占 2048 字节。即使这个节点只有一个子节点，其他 255 个槽位都是 null，内存照样被占用。
这就是 Tries 的核心矛盾：查找快，但空间浪费大。PPT 第 21 页的表格里，R-way trie 对
actors.txt直接 “out of memory”，就是因为 R 太大（65,536 个 Unicode 字符）时，每个节点的数组太大，无法承受。一句话总结
Tries 用“逐字符走路径”代替“比较整个键”，查找命中检查 L 个字符，查找未命中通常只检查少数几个字符，比哈希和红黑树对字符串键更快。代价是每个节点要维护 R 个槽位，空间消耗随 R 增大而急剧膨胀。后续的 TST（ternary search trie）就是用来解决这个空间问题的。