2082 字
10 分钟
diff
diff
一、背景与目标
在虚拟 DOM diff 算法中，处理有 key 的子节点时，如何高效地移动、插入和删除 DOM 元素，是提升性能的关键。本节代码实现了 Vue3 快速 Diff 算法的核心部分，主要解决：
- 如何识别哪些节点需要移动
- 如何高效地移动节点
- 如何插入/删除节点
设计动机： 传统的 diff 算法复杂度高，性能低。Vue3 通过分段对比、key 索引、最长递增子序列等优化手段，极大提升了性能，减少了 DOM 操作次数。
二、整体流程概览
主要分为以下几步，每一步的设计目的如下：
- 处理前置相同节点：快速跳过头部无需变化的节点，减少后续 diff 范围。
- 处理后置相同节点：快速跳过尾部无需变化的节点，进一步缩小 diff 范围。
- 处理新增/删除节点：识别只剩新节点或只剩旧节点的情况，直接插入或卸载。
- 处理需要移动的节点：对中间乱序部分，精准判断哪些节点需要 patch、插入、卸载或移动。
三、详细步骤与代码说明
1. 处理前置相同节点
原理与目的：
- 从头开始，依次比较新旧节点的 key，遇到不同为止。
- 这样可以快速跳过两端未变化的部分，提升 diff 性能。
关键变量说明：
j：头部指针，指向当前比较的节点索引。oldVNode、newVNode：当前比较的旧/新节点。
let j = 0;let oldVNode = oldChildren[j];let newVNode = newChildren[j];while (oldVNode.key === newVNode.key) { patch(oldVNode, newVNode, container); // 复用和更新节点 j++; oldVNode = oldChildren[j]; newVNode = newChildren[j];}2. 处理后置相同节点
原理与目的：
- 从尾部开始，依次比较新旧节点的 key，遇到不同为止。
- 跳过尾部未变化的部分，进一步缩小 diff 范围。
关键变量说明：
oldEnd、newEnd：分别指向旧/新子节点的末尾索引。
let oldEnd = oldChildren.length - 1;let newEnd = newChildren.length - 1;oldVNode = oldChildren[oldEnd];newVNode = newChildren[newEnd];while (oldVNode.key === newVNode.key) { patch(oldVNode, newVNode, container); oldEnd--; newEnd--; oldVNode = oldChildren[oldEnd]; newVNode = newChildren[newEnd];}3. 处理新增/删除节点
判断条件与设计动机：
- 如果
j > oldEnd，说明旧节点已全部处理完，剩下的新节点全部是新增，直接插入。 - 如果
j > newEnd，说明新节点已全部处理完，剩下的旧节点全部是多余的，直接卸载。
关键变量说明：
anchorIndex、anchor：用于确定插入新节点的锚点位置。
if (j > oldEnd && j <= newEnd) { // 新节点剩余，插入 const anchorIndex = newEnd + 1; const anchor = anchorIndex < newChildren.length ? newChildren[anchorIndex].el : null; while (j <= newEnd) { patch(null, newChildren[j++], container, anchor); // 挂载新节点 }} else if (j > newEnd && j <= oldEnd) { // 旧节点剩余，卸载 while (j <= oldEnd) { unmount(oldChildren[j++]); // 卸载多余节点 }}4. 处理需要移动的节点（中间乱序区间）
4.1 构建 key 索引表
原理与目的：
- 为了能 O(1) 查找新节点 key 在新 children 中的位置，构建 key 到索引的映射。
关键变量说明：
keyIndex：对象，key 为新节点的 key，值为其在 newChildren 中的索引。newStart、newEnd：中间区间的起止索引。
const keyIndex = {};for (let i = newStart; i <= newEnd; i++) { keyIndex[newChildren[i].key] = i;}4.2 构建 sources 数组
原理与目的：
sources数组长度等于新 children 中未处理的节点数。- 记录新 children 区间内每个节点在旧 children 中的索引，未找到则为 -1。
- 后续用于判断哪些节点需要插入、哪些需要移动。
关键变量说明：
count：新 children 中未处理节点的数量。sources：记录新节点在旧节点中的索引。
const count = newEnd - j + 1;const sources = new Array(count).fill(-1);4.3 遍历旧节点，更新/卸载
原理与目的：
- 遍历旧 children 区间，查找每个旧节点在新 children 中的位置。
- 找到则 patch 并记录索引，未找到则卸载。
- 同时判断是否有节点需要移动。
关键变量说明：
patched：已处理的节点数量，防止多余处理。pos：记录遍历过程中遇到的最大新节点索引，用于判断是否乱序。moved：标记是否有节点需要移动。
for (let i = oldStart; i <= oldEnd; i++) { oldVNode = oldChildren[i]; if (patched <= count) { const k = keyIndex[oldVNode.key]; // 新 children 中的索引 if (k !== undefined) { newVNode = newChildren[k]; patch(oldVNode, newVNode, container); patched++; sources[k - newStart] = i; // 记录旧节点索引 // 判断是否需要移动节点 if (k < pos) { moved = true; } else { pos = k; } } else { unmount(oldVNode); } } else { unmount(oldVNode); }}-
设置 moved 的条件：
- 在遍历旧节点时，记录每次找到新 children 中对应 key 的索引
k。 - 维护一个变量
pos，每次遇到更大的k时更新pos。 - 如果当前
k < pos，说明当前节点在新 children 中的位置比前一个已处理节点靠前，说明出现了乱序（即有节点需要移动），此时设置moved = true。
- 在遍历旧节点时，记录每次找到新 children 中对应 key 的索引
-
为什么要这样判断：
- 如果所有
k都是递增的，说明新旧节点的相对顺序一致，无需移动。 - 一旦出现
k小于前面的pos，说明有节点在新 children 中被插到了前面，需要移动。 - 这样可以提前判断是否需要进入后续的 DOM 移动逻辑，避免不必要的操作。
- 如果所有
4.4 判断是否需要移动节点
原理与目的：
- 如果
moved为 true，说明 sources 不是递增的，有节点需要移动。 - 通过计算 sources 的最长递增子序列（LIS），LIS 内的节点不需要移动，其余的都需要移动。
- 这样可以最小化 DOM 移动操作次数。
关键变量说明：
seq：sources 的 LIS，表示无需移动的节点索引。s、i：倒序遍历 sources 和 LIS。anchor：插入/移动节点的目标位置。
if (moved) { const seq = lis(sources); let s = seq.length - 1; let i = count - 1; for (i; i >= 0; i--) { if (sources[i] === -1) { // 新增节点 const pos = i + newStart; const newVNode = newChildren[pos]; const nextPos = pos + 1; const anchor = nextPos < newChildren.length ? newChildren[nextPos].el : null; patch(null, newVNode, container, anchor); } else if (i !== seq[s]) { // 需要移动的节点 const pos = i + newStart; const newVNode = newChildren[pos]; const nextPos = pos + 1; const anchor = nextPos < newChildren.length ? newChildren[nextPos].el : null; insert(newVNode.el, container, anchor); } else { // 节点在 LIS 中，无需移动 s--; } }}四、最长递增子序列（LIS）算法
原理与目的：
- 在 sources 数组中，LIS 表示无需移动的节点索引，其余的都需要移动。
- 通过 LIS 算法，最小化 DOM 移动次数。
关键变量说明：
arr：sources 数组。p：前驱数组，用于回溯 LIS。result：LIS 的索引序列。
function lis(arr) { const p = arr.slice(); const result = [0]; for (let index = 0; index < arr.length; index++) { const arrI = arr[index]; if (arrI !== -1) { let lastIndex = result[result.length - 1]; if (arrI > arr[lastIndex]) { p[index] = lastIndex; result.push(index); continue; } let left = 0, right = result.length - 1; while (left < right) { let mid = (left + right) >> 1; if (arr[result[mid]] < arrI) { left = mid + 1; } else { right = mid; } } if (arrI < arr[result[left]]) { if (left > 0) { p[index] = result[left - 1]; } result[left] = index; } } } let first = result.length, end = result[first - 1]; while (first-- > 0) { result[first] = end; end = p[end]; } return result;}设计动机：
- LIS 算法复杂度 O(n log n)，能高效找出最大不动子序列，极大减少 DOM 移动。
- 只需移动非 LIS 的节点，保证最优性能。
五、总结与面试要点
- 前后置节点优化：通过头尾双指针，快速跳过无需处理的节点，提升性能。
- sources 数组：记录新节点在旧节点中的位置，辅助判断哪些节点需要移动。
- 最长递增子序列：LIS 算法找出无需移动的节点，最小化 DOM 操作。
- 插入/卸载/移动：分别处理新增、删除、移动节点，保证最终 DOM 与新虚拟节点一致。
- 变量与判断条件解释：每个变量和判断条件都服务于性能最优和最小 DOM 操作的目标。
面试建议：
- 能手写核心 diff 逻辑，理解每一步的目的和设计动机。
- 能解释为什么要用 LIS，如何减少 DOM 操作。
- 能举例说明 sources 数组和 key 的作用。
- 能详细说明 moved、patched、pos 等变量的意义和判断条件。