這篇文章帶大家透過圖文來深入解析下Vue3中的 diff 演算法，希望對大家有幫助！
這篇文章主要分析Vue3 diff演算法，透過本文你可以知道：
# #diff的主要過程，核心邏輯
diff是如何進行節點重複使用、移動、卸載
key子節點時。
。
。
結束，再處理剩餘的新舊節點。
，說明需要對舊節點進行unmount
;
這裡貼下省略後的程式碼。
const patchUnkeyedChildren = (c1, c2,...res) => {
c1 = c1 || EMPTY_ARR
c2 = c2 || EMPTY_ARR
// 获取新旧子节点的长度
const oldLength = c1.length
const newLength = c2.length
// 1. 取得公共长度。最小长度
const commonLength = Math.min(oldLength, newLength)
let i
// 2. patch公共部分
for (i = 0; i < commonLength; i++) {
patch(...)
}
// 3. 卸载旧节点
if (oldLength > newLength) {
// remove old
unmountChildren(...)
} else {
// mount new
// 4. 否则挂载新的子节点
mountChildren(...)
}
}從上面的程式碼可以看出，在處理無
key子節點的時候，邏輯還是非常簡單粗暴的。準確的說處理無key子節點的效率並不高。 因為不管是直接對公共部分
，還是直接對新增節點進行mountChildren（其實是遍歷子節點，進行patch操作），其實都是在遞歸進行patch，這就會影響到效能。 2.0
key子節點序列有key子序列的時候，會進行細分處理。主要會經過下列一種情況的判斷：
let i = 0 const l2 = c2.length let e1 = c1.length - 1 // prev ending index let e2 = l2 - 1 // next ending index
下面開始分情況進行diff處理。
2.1 起始位置節點類型相同
遍歷。
處理
處理節點類型不同，則
// i <= 2 && i <= 3
while (i <= e1 && i <= e2) {
const n1 = c1[i]
const n2 = c2[i]
if (isSameVNodeType(n1, n2)) {
// 如果是相同的节点类型，则进行递归patch
patch(...)
} else {
// 否则退出
break
}
i++
}上面上略了部分程式碼，但不影響主要邏輯。 從程式碼可以知道，遍歷時，利用前面在函數全域上下文中宣告的三個指針，進行遍歷判斷。
保證能充分遍歷到起始位置相同的位置，i <= e1 && i <= e2。
一旦遇到類型不同的節點，就會跳出diff遍歷。
2.2 結束位置節點類型相同
#開始位置相同
結束，會緊接著從序列尾部開始遍歷diff。
此時需要對尾指標e1、e2進行遞減。 <div class="code" style="position:relative; padding:0px; margin:0px;"><pre class="brush:js;toolbar:false;">// i <= 2 && i <= 3
// 结束后： e1 = 0 e2 = 1
while (i <= e1 && i <= e2) {
const n1 = c1[e1]
const n2 = c2[e2]
if (isSameVNodeType(n1, n2)) {
// 相同的节点类型
patch(...)
} else {
// 否则退出
break
}
e1--
e2--
}</pre><div class="contentsignin">登入後複製</div></div>從程式碼可以看出，
邏輯與第一種基本上一樣，相同型別進行patch處理。
不同類型
break，跳出迴圈遍歷。 並且對尾指標進行遞減操作。
2.3 相同部分遍歷結束，新序列中有新增節點，進行掛載經過上面兩種情況的處理，已經
完首尾相同部分的節點，接下來是對新序列中的新增節點進行
patch
在经过上面两种请款处理之后，如果有新增节点，可能会出现 i > e1 && i <= e2的情况。
这种情况下意味着新的子节点序列中有新增节点。
这时会对新增节点进行patch。
// 3. common sequence + mount
// (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
// nextPos < l2，说明有已经patch过尾部节点，
// 否则会获取父节点作为锚点
const anchor = nextPos < l2 ? c2[nextPos].el : parentAnchor
while (i <= e2) {
patch(null, c2[i], anchor, ...others)
i++
}
}
}从上面的代码可以知道，patch的时候没有传第一个参数，最终会走mount的逻辑。
可以看这篇 主要分析patch的过程
https://mp.weixin.qq.com/s/hzpNGWFCLMC2vJNSmP2vsQ
在patch的过程中，会递增i指针。
并通过nextPos来获取锚点。
如果nextPos < l2，则以已经patch的节点作为锚点，否则以父节点作为锚点。
2.4 相同部分遍历结束，新序列中少节点，进行卸载
如果处理完收尾相同的节点，出现i > e2 && i <= e1的情况，则意味着有旧节点需要进行卸载操作。
// 4. common sequence + unmount
// (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], parentComponent, parentSuspense, true)
i++
}
}通过代码可以知道，这种情况下，会递增i指针，对旧节点进行卸载。
2.5 乱序情况
这种情况下较为复杂，但diff的核心逻辑在于通过新旧节点的位置变化构建一个最大递增子序列，最大子序列能保证通过最小的移动或者patch实现节点的复用。
下面一起来看下如何实现的。
2.5.1 为新子节点构建key:index映射
// 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
const s1 = i // s1 = 2
const s2 = i // s2 = 2
// 5.1 build key:index map for newChildren
// 首先为新的子节点构建在新的子序列中 key：index 的映射
// 通过map 创建的新的子节点
const keyToNewIndexMap = new Map()
// 遍历新的节点，为新节点设置key
// i = 2; i <= 5
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处理之后，i = 2，e1 = 4，e2 = 5
经过遍历之后keyToNewIndexMap中，新节点的key:index的关系为 E : 2、D : 3 、C : 4、H : 5
keyToNewIndexMap的作用主要是后面通过遍历旧子序列，确定可复用节点在新的子序列中的位置
2.5.2 从左向右遍历旧子序列，patch匹配的相同类型的节点，移除不存在的节点
经过前面的处理，已经创建了keyToNewIndexMap。
在开始从左向右遍历之前，需要知道几个变量的含义：
// 5.2 loop through old children left to be patched and try to patch // matching nodes & remove nodes that are no longer present // 从旧的子节点的左侧开始循环遍历进行patch。 // 并且patch匹配的节点 并移除不存在的节点 // 已经patch的节点个数 let patched = 0 // 需要patch的节点数量 // 以上图为例：e2 = 5; s2 = 2; 知道需要patch的节点个数 // toBePatched = 4 const toBePatched = e2 - s2 + 1 // 用于判断节点是否需要移动 // 当新旧队列中出现可复用节点交叉时，moved = true let moved = false // used to track whether any node has moved // 用于记录节点是否已经移动 let maxNewIndexSoFar = 0 // works as Map<newIndex, oldIndex> // 作新旧节点的下标映射 // Note that oldIndex is offset by +1 // 注意 旧节点的 index 要向右偏移一个下标 // and oldIndex = 0 is a special value indicating the new node has // no corresponding old node. // 并且旧节点Index = 0 是一个特殊的值，用于表示新的节点中没有对应的旧节点 // used for determining longest stable subsequence // newIndexToOldIndexMap 用于确定最长递增子序列 // 新下标与旧下标的map const newIndexToOldIndexMap = new Array(toBePatched) // 将所有的值初始化为0 // [0, 0, 0, 0] for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0
patched 用于记录已经patch的节点toBePatched 用于记录需要进行patch的节点个数moved 用于记录是否有可复用节点发生交叉maxNewIndexSoFar用于记录当旧的子序列中存在没有设置key的子节点，但是该子节点出现于新的子序列中，且可复用，最大下标。newIndexToOldIndexMap用于映射新的子序列中的节点下标 对应于 旧的子序列中的节点的下标newIndexToOldIndexMap初始化为一个全0数组，[0, 0, 0, 0]知道了这些变量的含义之后 我们就可以开始从左向右遍历子序列了。
遍历的时候，需要首先遍历旧子序列，起点是s1，终点是e1。
遍历的过程中会对patched进行累加。
卸载旧节点
如果patched >= toBePatched，说明新子序列中的子节点少于旧子序列中的节点数量。
需要对旧子节点进行卸载。
// 遍历未处理旧序列中子节点
for (i = s1; i <= e1; i++) {
// 获取旧节点
// 会逐个获取 c d e
const prevChild = c1[i]
// 如果已经patch 的数量 >= 需要进行patch的节点个数
// patched刚开始为 0
// patched >= 4
if (patched >= toBePatched) {
// all new children have been patched so this can only be a removal
// 这说明所有的新节点已经被patch 因此可以移除旧的
unmount(prevChild, parentComponent, parentSuspense, true)
continue
}
}如果prevChild.key是存在的，会通过前面我们构建的keyToNewIndexMap，获取prevChild在新子序列中的下标newIndex。
获取newIndex
// 新节点下标
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)
}以图为例，可以知道，在遍历过程中，节点c、d、e为可复用节点，分别对应新子序列中的2、3、4的位置。
故newIndex可以取到的值为4、3、2。
如果旧节点没有key怎么办？
// key-less node, try to locate a key-less node of the same type
// 如果旧的节点没有key
// 则会查找没有key的 且为相同类型的新节点在 新节点队列中 的位置
// j = 2: j <= 5
for (j = s2; j <= e2; j++) {
if (
newIndexToOldIndexMap[j - s2] === 0 &&
// 判断是否是新旧节点是否相同
isSameVNodeType(prevChild, c2[j])
) {
// 获取到相同类型节点的下标
newIndex = j
break
}
}如果节点没有key，则同样会取新子序列中，遍历查找没有key且两个新旧类型相同子节点，并以此节点的下标，作为newIndex。
newIndexToOldIndexMap[j - s2] === 0 说明节点没有该节点没有key。
如果还没有获取到newIndex，说明在新子序列中没有存在的与 prevChild 相同的子节点，需要对prevChild进行卸载。
if (newIndex === undefined) {
// 没有对应的新节点 卸载旧的
unmount(prevChild, parentComponent, parentSuspense, true)
}否则，开始根据newIndex，构建keyToNewIndexMap，明确新旧节点对应的下标位置。
时刻牢记
newIndex是根据旧节点获取的其在新的子序列中的下标。
// 这里处理获取到newIndex的情况
// 开始整理新节点下标 Index 对于 相同类型旧节点在 旧队列中的映射
// 新节点下标从 s2=2 开始，对应的旧节点下标需要偏移一个下标
// 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 会取 4 3 2
/**
* newIndex maxNewIndexSoFar moved
* 4 0 false
* 3 4 true
* 2
*
* */
if (newIndex >= maxNewIndexSoFar) {
maxNewIndexSoFar = newIndex
} else {
moved = true
}在构建newIndexToOldIndexMap的同时，会通过判断newIndex、maxNewIndexSoFa的关系，确定节点是否发生移动。
newIndexToOldIndexMap最后遍历结束应该为[5, 4, 3, 0]，0说明有旧序列中没有与心序列中对应的节点，并且该节点可能是新增节点。
如果新旧节点在序列中相对位置保持始终不变，则maxNewIndexSoFar会随着newIndex的递增而递增。
意味着节点没有发生交叉。也就不需要移动可复用节点。
否则可复用节点发生了移动，需要对可复用节点进行move。
遍历的最后，会对新旧节点进行patch，并对patched进行累加，记录已经处理过几个节点。
// 进行递归patch /** * old new * c c * d d * e e */ patch( prevChild, c2[newIndex], container, null, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized ) // 已经patch的 patched++
经过上面的处理，已经完成对旧节点进行了卸载，对相对位置保持没有变化的子节点进行了patch复用。
接下来就是需要移动可复用节点，挂载新子序列中新增节点。
2.5.3 移动可复用节点，挂载新增节点
这里涉及到一块比较核心的代码，也是Vue3 diff效率提升的关键所在。
前面通过newIndexToOldIndexMap，记录了新旧子节点变化前后的下标映射。
这里会通过getSequence方法获取一个最大递增子序列。用于记录相对位置没有发生变化的子节点的下标。
根据此递增子序列，可以实现在移动可复用节点的时候，只移动相对位置前后发生变化的子节点。
做到最小改动。
那什么是最大递增子序列？
[3, 6, 2, 7] 是数组 [0, 3, 1, 6, 2, 2, 7] 的最长严格递增子序列。[2, 3, 7, 101] 是数组 [10 , 9, 2, 5, 3, 7, 101, 18]的最大递增子序列。[0, 1, 2, 3] 是数组 [0, 1, 0, 3, 2, 3]的最大递增子序列。已上图为例，在未处理的乱序节点中，存在新增节点N、I、需要卸载的节点G，及可复用节点C、D、E、F。
节点CDE在新旧子序列中相对位置没有变换，如果想要通过最小变动实现节点复用，我们可以将找出F节点变化前后的下标位置，在新的子序列C节点之前插入F节点即可。
最大递增子序列的作用就是通过新旧节点变化前后的映射，创建一个递增数组，这样就可以知道哪些节点在变化前后相对位置没有发生变化，哪些节点需要进行移动。
Vue3中的递增子序列的不同在于，它保存的是可复用节点在 newIndexToOldIndexMap的下标。而并不是newIndexToOldIndexMap中的元素。
接下来我们看下代码部分：
// 5.3 move and mount
// generate longest stable subsequence only when nodes have moved
// 移动节点 挂载节点
// 仅当节点被移动后 生成最长递增子序列
// 经过上面操作后，newIndexToOldIndexMap = [5, 4, 3, 0]
// 得到 increasingNewIndexSequence = [2]
const increasingNewIndexSequence = moved
? getSequence(newIndexToOldIndexMap)
: EMPTY_ARR
// j = 0
j = increasingNewIndexSequence.length - 1
// looping backwards so that we can use last patched node as anchor
// 从后向前遍历 以便于可以用最新的被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) {
// mount new
// 挂载新的
patch(
null,
nextChild,
container,
anchor,
...
)
} else if (moved) {
// move if:
// There is no stable subsequence (e.g. a reverse)
// OR current node is not among the stable sequence
// 如果没有最长递增子序列或者 当前节点不在递增子序列中间
// 则移动节点
//
if (j < 0 || i !== increasingNewIndexSequence[j]) {
move(nextChild, container, anchor, MoveType.REORDER)
} else {
j--
}
}
}从上面的代码可以知道：
newIndexToOldIndexMap所取得的最大遞增子序列是[2]
的兄弟節點，則以兄弟節點作為錨點，否則以父節點作為錨點 ，說明是新增節點。需要對節點進行mount，這時只需給patch的第一個參數傳null即可。可以知道首先會對h節點進行patch。
是否為true。透過前面的分析，我們知道節點C & 節點E在前後變化中發生了位置移動。
，i**，i !== increasingNewIndexSequence[j]為true，並不會移動C節點 ，而是執行j--。
進行移動。
Vue3 diff演算法的學習分析。
Vue3 的diff演算法，會先進行收尾相同節點的patch處理，結束後，會掛載新增節點，卸載舊節點。
mount & move。以提高diff效率，實現節點重複使用的最大可能性。
vue.js教學】
以上是深入解析Vue3中的 diff 演算法（圖文詳解）的詳細內容。更多資訊請關注PHP中文網其他相關文章！
