关于diff:为什么-React-的-Diff-算法不采用-Vue-的双端对比算法

前言
都说“双端比照算法”，那么双端比照算法，到底是怎么样的呢？跟 React 中的 Diff 算法又有什么不同呢？
要理解这些，咱们先理解 React 中的 Diff 算法，而后再理解 Vue3 中的 Diff 算法，最初讲一下 Vue2 中的 Diff 算法，能力去比拟一下他们的区别。
最初讲一下为什么 Vue 中不须要应用 Fiber 架构。
React 官网的解析
其实为什么 React 不采纳 Vue 的双端比照算法，React 官网曾经在源码的正文里曾经阐明了，咱们来看一下 React 官网是怎么说的。
function reconcileChildrenArray(
returnFiber: Fiber,
currentFirstChild: Fiber | null,
newChildren: Array<*>,
expirationTime: ExpirationTime,
): Fiber | null {

// This algorithm can't optimize by searching from boths 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 不能通过双端比照进行 Diff 算法优化是因为目前 Fiber 上没有设置反向链表，而且想晓得就目前这种计划能继续多久，如果目前这种模式不现实的话，那么也能够减少双端比照算法。
即便是双端比照算法，咱们也要对这种状况进行优化，咱们应该应用 Map 这种数据结构计划去代替原来那种简直没有什么变动也进行暴力比拟的计划。它第一次搜寻循环是通过 forward-only 这种模式（就是只从左向右查找），（第一次循环可能还没有完结，还有节点没有比对的时候）如果还要持续向前循环查找那么就要通过 Map 这种数据类型了。（就目前这个单向链表的数据结构，如果采纳）双端比照查找算法比拟难管制它反向查找的，但它的确是一种胜利的算法。此外，双端比照算法的实现也在咱们的工作迭代当中。
第一次迭代，咱们就先将就应用这种不好的计划吧，每次新增 / 挪动都要增加所有的数据到一个 Map 的数据类型对象中。
“we’d need to copy the whole set”，这一句，每一个单词都懂，但就是不晓得他想说什么，所以就不翻译了，有晓得的大神吗？
自己程度无限，错漏不免，如有错漏，恳请各位斧正。
React 的官网尽管解析了，但咱们想要彻底了解到底为什么，还是要去具体理解 React 的 Diff 算法是怎么样的。在理解 React Diff 算法之前，咱们首先要理解什么是 Fiber，为什么 React 中要应用 Fiber？
Fiber 的构造
在 React15 以前 React 的组件更新创立虚构 DOM 和 Diff 的过程是不可中断，如果须要更新组件树层级十分深的话，在 Diff 的过程会十分占用浏览器的线程，而咱们都晓得浏览器执行 JavaScript 的线程和渲染实在 DOM 的线程是互斥的，也就是同一时间内，浏览器要么在执行 JavaScript 的代码运算，要么在渲染页面，如果 JavaScript 的代码运行工夫过长则会造成页面卡顿。
基于以上起因 React 团队在 React16 之后就改写了整个架构，将原来数组构造的虚构 DOM，改成叫 Fiber 的一种数据结构，基于这种 Fiber 的数据结构能够实现由原来不可中断的更新过程变成异步的可中断的更新。
Fiber 的数据结构次要长成以下的样子，次要通过 Fiber 的一些属性去保留组件相干的信息。
function FiberNode(
tag: WorkTag,
pendingProps: mixed,
key: null | string,
mode: TypeOfMode,
) {
// 作为静态数据构造的属性
this.tag = tag;
this.key = key;
this.elementType = null;
this.type = null;
this.stateNode = null;

// 用于连贯其余 Fiber 节点造成 Fiber 树
this.return = null;
this.child = null;
this.sibling = null;
this.index = 0;

this.ref = null;

// 作为动静的工作单元的属性
this.pendingProps = pendingProps;
this.memoizedProps = null;
this.updateQueue = null;
this.memoizedState = null;
this.dependencies = null;

this.mode = mode;

this.effectTag = NoEffect;
this.nextEffect = null;

this.firstEffect = null;
this.lastEffect = null;

// 调度优先级相干
this.lanes = NoLanes;
this.childLanes = NoLanes;

// 指向该 fiber 在另一次更新时对应的 fiber
this.alternate = null;
}

Fiber 次要靠以下属性连成一棵树构造的数据的，也就是 Fiber 链表。
// 指向父级 Fiber 节点
this.return = null;
// 指向子 Fiber 节点
this.child = null;
// 指向左边第一个兄弟 Fiber 节点
this.sibling = null;

举个例子，如下的组件构造：
function App() {
return (

<div>
  i am
  <span>Coboy</span>
</div>

)
}

对应的 Fiber 链表构造：

那么以上的 Fiber 链表的数据结构有什么特点，就是任何一个地位的 Fiber 节点，都能够非常容易晓得它的父 Fiber, 第一个子元素的 Fiber, 和它的兄弟节点 Fiber。却不容易晓得它前一个 Fiber 节点是谁，这就是 React 中单向链表 Fiber 节点的特点。也正是因为这些即使在协调的过程被中断了，再复原协调的时候，仍然晓得以后的 父节点和孩子节点等信息。
那么 React 是将对应组件怎么生成一个 Fiber 链表数据的呢？
Fiber 链表的生成
下面的组件在通过 JSX 的编译之后，初始化的时候会生成成一个相似于 React 15 或者 Vue 那种虚构 DOM 的数据结构。而后创立一个叫 fiberRoot 的 Fiber 节点，而后开始从 fiberRoot 这个根 Fiber 开始进行协调，生成一棵 Fiber 树，这个棵树被称为：workInProgress Fiber 树，意思是正在工作的 Fiber 树，接下来咱们具体理解一下具体是怎么生成一棵 Fiber 树的。要先理解 Fiber 树的生成原理才更好去了解 Fiber 树 diff 的过程。
以下是一段简略版的 Fiber 链表生成的代码片段。
这个协调子节点的函数接管两个参数，returnFiber 是父 Fiber，children 是这个节点的子元素的虚构 DOM 数据。
// 这个协调子节点的函数接管两个参数，returnFiber 是父 Fiber，children 是这个节点的子元素的虚构 DOM 数据。
export function reconcileChildren(returnFiber, children) {

// 如果是字符串或者数字则不创立 Fiber
if(isStringOrNumber(children)) {return}
const newChildren = isArray(children) ? children : [children]
// 上一轮的 fiber 节点
let previousNewFiber = null;
// 首次渲染（false）还是更新（true）let shouldTrackSideEffects = !!returnFiber.alternate
// 老 Fiber 节点
let oldFiber = returnFiber.alternate && returnFiber.alternate.child
let nextOldFiber = null
// 上一次协调返回的地位
let lastPlacedIndex = 0;
// 记录每个 fiber 节点的地位
let newIdx = 0;
// 如果不存在老 Fiber 则是初始化的过程，进行 Fiber 链表的创立
if(!oldFiber) {for (; newIdx < newChildren.length; newIdx++) {
        // 获取节点元素内容
        const newChild = newChildren[newIdx]
        // 如果节点为 null 则不须要创立 fiber 节点
        if(newChild === null) {continue}
        // 创立新 fiber 的时候记录了要害的父 fiber 等重要信息
        const newFiber = createFiber(newChild, returnFiber)
        // 记录以后每一个 fiber 的地位
        lastPlacedIndex = placeChild(
            newFiber,
            lastPlacedIndex,
            newIdx,
            shouldTrackSideEffects // 首次渲染（false）还是更新（true）)
        // 当上一轮的 fiber 节点为 null 的时候，这一轮的 fiber 就是头节点
        if(previousNewFiber === null) {
            // 父 fiber 的 child 就是第一个节点
            returnFiber.child = newFiber
        } else {
            // 如果不是第一个节点，那么就是兄弟节点
            // 上一轮 fiber 的兄弟节点是这一轮的 fiber 节点
            previousNewFiber.sibling = newFiber;
        }
       // 记录上一轮的 fiber，既是这一轮的 fiber 便是下一轮的上一轮 fiber
        previousNewFiber = newFiber
    }
    return
}

}

构建完的 workInProgress Fiber 树 会在 commit 阶段 渲染到页面。
在组件状态数据产生变更的时候，会依据最新的状态数据先会生成新的虚构 DOM，再去构建一棵新的 workInProgress Fiber 树，而在从新协调构建新的 Fiber 树的过程也就是 React Diff 产生的中央。接下来，咱们就看看 React Diff 算法是怎么样的。
React 的 Diff 算法
深度优先，有子节点，就遍历子节点，没有子节点，就找兄弟节点，没有兄弟节点，就找叔叔节点，叔叔节点也没有的话，就持续往上找，它爷爷的兄弟，如果始终没找到，就代表所有的更新工作都更新结束了。
重点是在更新本人的同时须要去协调子节点，也就是传说中进行 Diff 的中央。
进入协调的时候它本人就是父 Fiber，它的子节点在协调之前，是刚刚通过更新的状态数据生成的最新的虚构 DOM 数据，是个数组构造的元素数据。
那么要进行更新，就必定是认为最新的节点数据为准了，又因为最新的节点数据是一个数组，所以能够进行循环比照每一个节点，很显著这个循环是从左向右进行查找比对的。