Vue.js Diff算法：最长递增子序列在DOM中的应用

Vue.js 的快速 Diff 算法巧妙地将列表更新中的 DOM 最小化移动问题，转化为经典的最长递增子序列（LIS）求解任务：它先通过哈希查找构建新节点在旧列表中的位置映射数组，再以贪心+二分法高效求出 LIS，精准锁定那些在新旧顺序中保持相对位置一致、可原位复用的节点；其余节点则按需插入或移动——这一数学驱动的设计不仅将时间复杂度从暴力比对的 O(n²) 降至 O(n log n)，更在真实场景中大幅减少 DOM 操作，成为 Vue 高性能响应式更新背后低调而关键的“智能调度引擎”。

Vue.js 的快速 Diff 算法在处理列表更新时，并不直接暴力比对所有节点，而是借助最长递增子序列（LIS）来最小化 DOM 移动操作。它的核心目标不是找出“完全匹配”，而是确定哪些节点可以复用、哪些需要移动——而 LIS 正是求解“最少移动次数”的数学钥匙。

为什么需要 LIS？——从“移动代价”说起

当新旧 vnode 列表长度相同但顺序变化时（如 [a,b,c,d] → [b,a,d,c]），理想策略是只移动真正位置变了的节点，其余保持原位并复用。但如何判断“哪些能不动”？关键在于找出新列表中在旧列表里已有相对顺序的最长子序列。这个子序列里的节点，在 DOM 中原本就处于“正确相对位置”，无需移动；其余节点则需插入或调整。

LIS 在这里的作用是：把“节点复用+最小移动”问题，转化为一个经典的贪心动态规划问题，时间复杂度控制在 O(n log n)，远优于暴力 O(n²)。

如何构建 LIS 所需的“位置数组”？

算法第一步不是直接找子序列，而是为新列表中每个节点，查它在旧列表中的索引位置，生成一个 映射数组 newIndexToOldIndexMap：

• 遍历新列表，对每个节点 key，查它在旧列表中最后一次出现的索引（即 oldKeyToIndex 哈希表查找）
• 若没找到，记为 0（表示新节点）；若找到，记下该索引值
• 最终得到一个长度为 newLength 的数组，例如：[2, 0, 3, 1]（对应新节点在旧列表的位置）

这个数组中，严格递增的子序列（如 [2,3] 或 [0,1]）就代表一组在旧列表中本就“顺序靠前→靠后”的节点，它们在新列表中依然维持了这种偏序关系，因此可保留在原 DOM 位置上。

用贪心法求 LIS，并反推“不动节点”的索引

Vue 不需要完整 LIS 序列，只需要知道哪些新节点索引属于 LIS，从而标记为“不移动”。它采用经典贪心 + 二分方式构造 LIS 的 tails 数组，并同步维护 prev 和 result 数组回溯路径：

• tails[i] 存储长度为 i+1 的递增子序列的最小末尾值
• 遍历位置数组时，用二分定位插入点，更新 tails，同时记录每个位置的前驱索引
• 最后从 tails 最长长度处倒推，还原出 LIS 对应的新节点下标集合

这些下标对应的 vnode 就是“可原位复用、无需移动”的节点；其余节点则进入 insert/move 流程。

DOM 操作如何与 LIS 结果联动？

LIS 输出的“不动节点集合”，直接指导 patch 过程：

• 对属于 LIS 的新节点：跳过移动，仅执行 props 更新和子树 diff
• 对不属于 LIS 的节点：
  • 若在旧列表中存在（key 匹配），则调用 moveNode 插入到正确位置（参考其在新列表的索引）
  • 若不存在（key 新增），则创建新节点并插入
• 整个过程只需一次 DOM 插入/移动循环，避免反复重排

例如新列表 [b,a,d,c] 对应位置数组 [1,0,3,2]，其 LIS 可能是 [0,2]（对应新索引 1 和 3），意味着 a 和 c 可保位，b 和 d 需调整位置。

不复杂但容易忽略：LIS 在这里不是为了排序，而是为了识别“顺序保真度”最高的节点链——它是 Vue 在响应式更新中兼顾性能与准确性的关键数学支点。

文中关于的知识介绍，希望对你的学习有所帮助！若是受益匪浅，那就动动鼠标收藏这篇《Vue.js Diff算法：最长递增子序列在DOM中的应用》文章吧，也可关注golang学习网公众号了解相关技术文章。