00后系列-00后深入理解 React 和 Vue 的 diff 原理
声明
学艺不精，功力尚浅，懒得画图，重在分享。
虚拟DOM
DOM
首先，我们先聊聊DOM是什么。
DOM的全称是Document Object Model，翻译过来是文档对象模型的意思，
是W3C组织推荐的处理可扩展标志语言的标准编程接口。
听起来有些抽象，其实我的理解的DOM就是在网页上，一个用于描述页面长什么样的树形结构，
一种基于W3C组织的标准实现的，用于表示web页面结构的标准模型。
所谓的虚拟DOM，就是在当下主流的前端框架 react 或者 vue 中都会用一个JS对象来表示DOM节点， 而不是在框架里直接操作真实的DOM节点，这应该算是提高前端框架性能的一个重要手段吧。
ReactElement 和 Fiber
在老版本的React 中， React 对应的 虚拟DOM 节点 通常叫 ReactElement，通过递归的方式让 n 个 ReactElement 建立起联系，形容一颗虚拟DOM树。
但是原来的 ReactElement 只有 children 指针，这就导致通过递归来创建虚拟DOM树是不能中断的，
因为一旦中断，父节点和兄弟节点都找不到了，整个DOM树将无法从中断的节点开始完成剩余的遍历。
因此，新版 React 提出了 新的 Fiber 架构，Fiber 节点可以访问到父节点、子节点、兄弟节点，这就 解决了老架构无法实现 DOM 的可中断更新 的难题。
如下所示，React 内部采用了 双缓存 的思想，用 两棵 Fiber 树来表示真实的DOM。
ReactElement -> Fiber -> Fiber 树【正在内存中构建，workInProgress fiber 树】 -> Fiber 树【当前展示并要渲染到页面，current fiber 树】-> 真实DOM树
VNode
在 Vue 中，vNode 是 vue 对应的虚拟DOM 节点，它也是通过递归的方式来创建一个虚拟DOM树。
改进 diff 算法
首先，我们需要 完整比对两个树的 Diff 算法 是 一个 时间复杂度 O(n3)O(n^3)O(n3) 相对来说非常高 的算法，
n为树中节点的个数，这样的性能开销明显是不可接受的。
为了降低diff算法的时间复杂度，React 和 Vue 似乎都基于了以下 3个原则 来实现适合自己框架的diff算法。
- 只比较同级节点。
- 新老节点类型不同，先删除再新建。
- 用 key值 作为 新老节点 的 标识符。
React 的diff算法
引言
首先，React 只针对同级的节点diff，并且将 Diff 流程分为了两类，单节点Diff 和 多节点Diff。
区分的标准也很简单，newChild 孩子节点如果类型是 Array、iterator，代表更新后同级元素不是个单一的。
如果类型是 object、number、string时，代表更新后同级元素只有一个。
单节点diff
基于前文提到的3个原则，单节点的diff其实形容起来很简单。
先判断key是否相同，如果相同则判断类型type是否相同，都满足则复用老节点，其他情况都是直接删除老节点。
多节点diff
针对同级多节点，可以分成3类情况。
位置无变化、节点增删、节点移动，任何的DOM变化都会是这3种情况的一种或多种。
在日常开发中，节点的移动是比较少的情况，所以 React 的 Diff 算法会经历两轮遍历。
第一轮遍历是为了找出可复用的节点。
第二轮遍历是为了处理剩下的节点。
第一轮遍历中，判断老节点是否可复用的逻辑，会单节点diff的原则是一致的。
当 key相同，type不同 时，会将老的Fiber节点标记为DELETION，但不会结束遍历， 当出现 key不同， 新 Fiber 结点遍历完，老 Fiber 结点遍历完 中的一种或者多种情况时，第一轮遍历宣告结束。
此时会出现4种情况。
newFiber遍历结束，oldFiber遍历结束：不需要第二轮遍历，对应 位置无变化 的场景。
newFiber遍历结束，oldFiber有剩余节点：剩余的oldFiber节点标记为DELETION。
newFiber有剩余节点，oldFiber遍历结束：剩余的newFiber节点作为新增节点，被插入
newFiber有剩余节点，oldFiber有剩余节点：至此，才是 React diff算法 最核心的部分。
react diff 核心
当第一轮遍历后新老节点都有剩余时，可能的情况是某一个节点的位置发生了变化，
这个时候如果选择直接删除所有老节点，再新增剩余节点，这听起来是不合适的。
为了快速找到在可能存在顺序错乱的 newFiber 节点 里找到 对应 oldFiber 节点。
React 将 还未处理的 oldFiber 节点存入了 以 “自身节点的key 为 key，oldFiber本身 为 value” 的 Map中。
然后开始遍历尚未处理的newFiber节点，此时会比较两个变量的值。
lastPlacedIndex: 最后一个 可复用的oldFiber 的位置索引。
oldFiber.index: 以 key值作为索引，对应的 oldFiber节点的位置索引，通过 map 快速获取。
当 oldFiber.index >= lastPlacedIndex 时，说明 当前遍历的 newFiber 节点 是 可复用的 oldFiber 节点，并且 在 oldFiber 链表的 相对位置是靠后的，所以不需要移动位置，此时 lastPlacedIndex 需要 更新 为 oldFiber.index。
当 oldFiber.index < lastPlacedIndex 时，说明 对应的 oldFiber 节点 在 oldFiber 链表的相对位置是靠前的， 需要标记为 Placement，表明此节点发生过移动，此时 lastPlacedIndex 无需更新。
如果 map 里 找不到 newFiber 的 key 值，则直接创建新增节点。
至此，React的 diff算法也就介绍完毕。在用react 开发项目时，应该尽可能避免把相对位置靠后的节点从后面移动到前面，保证第一次遍历后剩余的节点更少，就能减少React diff算法的执行时间。
Vue2 的diff算法
引言
根据上文介绍的 React diff算法，可以看出 React 的 diff算法 对于 节点的前移 处理得并不好。
可能是为了解决这一问题，vue2 采用了一种名叫 双端diff 的算法。
顾名思义，双端就是新老节点的首尾部分，听起来像是算法中的双指针。
第一轮遍历
用 新前 表示新子节点中未处理节点的第一个节点；
用 新后 表示新子节点中未处理节点的最后一个节点；
用 旧前 表示旧子节点中未处理节点的第一个节点；
用 旧后 表示旧子节点中未处理节点的最后一个节点。
每一次遍历，都会进行最多4次双端比较。
新前 vs 旧前、新后 vs 旧后、新后 vs 旧前、新前 vs 旧后
当某个比较成功匹配后，就需要移动对应的两个指针，指针移动的方向就是向中间靠拢。
值得说明的是，与 react 在 diff算法 中 给节点打标记 的方式不同，
而 vue 会直接在diff过程中进行节点的更新、增删、移动。
当 新后 vs 旧前 或 新前 vs 旧后 匹配成功时，说明节点的相对位置没变，只需要更新节点。
当 新后 vs 旧前 或 新前 vs 旧后 匹配成功时，除了指针的更新，还需要进行节点的移动。
比如 新前 == 旧后，就说明发生了节点的前移，需要把 旧后 的DOM节点 移动到 旧前 的DOM节点 之前。
如果以上四种情况都不能匹配成功，就需要循环遍历老节点，找到 key值相同的 老节点。
其中，用map进行优化，避免后续反复的遍历老节点。
如果key值相同，但Vnode type类型发生改变，则需要创建一个新节点，放在 旧前 的DOM节点 之前。
如果key值相同，type不变，则直接将老的DOM节点插入到 旧前 的DOM节点 之前。
如果key值没有在老节点出现过，则认为是新创建的节点，放在 旧前 的DOM节点 之前。
经过这样一轮遍历后，DOM节点的前移和后移都会被处理，对应的双指针只剩下两种情况。
第二轮遍历
旧前 > 旧后：说明老节点之前就走完了，新节点还有尚未处理的DOM节点，需要批量创建。
新前 > 新后：说明新节点之前就走完了，老节点存在多余的DOM节点，需要批量删除。
Vue3 的 diff 算法
引言
行文至此，相信读者都能看出 React 和 vue2 的diff算法优化的策略是有很多相似点的。
基于对前端业务场景的判断，React 和 vue2 都认为DOM节点的移动是相对较少的情况，
所以复用老节点并更新相关数据是值得优先考虑的。
对此，React 的做法是从左到右进行第一次遍历，复用老节点，直到出现 key值匹配不上的情况。
对此，Vue2 的做法是采用双端diff算法，分为四种情况去匹配。
单从算法性能上来说，Vue2的diff算法明显性能会更好。
比如说我们现在有以下两组新老节点：
老：0， 1， 2， 3 新：3， 0， 1， 2
React: 第一轮遍历立即失效，0，1，2 都会被标记需要移动到3的后面，移动3次！
Vue2: 新节点首部 = 老节点尾部， 所以 3 需要移动到0的前面，移动1次！
为了根据key值获取老节点，React 和 vue2 都采用了 map 这一数据结构进行优化。
下面，我们继续探索 Vue3 的 快速diff算法。
第一轮遍历
- 从新老节点的首部节点开始，一个一个进行对比，直到遇到不相同的节点。
- 从新老节点的尾部节点开始，一个一个进行对比，直到遇到不相同的节点。
第二轮遍历
经过一轮遍历后，与react类似，根据新老节点的剩余结果可分为四种情况。
其他3种，与react类似，在此不赘述。
当中间这块新老节点都有剩余时，才是 Vue3 的 快速diff算法 的核心部分。
keyIndex ：key 为新节点 key ，value 为新节点的位置索引。
遍历老节点，根据 keyIndex 和老节点的key，可以获取到 value。
value的最大值 = 最大的位置索引 max。
当 出现 位置索引 value 比 max 小的情况，说明节点是发生移动的，否则位置索引k一定是单增。
遍历的同时，也会删除找不到key值对不上的老节点。
当这轮遍历结束后，会得到一个位置索引数组。
用最长递增子序列算法计算这个数组的最长递增子序列，在最长递增子序列中的节点是不需要移动的。
最后，从后往前遍历新结点，并根据位置索引数组判断，找不到key的为新建节点。
然后 子序列外的节点 和 新建的节点 每次都需要插入到下一个对应的新节点的前面。
举例说明
听起来有些抽象，下面举个例子。
老节点：【0，1，2，3，4，8，5，6 】
新节点：【0，1，7，3，4，2，5，6 】
经过第一轮遍历后，首部的【0，1】和尾部的【5，6】是可复用的。
剩余节点：老 =【2，3，4，8】，新 = 【7，3，4，2】
遍历老节点，得到 keyIndex: {2 : 4，3: 2，4: 3 }【索引值从1开始算，0 表示删除】
2 < 4 => 节点发生移动。
2，3，4 ： 找到对应的key了，更新老节点。
8: 找不到对应key，删除老节点。
老节点对应的位置索引数组：【4，2，3】。
计算最长递增子序列：【2，3】。
说明 第2个节点和第3个节点 无需移动。
最后 从 后往前 遍历新节点，
key = 2
在 keyIndex 可以找到，直接复用【前面已更新过了】。
插入到【3，4】的前面 ，【 3，4，2】
key = 7,
找不到对应的key，为新建节点，目前是最后一个节点，所以直接把新建节点放到最前面。
总结
行文至此，做个总结。
React 、Vue2、Vue3 的 diff算法 是基于前端业务场景做的优化，所以有很多相似之处。
- 只处理同级节点，使用key值，节点类型不同需删除后新建，时间复杂度已经降到(n）。
- 三者都优先处理简单的场景，或者说是节点不需要移动的场景。
当然，dom节点变动的场景也确实是相对较少。
react是从左到右，找到第一个key不同的节点。
Vue2是双端diff算法，新老首尾共四次比较，其中两次是首部比首部，尾部比尾部，对应的是只更新节点内容的情况。
Vue3是快速diff算法，首先比较的是首尾两部分，只是不再考虑双端diff中比较新老节点首部与尾部的情况。
- 针对复杂的场景，或者说需要节点移动的场景。
React 是用map实现根据key快速获取老节点，遍历新节点，如果 key值对应的老节点位置索引不是递增的，则给节点标记为placement。如果找不到对应 key 则为新建节点。
Vue2 是两者如果匹配就移动两边指针，如果是首尾部分匹配，则还需要移动节点，如果都不能匹配，则遍历老节点去找到key对应的节点，找不到则创建节点，最后都放到 旧前指针 的位置。当 新 / 老 节点两头的指针都已会合，与之相反的 新/ 老 节点 可能出现 首指针 > 尾指针 的情况，如果是新节点提前遍历结束，说明有多余的老节点要删除，反之就是需要新建更多的新节点。
Vue3的快速diff算法是根据新节点的位置索引，给老节点做标记，然后使用最长递增子序列算法计算出新节点中哪些节点是不需要移动的。最后，从后往前遍历新节点，在对应位置创建或者复用节点。
思考
综上所述，Vue3的快速diff算法似乎是其中的最优解，双端比较和最长递增子序列算法的结合，从最大程度上减少了移动节点的次数。既然如此，为什么 React 不用双端比较呢。
在 React 源码中，有一段官方的解释。
don't have backpointers on fibers.
Fiber 没有反向指针，这应该就是最直接的解释了。
function reconcileChildrenArray(
returnFiber: Fiber,
currentFirstChild: Fiber | null,
newChildren: Array<any>,
lanes: Lanes,
): Fiber | null {
// This algorithm can't optimize by searching from both ends since we
// don't have backpointers on fibers. I'm trying to see how far we can get
// with that model. If it ends up not being worth the tradeoffs, we can
// add it later.
// Even with a two ended optimization, we'd want to optimize for the case
// where there are few changes and brute force the comparison instead of
// going for the Map. It'd like to explore hitting that path first in
// forward-only mode and only go for the Map once we notice that we need
// lots of look ahead. This doesn't handle reversal as well as two ended
// search but that's unusual. Besides, for the two ended optimization to
// work on Iterables, we'd need to copy the whole set.
// In this first iteration, we'll just live with hitting the bad case
// (adding everything to a Map) in for every insert/move.
// If you change this code, also update reconcileChildrenIterator() which
// uses the same algorithm.
当你读懂了上段文字后，你就会明白 react 团队 受制于 Fiber 架构 没有反向指针的困扰，
要想实现双端diff 需要复制整个节点，并且觉得需要双端diff优化的情况也不是经常的，
所以在首次迭代中，会适应 adding everything to a Map 这种不好的情况。
ok！哈不动了，收笔。
参考文章
转载自:https://juejin.cn/post/7255855818594254906