Vue 2 的 diff 算法是怎样比较子节点的？

简答

Vue 2 已于 2023-12-31 停止维护，本题 Vue 2 部分以 2.7 源码为准。
同层比较：只在同一父节点的子节点之间比较；sameVnode 要求 key、标签等一致才复用，否则销毁重建。
Vue 2 的 updateChildren 维护旧头、旧尾、新头、新尾四个指针，依次尝试四种命中，命中后 patch 并按需移动 DOM，指针向中间收缩。
四种都不命中时，为剩余旧节点建立 key → 下标的映射查找新头；找不到就新建。循环结束后批量新增或删除剩余节点。
Vue 3 先同步相同前缀和后缀，对中间乱序部分用最长递增子序列确定不需要移动的节点；编译器生成的 PatchFlags、Block 和静态缓存（Cache Static）让运行时跳过不变内容。

sameVnode

两个 vnode 视为"同一个节点"需要：key 相同、asyncFactory 相同，并且标签相同、是否注释节点相同、是否都有 data，input 还要 type 相同（异步占位节点另有判断）。没有写 key 时两边 key 都是 undefined，同标签的节点会被就地复用，这就是列表用下标或不写 key 时状态错位的原因。

双端比较的四种命中

设 oldStart、oldEnd、newStart、newEnd 四个指针，循环条件为两组都还有未处理的节点（循环开头会跳过被置为 undefined 的旧节点）：

旧头 vs 新头：命中则 patch，两个头指针后移。
旧尾 vs 新尾：命中则 patch，两个尾指针前移。
旧头 vs 新尾：命中说明节点被移到了后面，patch 后把旧头的 DOM 插到旧尾 DOM 的后面。
旧尾 vs 新头：命中说明节点被移到了前面，patch 后把旧尾的 DOM 插到旧头 DOM 的前面。
都不命中：首次用 createKeyToOldIdx 为剩余旧节点建 key 映射。新头有 key 就查映射，没有 key 就用 findIdxInOld 逐个 sameVnode 比较。找到且 sameVnode 成立则 patch，把旧位置置为 undefined 并移到旧头之前；找不到或 key 相同但元素不同，就新建并插到旧头之前。新头指针后移。

循环结束后：旧节点先用完，把剩余新节点插入；新节点先用完，删除剩余旧节点。

text

旧：A B C D      新：D A B C
旧头 A vs 新头 D ✗；旧尾 D vs 新尾 C ✗；旧头 A vs 新尾 C ✗
旧尾 D vs 新头 D ✓ → 把 D 移到 A 前面，只移动一次

Vue 3 的做法

patchKeyedChildren 分五步：

从头同步，isSameVNodeType 成立就 patch，直到不同。
从尾同步。
旧的用完，挂载剩余新节点。
新的用完，卸载剩余旧节点。
中间未知序列：为新节点建 key → 下标映射，遍历旧节点 patch 可复用的、卸载找不到的，并记录 newIndexToOldIndexMap。只有检测到节点移动时才调用 getSequence 求最长递增子序列；从后往前遍历，在子序列中的节点不动，其余节点移动或新挂载。

编译期优化

Vue 2 编译器会标记静态根节点，patch 时跳过它们，但动态节点仍按完整树比较。Vue 3 的模板编译结果带有更多提示：

PatchFlags：标记节点哪些部分是动态的，如 TEXT、CLASS、PROPS，patchElement 只更新这些部分。
Block：块节点收集内部的动态后代到 dynamicChildren，更新时只遍历这个扁平数组，而不是整棵子树。
静态缓存（Cache Static，早期版本称为静态提升）：静态节点只创建一次，Vue 3.5 的编译器把它缓存到 _cache 中并标记为 CACHED，更新时完全跳过。

具体的编译策略见《Vue 模板编译如何减少运行时更新工作？》。

示例

用 @vue/compiler-dom（vue@3.5.x 依赖）编译 <div><p>static</p><span :class="c">{{msg}}</span></div>，输出的关键部分：

JavaScript

_cache[0] || (_cache[0] = _createElementVNode("p", null, "static", -1 /* CACHED */)),
_createElementVNode("span", { class: _normalizeClass(_ctx.c) },
  _toDisplayString(_ctx.msg), 3 /* TEXT, CLASS */)

常见追问

为什么不推荐用下标作 key？插入或删除中间项后，下标与数据的对应关系改变，sameVnode 会把不同数据的节点当成同一个复用，带状态的子组件或输入框就会错位。
双端比较和最长递增子序列哪个更好？两者都是启发式减少 DOM 移动，Vue 3 的方案在中间乱序部分能得到最少移动次数，但这里不给出普适的性能结论。