本篇文章带大家通过图文来深入解析下vue3中的 diff 算法，希望对大家有所帮助！
本篇文章主要分析vue3 diff算法，通过本文你可以知道：
diff的主要过程，核心逻辑
diff是如何进行节点复用、移动、卸载
并有一个示例题，可以结合本文进行练习分析
如果你还不是特别了解vnode、渲染器的patch流程，建议先阅读下面两篇文章：
vnode（https://mp.weixin.qq.com/s/dtfjpa91upjievlqapzcnq）
渲染器分析（https://mp.weixin.qq.com/s/hzpngwfclmc2vjnsmp2vsq）
1.0  diff 无key子节点在处理被标记为unkeyed_fragment时。
首先会通过新旧自序列获取最小共同长度commonlength。
对公共部分循环遍历patch。
patch 结束，再处理剩余的新旧节点。
如果oldlength > newlength，说明需要对旧节点进行unmount
否则，说明有新增节点，需要进行mount;
这里贴下省略后的代码。
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子节点的效率并不高。
因为不管是直接对公共部分patch，还是直接对新增节点进行mountchildren（其实是遍历子节点，进行patch操作），其实都是在递归进行patch，这就会影响到性能。
2.0 diff 有key子节点序列在diff有key子序列的时候，会进行细分处理。主要会经过以下一种情况的判断：
起始位置节点类型相同。结束位置节点类型相同。相同部分处理完，有新增节点。相同部分处理完，有旧节点需要卸载。首尾相同，但中间部分存在可复用乱序节点。在开始阶段，会先生面三个指正，分别是:
i = 0，指向新旧序列的开始位置e1 = oldlength - 1，指向旧序列的结束位置e2 = newlength - 1，指向新序列的结束位置
let i = 0const l2 = c2.lengthlet e1 = c1.length - 1 // prev ending indexlet e2 = l2 - 1 // next ending index
下面开始分情况进行diff处理。
2.1 起始位置节点类型相同
对于起始位置类型相同的节点，从左向右进行diff遍历。
如果新旧节点类型相同，则进行patch处理
节点类型不同，则break，跳出遍历diff
// i <= 2 && i <= 3while (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 结束，会紧接着从序列尾部开始遍历 diff。
此时需要对尾指针e1、e2进行递减。
// i <= 2 && i <= 3// 结束后： e1 = 0 e2 = 1while (i <= e1 && i <= e2) { const n1 = c1[e1] const n2 = c2[e2] if (issamevnodetype(n1, n2)) { // 相同的节点类型 patch(...) } else { // 否则退出 break } e1-- e2--}
从代码可以看出，diff逻辑与第一种基本一样，相同类型进行patch处理。
不同类型break，跳出循环遍历。
并且对尾指针进行递减操作。
2.3 相同部分遍历结束，新序列中有新增节点，进行挂载
经过上面两种情况的处理，已经patch完首尾相同部分的节点，接下来是对新序列中的新增节点进行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 = 0if (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 = 5const s1 = i // s1 = 2const s2 = i // s2 = 2// 5.1 build key:index map for newchildren// 首先为新的子节点构建在新的子序列中 key：index 的映射// 通过map 创建的新的子节点const keytonewindexmap = new map()// 遍历新的节点，为新节点设置key// i = 2; i <= 5for (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 = 4const tobepatched = e2 - s2 + 1// 用于判断节点是否需要移动// 当新旧队列中出现可复用节点交叉时，moved = truelet 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 用于确定最长递增子序列// 新下标与旧下标的mapconst 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 newindexif (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 <= 5for (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 = 0j = increasingnewindexsequence.length - 1// looping backwards so that we can use last patched node as anchor// 从后向前遍历 以便于可以用最新的被patch的节点作为锚点// i = 3for (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]j = 0遍历的时候从右向左遍历，这样可以获取到锚点，如果有已经经过patch的兄弟节点，则以兄弟节点作为锚点，否则以父节点作为锚点newindextooldindexmap[i] === 0，说明是新增节点。需要对节点进行mount，这时只需给patch的第一个参数传null即可。可以知道首先会对h节点进行patch。否则会判断moved是否为true。通过前面的分析，我们知道节点c & 节点e在前后变化中发生了位置移动。故这里会移动节点，我们知道 j 此时为0，i 此时为**2**，i !== increasingnewindexsequence[j]为 true，并不会移动c节点，而是执行 j--。后面因为 j < 0，会对 d、e节点进行移动。至此我们就完成了vue3 diff算法的学习分析。
这里为大家提供了一个示例，可以结合本文的分析过程进行练习：
可以只看第一张图进行分析，分析结束后可以与第二三张图片进行对比。
图一：
图二 & 三：
总结通过上面的学习分析，可以知道，vue3 的diff算法，会首先进行收尾相同节点的patch处理，结束后，会挂载新增节点，卸载旧节点。
如果子序列的情况较为复杂，比如出现乱序的情况，则会首先找出可复用的节点，并通过可复用节点的位置映射构建一个最大递增子序列，通过最大递增子序列来对节点进行mount & move。以提高diff效率，实现节点复用的最大可能性。
【相关推荐：vue.js教程】
以上就是深入解析vue3中的 diff 算法（图文详解）的详细内容。