理解DOM Diff算法
虚拟 DOM 出现的背景：在 jQuery 时代，可以自行控制 DOM 操作的时机，手动调整，但是当项目很大时，操作 DOM 的复杂度就会上来，DOM 操作会很耗费性能，操作 DOM 就还需要考虑优化 DOM 操作，提升性能。《高性能 JavaScript》这本书中说，把 DOM 和 JavaScript 各自想象成一个岛屿，它们之间用收费桥梁连接。操作 DOM 后需要经过跨流程通信和渲染线程触发的重新渲染（重绘或者重排），在开发中，应尽量减少操作 DOM。而虚拟 DOM 出现后，更新 DOM 交给框架处理。操作虚拟 DOM 可能并没有操作真实 DOM 快，但是它让开发人员不再把很多精力放在操作 DOM 上，而是专注于处理业务数据。本文以 Vue 原码中的 DOM diff 算法为例，介绍一下这个算法的实现原理。
虚拟 DOM 是用 JavaScript 模拟 DOM 结构，通过计算出最小的变更，操作 DOM 结构，更新视图。而 Diff 算法是虚拟 DOM 最核心、最关键的部分，好的 Diff 算法可以正确、快速的更新 DOM。DOM diff 算法时间复杂度为 O(n)。它的大概逻辑如下：
- 只比较同一层级，不跨级比较；
- tag 不同（标签类型）则直接删掉重建，不再深度比较；
- tag 和 key 两者都相同则认为是相同的节点，不再深度比较。
虚拟 DOM 并不一定比真实 DOM 更新视图更快，但是它的出现让开发人员省去了操作 DOM 的时间成本和精力，让开发更专注于业务本身。虚拟 DOM 使用 JavaScript 模拟实现，这也为创建跨平台应用提供了可能，比如 React Native。
JavaScript 可以使用对象描述 DOM 结构，例如：
{
tag: 'div',
props: {
className: 'container',
},
children: [{
tag: 'p',
children: 'hello!'
}]
}
上面的对象映射出 DOM 结构就是：
<div class="container">
<p>hello!</p>
</div>
在 Vue 源码中，有一个 sameVnode 函数，它用来判断新老节点是不是同一个节点，代码大致如下：
function sameVnode (a, b) {
return (
a.key === b.key && (
(
a.tag === b.tag &&
a.isComment === b.isComment &&
isDef(a.data) === isDef(b.data) &&
sameInputType(a, b)
)
)
)
}
a 是 oldVnode 即老的虚拟 DOM，b 是新的虚拟 DOM，从代码中大致可以了解到，a 和 b 的判断条件有：
key我们添加的key，它们要相等；tag标签名要一致；isComment表示不是不是注释节点；isDef这个函数用来判断传入的数据是不是有值（即数据不等于 undefined 和 null 时返回 true）；sameInputType如果节点是 input 元素时，判断 type 是否相同；
接下来是 patch 函数，当数据发生变化时，set 方法会调用 dep.notify 通知所有订阅者 Watcher，订阅者就会调用 patch 函数，给真实 DOM 打补丁，更新视图。
大致代码如下：
function patch (oldVnode, vnode, hydrating) {
if (isUndef(vnode)) { // 如果新的虚拟节点是 undefined 或 null，并且老虚拟节点有值
// 说明我们删除了节点，就调用 Destroy 生命周期钩子
if (isDef(oldVnode)) invokeDestroyHook(oldVnode)
return;
}
let isInitialPatch = false
const insertedVnodeQueue = []
if (isUndef(oldVnode)) { // 如果老节点没有值
// 这说明是首次调用 path，这是初次渲染
// 初次渲染就直接把 vnode 挂载到 DOM 元素上
isInitialPatch = true
createElm(vnode, insertedVnodeQueue)
} else {
// 判断老虚拟节点是不是真实 DOM
const isRealElement = isDef(oldVnode.nodeType)
// 如果不是真实 DOM 并且 vnode 相同，就调用 pathVnode 进一步处理
if (!isRealElement && sameVnode(oldVnode, vnode)) {
// patch existing root node
patchVnode(oldVnode, vnode, insertedVnodeQueue, null, null)
}else{ // 不相等就直接删掉 oldVnode，重新创建
const oldElm = oldVnode.elm // oldVnode 对应的真实元素
const parentElm = nodeOps.parentNode(oldElm); // 拿到父元素
createElm(vnode, insertedVnodeQueue);
if(parentElm !== null){
// 将新元素插入到父元素中
insertBefore(parentElm, vnode.elm, nodeOps.nextSibling(oldElm));
// 移除老的节点
removeVnodes(parentElm, [oldVnode], 0, 0);
}
}
} // 返回新的节点
return vnode.elem
}
大致流程如下：
patch 函数
当 oldVnode 与 newVnode 相同时，调用 patchVnode 函数。他比较的不是真实节点，而是虚拟节点（JS 对象）。大致代码如下：
function patchVnode (oldVnode, vnode) {
if (oldVnode === vnode) {
// 新老节点相同，就直接返回
return
}
// oldVnode 和 vnode 的标签一样，直接把老的虚拟DOM对应的元素赋给新的即可
const elm = vnode.elm = oldVnode.elm;
const oldCh = oldVnode.children; // 获取到老虚拟节点的儿子
const ch = vnode.children; // 获取到新虚拟节点的儿子
// 比较新老虚拟节点的儿子节点
// 如果 vnode 没有文本
if (isUndef(vnode.text)) {
// 如果都有儿子节点
if (isDef(oldCh) && isDef(ch)) {
if (oldCh !== ch) // 而且两个儿子节点不相同，这时就要更新儿子节点
updateChildren(elm, oldCh, ch, insertedVnodeQueue);
} else if (isDef(ch)) {
// oldVnode 有文本，新的没有，删掉老的文本
if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '');
// 如果新的儿子有，老的儿子节点没有
// 会把新增的子节点插入到老的 DOM 上
addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue);
} else if (isDef(oldCh)) {
// 如果 oldVnode 有子节点，而 vnode 没有子节点
// 就直接删掉子节点
removeVnodes(oldCh, 0, oldCh.length - 1);
} else if (isDef(oldVnode.text)) {
// 老的有文本，新的没有文本
// 就把老的元素文本设置成空
nodeOps.setTextContent(elm, '');
}
} else if (oldVnode.text !== vnode.text) {
// 都有文本，但不相同，就使用 vnode（新的）的文本
nodeOps.setTextContent(elm, vnode.text);
}
}
patchVnode 的函数执行大致如下：
patchVnode 函数
接下来是 diff 算法中最为核心的一个函数：updateChildren。DOM diff 算法有以下几个特点：
- 先同级比较，再比较子节点；
- 先判断一方有 children，一方没有 children 的情况；
- 比较都有 children 的情况；
- 递归比较子节点；
updateChildren 函数代码大致如下：
function updateChildren (parentElm, oldCh, newCh, insertedVnodeQueue) {
// parentElm 是传入的父元素，oldCh 是老的子节点；newCh 是新的子节点
let oldStartIdx = 0; // oldVnode 子节点初始索引
let newStartIdx = 0 // vnode 子节点初始索引
let oldEndIdx = oldCh.length - 1 // oldVnode 子节点的尾索引
let oldStartVnode = oldCh[0] // oldVnode 第一个子节点
let oldEndVnode = oldCh[oldEndIdx] // oldVnode 最后一个子节点
let newEndIdx = newCh.length - 1 // vnode 子节点的尾索引
let newStartVnode = newCh[0] // vnode 的第一个子节点
let newEndVnode = newCh[newEndIdx] // vnode 的最后一个子节点
let oldKeyToIdx, idxInOld, vnodeToMove;
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if (isUndef(oldStartVnode)) { // 如果 oldVnode 的第一个子节点没有值
// 指针向右移动
oldStartVnode = oldCh[++oldStartIdx];
} else if (isUndef(oldEndVnode)) { // 如果 oldVnode 的最后一个子节点没有值
// 指针向左移动
oldEndVnode = oldCh[--oldEndIdx]
}
else if (sameVnode(oldStartVnode, newStartVnode)) { // 判断开始和开始索引的子节点是否相同
// 相同就递归（子节点里可能还有子节点，还需要判断）
patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx);
// 两个指针同时前进（向右移动）
oldStartVnode = oldCh[++oldStartIdx]
newStartVnode = newCh[++newStartIdx]
} else if (sameVnode(oldEndVnode, newEndVnode)) { // 两个尾部元素是不是相同
// 相同递归做进一步处理
patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
// 两个指针同时向左移动
oldEndVnode = oldCh[--oldEndIdx]
newEndVnode = newCh[--newEndIdx]
} else if (sameVnode(oldStartVnode, newEndVnode)) { // 老的开始节点和新的结束节点如果相同
patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
// 把 oldStartVnode 对应的元素（头指针指向的节点）移动到 oldEndVnode 对应的元素（尾指针指向的节点）的前面
nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
oldStartVnode = oldCh[++oldStartIdx] // 老的指针向右移动
newEndVnode = newCh[--newEndIdx] // 新的指针向左移动
} else if (sameVnode(oldEndVnode, newStartVnode)) { // 老的结束节点和新的开始节点如果相同
patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
// 把 oldEndVnode 对应的元素（尾指针指向的节点）移动到 oldStartVnode 对应的元素（头指针指向的节点）的前面
nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
oldEndVnode = oldCh[--oldEndIdx] // 老的指针向左移动
newStartVnode = newCh[++newStartIdx] // 新的指针向右移动
}
// 上面四个判断是做优化用的几个“特殊情况”，即开始与结束、开始与开始、结束与开始、结束与结束的节点都不相同
else {
// 如果 oldKeyToIdx 没有，就遍历老的子节点，生成一个对象，对象的键是元素的 key，值是元素的索引
if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
// 新节点的 key，能否对应上 oldCh 中的某个节点的 key
idxInOld = isDef(newStartVnode.key) // 新的开始元素有没有 key
? oldKeyToIdx[newStartVnode.key] // 通过 key 可以拿到老的子元素的索引
// 如果新的开始元素没有 key，就遍历老的子节点，找到对应 key 的索引，没有找到会是 undefined
: findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
if (isUndef(idxInOld)) { // 如果 idxInOld 是 undefined，说明没有找到对应的 key
// 新节点的 key 没有找到对应的旧节点，则新节点 key 对应的元素会插入到 oldStartVnode 对应的元素的前面
createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx) // 1
} else { // 如果找到了对应的 key，通过索引获取到老节点 key 对应的元素
vnodeToMove = oldCh[idxInOld] // 引用
if (sameVnode(vnodeToMove, newStartVnode)) { // 比较是否相同
patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
oldCh[idxInOld] = undefined // 把对应的元素设置成 undefined
// 然后把 vnodeToMove 对应的元素移动到 oldStartVnode 对应的元素前面
nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
} else {
// 相同的 key，但是不是同一个节点，则新节点 key 对应的元素会插入到 oldStartVnode 对应的元素的前面，与 1 处一样
createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx);
// createElm(vnodes[startIdx], insertedVnodeQueue, parentElm, refElm, false, vnodes, startIdx)
}
}
// 操作完之后，将新节点的开始指针向右移动
newStartVnode = newCh[++newStartIdx]
}
} // 上面判断条件走完之后，需要判断新的开始索引是不是移动到结束索引的右边去了
if (newStartIdx > newEndIdx) {
removeVnodes(oldCh, oldStartIdx, oldEndIdx) // 把旧的开始和结束之间的元素移除
}
}
下面以一个例子演示一下 diff 的工作流程。
假如 oldVnode 是左边的结构，vnode 是右边的结构。
新旧虚拟DOM树
遍历子节点之后，初始化指针：
初始化指针
然后判断，首先是 oldStart 和 newStart，发现节点相同（假设相同的字母，它们的 key 也相同），两个指针都向右移动。一个指向 C，一个指向 E，发现节点不一样，然后：
- oldEndIdx 和 newEndIdx 对应的节点比较，不相同（D 和 C 节点）；
- oldStartIdx 和 newEndIdx 对应的节点比较，发现一样（oldStartIdx 已经往右移动了，对应于 C，而 newEndIdx 对应的也是 C），这个时候会遍历 C 中子节点，发现没有子节点，然后将 oldStartIdx 对应的节点 C 插入到 oldEndIdx （D 节点）的后面，然后 oldStartIdx++，newEndIdx--，新旧指针就移动到了如下的位置：
oldStart=newEnd
- 走完一次 while 循环，接着又开始一轮。
oldStart和newStart都指向 E 节点，两个指针都向右移动（都和 end 指针重合），然后（又一轮循环）oldEnd和newEnd都指向 D 节点，指针都向左移动。接着又一轮循环，结果发现循环条件不能满足，diff 算法结束，DOM 更新完成。
下面是有新增元素的例子：
新旧节点如下（第一行是旧节点）：
A B C D
C D M E
调用 updateChildren 时会发现开始与开始、结束与结束、开始与结束、结束与开始对应的节点都不一样。这时候就要遍历旧节点，找到与 newStartIdx 对应元素的 key 一样的节点。在旧节点中可以找到 C，它的索引值是 2。把 oldChildren[2]（C 节点所在位置）设置成 undefined，然后把 oldVnode 中的 C 移到 oldStartVnode 的前面（A 节点）。
C A B undefined D
C D M E
然后 newStartIdx 向右移动，条件判断，发现 oldEndVnode 也是 D 节点，会把 D 节点移动到 oldStartVnode （A 节点）前面，变成：
C D A B undefined undefined
C D M E
newStartIdx 继续向右移动，发现新的节点 M（key 没有在 oldChildren 中找到），把 M 放到 oldStartVnode（A 节点）前面，变成：
C D M A B undefined undefined
C D M E
newStartIdx 继续向右移动，新节点 E 与 M 一样，变成：
C D M E A B
C D M E
移动之后，newStartIdx ++，此时的 newStartIdx （为 4）会比 newEndIdx （为 3 指向 E 点）大，就会把 oldStartIdx 和 oldEndIdx 之间的节点删掉，即删掉 A 与 最右边的 undefined 之间的节点（包括自身）。变成：
C D M E
C D M E
到此，diff 完毕。
通过代码我们能发现，Vue 会通过判断 key 的方式来判断是不是同一个节点。如果使用数组的索引作为 key，当对数组排序然后重新渲染时，节点的索引值很可能会发生改变，索引值发生改变导致 key 也会发生改变，节点还是原来的节点，但是它的 key 却发生了变化，这会导致 Vue 重新创建节点，而不是移动节点。因此不推荐使用索引作为 key。更不推荐使用随机数（比如 Math.random）作为 key，当组件更新时，随机数会跟着变化，导致 key 每次都不一样。