虚拟dom和diff算法
站长
· 阅读数 2
虚拟 DOM（Virtual DOM）和 Diff 算法是 React 和 Vue 等现代前端框架中用于提高性能和优化渲染的重要概念。
虚拟 DOM
- 虚拟 DOM 是一个内存中的虚拟表示，它是真实 DOM 的轻量级复制品。当组件的状态发生变化时，框架会首先在内存中构建一个虚拟 DOM 树，然后通过比对虚拟 DOM 和上一次渲染的虚拟 DOM 树，找出两者之间的差异（Diff），最后只对必须更新的部分进行实际的 DOM 操作。 - 优势：由于直接操作真实 DOM 的成本较高，虚拟 DOM 可以减少对真实 DOM 的操作次数，从而提高页面渲染性能。 - 应用：虚拟 DOM 的概念被广泛应用于现代前端框架中，例如 React、Vue 等。
Diff算法有大概有简单Diff算法，双端Diff算法和快速Diff算法三种，而快速Diff算法中又借鉴了简单Diff算法的思路，所以下面会介绍分析三种算法。 Vue2.0使用的是双端Diff算法。Vue3.0使用的是快速Diff算法。
Diff算法的作用
Vue是提供了声明式的方法方便开发人员编写出响应式的代码，框架内部封装了指令式的查找修改DOM的过程，对于数据变化后更新视图这一过程，判断哪里需要修改，执行修改更新的过程，就是Diff算法要处理的问题，主要目的是精确查到需要更新的虚拟DOM，优化DOM更新消耗的性能。
Diff算法的简洁流程
- 找到key值匹配的oldVNode 和newVNode ，更新他们的内容
- 判断是否要移动DOM，三种diff有不同的判断方案
- 判断是否有新增节点要挂载，或者有节点要被移除
1. 简单Diff 算法
简单Diff算法核心是与当前节点的(旧)索引与最大索引值比较，如果小于，要移动节点（简单来说就是原先在前面的节点，被移动到后面）。
对于前后节点数量都一样的情况，核心流程如下：
核心流程.png
特殊情况处理：
- 遍历完oldVNodeChildren，没有找到匹配的VNode, 说明当前newVNode是新增的，需要挂载。
- 上面的更新步骤结束后，遍历oldVNodeChildren，如果有节点在新的数组中找不到对应的元素，说明该节点需要卸载。
2. 双端Diff算法
双端Diff算法会采用newStartIdx，newEndIdx, oldStartIdx, oldEndIdx四个指针，从首尾指针两两对比找可以复用节点，如果首尾都找不到，直接用数组的findIndex方法用新数组的头元素去旧数组里找，进行更新，移动后，把oldVNode置为undefined.
双端diff图
function patchKeyedChildren (n1, n2, container) {
const oldChildren = n1.children;
const newChildren = n2.children;
// 定义四个索引值
let oldStartIdx = 0;
let oldEndIdx = oldChildren.length - 1;
let newStartIdx = 0;
let newEndIdx = newChildren.length - 1;
// 四个索引指向vnode节点
let oldStartVNode = oldChildren[oldStartIdx];
let oldEndVNode = oldChildren[oldEndIdx];
let newStartVNode = newChildren[newStartIdx];
let newEndVNode = newChildren[newEndIdx];
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
// 如果旧数组的首尾节点被处理过了，直接跳到下一个位置
if (!oldStartVNode) {
oldStartVNode = oldChildren[++oldStartIdx]
} else if (!oldEndVNode) {
oldEndVNode = oldChildren[--oldEndIdx];
} else if (oldStartVNode.key == newStartVNode.key) {
// 第一步，oldStartVNode 和 newStartVNode比较（头部节点比较）
patch(oldStartVNode, newStartVNode, container);
oldStartVNode = oldChildren[++oldStartIdx];
newStartVNode = newChildren[++newStartIdx];
} else if (oldEndVNode.key == newEndVNode.key) {
// 第二步,oldEndVNode 与newEndVNode比对（尾部节点比较）
// 节点在新的顺序中依旧处于尾部，不需要移动，但是依旧需要打补丁
patch(oldEndVNode, newEndVNode, container);
// 更新尾部的节点和指针
oldEndVNode = oldChildren[--oldEndIdx];
newEndVNode = newChildren[--newEndIdx];
} else if (oldStartVNode.key == newEndVNode.key) {
// 第三步，oldStartVNode与newEndVNode对比
patch(oldEndVNode, newEndVNode, container);
// oldStartVNode 插入到oldEndVNode后面(也就是他的下一个兄弟节点的前面)
insert(oldStartVNode.el, oldEndVNode.el.nextSibling, container);
// 更新索引到下一个位置
oldStartVNode = oldChildren[++oldStartIdx];
newEndVNode = newChildren[--newEndIdx];
} else if (oldEndVNode.key == newStartVNode.key) {
// 依然要调用patch函数进行打补丁
patch(oldEndVNode, newStartVNode, container);
// 移动DOM操作
//oldEndVNode.el 移动到 oldStartVNode.el前面
insert(oldEndVNode.el, container, oldStartVNode.el);
// 移动DOM完成后，更新索引值，并指向下一个位置
oldEndVNode = oldChildren[--oldEndIdx];
newStartVNode = newChildren[++newStartIdx];
} else {
// 四个首尾节点都没有匹配上
// 拿新的一组子节点中的头部节点去旧的一组节点重查找
const idxOnOld = oldChildren.findIndex(node => node.key == newStartVNode.key);
if (idxOnOld > 0) { // 说明非头节点的元素变成了头节点
const vnodeToMove = oldChildren[idxOnOld];
patch(vnodeToMove, newStartVNode, container);
insert(vnodeToMove.el, container, oldStartVNode.el);
// 由于位置idxInOld处的节点对应真实的DOM已经移动到了别处，因此可以设置为undefined;
oldChildren[idxOnOld] = undefined;
// 更新newStartIdx到下一个位置
newStartVNode = newChildren[++newStartIdx];
} else { // 说明是新增的节点，当前在新数组中是newStartIdx
patch(undefined, newStartVNode, container, oldStartVNode.el)
newStartVNode = newChildren[++newStartIdx];
}
}
}
// 循环结束后检查索引值的情况
if (oldEndIdx < oldStartIdx && newStartIdx <= newEndIdx) {
// 说明有新的节点遗漏，需要挂载
for (let i = newStartIdx; i <= newEndIdx; i++) {
patch(null, newChildren[i], container, oldEndVNode.el);
}
} else if (newEndIdx < newStartIdx && newStartIdx <= newEndIdx) {
// 移除操作
for (let i = oldStartIdx; i <= oldEndIdx; i++) {
unmount(oldChildren[i]);
}
}
}
3. 快速Diff算法
快速diff算法增加了预处理。首先在首尾遍历更新key值匹配上的节点，更新他们的内容（即只更新，不需要移动）。
预处理之后，判断是否需要新增或者删除节点。剩下的节点需要判断是否需要移动位置。这时候会利用这些节点在oldChlidren中的索引，求出最长递增子序列，索引（oldChildren中的）在最长递增子序列里的不需要移动，否则就需要移动。
快速diff
function patchKeyedChildren(n1, n2, container) {
const newChildren = n2.children;
const oldChildren = n1.children;
// 处理相同的前置节点
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];
}
// 更新相同的后置节点
let oldEnd = oldChildren[oldChildren.length] - 1;
let newEnd = newChildren[newChildren.length] - 1;
oldVNode = oldChildren[oldEnd];
newVNode = newChildren[newEnd];
while (oldVNode.key == newVNode.key) {
//调用patch函数进行更新
patch(oldVNode, newVNode, container);
// 递减oldEnd 和 nextEnd
oldEnd--;
newEnd--;
oldVNode = oldChildren[oldEnd];
newVNode = newChildren[newEnd];
}
// 新增节点的情况
// 预处理完毕，如果满足以下条件，说明j到newEnd之间的节点应该作为新节点插入
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) {
// 删除节点的情况oldEnd >= j
while (j <= oldEnd) {
unmount(oldChildren[j++]);
}
} else {
// 预处理之后还需要移动中间的元素的情况
const count = newEnd - j + 1;
const source = new Array(count).fill(-1); // 用来存储新的一组子节点在旧一组子节点中的位置索引，后面会用它来计算出一个最长的递增子序列，并用于辅助完成DOM移动的操作
const oldStart = j;
const newStart = j;
// 时间复杂度太高,不能这么写
// // 遍历旧的一组子节点
// for (let i = oldStart; i <= oldEnd; i++){
// const oldVNode = oldChildren[i];
// // 遍历新的一组节点
// for (let k = newStart; k <= newEnd; k++){
// const newVNode = newChildren[i];
// if (oldVNode.key == newVNode.key) {
// // 调用patch进行更新
// patch(oldVNode, newVNode, container);
// // 最后填充source数组
// source[k - newStart] = i;
// }
// }
// }
// 新增两个变量，moved 和 pos
let moved = false; // 节点是否需要移动
let pos = 0; // 最大索引值
const keyIndex = {}; // key:VNode.key, value: 节点在newVNode中的索引
for (let i = newStart; i <= newEnd; i++) {
keyIndex[newChildren[i].key] = i;
}
let patched = 0; // 更新过的节点数量
for (let i = oldStart; i <= oldEnd; i++) {
oldVNode = oldChildren[i];
if (patched <= count) {
const k = keyIndex[oldVNode.key];
if (typeof k !== 'undefined') {
newVNode = newChildren[k];
patch(oldVNode, newVNode, container);
patched++;
// 填充source数组
source[k - newStart] = i;
if (k < pos) {
moved = true; // 有一个元素需要移动就是需要移动
} else {
pos = k;
}
} else {
// 旧节点不存在新数组中
unmount(oldVNode);
}
} else {
// 更新过的节点值大于需要更新的节点值，卸载多余的节点
unmount(oldVNode);
}
}
if (moved) {
// 计算最长递增子序列，子序列在更新前后顺序没有变化
const seq = getSequence(source);// 返回的是索引值
// s指向最长递增子序列的最后一个元素
let s = seq.length - 1;
let i = count - 1;
for (i; i >= 0; i--){
if (source[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);
}
if (i != seg[s]) {
// 索引值不在最长递增子序列里，需要移动
const pos = i + newStart;
const newVNode = newChildren[pos];
// 该节点的一个节点的位置索引
const nextPos = pos + 1;
//
const anchor = nextPos < newChildren.length ? newChildren[nextPos].el : null;
// 移动节点是通过insert函数实现的
insert(newVNode, container, anchor);
} else {
s--;
}
}
}
}
}