关键词：react16 架构、react Reconciler、react commit 阶段、react 协调器
在 react 中：一个DOM节点在某一时刻最多会有4个节点和他相关。
一个DOM节点在某一时刻最多会有4个节点和他相关。
-
JSX对象。即ClassComponent的render方法的返回结果，或FunctionComponent的调用结果。JSX对象中包含描述DOM节点的信息。 -
workInProgress Fiber。如果该DOM节点将在本次更新中渲染到页面中，workInProgress Fiber代表该DOM节点对应的Fiber节点。 -
current Fiber。如果该DOM节点已在页面中，current Fiber代表该DOM节点对应的Fiber节点。 -
DOM节点本身。
Diff算法的本质是对比1和2，生成3。
概览
Diff的瓶颈以及React如何应对
由于Diff操作本身也会带来性能损耗， 即使在最前沿的算法中，将前后两棵树完全比对的算法的复杂程度为 O(n 3 )，其中n是树中元素的数量。
如果在React中使用了该算法，那么展示1000个元素所需要执行的计算量将在十亿的量级范围
为了降低算法复杂度，React的diff会预设三个限制：
-
只对同级元素进行Diff。如果一个DOM节点在前后两次更新中跨越了层级，那么React不会尝试复用他。
-
两个不同类型的元素会产生出不同的树。如果元素由div变为p，React会销毁div及其子孙节点，并新建p及其子孙节点。
-
开发者可以通过 key prop来暗示哪些子元素在不同的渲染下能保持稳定。
Diff是如何实现的
我们从Diff的入口函数reconcileChildFibers出发，该函数会根据newChild（即JSX对象）类型调用不同的处理函数。
从同级的节点数量将Diff分为两类：
-
当newChild类型为object、number、string，代表同级只有一个节点
-
当newChild类型为Array，同级有多个节点
单节点 diff
路程图：
React通过先判断key是否相同，如果key相同则判断type是否相同，只有都相同时一个DOM节点才能复用。
多节点 diff
主要分为以下几种情况
- 节点更新
- 节点属性变化
- 节点类型更新
- 节点新增或减少
- 节点位置变化
diff 思路
React 团队发现，在日常开发中，相较于新增和删除，更新组件发生的频率更高。所以Diff会优先判断当前节点是否属于更新。
本质上是进行了两轮遍历：
- 第一轮遍历：处理更新的节点。
- 第二轮遍历：处理剩下的不属于更新的节点。
为何不用双向指针的方式？
虽然本次更新的JSX对象 newChildren为数组形式，但是和newChildren中每个组件进行比较的是current fiber，同级的Fiber节点是由sibling指针链接形成的单链表，即不支持双指针遍历。
即 newChildren[0]与fiber比较，newChildren[1]与fiber.sibling比较。
所以无法使用双指针优化。
第一次遍历
第一轮遍历步骤如下：
-
let i = 0，遍历newChildren，将newChildren[i]与oldFiber比较，判断DOM节点是否可复用。 -
如果可复用，
i++，继续比较newChildren[i]与oldFiber.sibling，可以复用则继续遍历。 -
如果不可复用，分两种情况：
-
key不同导致不可复用，立即跳出整个遍历，第一轮遍历结束。
-
key相同type不同导致不可复用，会将
oldFiber标记为DELETION，并继续遍历
- 如果
newChildren遍历完（即i === newChildren.length - 1）或者oldFiber遍历完（即oldFiber.sibling === null），跳出遍历，第一轮遍历结束。
第二轮遍历
newChildren与oldFiber同时遍历完
那就是最理想的情况：只需在第一轮遍历进行组件更新
newChildren没遍历完，oldFiber遍历完
已有的DOM节点都复用了，这时还有新加入的节点，意味着本次更新有新节点插入，我们只需要遍历剩下的newChildren为生成的workInProgress fiber依次标记Placement。
newChildren遍历完，oldFiber没遍历完
意味着本次更新比之前的节点数量少，有节点被删除了。所以需要遍历剩下的oldFiber，依次标记Deletion。
newChildren与oldFiber都没遍历完
这意味着有节点在这次更新中改变了位置。
这是Diff算法最精髓也是最难懂的部分。我们接下来会重点讲解。
处理移动的节点
由于有节点改变了位置，所以不能再用位置索引i对比前后的节点，那么如何才能将同一个节点在两次更新中对应上呢？
我们需要使用key。
为了快速的找到key对应的oldFiber，我们将所有还未处理的oldFiber存入以key为key，oldFiber为value的Map中。
const existingChildren = mapRemainingChildren(returnFiber, oldFiber);
接下来遍历剩余的newChildren，通过newChildren[i].key就能在existingChildren中找到key相同的oldFiber。
标记节点是否移动
既然我们的目标是寻找移动的节点，那么我们需要明确：节点是否移动是以什么为参照物？
我们的参照物是：最后一个可复用的节点在oldFiber中的位置索引（用变量lastPlacedIndex表示）。
由于本次更新中节点是按newChildren的顺序排列。在遍历newChildren过程中，每个遍历到的可复用节点一定是当前遍历到的所有可复用节点中最靠右的那个，即一定在lastPlacedIndex对应的可复用的节点在本次更新中位置的后面。
那么我们只需要比较遍历到的可复用节点在上次更新时是否也在lastPlacedIndex对应的oldFiber后面，就能知道两次更新中这两个节点的相对位置改变没有。
我们用变量oldIndex表示遍历到的可复用节点在oldFiber中的位置索引。如果oldIndex < lastPlacedIndex，代表本次更新该节点需要向右移动。
lastPlacedIndex初始为0，每遍历一个可复用的节点，如果oldIndex >= lastPlacedIndex，则lastPlacedIndex = oldIndex。