##react diff过程分析
React 的 render() 方法，会创建一棵由 React 元素组成的树。在下一次 state 或 props 更新时， 相同的 render() 方法会返回一棵不同的树。React 需要基于这两棵树之间的差别来判断如何高效的更新 UI， 以保证当前 UI 与最新的树保持同步。
如果将两棵树中所有的节点全部遍历去对比来确定哪些 ui 会更新，那这个开销是非常大的。即使使用最优算法，1000 个元素所需要执行的计算量都将在十亿的量级范围。
因此为了降低算法的复杂度，react的diff会预设三个限制：
- 只对同级元素进行 diff。如果在更新中，节点跨越了层级，那在
render()时节点会被重新渲染 - 如果节点的类型发生了改变，
react会销毁它和它所有子孙节点，在render()时重新渲染 - 如果节点有 key 属性，那在 key 属性不变的情况下，节点不会被重新渲染
diff 的入口函数是reconcileChildFibers我们可以发现该函数会根据newChild的类型调用不同的处理函数。大概可以氛围两类：
- 单节点 diff
- 多节点 diff
单节点 diff
单节点 diff 时会进入到函数reconcileSingleElement这个函数做的事情如下：
<div style="text-align: left">
<img src="https://img.yuanmabao.com/zijie/pic/2022/08/16/uvh12ejafch.png" width="700" alt=""/>
</div>
其中最关键的步骤就是第二步，对于dom节点是否可以复用的判断，其实现逻辑：
代码语言：typescript复制function reconcileSingleElement(
returnFiber: Fiber,
currentFirstChild: Fiber | null,
element: ReactElement
): Fiber {
const key = element.key;
let child = currentFirstChild;
// 首先判断是否存在对应DOM节点
while (child !== null) {
// 上一次更新存在DOM节点，接下来判断是否可复用
// 首先比较key是否相同
if (child.key === key) {
// key相同，接下来比较type是否相同
switch (child.tag) {
// ...省略case
default: {
if (child.elementType === element.type) {
// type相同则表示可以复用
// 返回复用的fiber
return existing;
}
// type不同则跳出switch
break;
}
}
// 代码执行到这里代表：key相同但是type不同
// 将该fiber及其兄弟fiber标记为删除
deleteRemainingChildren(returnFiber, child);
break;
} else {
// key不同，将该fiber标记为删除
deleteChild(returnFiber, child);
}
child = child.sibling;
}
// 创建新Fiber，并返回 ...省略
}我们会发现如果 key 相同，type 不同的情况下会将其child和兄弟节点都删除掉。但是 key 不同的话只会删除将child删除。我们可以通过一个例子来理解其原因：
<!--当前页面-->
<ul>
<li>1</li>
<li>2</li>
<p>3</p>
</ul>
<!--更新后的页面-->
<ul>
<p>1</p>
</ul>本次更新后的节点只有一个，所以会走单节点 diff，在reconcileSingleElement方法中的 while 中会对三个 li 节点进行
遍历来寻找是否有能够复用的节点。
当 key 相同的时候（这里是null === null），代表我们找到了这次更新的节点所对应的上次的节点。所以我们只用判断这两个节点能否复用，其他的节点就不考虑了。
当 key 不同的时候，如果 type 不同只是代表当前节点不能被复用，后面有可能会有能复用的，所以就只是删除child继续遍历兄弟节点。
所以根据 react 的 diff 特性，开发中可以这样优化
代码语言：html复制<!--当前页面-->
<ul>
<li key="li-1">1</li>
<li key="li-2">2</li>
<p key="p-1">3</p>
</ul>
<!--更新后的页面-->
<ul>
<p key="p-1">1</p>
</ul>这样的话这个p节点就会被复用，可以节约渲染的开销
多节点 diff
先来看看我们会遇到的情况
- 1、节点更新
// 之前
<ul>
代码语言：txt复制<li key="0">0</li><li key="1">1</li></ul>
// 之后 (节点key改变)
<ul>
代码语言：txt复制<li key="2">0</li><li key="1">1</li></ul>
// 之后 (节点类型变化)
<ul>
代码语言：txt复制<div key="0">0</div><li key="1">1</li></ul>
代码语言：txt复制- 2、节点增减
// 之前
<ul>
代码语言：txt复制<li key="0">0</li><li key="1">1</li></ul>
// 之后 (节点增加)
<ul>
代码语言：txt复制<li key="0">0</li><li key="1">1</li><li key="1">2</li></ul>
// 之后 (节点减少)
<ul>
代码语言：txt复制<li key="0">0</li></ul>
代码语言：txt复制- 3、节点位置变化
// 之前
<ul>
代码语言：txt复制<li key="0">0</li><li key="1">1</li></ul>
// 之后 (节点增加)
<ul>
代码语言：txt复制<li key="1">1</li><li key="0">0</li></ul>
代码语言：txt复制如果让我自己来处理多节点找复用的话，我的第一反应是遍历更新后的节点列表，然后在每一次遍历中去遍历更新前的节点列表，借此来寻找可复用的节点。这样的算法复杂度是:n^2。那么让我们来看看 react 的 diff 算法的复杂度是多少
react 在 diff 的时候会遍历两轮，第一轮主要处理能否复用，第二轮主要处理新增和删除以及排序
第一轮遍历
代码语言：typescript复制// 第一轮遍历开始之前
var lastPlacedIndex = 0; // 在第二轮遍历会用到
// 遍历newChildren（oldFiber === null：旧节点遍历光了，会跳出循环）
for (; oldFiber !== null && newIdx < newChildren.length; newIdx ) {
...
// 和对应的oldFiber作比较（能不能复用）
var newFiber = updateSlot(returnFiber, oldFiber, newChildren[newIdx], lanes);
...
if (newFiber === null) {
...
/**
* key不同导致的不能复用，直接跳出循环;
* key相同type不同导致的不可复用会将oldFiber标记为DELETION，并继续遍历
* */
break;
}
...
lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx); // 更新lastPlacedIndex
oldFiber = nextOldFiber; //更新oldFiber
}从三面的代码我们可以看出循环会有两种可能结束：
- 直接跳出循环：
newChildren和oldFiber都没遍历完； newChildren遍历完或oldFiber遍历完或二者同时遍历完；
接着我们带着第一轮遍历的结果来看第二轮遍历
第二轮遍历
对于结果二我们就不用细讲了，二者同时遍历意味着这次 diff 完成；newChildren遍历完oldFiber没完，意味着有节点剩下，依次删除就好了；如果是oldFiber遍历完成，newChildren没完，那就意味着有新增，直接依次加入就好了。
这轮遍历重点关注结果一，结果一的跳出是由于更新前后同一个index对应的两个fiber的key变了。这里除了是节点本身真的变了之外，还有一种可能是节点的位置发生了改变，所以这里我们还需要将能复用，但是位置发生了改变的节点的正确位置找到，所以说到底，这其实是一个排序算法。
这里我们用字母abcd来代替节点。然后通过一个例子来说明下这个排序的算法。
const oldList = ["a", "b", "c", "d"];
const newList = ["a", "d", "c", "b"];
// 我们需要做的工作其实是将oldList的顺序变成和newList一样，这样就能是实现节点的复用
// 我们首先定义一个lastPlacedIndex，它代表了在oldList中第一个可被复用的节点的index
// 它会在第一次循环中被定义且赋初值为0，这里我们就假设第一轮遍历中没有找到可复用的节点，所以它的值依然为0
let lastPlacedIndex = 0;
// 循环newList
----第一次循环开始----
节点a在oldList中的index是0,0是>=lastPlacedIndex的,所以更新lastPlacedIndex=index,节点不需要移动
此时：
lastPlacedIndex:0
oldList:["a", "b", "c", "d"]
----第一次循环结束----
----第二次循环开始----
节点d在oldList中的index是3,3是>=lastPlacedIndex的,所以更新lastPlacedIndex=index,节点不需要移动
此时:
lastPlacedIndex:3
oldList:["a", "b", "c", "d"]
----第二次循环结束----
----第三次循环开始----
节点c在oldList中的index是2,2是<lastPlacedIndex的,所以不更新lastPlacedIndex,节点移动到lastPlacedIndex的位置
此时:
lastPlacedIndex:3
oldList:["a", "b","d","c"]
----第三次循环结束----
----第四次循环开始----
节点b在oldList中的index是1,1是<lastPlacedIndex的,所以不更新lastPlacedIndex,节点移动到lastPlacedIndex的位置
此时:
lastPlacedIndex:3
oldList:["a","d","c","b"]
----第四次循环结束----
// 所以循环结束后oldList的顺序就变成了["a","d","c","b"],我们的工作就做完了所以我们会发现 react 通过两次遍历将多节点diff算法的复杂度成功降到了n，比起n^2可以说是减少了太多了。
然后我也简单的实现了 react 的第二次遍历。直接看代码吧。
代码语言：javascript复制const react = (inputs, outputs) => {
let lastPlacedIndex = 0;
inputs = inputs.filter((item) => outputs.includes(item)); // 去掉被删除了的节点
let temp = inputs.slice(0);
const locationMapList = []; // 用来记录新增的节点的位置
outputs.forEach((item, index) => {
const oldIndex = inputs.indexOf(item);
const canPlaced = !(oldIndex === -1);
/* 有对应的旧节点 */
if (canPlaced) {
/* 可复用的旧节点不需要移动位置 */
if (oldIndex >= lastPlacedIndex) {
lastPlacedIndex = oldIndex;
/* 可复用的旧节点，但是需要将节点放置到列表的最右边去 */
} else {
// 可复用节点入数组正确的位置（lastPlacedIndex的右边）
temp.splice(lastPlacedIndex 1, 0, item);
// 删除错误位置的可复用节点
temp.splice(oldIndex, 1);
}
/* 没有可复用的旧节点 */
} else {
// 记录位置
locationMapList.push({
index,
value: item,
});
}
});
/* 将新增的加进对应位置 */
locationMapList.forEach((item) => {
temp.splice(item.index, 0, item.value);
});
return temp;
};
/* 节点数量相同 */
console.log(react(["a", "b", "c", "d"], ["a", "d", "c", "b"])); // ["d", "c", "a", "b"];
/* 新增了节点 */
console.log(react(["a", "b", "c"], ["e", "a", "g", "c", "d", "b", "l"])); // ["e", "a", "g", "c", "d", "b", "l"]
/* 删除了节点 */
console.log(react(["a", "b", "c", "d", "e"], ["d", "a", "e"])); // ["d", "a", "e"];
/* 既有删除又有新增 */
console.log(react(["a", "b", "c", "d"], ["a", "d", "c", "g", "e", "l"])); // ["a", "d", "c", "g", "e", "l"];参考文章：https://react.iamkasong.com/diff/prepare.html
