Diff 算法
Diff算法的核心就是针对具有相同父节点的同层新旧子节点进行比较，而不是使用逐层搜索递归遍历的方式。时间复杂度为O(n)。
如何理解？
说白点，就是当新旧VNode树在同一层具有相同的VNode节点时，才会继续对其子节点进行比较。一旦旧VNode树同层中的节点在新VNode树中不存在或者是多余的，都会在新的真实DOM中进行添加或者删除。
下面就拿一副图进行解释。
从上面的示例图可以看到，Diff算法中只会对同一层的元素进行比较，并且必须拥有相同节点元素，才会对其子节点进行比较，其他多余的同层节点都会一律做删除或添加操作。
接下来，我们就从源码角度来看看这过程到底是如何发生的。🤔
diff 流程图
当数据发生改变时，set 方法会让调用Dep.notify通知所有订阅者Watcher，订阅者就会调用patch给真实的 DOM 打补丁，更新相应的视图。
从源码角度进行探究
我们依然是从_update方法入手，看看到底是如何操作的。
1Vue.prototype._update = function (vnode, hydrating) {
2 const vm = this // 缓存vue实例
3 const prevEl = vm.$el // 获取实例中真实DOM元素
4 const prevVnode = vm._vnode // 获取旧VNode树
5 vm._vnode = vnode // 将新VNode树保存到实例的_vnode上，便于下次更新获取旧VNode树
6
7 if (!prevVnode) {
8 // 判断是否有旧VNode树，并进行相应的处理
9 // initial render
10 // 最开始的一次，即第一次渲染时是没有旧VNode树，直接执行__patch__
11 vm.$el = vm.__patch__(vm.$el, vnode, hydrating, false /* removeOnly */)
12 }
13 else {
14 // updates
15 vm.$el = vm.__patch__(prevVnode, vnode) // 新VNode树与旧VNode树进行__patch__
16 }
17 // ...
18}
每一次更新模板时，都会先将渲染好的新VNode树保存到实例的_vnode属性上，这样做的目的是为了下一次更新时，能获取到旧VNode树进行比较。
针对是否拥有旧的VNode树，使用__patch__方法执行相应逻辑，也即执行了patch过程。
1const inBrowser = typeof window !== 'undefined' // 浏览器环境
2Vue.prototype.__patch__ = inBrowser ? patch : noop // 只有在浏览器环境才能进行patch
3
4var patch = createPatchFunction({ nodeOps, modules })
可以看到，只有在浏览器的环境下才能进行patch过程，而实现patch的，就是createPatchFunction方法，我们接着看下去。
1function createPatchFunction(backend) {
2 // ...
3 // 省略了很多私有工具方法，下面会拿出一些进行说明
4 return function patch(oldVnode, vnode, hydrating, removeOnly) {
5 if (isUndef(oldVnode)) {
6 // 当旧VNode树不存在时，则直接创建一个根元素
7 // empty mount (likely as component), create new root element
8 isInitialPatch = true
9 createElm(vnode, insertedVnodeQueue) // 直接根据新VNode树并生成真实DOM
10 }
11 else {
12 // 当存在旧VNode树时，则进行相应的比较
13 // ...
14 if (sameVnode(oldVnode, vnode)) {
15 // 新旧节点是相同时
16 // patch existing root node
17 // 当新旧节点相同时则进行patch比较
18 patchVnode(oldVnode, vnode, insertedVnodeQueue, null, null, removeOnly)
19 }
20 else {
21 // 新旧节点不相同时
22 const oldElm = oldVnode.elm // 获取旧节点元素
23 const parentElm = nodeOps.parentNode(oldElm) // 获取旧节点的父节点
24
25 // create new node
26 createElm(
27 // 由于新旧节点是不同的，因此会根据新节点创建一个新的节点
28 vnode,
29 insertedVnodeQueue,
30 oldElm._leaveCb ? null : parentElm,
31 nodeOps.nextSibling(oldElm)
32 )
33
34 // destroy old node
35 if (isDef(parentElm)) {
36 // 创建好新节点后，删除旧节点
37 removeVnodes(parentElm, [oldVnode], 0, 0)
38 }
39 else if (isDef(oldVnode.tag)) {
40 // 删除响应节点后，也会调用相应的回调
41 invokeDestroyHook(oldVnode)
42 }
43 }
44 }
45 }
46}
好啦，对于patch比较过程，你也应该有了一个大概了解。现在就来简单总结一下上述代码。
- 当旧
VNode树不存在时，直接根据新VNode树创建相应的真实DOM。
- 当旧
VNode树存在时，则会调用sameVnode方法比较当前新旧节点是否相同。
- 当新旧节点是相同时，会调用
patchVnode方法比较新旧节点（过程就是继续比较其子节点，递归下去～）。
- 当新旧节点是不同时，则会先按照新
VNode节点创建新的真实DOM节点，再根据旧VNode节点将相应的真实DOM节点进行删除。
是不是很简单 🤔...那么问题来了，不是说patch过程是使用Diff算法进行比较的吗？怎么还看不到，甭急，下面我会讲到哈。
在上面的总结中，我们是可以看到两个方法，分别是sameVnode方法和patchVnode方法。接下来我们就来探讨一下这两个方法。
sameVnode
判断两个节点间是否相同
1function sameVnode(a, b) {
2 // 判断两个节点间是否相同
3 return (
4 a.key === b.key // 两个节点间相同，首先是唯一标识key必须相同
5 && ((a.tag === b.tag && a.isComment === b.isComment && isDef(a.data) === isDef(b.data) && sameInputType(a, b)) // 接着就是节点标签名、是否为注释、数据是否为空、input类型都必须相同
6 || (isTrue(a.isAsyncPlaceholder) && a.asyncFactory === b.asyncFactory && isUndef(b.asyncFactory.error)))
7 )
8}
9
10function sameInputType(a, b) {
11 // 比较两个节点的input类型是否相同
12 if (a.tag !== 'input')
13 return true
14
15 let i
16 const typeA = isDef((i = a.data)) && isDef((i = i.attrs)) && i.type
17 const typeB = isDef((i = b.data)) && isDef((i = i.attrs)) && i.type
18 return typeA === typeB || (isTextInputType(typeA) && isTextInputType(typeB))
19}
比较两个新旧节点间是很简单的，主要是按照下面几个属性进行判断。
VNode节点唯一标识key。- 是否同为注释
isComment。
- 数据属性是否为空
isDef。
- 是否为相同的
input类型sameInputType。
patchVnode
好啦，接着就到我们的主角patchVnode方法了，这个才是Diff相关方法，我们先来看看源码是如何实现的。🤔
1function patchVnode(oldVnode, vnode, insertedVnodeQueue, ownerArray, index, removeOnly) {
2 if (oldVnode === vnode) {
3 // 当发现两个节点是完全一模一样时，则直接返回
4 return
5 }
6 // ...
7 const elm = (vnode.elm = oldVnode.elm)
8 // ...
9 let i
10 const data = vnode.data
11 if (isDef(data) && isDef((i = data.hook)) && isDef((i = i.prepatch)))
12 i(oldVnode, vnode) // 根据新VNode更新旧VNode的选项配置、数据属性、propsData等
13
14 const oldCh = oldVnode.children // 获取oldVNode的子节点集合
15 const ch = vnode.children // 获取VNode的子节点集合
16 // ...
17 if (isUndef(vnode.text)) {
18 // 当VNode不为文本节点时
19 if (isDef(oldCh) && isDef(ch)) {
20 // 当oldVNode的子节点和VNode的子节点都不为空时
21 if (oldCh !== ch) {
22 // 当oldVNode的子节点和VNode的子节点不等时，再递归执行updateChildren比较子节点
23 updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)
24 }
25 }
26 else if (isDef(ch)) {
27 // 当只有VNode的子节点存在而oldVNode的子节点不存在时
28 // ...
29 if (isDef(oldVnode.text)) {
30 // 当oldVNode为文本节点时，先置空文本
31 nodeOps.setTextContent(elm, '')
32 }
33 addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue) // 根据位置对真实DOM添加新的节点
34 }
35 else if (isDef(oldCh)) {
36 // 当oldVNode的子节点存在, 而VNode的子节点不存在时
37 removeVnodes(elm, oldCh, 0, oldCh.length - 1) // 直接移除所有多余节点
38 }
39 else if (isDef(oldVnode.text)) {
40 // 当只有oldVNode的子节点存在,并且是文本节点时
41 nodeOps.setTextContent(elm, '') // 直接置空文本处理
42 }
43 }
44 else if (oldVnode.text !== vnode.text) {
45 // 当oldVNode文本节点不等于VNode文本节点时
46 nodeOps.setTextContent(elm, vnode.text) // 直接将oldVNode节点设置为VNode节点文本内容
47 }
48 // ...
49}
patchVnode方法做的事情不多，最主要就是按照一下场景做了处理;
diff过程中又分了好几种情况，oldCh 为 oldVnode的子节点，ch 为 Vnode的子节点：
- 首先进行文本节点的判断，若
oldVnode.text !== vnode.text，那么就会直接进行文本节点的替换；
在vnode没有文本节点的情况下，进入子节点的 diff；- 当
oldCh 和 ch 都存在且不相同的情况下，调用 updateChildren 对子节点进行 diff；
- 若
oldCh不存在，ch 存在，首先清空 oldVnode 的文本节点，同时调用 addVnodes 方法将 ch 添加到elm真实 dom 节点当中；
- 若
oldCh存在，ch不存在，则删除 elm 真实节点下的 oldCh 子节点；
- 若
oldVnode 有文本节点，而 vnode 没有，那么就清空这个文本节点。
接下来才是最重点呀。。😅 在上面中留下了updateChildren方法，那么这个方法又是干啥？
不瞒你说，updateChildren方法在根据场景Diff后，将oldVNode树作出相应的改动。在没有看源码之前，我会先阐述一下。
Diff算法过程中，在将oldVNode树改动时，优先考虑相同位置的相同节点，再考虑需要移动的相同节点，最后才考虑创建或删除节点。
updateChildren
有了上面的简单理解，我们就来继续探究啦 😄。
1function updateChildren(parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {
2 let oldStartIdx = 0 // 旧节点开始位置
3 let newStartIdx = 0 // 新节点开始位置
4 let oldEndIdx = oldCh.length - 1 // 旧节点结束位置
5 let oldStartVnode = oldCh[0] // 旧节点第一个元素
6 let oldEndVnode = oldCh[oldEndIdx] // 旧节点最后一个元素
7 let newEndIdx = newCh.length - 1 // 新节点结束位置
8 let newStartVnode = newCh[0] // 新节点第一个元素
9 let newEndVnode = newCh[newEndIdx] // 新节点最后一个元素
10 let oldKeyToIdx, idxInOld, vnodeToMove, refElm
11 // ...
12 while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
13 // 同时从新旧子节点集合开始遍历
14 if (isUndef(oldStartVnode)) {
15 // 从第一项开始，一直遍历旧节点初始元素直到不为空为止
16 oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left
17 }
18 else if (isUndef(oldEndVnode)) {
19 // 从最后一项开始，一直遍历旧节点直到不为空为止
20 oldEndVnode = oldCh[--oldEndIdx]
21 }
22 else if (sameVnode(oldStartVnode, newStartVnode)) {
23 // （相同位置场景）当第一项旧节点和第一项新节点相同时，则继续执行patchVnode递归执行下去
24 patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
25 oldStartVnode = oldCh[++oldStartIdx]
26 newStartVnode = newCh[++newStartIdx]
27 }
28 else if (sameVnode(oldEndVnode, newEndVnode)) {
29 // （相同位置场景）当最后一项旧节点和最后一项新节点相同时，则继续执行patchVnode递归执行下去
30 patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
31 oldEndVnode = oldCh[--oldEndIdx]
32 newEndVnode = newCh[--newEndIdx]
33 }
34 else if (sameVnode(oldStartVnode, newEndVnode)) {
35 // （需要移动场景）当第一项旧节点和最后一项新节点相同时，先执行patchVnode递归执行下去，再执行insertBefore将真实DOM节点插入到相应位置
36 patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
37 canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
38 oldStartVnode = oldCh[++oldStartIdx]
39 newEndVnode = newCh[--newEndIdx]
40 }
41 else if (sameVnode(oldEndVnode, newStartVnode)) {
42 // （需要移动场景）当最后一项旧节点和第一项新节点相同时，先执行patchVnode递归执行下去，再执行insertBefore将真实DOM节点插入到相应位置
43 patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
44 canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
45 oldEndVnode = oldCh[--oldEndIdx]
46 newStartVnode = newCh[++newStartIdx]
47 }
48 else {
49 // 比较头尾都无相同元素时，直接判断新节点是否在旧节点结合中，若有则直接移动相应的位置，若无则直接新建一个节点
50 if (isUndef(oldKeyToIdx))
51 oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
52 // 将旧节点结合创建一个哈希表
53 idxInOld = isDef(newStartVnode.key)
54 ? oldKeyToIdx[newStartVnode.key]
55 : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx) // 根据哈希表，判断新节点是否在哈希表中，并获得对应旧节点的索引位置
56 if (isUndef(idxInOld)) {
57 // 当新节点不在旧节点集合中时，新建一个真实DOM节点
58 createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
59 }
60 else {
61 // 当新节点在旧节点集合中时，则会先判断两个节点是否相同
62 vnodeToMove = oldCh[idxInOld] // 根据索引位置获得旧节点
63 if (sameVnode(vnodeToMove, newStartVnode)) {
64 // 当两个节点是相同时，继续执行patchVnode递归执行下去，再执行insertBefore将真实DOM节点插入到相应位置
65 patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
66 oldCh[idxInOld] = undefined
67 canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
68 }
69 else {
70 // 当两个节点不同时，直接新建一个新的DOM节点
71 // same key but different element. treat as new element
72 createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
73 }
74 }
75 newStartVnode = newCh[++newStartIdx]
76 }
77 }
78 if (oldStartIdx > oldEndIdx) {
79 // 跳出循环后，若新节点依旧存在，那么就要遍历剩余的新节点并逐个新增到真实DOM中
80 refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm
81 addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
82 }
83 else if (newStartIdx > newEndIdx) {
84 // 跳出循环后，若旧节点依旧存在，那么就要将真实DOM中对应旧VNode节点进行删除操作
85 removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
86 }
87}
具体的 diff 分析
我们可以假设有旧的 Vnode 数组和新的 Vnode 数组这两个数组,而且有四个变量充当指针分别指到两个数组的头尾.
重复下面的对比过程，直到两个数组中任一数组的头指针超过尾指针，循环结束 :
- 头头对比: 对比两个数组的头部，如果找到，把新节点 patch 到旧节点，头指针后移
- 尾尾对比: 对比两个数组的尾部，如果找到，把新节点 patch 到旧节点，尾指针前移
- 旧尾新头对比: 交叉对比，旧尾新头，如果找到，把新节点 patch 到旧节点，旧尾指针前移，新头指针后移
- 旧头新尾对比: 交叉对比，旧头新尾，如果找到，把新节点 patch 到旧节点，新尾指针前移，旧头指针后移
- 利用 key 对比: 用新指针对应节点的 key 去旧数组寻找对应的节点,这里分三种情况,当没有对应的 key，那么创建新的节点,如果有 key 并且是相同的节点，把新节点 patch 到旧节点,如果有 key 但是不是相同的节点，则创建新节点
我们假设有新旧两个数组:
- 旧数组:
[1, 2, 3, 4, 5]
- 新数组:
[1, 4, 6, 1000, 100, 5]
首先我们进行头头对比,新旧数组的头部都是1,因此将双方的头部指针后移.
我们继续头头对比,但是2 !== 4导致对比失败,我进入尾尾对比,5 === 5,那么尾部指针则可前移.
现在进入新的循环,头头对比2 !== 4,尾尾对比4 !== 100,此时进入交叉对比,先进行旧尾新头对比,即4 === 4,旧尾前移且新头后移.
接着再进入一个轮新的循环,头头对比2 !== 6,尾尾对比3 !== 100,交叉对比2 != 100 3 != 6,四种对比方式全部不符合,如果这个时候需要通过key去对比,然后将新头指针后移
继续重复上述对比的循环方式直至任一数组的头指针超过尾指针，循环结束.
在上述循环结束后,两个数组中可能存在未遍历完的情况: 循环结束后，
- 先对比旧数组的头尾指针，如果旧数组遍历完了（可能新数组没遍历完，有漏添加的问题），添加新数组中漏掉的节点
- 再对比新数组的头尾指针，如果新数组遍历完了（可能旧数组没遍历完，有漏删除的问题），删除旧数组中漏掉的节点
参考
