Vue2.0加入了Virtual Dom，Vue的Diff位于patch.js文件中，该算法来源于snabbdom，复杂度为O(n)
React的 Diff其实和Vue的 Diff 大同小异，只比较同层级节点，不会跨层级比较，目的就是最小变动
Diff 的过程就是调用 patch 函数，就像打补丁一样修改真实DOM。
patch函数
// 只保留核心部分
function patch(oldVnode, vnode) {
if (sameVnode(oldVnode, vnode)) {
patchVnode(oldVnode, vnode)
} else {
const oEl = oldVnode.el
let parentEle = api.parentNode(oEl)
createEle(vnode)
if (parentEle !== null) {
api.insertBefore(parentEle, vnode.el, api.nextSibling(oEl))
api.removeChild(parentEle, oldVnode.el)
oldVnode = null
}
}
return vnode
}
(oldVnode, vnode) 也就是新旧两个虚拟DOM节点，一个完整的 vnode 都有什么属性：
// body下的 <div id="v" class="classA"><div> 对应的 oldVnode 就是
{
el: div // 对真实节点的引用，document.querySelector('#id.classA')
tagName: 'DIV', // 节点的标签
sel: 'div#v.classA' // 节点的选择器
data: null, // 一个存储节点属性的对象，对应节点的 el[prop] 属性，如onclick, style
children: [], // 存储子节点的数组，每个子节点也是 vnode 结构
text: null, // 如果是文本节点，对应文本节点的textContent，否则为null
}
需要注意的是，属性
el引用的是此Virtual DOM对应的真实DOM，patch()的参数vnode中的el最初为null，因为patch()之前它还没有对应的真实DOM
-
patch(oldVnode, vnode)的第一部分：
if (sameVnode(oldVnode, vnode)) {
patchVnode(oldVnode, vnode)
}
sameVnode() 的作用是看这两个节点是否值得比较，代码很简单：
function sameVnode(oldVnode, vnode){
// 只保留核心部分
return vnode.key === oldVnode.key && vnode.sel === oldVnode.sel
}
两个 vnode 的 key 和 sel 相同才会去比较它们，比如 p和span、div.classA和div.classB 都被认为是不同结构而不去比较它们。
不值得比较的节点会进入 else 中，过程如下：
else {
// 1. 获取 oldVnode.el 的父节点，parentEle 是真实DOM
const oEl = oldVnode.el
let parentEle = api.parentNode(oEl)
// 2. 为 vnode 创建它的真实DOM，令 vnode.el = 真实DOM
createEle(vnode)
if (parentEle !== null) {
// 3. parentEle 将新的DOM插入，移除旧的DOM
api.insertBefore(parentEle, vnode.el, api.nextSibling(oEl))
api.removeChild(parentEle, oldVnode.el)
oldVnode = null
}
}
当不值得比较时，新节点直接把老节点整个替换掉了
最后执行：return vnode，返回的 vnode 与传入时的 vnode 的区别就在于：vnode.el，之前 vnode.el=null，而现在 vnode.el=对应的真实DOM
var oldVnode = patch (oldVnode, vnode)
至此完成一个patch过程。
-
patchVnode(oldVnode, vnode)
两个节点值得比较时，会调用patchVnode()函数
patchVnode (oldVnode, vnode) {
// 只保留核心部分
const el = vnode.el = oldVnode.el // 引用真实DOM
let i, oldCh = oldVnode.children, ch = vnode.children
if (oldVnode === vnode) return
if (oldVnode.text !== null && vnode.text !== null && oldVnode.text !== vnode.text) {
api.setTextContent(el, vnode.text)
}else {
updateEle(el, vnode, oldVnode)
if (oldCh && ch && oldCh !== ch) {
updateChildren(el, oldCh, ch)
}else if (ch){
createEle(vnode) //create el's children dom
}else if (oldCh){
api.removeChildren(el)
}
}
}
const el = vnode.el = oldVnode.el 这是很重要的一步，让 vnode.el 引用到当前的真实DOM，当 el 变量修改时，vnode.el 会同步变化。
节点比较的5种情况
-
if (oldVnode === vnode)它们的引用一致，可以认为没有变化，直接return -
if (oldVnode.text !== null && vnode.text !== null && oldVnode.text !== vnode.text)文本节点的比较，需要修改时，则会调用oldVnode.textContent = vnode.text -
if (oldCh && ch && oldCh !== ch)两个节点都有子节点，且它们不一样，则调用updateChildren()函数去比较子节点，这是Diff的核心 -
else if (ch)只有新的节点有子节点，调用createEle(vnode)，vnode.el已经引用了老的DOM几点，createEle函数会在老的DOM节点上添加子节点。 -
else if (oldCh)新节点没有子节点，老节点有子节点，则直接删除老节点。
updateChildren
function updateChildren(parentElm, oldCh, newCh) {
let oldStartIdx = 0, 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
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if (oldStartVnode == null) { //对于vnode.key的比较，会把oldVnode = null
oldStartVnode = oldCh[++oldStartIdx]
} else if (oldEndVnode == null) {
oldEndVnode = oldCh[--oldEndIdx]
} else if (newStartVnode == null) {
newStartVnode = newCh[++newStartIdx]
} else if (newEndVnode == null) {
newEndVnode = newCh[--newEndIdx]
} else if (sameVnode(oldStartVnode, newStartVnode)) { // 比较方式一
// 头头比较通过，patch不同之处，如class、style
patchVnode(oldStartVnode, newStartVnode)
// 向后移动指针
oldStartVnode = oldCh[++oldStartIdx]
newStartVnode = newCh[++newStartIdx]
} else if (sameVnode(oldEndVnode, newEndVnode)) { // 比较方式二
// 尾尾比较通过，patch不同之处
patchVnode(oldEndVnode, newEndVnode)
// 向前移动指针
oldEndVnode = oldCh[--oldEndIdx]
newEndVnode = newCh[--newEndIdx]
} else if (sameVnode(oldStartVnode, newEndVnode)) { // 比较方式三
// 旧头与新尾比较通过，patch不同之处
patchVnode(oldStartVnode, newEndVnode)
// 移除这个旧节点，再添加到数组尾部
api.insertBefore(parentElm, oldStartVnode.el, api.nextSibling(oldEndVnode.el))
oldStartVnode = oldCh[++oldStartIdx]
newEndVnode = newCh[--newEndIdx]
} else if (sameVnode(oldEndVnode, newStartVnode)) { // 比较方式四
// 新头与旧尾比较通过，patch不同之处
patchVnode(oldEndVnode, newStartVnode)
// 移除这个旧节点，再添加到数组头部
api.insertBefore(parentElm, oldEndVnode.el, oldStartVnode.el)
oldEndVnode = oldCh[--oldEndIdx]
newStartVnode = newCh[++newStartIdx]
} else {
// 四种比较方式都不满足，如果设置了key，则使用 key 比较
if (oldKeyToIdx === undefined) {
// 由key生成index表，由此可见，应该给节点数组设置唯一key
oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
}
idxInOld = oldKeyToIdx[newStartVnode.key]
if (!idxInOld) {
// 用新节点的key在 旧节点数组中查找，没有找到这个节点，则插入新节点
api.insertBefore(parentElm, createEle(newStartVnode).el, oldStartVnode.el)
newStartVnode = newCh[++newStartIdx]
} else {
elmToMove = oldCh[idxInOld]
if (elmToMove.sel !== newStartVnode.sel) {
// key虽相同，但节点不同，把这个旧节点替换成新节点
api.insertBefore(parentElm, createEle(newStartVnode).el, oldStartVnode.el)
} else {
// 两个节点相同，则patch不同之处
patchVnode(elmToMove, newStartVnode)
oldCh[idxInOld] = null
// 移除这个旧节点，重新插入更新后的节点
api.insertBefore(parentElm, elmToMove.el, oldStartVnode.el)
}
newStartVnode = newCh[++newStartIdx]
}
}
}
// 检查新旧节点是否还有剩余
if (oldStartIdx > oldEndIdx) {
// 旧节点数组遍历完了，则直接插入剩下的新节点
before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].el
addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx)
} else if (newStartIdx > newEndIdx) {
// 新节点遍历完了，那么直接移除剩下的旧节点
removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
}
}
代码很密集，用图描述这个过程：
updateChildren.png
只有在
oldCh和newCh都存在的情况下才会执行updateChildren()，可知updateChildren()进行的是同层级下的Children的更新比较，也就是传说中的Diff了。
一系列变量
- 旧节点数组
oldCh，新节点数组newCh -
oldStartIdx、oldEndIdx分别指向oldCh头部和尾部，对应元素oldStartVnode、oldEndVnode -
newStartIdx、newEndIdx分别指向newCh头部和尾部，对应元素newStartVnode、newEndVnode -
oldKeyToIdx是一个Map，其key就是v-bind:key的值，value对应的就是当前vnode
过程可以概况为：
头头比较、尾尾比较，头尾比较，尾头比较，如果 4 种比较都不匹配，但设置了key，则会用key进行比较。
具体的Diff分析
Vue2在比较过程中会直接操作DOM，相比之下，React把Diff和DOM操作分为两个阶段，DOM操作在提交阶段。
Diff的遍历过程中，只要是对DOM的操作都会调用 api.insertBefore()，api.insertBefore()只是原生insertBefore()的简单封装。
官方文档：
parentElement.insertBefore(newElement, referenceElement)，如果referenceElement为null，则newElement将被插入到子节点的末尾；如果newElement已经存在于DOM树中，则首先会从DOM树中移除。
- 对于头头比较
sameVnode(oldStartVnode, newStartVnode)和尾尾比较sameVnode(oldEndVnode, newEndVnode)，为true时是不需要对移动DOM的，只是更新节点(patchVnode)。 -
设置
key (v-bind:key="xxx")与不设置key的区别：- 不设
key(undefined)，newCh和oldCh只会进行头尾两端的相互比较；而且sameVnode()在判断两个节点是否值得比较时，无法比较key是否相同。
在特定情况下，比如v-for的列表是10个多选框，选中哪一个则删除哪一个，那么会发现：删除第一个checkbox，新的第一个checkbox会处于选中状态！ - 设置
key，如果头尾两端的比较都不匹配，还会从用key生成的Map对象oldKeyToIdx中查找匹配的节点，最大化的复用节点，提高性能。 - 不建议直接用
index作为key，其实就相当于不加key。当删除/插入元素时，因为后续元素的key="index"都会发生变化，导致它们重新渲染，无法复用，浪费性能。
key="index"只适用于比较稳定的状态。
- 不设
- 当
sameVnode(oldStartVnode, newEndVnode)值得比较时，说明oldStartVnode.el跑到oldEndVnode.el的后边了。
假设startIdx遍历到1.png
- 当
sameVnode(oldEndVnode, newStartVnode)值得比较，oldEndVnode.el跑到了oldStartVnode.el的前边。
准确的说应该是oldEndVnode.el需要移动到oldStartVnode.el的前边。
而实际操作是，先插入，后移除。
2038.png
-
4种头尾方式比较完后，就会去检查旧节点的Map表。根据新节点的
key，到表中查找是否有这样一个节点。- 找不到，说明这个新节点不存在与旧节点树中，将新节点插入到
oldStartVnode.el的前边。
- 找不到，说明这个新节点不存在与旧节点树中，将新节点插入到
createEle.png
- 找到了，也要去检查两个节点是否还是同一节点
elmToMove.sel !== newStartVnode.sel
如果是同一节点，则更新节点，移动到新的位置；否则，替换这个旧节点。
-
while循环结束后（新、旧有一个发生了交叉），也分为两种情况：-
oldStartIdx > oldEndIdx表示旧节点先遍历完。当然有可能newCh也刚好遍历完，但都归为此类。
那么，直接插入剩下的新节点即可。
-
before.png
-
newStartIdx > newEndIdx表示新节点遍历结束，那么就移除剩下的旧节点。
remove.png
小结
- 尽量不要跨层级的修改DOM
- 设置
Key可以最大化的利用节点 - 不要盲目相信
Diff的效率，在必要时可以手工优化
举个例子.png
原有的 oldCh 的顺序是 A 、B、C、D、E、F、G，更新后成 ch 的顺序 F、D、A、H、E、C、B、G
初始状态.png
为了更好理解后续的 STEP，先看下相关符合标记的说明：
图解说明.png
STEP-1
对比 A-F --> G-G，sameVnode(oldEndVnode, newEndVnode)值得比较，DOM顺序不变
- 对
G进行patchVnode()，更新oldG.el - 移动指针：
--oldEndIdx，--newEndIdx
step-1.png
STEP-2
对比 A-F --> F-B --> A-B --> F-F，sameVnode(oldEndVnode, newStartVnode)值得比较
- 对
F进行patchVnode()，更新oldF.el - 找到
oldStartVnode在DOM中的位置A，在其前面插入更新后的F - 移动指针：
--oldEndIdx，++newStartIdx
step-2.png
STEP-3
对比 A-D --> E-B --> A-B --> E-D，sameVnode(old, new)都不匹配，则取newStartVnode的key，即D.key， 在 oldKeyToIdx 中查找，并成功找到对应的D
- 将
D赋值给elmToMove，图示中为vnodeToMove - 对
D进行patchVnode()，更新oldD.el - 将
oldCh中对应D的vnode置空：oldCh[idxInOld] = null - 找到
oldStartVnode在DOM中的位置A，在其前面插入更新后的D - 移动指针：
++newStartIdx
step-3.png
STEP-4
对比 A-A，sameVnode(oldStartVnode, newStartVnode)匹配成功，进行比较，DOM顺序不变
- 将
A进行patchVnode()，更新oldA.el - 移动指针：
++oldStartIdx，++newStartIdx
step-4.png
STEP-5
对比 B-H --> E-B --> B-B，sameVnode(oldStartVnode, newEndVnode)值得比较
- 将
B进行patchVnode()，更新oldB.el - 找到
oldEndVnode - E的下一个兄弟节点G，在其前面（G前面、E后面）插入更新后的B - 移动指针：
++oldStartIdx，--newEndIdx
step-5.png
STEP-6
对比 C-H --> E-C --> C-C，sameVnode(oldStartVnode, newEndVnode)值得比较（同STEP-5）
- 将
C进行patchVnode()，更新oldC.el - 找到
oldEndVnode - E的下一个兄弟节点B，在其前面（B前面、E后面）插入更新后的C - 移动指针：
++oldStartIdx，--newEndIdx
step-6.png
STEP-7
因为 STEP-3 中的 oldCh[idxInOld] = null，当前获取的 oldStartVnode = null
- 移动指针：
++oldStartIdx
step-7.png
STEP-8
对比 E-H --> E-E，sameVnode(oldEndVnode, newEndVnode)值得比较，DOM顺序不变
- 将
E进行patchVnode()，更新oldE.el - 移动指针：
--oldEndIdx，--newEndIdx
step-8.png
last
此时的 oldStartIdx > oldEndIdx，有一方发生了交叉，则退出循环。
if (oldStartIdx > oldEndIdx) {
before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].el
addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx)
}
旧VirtualDOM 首先发生交叉，所以把新VirtualDOM中剩余的节点直接插入到oldCh中
- 找到
newEndIdx + 1 位置E --> before - 剩余的待处理部分：
newStartIdx -- newEndIdx 之间的 vnode视为新增的部分-- [ H ] - 插入到
before位置E的前面
last.png
注意点
- 在
Diff过程中，oldCh和newCh的位置并不会发生变化，真正进行操作的是传入的parentElm -- 父vnode的elm - 插入操作使用的
insertBefore(newElement, referenceElement)，在指定节点前插入。 -
patch()中其实还有一个数组insertedVnodeQueue，涉及到组件的patch过程：组件的$mount函数之后之后并不会立即触发组件实例的mounted钩子，而是把当前实例push到insertedVnodeQueue中，然后在patch的倒数第二行执行invokeInsertHook -- 触发所有组件实例的insert钩子，而组件的insert钩子函数中才会触发组件实例的mounted钩子。比如，在patch的过程中，patch了多个组件vnode，它们都进行了$mount即生成DOM，但没有立即触发mounted，而是等整个patch完成，再逐一触发。
