前言
我们都知道，虚拟 dom 是 Vue 和 React 页面渲染性能优化的大杀器，可是在更新时，他们是如何高效地计算出更改的地方的呢？
diff 算法的真面目
传统 diff 算法（计算一颗树映射到例外一颗树所需的最小操作数）的步骤说起来非常简单：
- 将两颗树中所有的节点一一对比，循环递归；
- 更新树，即删除未找到的旧节点，更新未找到的新节点，更新节点位置。
但是该算法经历了太多次进化，时间复杂度从1979年的 O((m3)(n3)) ，发展到2011年的 O(n^3) ，哪怕是这样，传统的 diff 算法仍然不足以为前端所用，毕竟这种复杂度意味着假如虚拟 dom 有1000个节点就需要进行10^9次比较。
// 传统diff算法处理dom更新 简单实现
let result = [];
// 比较叶子节点
const diffLeafs = function (beforeLeaf, afterLeaf) {
// 获取较大节点树的长度
let count = Math.max(beforeLeaf.children.length, afterLeaf.children.length);
// 循环遍历
for (let i = 0; i < count; i++) {
const beforeTag = beforeLeaf.children[i];
const afterTag = afterLeaf.children[i];
// 添加 afterTag 节点
if (beforeTag === undefined) {
result.push({ type: "add", element: afterTag });
// 删除 beforeTag 节点
} else if (afterTag === undefined) {
result.push({ type: "remove", element: beforeTag });
// 节点名改变时，删除 beforeTag 节点，添加 afterTag 节点
} else if (beforeTag.tagName !== afterTag.tagName) {
result.push({ type: "remove", element: beforeTag });
result.push({ type: "add", element: afterTag });
// 节点不变而内容改变时，改变节点
} else if (beforeTag.innerHTML !== afterTag.innerHTML) {
if (beforeTag.children.length === 0) {
result.push({
type: "changed",
beforeElement: beforeTag,
afterElement: afterTag,
html: afterTag.innerHTML
});
} else {
// 递归比较
diffLeafs(beforeTag, afterTag);
}
}
}
return result;
}
// 拿到处理队列后再进行处理...
根据前端真实场景优化算法
Vue 和 React 是怎么将 diff 算法的时间复杂度从 O(n^3) 降至 O(n) 的呢？这来自对于前端真实场景的深刻理解。
首先，虚拟 dom 虽然是树状结构，但是在前端开发中，需要节点跨层级移动的 ui 非常少，与其耗费算力在这个上面，不如直接默认为删除或新增，将比对停留在同级之间；
function patch (oldVnode, vnode, parentElm) {
if (!oldVnode) {
addVnodes(parentElm, null, vnode, 0, vnode.length - 1);
} else if (!vnode) {
removeVnodes(parentElm, oldVnode, 0, oldVnode.length - 1);
} else {
if (sameVnode(oldVNode, vnode)) {
patchVnode(oldVNode, vnode);
} else {
removeVnodes(parentElm, oldVnode, 0, oldVnode.length - 1);
addVnodes(parentElm, null, vnode, 0, vnode.length - 1);
}
}
}
其次，如果两个节点的类型不一样，默认就不可能是同一节点，自然不用再往下比对了，直接替换就可以了；
function sameVnode (a, b) {
return (
a.key === b.key &&
a.tag === b.tag &&
a.isComment === b.isComment &&
(!!a.data) === (!!b.data) &&
sameInputType(a, b)
)
}
最后，同一级的大量同类型子节点，是前端开发中常见的（ v-for ），可通过开发者提供唯一的 id 来判断是否为同一节点，以空间换时间。
自此，框架开发者通过对前端的理解，完成了看似粗暴，实则与实际场景贴切的优化。
Vue 和 React 的 diff 算法差别在哪
虽然两者的优化思想是一致的，但是在细节上， Vue 和 React 对于 diff 算法的实现还是有一些区别，除了对于节点是否相同的判断差异外（比如 className 不同的同类型节点， Vue 会认为不是相同的但是 React 会），主要差异在于同级多个同类型子节点——即列表更新。
React 的列表更新
React 首先对新集合的节点( nextChildren )进行遍历， lastIndex 初始为零，通过唯一的 key 可以取得老集合中相同的节点并判断：
- 如果不存在，便在 lastIndex 后添加新节点；
- 如果存在相同节点，则进行移动操作，但在移动前：
- 1 lastIndex 大于等于当前节点在老集合中的位置，执行移动操作；
- 2 lastIndex 小于当前节点在老集合中的位置，不执行移动操作；
- 更新 lastIndex 为 lastIndex 和老位置中的较大值；
遍历结束后，将未匹配的节点删除。
- 更新 lastIndex 为 lastIndex 和老位置中的较大值；
其中第二步判断是因为，如果老节点的位置比新节点位置靠后，说明该节点不会影响到其他节点的位置，在他之前多出的节点必然会被移动到后放或者被删除，所以该节点不用进行操作。
但是有一种情形是 React 算法实现中待优化的：
当遍历到 D 时，此时 D 不移动，但它导致 lastIndex 更新为3，从而使得其他元素 A ， B ， C 的 index < lastIndex ，导致 A ，B ， C 都要去移动。
Vue 的列表更新
function updateChildren (parentElm, oldCh, newCh) {
/* 定义 oldStartIdx、newStartIdx、oldEndIdx 以及 newEndIdx
分别是新老两个 VNode 的两边的索引
同时 oldStartVnode、newStartVnode、oldEndVnode 以及 newEndVnode
分别指向这几个索引对应的 VNode 节点 */
let oldStartIdx = 0;
let newStartIdx = 0;
let oldEndIdx = oldCh.length - 1;
let oldStartVnode = oldCh[0];
let oldEndVnode = oldCh[oldEndIdx];
let newEndIdx = newCh.length - 1;
let newStartVnode = newCh[0];
let newEndVnode = newCh[newEndIdx];
let oldKeyToIdx, idxInOld, elmToMove, refElm;
// oldStartIdx、newStartIdx、oldEndIdx 以及 newEndIdx 会逐渐向中间靠拢
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
// 当 oldStartVnode 或者 oldEndVnode 不存在的时候，oldStartIdx 与 oldEndIdx 继续向中间靠拢
if (!oldStartVnode) {
oldStartVnode = oldCh[++oldStartIdx];
} else if (!oldEndVnode) {
oldEndVnode = oldCh[--oldEndIdx];
} else if (sameVnode(oldStartVnode, newStartVnode)) {
// oldStartIdx、newStartIdx、oldEndIdx 以及 newEndIdx 两两比对的过程
patchVnode(oldStartVnode, newStartVnode);
oldStartVnode = oldCh[++oldStartIdx];
newStartVnode = newCh[++newStartIdx];
} else if (sameVnode(oldEndVnode, newEndVnode)) {
patchVnode(oldEndVnode, newEndVnode);
oldEndVnode = oldCh[--oldEndIdx];
newEndVnode = newCh[--newEndIdx];
} else if (sameVnode(oldStartVnode, newEndVnode)) {
// 两种交叉比对的情况，匹配上是会将对应的节点移动到头或尾
patchVnode(oldStartVnode, newEndVnode);
nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm));
oldStartVnode = oldCh[++oldStartIdx];
newEndVnode = newCh[--newEndIdx];
} else if (sameVnode(oldEndVnode, newStartVnode)) {
patchVnode(oldEndVnode, newStartVnode);
nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm);
oldEndVnode = oldCh[--oldEndIdx];
newStartVnode = newCh[++newStartIdx];
} else {
// 4种情况都没匹配上，先创建keyMap，找到相同的节点
let elmToMove = oldCh[idxInOld];
if (!oldKeyToIdx) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
idxInOld = newStartVnode.key ? oldKeyToIdx[newStartVnode.key] : null;
// 如果没找到就创建一个新的
if (!idxInOld) {
createElm(newStartVnode, parentElm);
newStartVnode = newCh[++newStartIdx];
} else {
// 如果找到了，且是同类型节点，更新
elmToMove = oldCh[idxInOld];
if (sameVnode(elmToMove, newStartVnode)) {
patchVnode(elmToMove, newStartVnode);
oldCh[idxInOld] = undefined;
nodeOps.insertBefore(parentElm, newStartVnode.elm, oldStartVnode.elm);
newStartVnode = newCh[++newStartIdx];
} else {
// 否则也创建新的
createElm(newStartVnode, parentElm);
newStartVnode = newCh[++newStartIdx];
}
}
}
}
// 新老集合有其中一个遍历完毕，开始处理该删除或新增的
if (oldStartIdx > oldEndIdx) {
refElm = (newCh[newEndIdx + 1]) ? newCh[newEndIdx + 1].elm : null;
addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx);
} else if (newStartIdx > newEndIdx) {
removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx);
}
}
Vue 的列表更新与 React 不同，他的比对顺序会相对复杂：
不断循环判断并执行以下步骤：
- 先找到老集合中的前后边界的节点；
- 将新老集合的前后边界节点两两比对，当比对成功时一起对应指针向中间靠拢（如果是前后交叉匹配成功，进行移动操作）；
- 通过新节点的 key 找到老集合中的相同节点，若找到，便进行移动；若未找到，创建一个新节点插入。
直到新老边界指针有一组出现交叉，则表示其中一组已经遍历结束，退出循环开始剩余节点的新增或删除。
其中的步骤二，正好解决的就是 React 待优化的场景，同样的场景在 Vue 中执行时,只需要把 D 移动到第一位就行了：
但是当 Vue 遇到 React 例一中的场景，却变得无能为力，会直接开始依靠 key 遍历更新。
小结
Vue 和 React 的 diff 算法优化思想是几乎相同的，但是他们在具体实现上的差别是因为处理某些场景的优先级不同导致的， Vue 对于节点列表中的移动场景更新渲染更友好（拖拽，翻转等），而 React 在这方面并没有做太多优化。不过 Vue 和 React 的关系总是这样，一个是开创者，一个是优化者（理性讨论不是引战～）。
