一次性说清楚Vue的Diff算法

Diff算法作用

当数据改变时，Vue 会生成一棵全新的 虚拟 DOM 树（VNode Tree）。如果没有 Diff 算法，我们只能：

• 暴力替换：删掉旧的 DOM，重新渲染整个列表。这会导致严重的性能抖动、输入框焦点丢失、音视频播放中断。
• Diff 的介入：它通过算法算出“哪些节点没动”、“哪些节点只是换了位置”、“哪些节点需要更新属性”，从而保证 DOM 操作次数最少

虚拟DOM

虚拟 DOM 的本质是 对真实 UI 结构的轻量级描述。它是一个纯粹的 JavaScript 对象

为什么要有虚拟DOM

性能提升：直接操作 DOM 的代价极高（涉及 CSS 计算、布局、重绘）。通过在 JS 层进行对比（Diff），计算出最小变更量，再“一次性”应用到 DOM 上，可以显著减少浏览器的渲染负担。

跨平台能力：虚拟 DOM 使得 Vue 摆脱了对浏览器的强依赖。由于 VNode 是抽象的，它可以被渲染为 Web DOM，也可以渲染为小程序、甚至 Native 移动端 UI。

声明式编程：开发者只需关注状态（Data），由框架负责将状态映射到 VNode，再由 VNode 同步到 DOM

虚拟DOM的身份证-Key

key 用来标识组件或元素的唯一性，它的作用在于在virtual dom对比更新过程中确定哪些组件或元素需要被更新，删除或重新渲染

双端Diff算法（Vue2）

• 对新旧节点的两个端点进行比较，用四个索引值分别指向新旧两组子节点的端点，首尾进行比较，如果找到可复用节点，则移动节点位置，同时更新索引值，
• 若一轮比较之后，没有找到可复用的节点，则拿新节点的头部节点去旧节点中寻找，若找到可复用的节点，则移动位置，同时更新索引值，若找不到可复用的节点，则说明是新增节点，
• 当更新完毕，有节点在更新过程中被遗漏了，说明该节点只在旧节点中出现，将其进行移除

核心变量

• 旧列表指针：oldStartIdx, oldEndIdx
• 新列表指针：newStartIdx, newEndIdx

执行步骤（循环条件：oldStart <= oldEnd && newStart <= newEnd）

第一步：四种理想情况匹配

算法会按以下顺序进行 key 的比对：

1. 旧头 vs 新头：匹配成功，则 patch 节点，两个 Start 指针向后移。
2. 旧尾 vs 新尾：匹配成功，则 patch 节点，两个 End 指针向前移。
3. 旧头 vs 新尾：匹配成功，说明原本在头的节点跑到了尾部。patch 后，将旧头对应的真实 DOM 移动到 oldEnd 对应的 DOM 之后，oldStart++, newEnd--。
4. 旧尾 vs 新头：匹配成功，说明原本在尾的节点跑到了头部。patch 后，将旧尾对应的真实 DOM 移动到 oldStart 对应的 DOM 之前，oldEnd--, newStart++。

第二步：非理想情况（乱序）

如果以上四种都没中，就进入“查表法”：

• 根据 oldChildren 生成一个 { key: index } 的映射表。
• 拿着 newStart 指向的节点的 key 去表里找。找到了：将找到的旧节点移动到 oldStart 之前，并把旧数组对应位置设为 undefined。没找到：说明是新节点，直接在 oldStart 之前创建新 DOM。

第三步：收尾

• 如果 oldStart > oldEnd，但新列表还有剩余，说明有新节点需添加。
• 如果 newStart > newEnd，但旧列表还有剩余，说明有旧节点需卸载。

快速Diff算法（Vue3）

• 先比较有没有相同的前置节点以及后置节点，建立索引值初始化为0，指向子节点的开头，开启while循环，进行比较，直到遇到不同的节点，
• 以及两个后置索引，分别指向最后一个节点，开启while循环进行比较,比较完毕，对于新增节点则挂载，有删除节点则卸载
• 复杂情况下，创建source数组，用来存储新的一组子节点在旧的子节点中的位置索引，为新的子节点构建一张索引表，存储key和节点索引间的映射.并计算出最长递增子序列，
• 最长子序列所指向的节点即为不需要移动的节点

步骤一：预处理 (Pre-process)

从两端向中间扫描，把能直接对应的节点先处理掉。

1. 自前向后：比较 old[i] 和 new[i]，直到 key 不同或超出范围。
2. 自后向前：比较 old[oldEnd] 和 new[newEnd]，直到 key 不同。

这一步能处理大部分场景： 比如在列表末尾插入一个元素，或者删除开头的元素。经过预处理，可能对比已经结束了。

步骤二：未知序列处理 (The Core)

预处理完后，如果还剩下中间一段乱序的节点，Vue 3 会开始真正的硬核操作：

1. 构建映射表：建立新节点 key -> index 的映射。
2. 构建位置数组 source：长度等于新乱序序列的长度。初始化为 -1。遍历旧乱序序列，通过 key 找到新序列中的位置。如果找到了，将 source[newIdx] 设为该旧节点的原始索引。这一步完成了“哪些节点可以复用”的统计。

步骤三：移动与挂载 (LIS 登场)

这是最关键的步骤，决定了如何以最少次数移动 DOM。

1. 计算 LIS (最长递增子序列)：针对 source 数组计算其最长递增子序列。例如 source = [2, 3, 1, -1]，其 LIS 是索引 [0, 1]（对应值 2, 3）。
2. 倒序遍历新序列：如果 source[i] === -1：说明是新节点，创建并挂载。如果 i 在 LIS 索引中：说明该节点相对位置没变，不动它。如果 i 不在 LIS 索引中：说明它需要移动，将其对应的 DOM 移动到后一个节点之前。