我报名参加金石计划1期挑战——瓜分10万奖池，这是我的第1篇文章，点击查看活动详情

React的diff算法，根据节点数量可以简单明了的分为两种：

单节点diff算法

多节点diff算法

1. 单节点diff算法

单点diff算法，场景比较单一、简单 先根据key(jsx的key属性)是否相同，如果相同再进行type是否也相同，如果两者都相同，该dom节点才可以复用

2. 多点diff算法

多节点diff算法，顾名思义，多个dom节点进行比较；总得来说，一共分为三个场景

1.节点更新

1.1节点属性变化

1.2 节点类型变化

2.节点新增或减少

2.1 新增节点

2.2 删除节点

3.节点位置变化

节点的更新，我们都知道一共是三种：

1. 新增
2. 删除
3. 更新

React团队在日常开发中发现，更新在日常开发中发生的频率要比其他两种的频率更高，所以diff在处理节点时会优先判断该节点的状态是否是更新状态。

又因为React特殊的单链表结构，无法进行双指针优化，所有diff算法根据更新进行两轮遍历。

第一轮：处理更新的节点

第二轮：处理剩下的节点

具体实现

第一轮遍历

在第一轮遍历中， 会将新的节点数组，newChildren，将其每一个节点按照从左到右的顺序，依次与oldFiber进行比较，判断dom节点是否可以复用(复用规则参考单节点，key和type是否都一样)；

如果可以复用，继续将剩余的newChildren中的节点们和oldFiber.sibling（兄弟节点进行比较），如果可以复用，就一直遍历下去；

如果不可以复用，这里，不可复用将会出现两种情况：

1. key不同导致不可以复用，将会立刻跳出整个遍历，第一轮遍历马上结束（key不同，老厉害了）；
2. key相同但是type不同(key一样，但是type从div变成了span)，会将oldFiber标记为DELETION（删除），然后继续进行遍历；

如果newChildren遍历完或者oldFiber遍历完，将会跳出第一轮遍历

看完了刚刚的描述，我们知道了在多节点diff算法中，第一轮遍历，也就是处理更新的节点这一轮遍历中，具体如何进行复用dom节点，但是我们也有几种特殊的情况，是第一轮无法处理的，

如我们上面说的key节点不同（因为跳出了第一轮遍历），newChildren或者oldFiber两者没有遍历完（这里又可以分为三种情况：1.前者遍历完；2.后者遍历完；3.两者同时遍历完）

带着这些疑问，我们进行第二轮的遍历

第二轮遍历

这里我们，根据第一轮遍历的结果进行处理：

1. 如果是newChildren和oldFiber同时都遍历完了，皆大欢喜，在第一轮diff就会结束；

2. newChildren没遍历完，但是oldFiber遍历完了 这说明已经有的dom都已经复用完了，剩下的newChildren中的节点，都是新增的节点，我们只需要遍历剩下的节点，然后为它们打上Placement的标记就好了

3. newCHildren遍历完了，oldFiber没有遍历完 这说明更新后，新的比老的少了，有节点被删除了。也就是没有遍历到的oldFiber节点，我们依次给它们打上Deletion就可以了

4. newChildren与oldFiber都没有遍历完

这个场景是diff算法中，最最复杂的场景，因为这种场景意味着出现了移动的节点。

因为有节点变更了位置，所以我们前面用的下标，就变得不可靠了！

那么我们还能用什么东东呢？

key，我们要使用key，为了快速找到key对应的oldFiber，我们将所有还没有处理的oldFiber存入以该节点的key为key，oldFiber为value的Map中

// React源码
const existingChildren = mapRemainingChildren(returnFiber, oldFiber);

然后我们遍历我们刚刚还没有用完的newChildren，通过该数组中每个节点的key去上述map中找到对应key的oldFiber。

在这里，我们首先要知道：节点是否移动是通过啥判断的，也就是说节点移动的参照是什么？？

通过学习，得知，参照物是：最后一个可复用的节点在oldFiber中的位置索引 react中，用lastPlacedIndex表示！！！

这开始之前，我们需要明确，可复用节点和lastPlacedIndex的关系，以及oldIndex

我们知道，在前面的遍历过程中，我们根据newChildren的顺序进行遍历，那么lastPlacedIndex一定是最后一个可复用的节点，也就是newChildren数组中，所能复用的最后右边的节点的下标;

变量oldIndex表示遍历到可复用节点在oldFiber中的索引位置；

所以我们根据比较两个下标，来进行判断节点如何进行移动：

如果oldFiber的值 < lastPlacedIndex，则代表，这个节点，需要向右边移动

刚开始，lastPlacedIndex默认值为0,每有一个可以复用的节点，并且oldIndex >= lastPlacedIndex,会将前者的值赋值给后者。

一个小demo🌰：

//前 
//oldFiber
    <div key='1'>前端江鸟1</> //1
    <div key='2'>前端江鸟2</> //2
    <div key='3'>前端江鸟3</> //3
    <div key='4'>前端江鸟4</> //4

//后 
//newChildren
   <div key='1'>前端江鸟1</>  //1 
   <div key='3'>前端江鸟3</>  //3
   <div key='4'>前端江鸟4</>  //4
   <div key='2'>前端江鸟2</>  //2

第一轮遍历：

为了方便演示，我们用注释代表节点 第一轮： 前后对比，1的key和type一样，可以复用，此时oldIndex = 0;lastPlaceIndex = 0;

继续： 发现2不等于3，key不相同，无法复用，直接跳出第一轮遍历；

---

第二轮遍历：

开始前，我们知道当前的lastPlaceIndex = 0！！！

根据前文所说，newChildren和oldFiber都没有遍历完，触发率最复杂的第四种场景！ 😄😄😄

开始：

//前 
//oldFiber
    <div key='2'>前端江鸟2</> //2
    <div key='3'>前端江鸟3</> //3
    <div key='4'>前端江鸟4</> //4

//后 
//newChildren
   <div key='3'>前端江鸟3</>  //3
   <div key='4'>前端江鸟4</>  //4
   <div key='2'>前端江鸟2</>  //2

将剩余oldFiber保存为map(key是节点的key，value是节点)

newChildren根据下标依次遍历，发现key = 3在oldFiber中存在，这时，oldIndex = 2；此时lastPlacedIndex = 0；发现oldIndex > lastPlacedIndex,按照前文所说，该节点位置不变，这时，lastPlaceIndex = oldIndex = 2；

继续遍历：

key = 4在oldFiber中存在，这时oldIndex = 3,此时lastPlacedIndex = 2，发现oldIndex > lastPlacedIndex,按照前文所说，该节点位置不变，这时，lastPlaceIndex = oldIndex = 3；

继续遍历：

key = 2在oldFiber中存在，oldIndex = 1，此时lastPlaceIndex = 3,发现oldIndex < lastPlaceIndex,按照前文所说，该节点位置变更了，该节点向右移动了！！

oldFiber和newChildren都遍历完了，皆大欢喜！！！

最后，根据结果，发现，134都没有位移，2发生了向右位移！！

总结

React在diff算法中，如何复用，一共就这些情况，这里尽量不涉及源码，只说思想，争取明白diff的思想，明白diff如何复用dom节点！！！ 最后，如果有不对的地方，欢迎指正，共同进步！！