一、什么是diff算法？
为了增强用户体验，React从版本16开始将同步更新重构成了可中断的异步更新，即采用了新的Reconciler(协调器，用于找出变化的组件），而新的Reconciler中采用了fiber架构。fiber架构的原理在此不再详细解释，我们目前只需要知道fiber节点可以保存dom信息，fiber节点构成的树叫fiber树，而更新dom是要用到‘双缓存技术’，即比较旧的fiber树与此次要渲染的jsx对象，返回新的fiber树进行渲染。在旧fiber树与jsx对象比较时，决定哪些节点要复用的过程，就是diff算法。
由于diff本身也会带来性能消耗，为了降低算法复杂度，React对diff做了三个预设限制：
- 只对同级元素进行diff，如果某元素在更新之后跨越了层级，那么React不会复用它
- 两个不同类型的元素会产生两颗不同的树，即如果元素由div变成p，那么React会删除div及其子孙节点，新建p及其子孙节点
- 开发者可以使用key参数表示哪些元素在不同的渲染下保持稳定，例如
更新前
<p key='1'></p>
<div key='2'></div>
更新后
<div key='2'></div>
<p key='1'></p>
如果没有key会走第二条限制，有了key，react就可以判断div和p节点是存在的，可以复用，只需要交换顺序。
diff算法会根据不同的jsx对象执行不同的处理函数，根据jsx对象的不同，我们可以分为两类：
1.JSX对象（之后都用newChildren表示）的类型为object、number、string，代表同级只有一个节点
2. newChildren的类型为Array，代表同级有多个节点。
二、单节点diff
对于单节点diff，用一个流程图就可以解释
注意：比较newChildren与current fiber(之后称为oldFiber)时，只有当key相同且元素类型相同时，dom节点才可以复用，如果fiber上的dom信息存在，而且key相同但元素类型不同，那么要删除该fiber及其所有兄弟节点，如果dom信息存在，但key不同，那么只是删除该fiber节点。例如
更新前
<div>1</div>
<div>2</div>
<div>3</div>
更新后
<p>1</p>
由于key的默认值为null，所以更新前与更新后满足key相同且元素类型不同，那么我们要删除更新前的三个div节点，新增p节点
三、多节点diff
对于多节点diff, 我们要遍历newChildren和oldFiber进行比较。由于React团队发现dom节点一般有更新，增加，删除这三种操作，而更新更为频繁，所以他们设置更新的优先级高于增加删除。基于以上原因，在多节点diff算法的实现中有两层遍历，第一层遍历处理更新的节点，第二层遍历处理更新以外的节点。
第一层遍历
遍历newChildren与oldFiber, 判断节点是否可复用，如果可以复用，则继续遍历。
如果不能复用，分为两种情况：
- key相同但type不同，那么将oldFiber标记为DELETION，继续遍历
- key不相同，立即跳出遍历。
第二层遍历
第二层遍历从第一层遍历的结束位开始
第一层遍历结束后有4种结果
- newChildren与oldFiber都遍历完，此时我们只需要在第一遍遍历的基础上进行更新。
- newChildren遍历完，oldFiber没有遍历完，说明有节点被删除了，那我们只需要遍历剩下的oldFiber，并打上DELETION标记。
- newChildren没有遍历完，oldFiber遍历完，说明增加了一些节点，那我们需要遍历剩下的newChildren为生成的workInProgress Fiber打上Placement标签
- newChildren和oldFiber都没有遍历完 ，这主要是由于遍历到的节点key不相同导致的。这说明有节点的位置改变了。通过比较newChildren中的节点与其在oldFiber中的位置信息，我们可以知道它的相对顺序。
首先我们要判断newChildren中遍历到的节点，在oldFiber中是否存在，基于此，React将oldFiber中的节点以key-oldfiber 键值对的形式存在Map中，只需要newChildren的key，就可以判断oldFiber中有没有相应的节点。
如果oldFiber中没有相应的节点，则将newChildren生成的fiber打上placement标记
如果有相应的节点，将它的索引记为oldIndex，与上一次可复用节点在oldFiber的索引位置lastPlacedIndex比较，如果每次可复用的节点在上一次可复用右边就说明位置没有变化，即
若oldIndex >=lastPlacedIndex, 说明相对位置没有变化，那么令lastPlacedIndex=oldIndex
若oldIndex<lastPlacedIndex, 代表本节点需要向右移动。
例如:
//更新后
abcd
//更新前
acbd
第一次遍历, a节点可复用，lastPlacedIndex=0, b节点key不同，跳出遍历
第二次遍历
//更新后
bcd
//更新前
cbd
1.遍历b,发现它的oldIndex=2 ( 在acbd中的位置）,由于oldIndex>lastPlacedIndex ，则lastPlacedIndex=oldIndex
2. 遍历c,oldIndex=1,则oldIndex<lastPlacedIndex, 则本次更新节点需要向右移动，阅读源码发现是打了Placement标签
3. 遍历d, oldIndex=3, oldIndex>lastPlacedIndex, 那么lastPlacedIndex=oldIndex, 遍历结束
