高级数据结构

字典树

它的卖点：前缀查询

哈希表查一个词是 O(1)（平均），字典树是 O(len)。听起来更差 —— 但字典树能做哈希表做不到的事：前缀查询。

「以 app 开头的词有哪些」，哈希表只能全表扫描； 字典树顺着 a → p → p 走三步，剩下的子树就是全部答案。

实测 20 万个词、200 个三字前缀，把每个前缀下的词全收集出来：

Trie 走到前缀节点再 DFS        4 ms
数组 filter(startsWith) 全表扫  267 ms      → 73×
（两者结果一致：都命中 2344 个词）

⭐ 这是自动补全、IP 路由表这类场景选它的原因 —— 也是选它的唯一硬理由。 下面会看到，除了前缀查询，它在各方面都不如哈希表。

⚠️ 「与词典规模无关」：步数无关，耗时很有关

常见的说法是「这三步跟词典里有 100 个词还是 1000 万个词毫无关系」。 步数确实无关，耗时不是。 实测（8 字词，10 万次查询，每组重复 5 次取中位数）：

词典规模 全命中查询 全不命中 平均走过的层数
100 7.7 ms 3.1 ms 8.00
10,000 31.5 ms 7.1 ms 8.00
200,000 90.2 ms 33.1 ms 8.00
1,000,000 120.2 ms 53.3 ms 8.00

🚨 走的层数一模一样（8.00），耗时却涨了 15.6 倍。 涨的不是步数，是每一步的代价 —— 词典越大节点越多、越分散，每次 children.get(ch) 越可能是一次 cache miss。

⚠️ 这里有个坑我差点栽进去：第一版我用随机词做 probe，词典小的时候 大部分 probe 在第一二层就断了，测出来的「涨幅」里混着命中率变化。 把 probe 固定成「全部来自词典」（必走满 8 层）之后，才是规模的纯效应。 📌 比较两组耗时之前，先确认两组做的事情一样多（上表最后一列就是为此存在的）。

⭐ 所以准确的说法是：渐进复杂度与规模无关，常数不是。 面试答 O(len) 没问题，但别把它理解成「一百万词和一百词一样快」。

结构

每个节点代表「一个前缀」，边代表一个字符：

插入 "cat" "car" "card" "dog" 之后：

  root
   ├─ c ─ a ─ t*
   │       └─ r* ─ d*
   └─ d ─ o ─ g*

  * 表示「这里是一个完整单词的结尾」

🚨 那个 * 标记（isEnd）不能省。没有它就分不清 「car 是一个词」和「car 只是 card 路上的一段」。

省掉之后 search 就退化成了 startsWith。插入 cat/car/card/dog 后实测：

search("car")     正确 true    省掉 isEnd 得 true
search("ca")      正确 false   省掉 isEnd 得 true    ❌
search("c")       正确 false   省掉 isEnd 得 true    ❌
search("do")      正确 false   省掉 isEnd 得 true    ❌
search("cards")   正确 false   省掉 isEnd 得 false
search("dog")     正确 true    省掉 isEnd 得 true

6 个用例错 3 个，方向完全一致：只会把「前缀」误判成「完整单词」， 不会反过来漏掉真单词。 ⚠️ 于是只测「词典里的词查得到吗」这一类用例，它 100% 通过 —— 要测出来必须专门查一个是前缀但不是词的串。

class Trie {
  constructor() { this.root = { children: new Map(), isEnd: false }; }

  insert(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) {
        node.children.set(ch, { children: new Map(), isEnd: false });
      }
      node = node.children.get(ch);
    }
    node.isEnd = true;                // 🚨 走完才标记
  }

  // 沿着 word 走，走不通返回 null
  _walk(word) {
    let node = this.root;
    for (const ch of word) {
      node = node.children.get(ch);
      if (node === undefined) return null;
    }
    return node;
  }

  search(word) { const n = this._walk(word); return n !== null && n.isEnd; }

  startsWith(prefix) { return this._walk(prefix) !== null; }
}

⭐ search 和 startsWith 只差最后那个 isEnd 判断 —— 这正是那个标记存在的全部意义。

Map 版 vs 长度 26 的数组版：差距比想象的小

流传的说法是「字符集确定时数组版更快，省掉哈希」。 实测（20 万个 8 字词，同一进程、预热后、9 次取中位数）：

插入 全命中查询
Map 版 187 ms 199 ms
长度 26 数组版 220 ms 156 ms

