字典树和哈希表相比，各有什么优缺点？该怎么选？
简化版
哈希表：等值查找平均 O(1)（但要算整串哈希，仍和串长有关）、省内存、实现简单，但不支持前缀匹配、无序、有哈希冲突。Trie：查找稳定 O(L)、天然支持前缀匹配和字典序遍历、无哈希冲突、公共前缀省空间，但空间开销大、实现复杂。要前缀操作/自动补全/有序 → Trie；只做等值查找、省内存 → 哈希表。
详细版
| 维度 | 哈希表 | 字典树 Trie |
|---|---|---|
| 等值查找 | 平均 O(1)*，最坏 O(n) | O(L) 稳定 |
| 前缀匹配 | ❌ 不支持 | ✅ 天然支持 O(前缀长) |
| 按字典序遍历 | ❌ 无序 | ✅ 按序 DFS 即可 |
| 哈希冲突 | 有（需处理） | 无 |
| 空间 | 较省 | 大（节点多、指针稀疏） |
| 公共前缀 | 不利用 | 共享，省空间 |
| 实现复杂度 | 简单 | 较复杂 |
（*哈希的 O(1) 不含算哈希值的 O(L)；严格说等值查找哈希和 Trie 都要 O(L) 级处理字符串。）
完整版教学
一、等值查找：其实都离不开 O(L)
很多人以为「哈希 O(1) 完胜 Trie O(L)」，这不准确。哈希表查一个字符串，必须先计算整个字符串的哈希值，这本身就是 O(L)；还可能有冲突要逐个比较。所以对字符串来说，哈希的等值查找也是 O(L) 级别，只是常数更小、更简单。
Trie 的 O(L) 是稳定的——没有冲突、不随集合增大退化。哈希在冲突严重或需要 rehash 时会抖动。所以「谁更快」在等值查找上其实差别不大，真正的分水岭在前缀操作。
二、Trie 的杀手锏：前缀相关操作
这是 Trie 存在的核心理由，哈希表根本做不到：
- 前缀匹配：「有没有以
app开头的词」——Trie 走到app节点看有没有子树即可；哈希表把字符串打散成哈希值，前缀信息全丢了，只能遍历所有 key 逐个判断（O(N×L)）。 - 自动补全：列出所有以某前缀开头的词——Trie 收集子树；哈希无能为力。
- 字典序遍历：Trie 按 a→z DFS 天然有序；哈希表完全无序。
- 最长前缀匹配（如 IP 路由）：Trie 沿路径走到最深匹配；哈希做不到。
一句话：只要涉及「前缀、有序」，就是 Trie 的主场。
三、哈希表的优势：省内存、简单
Trie 的代价是空间——节点多、定长数组子指针稀疏（见复杂度专题）。哈希表则紧凑得多，只存实际的键值对。所以：
- 内存敏感、只做等值查找（判断词在不在、去重、计数）→ 哈希表更划算。
- 哈希表实现简单、语言内置（
HashMap/HashSet），开箱即用；Trie 通常要手写。
四、公共前缀：Trie 省空间的一面
虽然 Trie 整体空间开销大，但在前缀重合度高的数据上，它能靠共享前缀省空间。比如存大量 com.example.xxx 的包名、或大量共享前缀的 URL/IP，Trie 让公共前缀只存一份。而哈希表把每个完整字符串都存一遍，反而更费。所以「前缀重合度」是权衡的关键变量：重合度高 Trie 可能更省，重合度低 Trie 浪费严重。
五、怎么选（结论）
- 需要前缀匹配 / 自动补全 / 最长前缀 / 字典序 → Trie（无可替代）。
- 只需等值查找 / 去重 / 计数，且内存敏感 → 哈希表（更省更简单）。
- 前缀重合度极高的大规模字符串 → Trie（或压缩 Trie）可能既快又省。
- 前缀几乎不重合、随机字符串 → 哈希表（Trie 会退化、浪费空间）。
六、常见误区与追问
| 考点 | 正确口径 |
|---|---|
| 等值查找 | 哈希表通常更简单省空间 |
| 前缀查询 | Trie 天然支持 |
| 有序遍历 | Trie 可按字符顺序 DFS 输出 |
HashMap: key -> value
Trie: prefix path -> subtree of candidates哈希表回答“这个完整 key 在不在”，Trie 更擅长回答“这个前缀下面有什么”。
- 误区：Trie 在所有字符串查找中都优于哈希表。 只做等值查找时，哈希表通常实现更简单、空间更省。
- 误区：哈希表不能处理字符串。 哈希表当然能处理完整字符串 key，只是不擅长枚举共同前缀下的所有词。
- 误区：Trie 一定更省空间。 公共前缀多时 Trie 省空间；公共前缀少时孩子指针可能更浪费。
- 追问：自动补全该选谁？ Trie 更合适，因为可以定位前缀节点后遍历候选。
- 追问：URL 路由匹配常用什么？ 静态前缀多时可用 Trie 或压缩 Trie；纯等值路由也可用哈希表。
- 追问：复杂度怎么比较？ 哈希表平均查找要计算整个 key 的哈希，Trie 逐字符走 O(L)，两者都和字符串长度有关。
七、加强记忆
Trie vs 哈希表：等值查找两者都是 O(L) 级（哈希要算整串哈希、有冲突；Trie 稳定无冲突）。分水岭是前缀操作——Trie 天然支持前缀匹配/自动补全/最长前缀/字典序（哈希做不到），且公共前缀共享；代价是空间大、实现复杂。哈希表省内存、简单、内置，但无序、不支持前缀。要前缀/有序选 Trie，只等值查找且省内存选哈希。