当响应式数据变化，虚拟 DOM 树瞬间翻新。Diff 算法的职责，是在新旧两棵树之间寻找“最小可感知的差异”，并把这些差异映射为最少的 DOM 指令。Vue 2 的双端 Diff 已足够优秀，但 Vue 3 通过“快速 Diff”进一步把复杂度削到极致——无一次多余移动，无一次多余创建。本文带你走进这条由索引、哈希、LIS 构成的精密流水线。

一、Vue2双端 Diff 的问题：移动并不总是必要

想象旧列表 [a, b, c, d]，新列表 [e, b, c, d, a]。双端 Diff 会经历：

• 头头失败、尾尾失败、旧头新尾失败、新头旧尾失败 → 进入暴力查找
• 结果：e、b、c、d、a 都经历一次移动，共 5 次 DOM 操作

然而 b、c、d 的相对顺序并未改变，理想情况下只需：

• 新建 e 并插入至最前
• 移动 a 至末尾
• 总计 2 次操作

Vue 3 的目标正是识别并消除这种“伪移动”。

二、快速 Diff 的三把钥匙

Key → Index 哈希：遍历未处理的新节点，构建 keyToNewIndexMap: Map<key, index>，O(n) 时间完成新节点索引定位，避免后续线性扫描。

索引映射数组：初始化 newIndexToOldIndexMap: number[]，长度等于未处理新节点数，默认值 0 表示“尚未匹配”。随后遍历旧节点，若命中哈希，则把 旧索引 + 1 写入对应槽位（+1 可区分索引 0 与未匹配）。

最长递增子序列 (LIS)：对 newIndexToOldIndexMap 调用 贪心 + 二分 版 LIS，获得可原地复用的索引序列。

• 位于序列中的节点 → 相对顺序不变，无需移动
• 其余节点 → 只需新建或一次性移动

这一步把 “移动次数” 从 O(n) 降至 O(n - LIS)。

三、五步流水线：从哈希到 DOM

以 [a, b, c, d] → [e, b, c, d, a] 为例：

1. 头头、尾尾比对头头失败，尾尾失败，剩余 [a] vs [e, b, c, d, a]
2. 索引映射

3. 填充映射数组

4. 计算 LIS

5. 倒序遍历i = 4 (a) → 存在于 LIS，不动i = 0 (e) → 值为 0，新建并插入总操作：新建 1 次，移动 1 次，其余复用

四、LIS 算法：贪心 + 二分

复杂度 Θ(n log n)，内存 Θ(n)，在 10 万节点场景下依旧毫秒级。

DOM 操作的最小化证明

• 移动次数 ≤ n - LIS
• 创建次数 = 新节点数 - 匹配节点数
• 删除次数 = 旧节点数 - 匹配节点数

通过索引哈希 + LIS，所有操作均是不可或缺的，确保没有一次多余重排。

结论

Vue 3 快速 Diff 把“找出差异”抽象为“找出最长递增子序列”，再用哈希索引将复杂度压到理论下界。每一次指针移动、每一次二分查找，都是为了把 DOM 渲染，让性能再无冗余。