Diff算法全解析：双端比较与最长递增子序列详解

Vue3的Diff算法并非单一技术突破，而是一套精妙分层的策略组合：先通过前后双端比对快速复用首尾相同节点，大幅压缩待处理范围；再高效批量处理新增与删除，规避无谓查找；最后针对最棘手的乱序移动，借助key映射构建位置关系图，并以最长递增子序列（LIS）为核心优化手段，精准识别无需移动的天然有序节点子集，将时间复杂度从O(n²)显著降至O(n log n)——这不仅是性能跃升，更是对真实场景中列表更新规律的深刻洞察与工程化落地。

Vue3 的 Diff 算法不是单点突破，而是一套分层递进的策略组合。它把列表更新拆解为可预测、可跳过、可加速的多个阶段，最长递增子序列（LIS）只是压轴环节，专治最棘手的乱序移动问题。

前序与后序双端比对：快速收口相同结构

这是算法最先执行、也最常命中的步骤。它从新旧子节点数组的头尾同时推进，逐个比对类型和 key：

• 开头连续匹配的节点（如 [A,B,...] vs [A,B,X,...]），直接复用并递归 patch，不进入后续逻辑
• 结尾连续匹配的节点（如 [...,C,D] vs [X,...,C,D]），同样跳过，大幅压缩待处理区间
• 该阶段时间复杂度接近 O(1) 到 O(k)，k 是公共前后缀长度；多数真实场景下，增删只发生在中间，因此这一步就解决了大半工作

新增与删除节点：明确边界，一次清理

双端比对结束后，剩余未匹配的节点形成清晰的“缺口”：

• 若旧节点还有剩余（e1 > i-1），说明这些节点在新列表中已消失，批量卸载
• 若新节点还有剩余（e2 > i-1），说明是全新插入，按顺序挂载即可
• 这个过程不依赖 key 查找，也不触发移动，开销极低；它处理的是“存在性变化”，而非“位置重排”

Key 驱动的乱序映射：构建位置关系图

当剩余新旧节点数量相等但顺序错乱时（如 [1,3,4,2] → [1,2,3,4]），算法进入核心优化环节：

• 先建立 oldKeyToIndex 哈希表：遍历旧列表，记录每个 key 对应的最后索引
• 再生成 newIndexToOldIndexMap 数组：遍历新列表，对每个节点查其在旧列表中的位置，找不到则记为 0（代表新节点）
• 例如新列表 [b,a,d,c] 对应旧列表 [a,b,c,d]，得到位置数组 [1,0,3,2]（a 在旧列表索引 0，b 在索引 1，c 在 2，d 在 3）

最长递增子序列（LIS）：锁定最少移动方案

LIS 不是用来排序的，而是用来识别“天然有序、无需移动”的节点子集：

• 在 newIndexToOldIndexMap 中找严格递增子序列（如 [1,3] 或 [0,2]），这些对应的新节点在旧 DOM 中原本就保持相对顺序，可原位复用
• Vue3 使用贪心 + 二分法构造 tails 数组，并通过前驱链反推出 LIS 所含的新节点下标
• 其余下标对应的新节点，则按需执行 insert 或 move 操作——移动次数 = 剩余节点数 − LIS 长度
• 该步骤将乱序更新的时间复杂度从 O(n²) 降至 O(n log n)，对长列表效果显著

今天带大家了解了的相关知识，希望对你有所帮助；关于文章的技术知识我们会一点点深入介绍，欢迎大家关注golang学习网公众号，一起学习编程~