Vue 3 Diff 算法流程及实现
Vue 3 的 Diff 算法在运行时的虚拟 DOM 更新中起到了关键作用。它的主要目标是通过比较新旧虚拟 DOM 树，找出变化的部分，并高效地更新真实 DOM。
以下是 Vue 3 Diff 算法的详细解析以及实现。
Vue 3 Diff 算法流程
Vue 3 的核心 Diff 实现主要分为以下步骤：
1. 初步判断：节点类型对比
- 不同类型节点：直接替换
如果新旧节点的类型不同（如元素与文本），直接销毁旧节点并创建新节点。 - 相同类型节点：复用节点并递归更新
如果类型相同（如div和div），继续比较其属性和子节点。
2. 属性比较：patchProps
比较新旧节点的属性并更新：
- 新增属性：新节点有，旧节点没有，添加到 DOM。
- 移除属性：旧节点有，新节点没有，从 DOM 删除。
- 修改属性：新旧节点的属性值不同，更新为新值。
3. 子节点对比：核心 Diff
子节点对比是 Diff 算法的核心部分：
- 子节点为空：直接清空。
- 只有一个子节点：直接对比更新。
- 多个子节点：使用双端比较和最长递增子序列（LIS）优化。
双端比较
Vue 3 采用双端比较策略来减少遍历范围：
- 左端比较：从头开始，逐一对比新旧节点。
- 右端比较：从尾部开始，逐一对比新旧节点。
- 中间部分处理：
- 创建旧子节点的
key -> index映射表。 - 遍历新子节点，根据
key快速找到复用的旧节点。 - 计算最长递增子序列（LIS），优化节点移动。
- 创建旧子节点的
最长递增子序列（LIS）优化
最长递增子序列用于减少 DOM 移动操作：
- 计算新子节点中可以保留顺序的最大子序列。
- 仅移动那些不在 LIS 中的节点。
Diff 算法实现
以下是 Diff 核心逻辑的伪代码实现：
主流程：patch
function patch(oldVNode, newVNode, container) {
if (oldVNode.type !== newVNode.type) {
// 类型不同，直接替换
replaceNode(oldVNode, newVNode, container);
} else {
// 类型相同，复用节点
if (newVNode.type === 'text') {
// 文本节点更新
patchText(oldVNode, newVNode);
} else {
// 普通元素节点
patchProps(oldVNode, newVNode); // 更新属性
patchChildren(oldVNode, newVNode, container); // 更新子节点
}
}
}
属性比较：patchProps
function patchProps(oldVNode, newVNode) {
const oldProps = oldVNode.props || {};
const newProps = newVNode.props || {};
// 更新或新增属性
for (const key in newProps) {
if (newProps[key] !== oldProps[key]) {
setProp(newVNode.el, key, newProps[key]);
}
}
// 删除旧属性
for (const key in oldProps) {
if (!(key in newProps)) {
removeProp(newVNode.el, key);
}
}
}
子节点对比：patchChildren
function patchChildren(oldVNode, newVNode, container) {
const oldChildren = oldVNode.children || [];
const newChildren = newVNode.children || [];
if (Array.isArray(newChildren) && Array.isArray(oldChildren)) {
// 多个子节点，进入核心 diff
patchKeyedChildren(oldChildren, newChildren, container);
} else if (typeof newChildren === 'string') {
// 新子节点是文本，直接更新
container.textContent = newChildren;
} else {
// 其他情况（如清空）
container.innerHTML = '';
mountChildren(newChildren, container);
}
}
核心子节点 Diff：patchKeyedChildren
function patchKeyedChildren(oldChildren, newChildren, container) {
let oldStart = 0;
let oldEnd = oldChildren.length - 1;
let newStart = 0;
let newEnd = newChildren.length - 1;
// 双端比较
while (oldStart <= oldEnd && newStart <= newEnd) {
if (isSameVNodeType(oldChildren[oldStart], newChildren[newStart])) {
patch(oldChildren[oldStart], newChildren[newStart], container);
oldStart++;
newStart++;
} else if (isSameVNodeType(oldChildren[oldEnd], newChildren[newEnd])) {
patch(oldChildren[oldEnd], newChildren[newEnd], container);
oldEnd--;
newEnd--;
} else {
break; // 跳出双端比较，进入乱序部分
}
}
// 处理新增或删除的节点
if (oldStart > oldEnd) {
// 新增节点
for (let i = newStart; i <= newEnd; i++) {
mount(newChildren[i], container);
}
} else if (newStart > newEnd) {
// 删除节点
for (let i = oldStart; i <= oldEnd; i++) {
unmount(oldChildren[i]);
}
} else {
// 中间部分：乱序处理
const keyToIndexMap = new Map();
for (let i = oldStart; i <= oldEnd; i++) {
const key = oldChildren[i].key;
if (key != null) keyToIndexMap.set(key, i);
}
const toBePatched = newEnd - newStart + 1;
const newIndexToOldIndexMap = new Array(toBePatched).fill(-1);
for (let i = newStart; i <= newEnd; i++) {
const newChild = newChildren[i];
const oldIndex = keyToIndexMap.get(newChild.key);
if (oldIndex != null) {
newIndexToOldIndexMap[i - newStart] = oldIndex;
patch(oldChildren[oldIndex], newChild, container);
} else {
// 新增节点
mount(newChild, container);
}
}
// 计算最长递增子序列
const increasingSequence = getLongestIncreasingSubsequence(newIndexToOldIndexMap);
// 移动节点
let lastIndex = increasingSequence.length - 1;
for (let i = toBePatched - 1; i >= 0; i--) {
if (i === increasingSequence[lastIndex]) {
lastIndex--;
} else {
// 移动节点或插入
move(newChildren[i + newStart], container);
}
}
}
}
最长递增子序列：getLongestIncreasingSubsequence
function getLongestIncreasingSubsequence(arr) {
const p = arr.slice();
const result = [];
let u, v, c;
for (let i = 0; i < arr.length; i++) {
if (arr[i] === -1) continue;
u = 0;
v = result.length - 1;
while (u <= v) {
c = ((u + v) / 2) | 0;
if (arr[result[c]] < arr[i]) {
u = c + 1;
} else {
v = c - 1;
}
}
if (u >= result.length) {
result.push(i);
} else {
result[u] = i;
}
p[i] = result[u - 1] ?? -1;
}
return result.map((i) => arr[i]);
}
总结
Vue 3 的 Diff 算法通过 静态标记优化、双端比较 和 LIS 优化，极大地提升了运行时性能，减少了不必要的 DOM 操作。这种设计在实际开发中能够很好地适应各种动态场景，同时保持高效性。
原文地址：https://blog.csdn.net/gklcsdn/article/details/144030079
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！