1. 引言
在本教程中，我们将对比两种常用的数据结构：哈希表（Hash Table） 和 前缀树（Trie）。我们会从一个实际问题出发，分别使用这两种结构来解决它，然后从多个维度进行对比分析，帮助你理解它们的适用场景与优劣。
2. 问题描述
我们的问题是：
给定一个字符串集合（字典）{s₁, s₂, ..., sₙ} 和一个目标字符串 t，判断 t 是否存在于该字典中。
这个问题可以用哈希表或 Trie 来高效解决。
3. 哈希表解法
3.1. 构建哈希表
我们可以使用 哈希表 来存储字典中的所有字符串。哈希表是一种将键（key）映射到值（value）的结构，非常适合用于快速查找。
每个字符串作为 key 插入哈希表中。插入时，需要通过 哈希函数（hash function） 将字符串转换为整数索引，用于定位其在哈希表中的位置。
常见的哈希函数之一是 多项式滚动哈希函数：
$$ hash(s) = \sum_{i=0}^{n-1} s[i] \cdot p^i \mod m $$
其中 p 和 m 是两个预设的正整数。
哈希函数需要遍历整个字符串，因此其时间复杂度为 O(n)，其中 n 是字符串长度。
3.2. 哈希表查找
查找时，我们对目标字符串 t 同样计算哈希值，然后在哈希表中查找是否存在该值。
计算哈希值的时间复杂度是 O(n)，而查找哈希表的时间是 O(1)（假设哈希函数分布均匀），所以整体查找时间复杂度为 O(n)。
✅ 优点：查找速度快（平均情况下）
❌ 缺点：无法高效支持前缀匹配、自动补全等操作
4. Trie 解法
4.1. Trie 构建原理
Trie（又称前缀树）是一种树形结构，用于高效存储和检索字符串集合。每个节点代表一个字符，路径代表字符串。
构建 Trie 时，我们从根节点开始，逐字符插入。如果某个字符的路径不存在，就新建节点。插入完成后，将最后一个节点标记为“完整词节点”。
例如，构建包含 {to, tea, ten, in, inn} 的 Trie：
插入新词 teach 时，我们沿 tea 路径继续插入 c 和 h，并标记 h 节点为完整词节点：
构建过程需要逐字符处理，时间复杂度也为 O(n)。
4.2. Trie 查找机制
查找时，我们从根节点出发，沿着字符路径逐层向下。如果路径存在且最后一个节点是完整词节点，则字符串存在。
查找时间复杂度同样是 O(n)，但实际中可能更早失败（例如前缀不匹配时），从而节省时间。
✅ 优点：支持前缀搜索、自动补全、按字典序输出
❌ 缺点：内存消耗略高（需存储额外节点和指针）
5. 对比分析
| 对比维度 | 哈希表 | Trie |
|---|---|---|
| 查找速度 | O(n)，但整体更快 |
O(n)，但可提前失败 |
| 内存占用 | 通常较低（无共享结构） | 通常较高（有共享结构，节省前缀内存） |
| 支持操作 | 仅支持完整字符串匹配 | 支持前缀匹配、自动补全、字典序输出 |
| 插入复杂度 | O(n) |
O(n) |
| 适用场景 | 快速全词查找（如字典、缓存） | 搜索建议、自动补全、拼写检查 |
5.1. 查找速度对比
虽然两者查找时间复杂度相同，但实际表现不同：
- 哈希表：始终计算整个字符串的哈希值，查找快但无法提前失败。
- Trie：查找过程中一旦发现路径中断即可提前终止，效率更高（尤其在未命中时）。
5.2. 内存占用对比
- 哈希表：内存分配固定，存储字符串本身。
- Trie：每个节点需额外存储字符链接和标记，但共享前缀可以节省空间。
5.3. 应用场景对比
- 哈希表适合：全词匹配（如缓存、字典、去重）
- Trie 适合：前缀匹配（如搜索引擎、输入法、拼写检查）
6. 总结
| 项目 | 哈希表 | Trie |
|---|---|---|
| 时间复杂度 | O(n) |
O(n) |
| 内存占用 | 较低 | 较高（但前缀共享优化） |
| 支持操作 | 仅完整匹配 | 支持前缀匹配、自动补全、字典序输出 |
| 适用场景 | 快速查找、缓存、去重 | 搜索建议、输入法、拼写检查 |
✅ 哈希表 更适合需要快速查找全词的场景。
✅ Trie 更适合需要前缀匹配、自动补全或字典序输出的场景。
⚠️ 踩坑提醒：不要盲目选择 Trie，除非你确实需要它的前缀特性。否则哈希表通常更简单、更快、更省内存。