Vue 源码解读：聊聊三种 Diff 算法
简单来说，当新旧 vnode 的子节点都是一组节点时，为了以最小的性能开销完成更新操作，需要比较两组子节点，用于比较的算法就叫作 Diff 算法。我们知道，操作 DOM 的性能开销通常比较大，而渲染器的核心 Diff 算法就是为了解决这个问题而诞生的。
Vue 为了实现高效的更新，需要做到最大限度地复用 DOM 节点，最大限度地降低操作 DOM 的次数，因此设计了一套高效的 Diff 算法。
采用 Diff 算法比较新旧节点的时候，只会进行同层级的比较，不会跨层级比较。因为跨层级的比较算法复杂度太高了，会得不偿失，因此跨层级的时候采取了简单粗暴的方案，直接重新生成新的 DOM 节点替代旧的 DOM 节点。
本篇文章要介绍三种 Diff 算法：简单 Diff 算法、双端 Diff 算法、快速 Diff 算法
简单 Diff 算法
简单 Diff 算法是比较暴力的算法，原理是通过双重 for 循环，找出新旧两组子节点中的差异来进行更新。
双端 Diff 算法
双端 Diff 算法是新旧两组子节点的头尾指针向中间移动的同时，对比头头、尾尾、头尾、尾头是否可以复用，如果可以复用，就进行节点的更新或移动操作。如果经过四个端点的比较，都没有可复用的节点，则拿新的一组子节点的头部节点去旧的一组子节点中查找，如果找到了可复用的节点，则将相应的节点进行更新操作，并将其移动到头部。
然而，拿新的一组子节点中的头部节点去旧的一组子节点中寻找可复用的节点，并非总能找到，这说明这个新的头部节点是新增节点，只需要将其挂载到头部即可。
经过上述处理，最后还剩下新的节点就批量新增，剩下旧的节点就批量删除。
Vue2 采用的算法，性能还不错。Vue2 中双端 Diff 算法的实现如下（省略了部分非关键的代码），其中有详细的注释，可以帮助大家理解：
function updateChildren(
parentElm,
oldCh,
newCh,
) {
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, vnodeToMove, refElm
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if (isUndef(oldStartVnode)) {
// 旧的头部节点为 undefined ，则说明该节点被处理过，直接跳过，选择下一个
// 节点为旧的头部节点
oldStartVnode = oldCh[++oldStartIdx]
} else if (isUndef(oldEndVnode)) {
// 旧的尾部节点为 undefined ，则说明该节点被处理过，直接跳过，选择下一个
// 节点为旧的尾部节点
oldEndVnode = oldCh[--oldEndIdx]
} else if (sameVnode(oldStartVnode, newStartVnode)) {
// 头头比较
patchVnode(
oldStartVnode,
newStartVnode,
newCh,
newStartIdx
)
// 更新两端指针，两端指针会向中间靠拢
oldStartVnode = oldCh[++oldStartIdx]
newStartVnode = newCh[++newStartIdx]
} else if (sameVnode(oldEndVnode, newEndVnode)) {
// 尾尾比较
patchVnode(
oldEndVnode,
newEndVnode,
newCh,
newEndIdx
)
// 更新两端指针，两端指针会向中间靠拢
oldEndVnode = oldCh[--oldEndIdx]
newEndVnode = newCh[--newEndIdx]
} else if (sameVnode(oldStartVnode, newEndVnode)) {
// 头尾比较，节点向右移动
patchVnode(
oldStartVnode,
newEndVnode,
newCh,
newEndIdx
)
// 更新两端指针，两端指针会向中间靠拢
oldStartVnode = oldCh[++oldStartIdx]
newEndVnode = newCh[--newEndIdx]
} else if (sameVnode(oldEndVnode, newStartVnode)) {
// 尾头比较，节点向左移动
patchVnode(
oldEndVnode,
newStartVnode,
newCh,
newStartIdx
)
// 更新两端指针，两端指针会向中间靠拢
oldEndVnode = oldCh[--oldEndIdx]
newStartVnode = newCh[++newStartIdx]
} else {
// 建立旧节点的 key -> index 映射表
if (isUndef(oldKeyToIdx))
oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
// 在旧的子节点中查找新的头部节点的 key
idxInOld = isDef(newStartVnode.key)
? oldKeyToIdx[newStartVnode.key]
: findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
if (isUndef(idxInOld)) {
// 在旧的子节点中没有找到新的头部节点的key ，
// 则新增该节点并插入到头部
createElm(
newStartVnode,
parentElm,
oldStartVnode.elm,
false,
newCh,
newStartIdx
)
} else {
vnodeToMove = oldCh[idxInOld]
if (sameVnode(vnodeToMove, newStartVnode)) {
// 找到，则将节点移动到头部，并将旧的节点原位置置为 undefined ，
// 表示该位置已无节点
patchVnode(
vnodeToMove,
newStartVnode,
newCh,
newStartIdx
)
oldCh[idxInOld] = undefined
} else {
// key 相同但是为不同元素的情况，则当作新增节点
createElm(
newStartVnode,
parentElm,
oldStartVnode.elm,
false,
newCh,
newStartIdx
)
}
}
// 更新新节点的头部指针
newStartVnode = newCh[++newStartIdx]
}
}
if (oldStartIdx > oldEndIdx) {
refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm
// 遗留有新节点，则批量新增新节点
addVnodes(
parentElm,
refElm,
newCh,
newStartIdx,
newEndIdx,
)
} else if (newStartIdx > newEndIdx) {
// 遗留有旧节点，则批量删除旧节点
removeVnodes(oldCh, oldStartIdx, oldEndIdx)
}
}
// 判断是否未定义
export function isUndef(v) {
return v === undefined || v === null
}
// key -> index 的映射表
function createKeyToOldIdx(children, beginIdx, endIdx) {
let i, key
const map = {}
for (i = beginIdx; i <= endIdx; ++i) {
key = children[i].key
if (isDef(key)) map[key] = i
}
return map
}
👆 上述代码均摘自 Vue.js 2.7.15 版本
Vue2 双端 Diff 算法的流程总结如下：
快速 Diff 算法
快速 Diff 算法是 Vue3 采用的算法，在三种算法之中，性能最佳。因此从这个角度来说，升级 Vue3 后，性能一般会得到提升。
Vue3 的 Diff 算法，会首先进行首尾相同节点的 patch 处理，结束后，会挂载新增节点，卸载旧节点。如果子序列的情况较为复杂，比如出现乱序的情况，则会首先找出可复用的节点，并通过可复用节点的位置映射构建一个最长递增子序列，通过最长递增子序列来最大程度减少节点的移动操作，以提高 Diff 效率，实现节点复用的最大可能性。这也是快速 Diff 算法比双端 Diff 算法效率高的原因。
其实，Vue / React 中 Diff 算法的目的都是为了实现节点复用的最大可能性。
Vue3 的 Diff 算法是在 patchKeyedChildren 函数中实现。可以看到尤大已经给 Diff 算法的每一步都作好了注释，在这里给尤大点赞👍
👆 图中代码源自 Vue.js 3.2.45 版本
可以看到快速 Diff 算法总共有 5 种情况需要处理：
-
sync from start （处理相同的前置节点）
-
sync from end （处理相同的后置节点）
-
common sequence + mount （处理完相同的前置节点和相同的后置节点后，新节点有剩余，则进行挂载）
-
common sequence + unmount （处理完相同的前置节点和相同的后置节点，旧的节点有剩余，则进行卸载）
-
unknown sequence （乱序情况的处理）
首先定义新旧子节点数组的初始指针 i 和新旧的子节点数组的尾部指针 e2 、e1
let i = 0
const l2 = c2.length
let e1 = c1.length - 1
let e2 = l2 - 1
之后开始处理相同前置节点，从左端开始遍历新旧子节点，直到找到不同的节点则跳出此循环。
// 1. 处理相同的前置节点
// (a b) c
// (a b) d e
while (i <= e1 && i <= e2) {
const n1 = c1[i]
const n2 = c2[i]
if (isSameVNodeType(n1, n2)) {
// 即使是可复用的节点，也要进行更新操作
patch(
n1,
n2,
container
)
} else {
break
}
i++
}
处理完相同的前置节点后，会进入相同的后置节点的处理，具体步骤是从新旧节点的尾部往前遍历，直到找到不同的节点，则跳出循环。
// 2. 处理相同的后置节点
// a (b c)
// d e (b c)
while (i <= e1 && i <= e2) {
const n1 = c1[e1]
const n2 = c2[e2]
if (isSameVNodeType(n1, n2)) {
patch(
n1,
n2,
container
)
} else {
break
}
e1--
e2--
}
处理完相同的前置节点和后置节点后，如果此时 i > e1 ，i <= e2 ，则说明新节点有剩余，则循环 i 到 e2 区间，完成新节点的挂载。
// 3. 处理完相同的前置节点和相同的后置节点后，新节点有剩余，则进行挂载
// (a b)
// (a b) c
// i = 2, e1 = 1, e2 = 2
// (a b)
// c (a b)
// i = 0, e1 = -1, e2 = 0
if (i > e1) {
if (i <= e2) {
const nextPos = e2 + 1
// 锚点元素
const anchor = nextPos < l2 ? (c2[nextPos] as VNode).el : parentAnchor
while (i <= e2) {
patch(
null,
c2[i],
container,
anchor
)
i++
}
}
}
处理完相同的前置节点和后置节点后，如果此时 i > e2 ，i <= e1 ，则说明旧节点有剩余，则需要循环 i 到 e1 区间，卸载剩余旧的节点。
// 4. 处理完相同的前置节点和相同的后置节点，旧的节点有剩余，则进行卸载
// (a b) c
// (a b)
// i = 2, e1 = 2, e2 = 1
// a (b c)
// (b c)
// i = 0, e1 = 0, e2 = -1
else if (i > e2) {
while (i <= e1) {
unmount(c1[i])
i++
}
}
处理完相同的前置节点、后置节点，完成了剩余新节点或剩余旧节点的挂载或卸载后，则要开始处理乱序的情况。这种情况较为复杂，不过核心逻辑在于通过新旧节点的位置变化构建一个最长递增子序列，最长子序列能保证通过最小的移动来实现新旧节点的更新操作。
首先循环新子节点数组，为新子节点构建 key:index 映射 keyToNewIndexMap，该映射的主要作用是后面通过遍历旧子序列，确定可复用节点在新的子序列中的位置。
// 5. 乱序情况的处理
// [i ... e1 + 1]: a b [c d e] f g
// [i ... e2 + 1]: a b [e d c h] f g
// i = 2, e1 = 4, e2 = 5
else {
const s1 = i
const s2 = i
// 5.1 为新子节点构建 key:index 映射
const keyToNewIndexMap: Map<string | number | symbol, number> = new Map()
for (i = s2; i <= e2; i++) {
// 获取的是新序列中的子节点
const nextChild = c2[i]
if (nextChild.key != null) {
// nextChild.key 存在
// a b [e d c h] f g
// e:2 d:3 c:4 h:5
keyToNewIndexMap.set(nextChild.key, i)
}
}
}
然后从左向右遍历旧子序列，patch 寻找到的可复用的节点，卸载不存在的节点。
// 5.2 从左向右遍历旧子序列，patch 可复用的节点，卸载不存在的节点
let j
// 已经 patch 的节点个数
let patched = 0
// 需要 patch 的节点数量，此时，e2 = 5; s2 = 2;
// toBePatched = 4
const toBePatched = e2 - s2 + 1
// 用于判断节点是否需要移动
// 当新旧队列中出现可复用节点交叉时，moved = true
let moved = false
// 代表遍历旧的一组子节点的过程中遇到的最大索引值
let maxNewIndexSoFar = 0
// 创建新旧节点的下标映射，注意，旧节点的 index 要向右偏移 1 个下标
// 并且旧节点 Index = 0 是一个特殊的值，用于表示新的节点中没有对应的旧节点
// 该映射用于后续计算最长递增子序列
const newIndexToOldIndexMap = new Array(toBePatched)
// 将所有的值初始化为 0
// [0, 0, 0, 0]
for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0
// 从左到右遍历旧子序列
for (i = s1; i <= e1; i++) {
const prevChild = c1[i]
if (patched >= toBePatched) {
// 如果已更新节点数大于等于需要更新节点数，
// 说明新节点以全部更新，剩余旧节点直接移除，并跳出当次循环
unmount(prevChild)
continue
}
// 新节点下标
let newIndex
if (prevChild.key != null) {
// 旧的节点有 key,
// 根据旧节点 key ，获取相同类型的新的子节点在新的队列中对应节点位置
// 这个时候 因为 c d e 是原来的节点 并且有 key
// h 是新增节点 旧节点中没有 获取不到 对应的 index 会走else
// 所以 newIndex 在开始时会有如下情况
/**
* node newIndex
* c 4
* d 3
* e 2
*/
// 这里是可以获取到 newIndex 的
newIndex = keyToNewIndexMap.get(prevChild.key)
} else {
// 旧节点没有 key ，
// 则会在新子序列中查找与该旧节点相同类型的子节点，
// 并记录该新节点的位置
for (j = s2; j <= e2; j++) {
if (
newIndexToOldIndexMap[j - s2] === 0 &&
// 判断新旧节点是否相同
isSameVNodeType(prevChild, c2[j])
) {
// 获取到相同类型节点的下标，跳出循环
newIndex = j
break
}
}
}
if (newIndex === undefined) {
// 如果还没有对应的新节点，
// 则该旧节点是多余的，将该旧节点卸载
unmount(prevChild)
} else {
// 找到了与该旧节点相同类型的新节点
// 注意旧节点的 index 要向右偏移 1 个下标，因此需要加 1，
// 避免索引为 0 的情况，因为 0 有特殊含义，
// 用于表示新的节点中没有对应的旧节点
// 偏移 1 个位置 i从 s1 = 2 开始，s2 = 2
// 4 - 2 获取下标 2，新的 c 节点对应旧 c 节点的位置下标 3
// 3 - 2 获取下标 1，新的 d 节点对应旧 d 节点的位置下标 4
// 2 - 2 获取下标 0，新的 e 节点对应旧 e 节点的位置下标 5
// [0, 0, 0, 0] => [5, 4, 3, 0]
// 新子序列中节点的下标在旧子序列中的对应的下标：
// [2, 3, 4, 5] = [5, 4, 3, 0]
newIndexToOldIndexMap[newIndex - s2] = i + 1
// 通过比较 newIndex 和 maxNewIndexSoFar 的值来判断节点是否需要移动
// newIndex 会取 4 3 2
/**
* newIndex maxNewIndexSoFar moved
* 4 0 false
* 3 4 true
* 2
*/
if (newIndex >= maxNewIndexSoFar) {
// 如果在遍历过程中遇到的索引值呈现递增趋势，则说明不需要移动节点
maxNewIndexSoFar = newIndex
} else {
// 否则需要移动
moved = true
}
// 调用 patch 函数完成更新
patch(
prevChild,
c2[newIndex],
container
)
// 每更新一个节点，都将 patched 变量 +1
patched++
}
}
最后，构造最长递增子序列，完成可复用节点的移动，新增节点的挂载。
// 5.3 构造最长递增子序列，完成可复用节点的移动，新增节点的挂载
// 经过上面操作后，newIndexToOldIndexMap = [5, 4, 3, 0]
// 得到 increasingNewIndexSequence = [2]
const increasingNewIndexSequence = moved
? getSequence(newIndexToOldIndexMap)
: []
// j = 0
j = increasingNewIndexSequence.length - 1
// 从后向前遍历 以便于可以用最新的被 patch 的节点作为锚点
// i = 3
for (i = toBePatched - 1; i >= 0; i--) {
// 5 4 3 2
const nextIndex = s2 + i
// 节点 h c d e
const nextChild = c2[nextIndex]
// 获取锚点
const anchor = nextIndex + 1 < l2 ? c2[nextIndex + 1].el : parentAnchor
// [5, 4, 3, 0] 节点 h 会被 patch，其实是 mount
// c d e 会被移动
if (newIndexToOldIndexMap[i] === 0) {
// 说明旧节点中不存在该节点，为新增节点，执行挂载
patch(
null,
nextChild,
container,
anchor
)
} else if (moved) {
// 如果没有最长递增子序列或者当前节点不在递增子序列中
// 则移动节点
if (j < 0 || i !== increasingNewIndexSequence[j]) {
move(nextChild, container, anchor, MoveType.REORDER)
} else {
j--
}
}
}
Vue3 快速 Diff 算法的流程总结如下：
vue2 和 vue3 diff 算法的区别
vue2、vue3 的 diff 算法实现差异主要体现在：处理完首尾节点后，对剩余节点的处理方式。
在 vue2 中是通过对旧节点列表建立一个 { key, oldVnode }的映射表，然后遍历新节点列表的剩余节点，根据 newVnode.key 在旧映射表中寻找可复用的节点，然后打补丁并且移动到正确的位置。
而在 vue3 中是建立一个存储新节点数组中的剩余节点在旧节点数组上的索引的映射关系数组，建立完成这个数组后也即找到了可复用的节点，然后通过这个数组计算得到最长递增子序列，这个序列中的节点保持不动，然后将新节点数组中的剩余节点移动到正确的位置。
转载自:https://juejin.cn/post/7305328476563030056