并发场景下 Trie 如何保证读写安全？
简化版
并发访问 Trie 时，核心问题是读线程不能看到写入一半的结构，写线程之间也不能互相破坏节点关系。
简单方案是给整个 Trie 加读写锁：查询加读锁，插入和删除加写锁。读多写少时还可以用不可变 Trie、Copy-on-Write、版本化根节点等方式，让读请求无锁或少锁。
具体方案要看读写比例、一致性要求和更新频率。
详细版
Trie 插入不是一个原子动作，它会逐层创建节点并修改孩子指针。
如果没有同步，读线程可能看到：
- 某个孩子指针刚创建但字段没初始化；
- 单词路径存在但
isEnd还没设置； - 删除过程中节点被清理导致空指针问题。
常见方案：
| 方案 | 特点 |
|---|---|
| 全局互斥锁 | 简单但并发低 |
| 读写锁 | 读多写少较合适 |
| 分段锁 | 并发更高，实现复杂 |
| Copy-on-Write | 读无锁，写复制路径 |
| 不可变快照 | 适合批量更新 |
完整版教学
1. Trie 并发问题来自哪里
Trie 的读操作通常是沿路径查找。
写操作则可能做这些事：
- 创建新节点；
- 修改某个孩子指针；
- 设置
isEnd； - 更新计数；
- 删除无用节点。
这些步骤不是天然原子的，多线程同时访问时就可能看到中间状态。
2. 最简单方案：全局锁
最粗暴也最容易正确的方案是全局锁。
search/startsWith/insert/delete 都先获取同一把锁这样不会有并发修改问题，但读操作之间也互相阻塞。
如果并发量很低，或者 Trie 很小，这个方案可以接受。
面试里不要一上来就追求无锁，先保证正确性，再谈性能优化。
3. 读写锁为什么常用
Trie 查询通常远多于更新。
读写锁允许多个读线程并发执行，但写线程独占。
| 操作 | 锁 |
|---|---|
| 查询单词 | 读锁 |
| 前缀匹配 | 读锁 |
| 插入单词 | 写锁 |
| 删除单词 | 写锁 |
这种方案实现相对简单，也能提升读多写少场景的吞吐。
4. 分段锁怎么理解
如果全局写锁成为瓶颈，可以考虑按第一层字符或路径分段加锁。
例如按首字符分成 26 段：
lock['a'], lock['b'], ..., lock['z']插入 apple 只锁 a 段，插入 banana 只锁 b 段。
这种方法能提高并发，但删除、跨段统计、全量遍历会更复杂。
5. Copy-on-Write Trie 怎么做
Copy-on-Write 的思路是写操作不修改旧路径，而是复制要修改的路径，最后用原子方式切换 root。
oldRoot -> 给读线程继续用
newRoot -> 写线程构建新版本
root = newRoot读线程拿到某个 root 后，看到的是一致快照。
这和可持久化 Trie 的路径复制思想很接近。
6. 删除为什么更危险
插入通常只增加节点，删除可能移除节点。
如果读线程正在沿旧路径访问，写线程把节点清掉，就可能出问题。
在有 GC 的语言里，对象不会立即释放，但逻辑一致性仍然可能错；在手动内存管理语言里，还要考虑悬空指针。
所以并发删除通常要更保守，比如写锁、引用计数、版本回收或延迟删除。
7. 怎么根据场景选方案
可以这样选：
| 场景 | 推荐方案 |
|---|---|
| 小规模、低并发 | 全局锁 |
| 读多写少 | 读写锁 |
| 写入分散 | 分段锁 |
| 读极多、批量更新 | Copy-on-Write |
| 只读词典 | 构建完成后不可变 |
如果词典是构建后只读的，最简单：构建阶段单线程或加锁，发布后所有查询无锁。
8. 常见误区与追问
- 误区：Trie 查询只是读，所以不用考虑并发。 如果同时有写入，读线程可能看到不一致的中间状态。
- 误区：给每个节点都加锁一定最好。 细粒度锁复杂，容易死锁，维护成本高。
- 误区：Copy-on-Write 没有成本。 写入会复制路径，内存和构建成本更高。
- 追问：读多写少怎么选？ 读写锁或不可变快照通常更合适。
- 追问：只读词典需要锁吗？ 构建完成并安全发布后，查询通常不需要锁。