⚠️ 说法只对了查询那一半（数组版快 1.27×），插入反而是 Map 版快 1.18×。 而且两个方向的差距都不到 30% —— 远没有「省掉哈希」这个说法暗示的那么大。 原因不难想：每建一个节点就要 new Array(26).fill(null)， 而 8 字随机词的 Trie 里绝大多数节点只有一两个孩子，那 26 个槽基本是空的。 空间上的代价见下面「复杂度与代价」那张表（数组版反而多占 31%）。

📌 测这一组时踩了个坑：第一次分两轮跑，量出「插入慢 1.75×、查询快 1.36×」， 和统一测量差了不少。同一篇文章里的数字必须来自同一套测量条件， 否则读者拿两个数字一对比就会发现打架，而作者自己看不出来。

⭐ 判据：查询远多于插入、字符集小且稠密才轮到数组版； 否则 Map 版更均衡，而且字符集不限于小写字母时它是唯一选择。

收集某个前缀下的所有词

自动补全就是「走到前缀节点，然后把子树里所有 isEnd 的路径收集出来」：

function collect(trie, prefix) {
  const node = trie._walk(prefix);
  if (node === null) return [];

  const res = [];
  const dfs = (cur, path) => {
    if (cur.isEnd) res.push(prefix + path);
    for (const [ch, child] of cur.children) dfs(child, path + ch);
  };
  dfs(node, '');
  return res;
}

⚠️ 这是回溯的形态，但没有「撤销」—— 因为 path + ch 每次都产生新字符串，没有共享状态要还原。 用一个共享数组 path.push(ch) 的话，就必须配 path.pop()。

复杂度与代价

操作 复杂度
插入 / 查询 / 前缀判断 O(len)
收集前缀下所有词 O(结果总长度)
空间 O(所有单词的总字符数)

🚨 空间是字典树的软肋，而且差距比「还费」这个词严重得多。 实测 10 万个词（每组在独立进程里测，避免上一组的垃圾算到下一组头上）：

词典特征 节点数 / 字符数 字符串数组 Trie(Map) Trie(26 数组)
几乎无公共前缀（随机 10 字） 707,559 / 1,000,000 = 0.71 0.8 MB 153.0 MB（191×） 199.8 MB（250×）
大量公共前缀（200 词根 + 3 字后缀） 175,717 / 986,560 = 0.18 0.8 MB 39.6 MB（50×） 49.6 MB（62×）

⚠️ 无公共前缀时是字符串数组的 191 倍 —— 不是「还费一点」，是两个数量级。 每个节点摊到 227 字节（Map 版），而它承载的信息只有一个字符。

⭐ 公共前缀确实有效：节点/字符比从 0.71 压到 0.18，内存从 191× 降到 50×。 但即使在最有利的情况下，它仍比数组费 50 倍。

和哈希表正面比一次

同一批 20 万个 8 字词，Trie(Map) 对 Set：

Trie Set
查「这个词在不在」（全命中） 199 ms 8 ms Set 快 23.7×
查「这个词在不在」（全不命中） 70 ms 5 ms Set 快 13.9×
内存 213.8 MB 5.0 MB Set 省 42.8×
查「以 xxx 开头的词」 4 ms 267 ms（全表扫） Trie 快 73×

⭐ 这张表就是整篇的结论：除了最后一行，哈希表全面碾压。 而最后一行哈希表根本做不了，只能退化成全表扫描。

👉 所以判据只有一条：要不要前缀查询。 要，用 Trie；不要，用哈希表， 不用犹豫，也不用觉得「Trie 更高级」。

⚠️ 面试里常见的追问是「为什么不用哈希表」，答「哈希表做不了前缀查询」就够； 如果对方追问代价，上面这张表随便挑一行。

一个容易忽略的用法：把数字按位存进 Trie

Trie 不限于字符串。把整数按二进制位（从高位到低位）插进一棵 0/1 两叉的 Trie， 就能 O(32) 地回答「数组里和 x 异或最大的数是多少」—— 从高位开始，每一位都优先往「与 x 当前位相反」的分支走。

📌 这一类题（最大异或对）在面试里出现频率不高，但一旦出现， 不知道这个套路基本做不出来。知道「按位建 Trie」这个词就够。

下一步

前面三种结构都是「树」。图的表示与遍历 往前走一步 —— 允许环，于是所有遍历都必须记 visited。

练习

勾选记录做过哪些，0 / 5 道。进度只存在这台设备的浏览器里；同一道题在别篇勾过，这里也会显示已做。

⚖️ 这里只给题号、官方标题和链接，不复述题面 —— 平台的题面文字有版权。 「这题考什么」写的是它对应本篇的哪个点，那部分是本站自己的内容。