Vue Diff 算法
涵盖 Diff 同层比较原理、key 的作用、Vue2 双端对比算法、Vue3 最长递增子序列算法。原文件中"diff 算法"和"为什么 v-for 需要 key"两节合并到本文。
一、为什么采用同层比较？
求通用树编辑距离的最优解可能非常昂贵，复杂度还取决于具体算法和约束。前端框架不会把跨父节点移动当成同一个 VNode 的常规复用场景，而是依据节点类型、key 与当前子节点序列进行补丁处理。
Vue 的解题思路（启发式假设）：
在前端真实的业务场景中，DOM 元素跨越不同父节点去移动的情况极少出现（比如极少会把一个属于 div 的 span 突然移到另一个 p 标签底下，大部分是直接隐藏或者重新渲染了）。
因此可把核心理解为：在同一父节点的子节点序列内匹配和复用；跨父节点的结构变化通常按卸载与挂载处理。
- 如果发现旧节点有，新节点没了，直接把旧的 DOM 连同它的子节点全部销毁。
- 如果发现新节点有，旧节点没有，直接创建新 DOM 挂载上去。
这显著缩小了问题规模，但不能把整个 Vue 3 keyed diff 一概写成 O(n)：建立映射和扫描是线性的，最长递增子序列步骤通常是 O(n log n)，组件子树的递归更新还取决于实际树结构。
二、什么是节点复用？key 到底有什么用？
在同层比较时，如果有多个并排的子节点（比如一个 <ul> 下面的许多 <li>），Vue 需要搞清楚新旧节点列表里，哪些是原来就有的，哪些是新插进来的。
如何判断是同一个节点？
Vue 源码中有一个 isSameVNodeType 函数，它的判断标准核心是两个：type（标签类型，比如 div 还是 span）必须相同，且 key 必须相同。
为什么不能用 index 作为 key？（高频面试题）
可以在面试时举这个经典的例子：
假设有一个列表：
[A, B, C]，你用它们的索引 0, 1, 2 做为 key。现在你在头部插入一个新数据 D，列表变成了：
[D, A, B, C]。Vue 在进行 Diff 的时候会怎么想？
它看到旧节点的 index: 0 对应 A，新节点的 index: 0 对应 D。因为它俩标签和 key (0) 都一样，Vue 就会认为这是同一个节点，直接复用 A 的真实 DOM，然后强行把 A 的文字改成 D。以此类推，B 变成 A，C 变成 B，最后再多创建一个 DOM 渲染 C。
这就导致了：原本只需要在头部往里塞一个新 DOM 就能解决的事，变成了所有 DOM 都被重新修改一遍文字。 如果你的列表里包含了带状态的组件（比如输入框输入了东西），这还会导致状态错乱。
结论：key 应是同级列表内稳定且唯一的基本值，例如业务 ID；不要求一定来自数据库。正确的 key 帮助 Vue 维持 VNode 和组件/DOM 状态的身份对应，但节点仍可能因类型变化等原因被替换，也不保证只有位置移动。
三、Vue 2 的"双端比较"和 Vue 3 的"最长递增子序列"
当遇到乱序的同层子节点（比如原本是 A B C D，变成了 D A B C），Vue 需要算出怎么移动现在的 DOM 最省事。
Vue 2 的"双端交叉比对"
核心思想：用 4 个指针，从两头向中间靠拢。
旧列表和新列表各自准备一个"头指针"和一个"尾指针"。每次循环做以下 4 次比对探测：
- 头跟头比：一样的话，说明头部的节点没动，头指针同时向后移。（比如新旧末尾加数据的场景）
- 尾跟尾比：一样的话，说明尾部的节点没动，尾指针同时向前移。
- 老头跟新尾比：一样的话，说明有一个节点从最前面跑到了最后面。Vue 会立刻调动真实的 DOM，把这个 DOM 移动到最后面。
- 老尾跟新头比：一样的话，说明有一个节点从最后面跑到了最前面。
为什么要这么设计？
因为在日常开发中，我们操作数组大部分时候是：push（尾部添加）、pop（尾部删除）、unshift（头部添加）、shift（头部删除）或者 reverse（反转）。双端对比这 4 步刚好能够以最完美、最快的方式命中并解决掉这些极限场景。
Vue 3 的升级版："最长递增子序列"（LIS）
虽然双端对比很强，但如果列表不仅头尾在变，中间的数据也被一顿爆改（比如 ABCD 变成了 C A E B D），双端对比最后还是得在旧列表的 Hash 映射里面傻找。
Vue 3 借鉴了 ivi 和 inferno 框架的算法，做得更极致。
核心思想：先剥洋葱，再找"钉子户"。
- 头尾预处理（剥洋葱）：先跟 Vue2 类似，从头部和尾部向中间扫描。只要头尾有相同的节点，直接跳过处理。（比如 A B C D 变成 A C D... 头部的 A 直接不管了）
- 构造映射表：对剩下的比较乱的节点，建立一个数组来记录新节点在旧节点中的相对位置
- 最长递增子序列（核心大招）：
假如剩余乱序节点的旧索引映射出来是
[4, 2, 5, 3]。我们用著名的算法求出它的最长递增子序列，发现是
[2, 3]。这意味着什么？意味着在新的 DOM 树里，原本索引是 2 和 3 的节点，它们的相对顺序是依然保持正确的。
"所以，最长递增子序列的本质，就是帮我们找到那些'不需要移动的钉子户'。"
以这帮钉子户节点为基准参考，Vue 只需要去移动那些"不在递增序列里"的节点。这保证了在任何乱序情况下，真实 DOM 的移动操作次数是最少的。
四、v-for 中 key 的作用
v-for 中的 key 是 VNode 身份提示，帮助 Vue 在新旧同级列表间匹配节点并保留正确的组件或 DOM 状态。没有 key 时，Vue 默认采用就地更新策略，尽量按位置修补已有元素；这不等同于“全量重新渲染”，但不适合依赖子组件状态或临时 DOM 状态的可重排列表。
参考：cnblogs
使用 index 作 key 时，头部插入后旧的数字 key 仍位于原位置，却对应了不同业务项，框架会按这些 key 复用节点并修改内容。稳定业务 ID 则能让节点身份随数据项移动，使框架识别出新增项与可复用项。
使用 index 作 key 时，插入或重排后，同一个数字 key 会被分配给不同业务项，Vue 可能把旧节点状态复用给新的数据项；含输入框或有内部状态的子组件时尤其容易错位。只有列表不会重排、插入或删除且没有更稳定标识时，index 才可能是可接受的退让方案。
五、面试总结话术
"整体来看，Diff 的演进就是为了应对业务中越来越复杂的页面呈现。
- 从大面来说，同层对比定下了基础，避免了无效计算。
- 细节上，用 key 值来做靶向制导，最大限度压榨和复用旧 DOM 节点。
- 在移动策略上，Vue 2 用双端对比解决日常最常见的头尾增删，而 Vue 3 则更进一步，通过求最长递增子序列，在极端乱序的情况下，找出了所有不需要动的基准节点，把真实 DOM 的移动次数做到了理论上的极小值。"
六、关联文档
七、易错点
- 只说"key 提升性能"不说"复用机制" → 要点出"key 是身份标识，相同 key 才能复用 DOM"
- 忽略 index 作为 key 的状态错乱案例
- 不区分 Vue2 双端对比与 Vue3 LIS 的应用场景
- 不知道最长递增子序列的真正含义是"不需要移动的节点"