react中的diff算法

diff算法
对于React团队发现在日常开发中对于更新组件的频率，会比新增和删除的频率更高，所以在diff算法里，判断更新的优先级会更高。对于Vue2的diff算法使用了双指针，React的diff算法没有使用双指针，是因为更新的jsx对象的newChildren为数组的形式，但是和newChildren中每个组件比较的是current fiber，对fiber的兄弟节点是通过silbing来相连的，我们通过下标来去获取下一个newChildren项，但是对于fiber只能通过fiber.silbing来获取对应的项，所以没有使用双指针法来进行diff。

所以React的diff算法的整体逻辑会经历两轮的遍历。

第一轮遍历：
会尝试逐个的复用节点；

第二轮遍历：
处理上一轮遍历中没有处理完的节点。

一、第一轮遍历：
从前往后以此进行遍历，存在三种情况：

• 若新旧子节点的key和type都相同，则说明可以复用；

• 若新旧子节点的key相同，但是type不同，这个时候会根据

  reactElement来生成一个全新的fiber，旧的fiber被放入到deletions数组中，回头统一删除，但是注意，此时遍历不回停止；

• 若新旧子节点的key和type都不相同，则结束遍历。

实例1：
前：

<div>
<div key='a'>a</div>
<div key='b'>b</div>	
<div key='c'>c</div>	
<div key='d'>d</div>	
</div>	

后：

<div>
<div key='a'>a</div>
<div key='b'>d</div>	
<div key='e'>e</div>	
<div key='d'>d</div>	
</div>	

我们发现div.key.a和我们发现div.key.b可以复用，继续往后走
走到div.key.e,我们发现key不同，结束第一轮遍历；

实例2：

<div>
<div key='a'>a</div>
<div key='b'>b</div>	
<div key='c'>c</div>	
<div key='d'>d</div>	
</div>	

更新后：

<div>
<div key='a'>a</div>
<div key='b'>b</div>	
<p key='c'>c</p>	
<div key='d'>d</div>	
</div>	

前面div.keya和div.keyb都会复用，接下来到了第3个节点，我们发现key是相同的，但是type不同，就会将对应的旧的fiberNode放到一个叫deletions中数组中，回头统一删除，然后根据新的react元素创建一个新的FiberNode,但此时的遍历不会结束。
接下来往后面继续遍历，遍历什么时候结束？
到末尾了，也就是遍历完了
或者是和实例1相同，发现key不同。

二、第二轮遍历：
如果第一轮遍历被提前停止了，那么意味着有新的React元素或者旧的FiberNode没有遍历完，此时就会采用第二轮遍历；
第二轮遍历会处理这么三种情况：
只剩下旧子节点：将旧的子节点放到deletions数组里面直接删除掉（删除的情况）；
只剩下新的jsx元素：根据RecreatElement元素来创建新的FiberNode节点（新增的情况）；
新旧节点都有剩余：
会将剩余的FiberNode节点放到一个map里面，遍历剩余的jsx元素，然后从map中找出可以复用的fiberNode,若能找到就拿来复用（移动的情况）
若不能找到，就新增，然后若剩余的jsx元素都遍历完了，map结构中还有剩余的fiber节点，就将这些fiber节点添加到deletions数组中，之后做统一删除。

例子：

// 之前
abcd

// 之后
acdb

===第一轮遍历开始===
a（之后）vs a（之前）  
key不变，可复用
此时 a 对应的oldFiber（之前的a）在之前的数组（abcd）中索引为0
所以 lastPlacedIndex = 0;

继续第一轮遍历...

c（之后）vs b（之前）  
key改变，不能复用，跳出第一轮遍历
此时 lastPlacedIndex === 0;
===第一轮遍历结束===

===第二轮遍历开始===
newChildren === cdb，没用完，不需要执行删除旧节点
oldFiber === bcd，没用完，不需要执行插入新节点

将剩余oldFiber（bcd）保存为map

// 当前oldFiber：bcd
// 当前newChildren：cdb

继续遍历剩余newChildren

key === c 在 oldFiber中存在
const oldIndex = c（之前）.index;
此时 oldIndex === 2;  // 之前节点为 abcd，所以c.index === 2
比较 oldIndex 与 lastPlacedIndex;

如果 oldIndex >= lastPlacedIndex 代表该可复用节点不需要移动
并将 lastPlacedIndex = oldIndex;
如果 oldIndex < lastplacedIndex 该可复用节点之前插入的位置索引小于这次更新需要插入的位置索引，代表该节点需要向右移动

在例子中，oldIndex 2 > lastPlacedIndex 0，
则 lastPlacedIndex = 2;
c节点位置不变

继续遍历剩余newChildren

// 当前oldFiber：bd
// 当前newChildren：db

key === d 在 oldFiber中存在
const oldIndex = d（之前）.index;
oldIndex 3 > lastPlacedIndex 2 // 之前节点为 abcd，所以d.index === 3
则 lastPlacedIndex = 3;
d节点位置不变

继续遍历剩余newChildren

// 当前oldFiber：b
// 当前newChildren：b

key === b 在 oldFiber中存在
const oldIndex = b（之前）.index;
oldIndex 1 < lastPlacedIndex 3 // 之前节点为 abcd，所以b.index === 1
则 b节点需要向右移动
===第二轮遍历结束===

最终acd 3个节点都没有移动，b节点被标记为移动

再看个例子：

// 之前
abcd
// 之后
dabc
===第一轮遍历开始===
d（之后）vs a（之前）
key不变，type改变，不能复用，跳出遍历
===第一轮遍历结束===
===第二轮遍历开始===
newChildren === dabc，没用完，不需要执行删除旧节点
oldFiber === abcd，没用完，不需要执行插入新节点
将剩余oldFiber（abcd）保存为map
继续遍历剩余newChildren
// 当前oldFiber：abcd
// 当前newChildren dabc
key === d 在 oldFiber中存在
const oldIndex = d（之前）.index;
此时 oldIndex === 3; // 之前节点为 abcd，所以d.index === 3
比较 oldIndex 与 lastPlacedIndex;
oldIndex 3 > lastPlacedIndex 0
则 lastPlacedIndex = 3;
d节点位置不变
继续遍历剩余newChildren
// 当前oldFiber：abc
// 当前newChildren abc
key === a 在 oldFiber中存在
const oldIndex = a（之前）.index; // 之前节点为 abcd，所以a.index === 0
此时 oldIndex === 0;
比较 oldIndex 与 lastPlacedIndex;
oldIndex 0 < lastPlacedIndex 3
则 a节点需要向右移动
继续遍历剩余newChildren
// 当前oldFiber：bc
// 当前newChildren bc
key === b 在 oldFiber中存在
const oldIndex = b（之前）.index; // 之前节点为 abcd，所以b.index === 1
此时 oldIndex === 1;
比较 oldIndex 与 lastPlacedIndex;
oldIndex 1 < lastPlacedIndex 3
则 b节点需要向右移动
继续遍历剩余newChildren
// 当前oldFiber：c
// 当前newChildren c
key === c 在 oldFiber中存在
const oldIndex = c（之前）.index; // 之前节点为 abcd，所以c.index === 2
此时 oldIndex === 2;
比较 oldIndex 与 lastPlacedIndex;
oldIndex 2 < lastPlacedIndex 3
则 c节点需要向右移动
===第二轮遍历结束===