Vue3.0 节点diff过程

吴翀2022年12月29日约 4 分钟

回顾之前分析的vnode的创建过程，我们了解了Vue3.x中对于虚拟节点的一些优化，其实无论是为vnode添加shapeFlag和patchFlag类型、或者是生成组件的block tree，都是为了

提高组件节点的patch效率，从而提升组件的创建或者更新速度。那么Vue 3.x在组件patch过程究竟做了什么优化呢？本文将从patch过程的一个小分支出发，来看看在Vue 3.x中

是如何优化带key值的节点的更新速度的。

在Vue中，带key值的节点通常存在于v-for指令渲染的列表中，当组件进入patch流程时，带key值的节点会进入patchKeyedChildren分支中，举一个简单的例子：假设有这样一个列表，

然后我们在中间插入一行，得到一个新列表：

可以看出新子节点相对于旧子节点的变化，无非是通过更新、删除、添加和移动节点来完成，而 diff 过程，就是在已知旧子节点的 DOM 结构、vnode和新子节点的vnode的

情况下，寻找一个最优的更新方式，来最大程度的减少更新节点的成本，从而达到优化的效果，而寻找这个最优的方式分为以下几个步骤：

在整个 diff 的过程，我们需要维护几个变量：头部的索引 i、旧子节点的尾部索引 e1和新子节点的尾部索引 e2。

同步头部节点就是从头部开始，依次对比新节点和旧节点，如果它们相同的则执行 patch 更新节点；如果不同或者索引 i 大于索引 e1 或者 e2，则同步过程结束：

同样的道理，继续从尾部开始，依次对比新节点和旧节点，如果它们相同的则执行 patch 更新节点；如果不同或者索引 i 小于或等于索引 e1 或者 e2，则同步过程结束：

同步完头部节点和尾部节点后，我们可以根据索引i，以及节点尾部索引e1，e2的位置来选择接下来的更新流程：

当 i > e1，并且 i <= e2时，可以得出旧子节点已经更新完毕，没有剩余节点，并且新子节点数组剩余节点，则证明有新添加的节点，就可以调用patch方法传入n1 === null来创建节点：

如果新子节点数组没有剩余节点也就是i > e2，并且旧节点数组有剩余节点也就是i <= e1，则证明有删除的节点，就可以调用unmount销毁旧节点：

单纯的添加和删除节点都是比较理想的情况，操作起来也很容易，但是有些时候我们会遇到比较复杂的未知子序列，这时候就需要通过结合移动、新增、删除节点等操作方式来的方式来寻找

最优的更新过程，首先根据新节点的顺序创建key为新节点的key，value为位置i的映射关系也就是keyToNewIndexMap：

同时创建新节点的位置到旧节点位置的映射，newIndexToOldIndexMap，并初始化位置为0：

接下来，遍历旧节点，为每个旧节点执行以下的步骤：

1、通过上面创建的映射关系，寻找到旧节点在新节点数组中的位置，如果能找到则调用patch同步节点；

2、如果找不到当前旧节点在新节点数组中的位置，则反过来遍历新节点数组，找到一个和当前旧节点相同的节点，并且这个新节点不能是一个已经被找到的节点；

3、如果在新节点数组中找不到这个旧节点，证明该旧节点已经删除，则调用mount方法销毁该节点，否则，更新新节点的位置到旧节点位置的映射，并通过maxNewIndexSoFar

来记录每次newIndex的位置，如果每次都是递增，则证明旧节点在新节点中的顺序没有改变，如果顺序改变了，则将moved设置为true，代表将要移动节点;

我们前面已经判断了是否移动节点，如果moved为true就通过getSequence(newIndexToOldIndexMap)计算最长递增子序列，也就是说找到最多的

不需要移动的节点，因为他们的位置是递增的说明他们在新节点中的位置顺序没有改变，接着我们采用倒序的方式遍历新子序列，因为倒序遍历可以

方便使用最后更新的节点作为锚点。在倒序的过程中，锚点指向上一个更新的节点，然后判断newIndexToOldIndexMap[i]是否为 0，如果是则表示这是新节点，

就需要挂载它；接着判断是否存在节点移动的情况，如果存在的话则看节点的索引是不是在最长递增子序列中，如果在则倒序最长递增子序列，

否则把它移动到锚点的前面：

子序列倒序完成，即完成了新节点的插入和旧节点的移动操作，也就完成了整个核心的diff过程。

来自同一个声音