关于react.js:老生常谈React的diff算法原理面试版

第一次发文章 not only（尽管）版式可能有点烂 but also（然而）最初赋有手稿钻研 finally 看完他你有播种

diff 算法：对于 update 的组件，他会将以后组件与该组件在上次更新是对应的 Fiber 节点比拟，将比拟的后果生成新的 Fiber 节点。

! 为了避免概念混同，强调

一个 DOM 节点，在某一时刻最多会有 4 个节点和他相干。

- 1.current Fiber。如果该 DOM 节点已在页面中，current Fiber 代表该 DOM 节点对应的 Fiber 节点。- 2.workInProgress Fiber。如果该 DOM 节点将在本次更新中渲染到页面中，workInProgress Fiber 代表该 DOM 节点对应的 Fiber 节点。- 3.DOM 节点自身。- 4.JSX 对象。即 ClassComponent 的 render 办法的返回后果，或者 FunctionComponent 的调用后果，JSX 对象中蕴含形容 DOM 节点信息。

diff 算法的实质上是比照 1 和 4，生成 2。

Diff 的瓶颈以及 React 如何应答

 因为 diff 操作自身也会带来性能损耗，React 文档中提到，即便在最前沿的算法中
将前后两棵树齐全比对的算法的复杂程度为 O(n 3)，其中 n 是树中元素的数量。如果在 React 中应用了该算法，那么展现 1000 个元素所须要执行的计算量将在十亿的量级范畴。这个开销切实是太过昂扬。

所以为了升高算法复杂度，React 的 diff 会预设 3 个限度：

 1. 同级元素进行 Diff。如果一个 DOM 节点在前后两次更新中逾越了层级，那么 React 不会尝试复用他。2. 不同类型的元素会产生出不同的树。如果元素由 div 变为 p，React 会销毁 div 及其子孙节点，并新建 p 及其子孙节点。3. 者能够通过 key prop 来暗示哪些子元素在不同的渲染下能保持稳定。

那么咱们接下来看一下 Diff 是如何实现的

咱们能够从同级的节点数量将 Diff 分为两类：

 1. 当 newChild 类型为 object、number、string，代表同级只有一个节点
- 2. 当 newChild 类型为 Array，同级有多个节点 

单节点 diff

 以类型 Object 为例，会进入这个函数 reconcileSingleElement

 这个函数会做如下事件：

 让咱们看看第二步判断 DOM 节点是否能够复用是如何实现的。

参考 前端进阶面试题具体解答

从代码能够看出，React 通过先判断 key 是否雷同，如果 key 雷同则判断 type 是否雷同，只有都雷同时一个 DOM 节点能力复用。

这里有个细节须要关注下：

1. 当 child !== null 且 key 雷同且 type 不同时执行 deleteRemainingChildren 将 child 及其兄弟 fiber 都标记删除。2. 当 child !== null 且 key 不同时仅将 child 标记删除。

例子：以后页面有 3 个 li，咱们要全副删除，再插入一个 p。

因为本次更新时只有一个 p，属于繁多节点的 Diff，会走下面介绍的代码逻辑。

解释：

 在 reconcileSingleElement 中遍历之前的 3 个 fiber（对应的 DOM 为 3 个 li），寻找本次更新的 p 是否能够复用之前的 3 个 fiber 中某个的 DOM。当 key 雷同且 type 不同时，代表咱们曾经找到本次更新的 p 对应的上次的 fiber，然而 p 与 li 的 type 不同，不能复用。既然惟一的可能性曾经不能复用，则剩下的 fiber 都没有机会了，所以都须要标记删除。当 key 不同时只代表遍历到的该 fiber 不能被 p 复用，前面还有兄弟 fiber 还没有遍历到。所以仅仅标记该 fiber 删除。

练习题：

 习题 1: 未设置 key prop 默认 key = null;，所以更新前后 key 雷同，都为 null，然而更新前 type 为 div，更新后为 p，type 扭转则不能复用。习题 2: 更新前后 key 扭转，不须要再判断 type，不能复用。习题 3: 更新前后 key 没变，然而 type 扭转，不能复用。习题 4: 更新前后 key 与 type 都未扭转，能够复用。children 变动，DOM 的子元素须要更新。

多节点 diff

同级多个节点的 Diff，肯定属于上面 3 中状况的一种或多种。

• 状况 1：节点更新

• 状况 2：节点新增或缩小

• 状况 3：节点地位变动

 留神在这里 diff 算法无奈应用双指针优化
在咱们做数组相干的算法题时，常常应用双指针从数组头和尾同时遍历以提高效率，然而这里却不行。

 尽管本次更新的 JSX 对象 newChildren 为数组模式，然而和 newChildren 中每个组件进行比拟的是 current fiber
同级的 Fiber 节点是由 sibling 指针链接造成的单链表。即 newChildren[0] 与 fiber 比拟，newChildren[1] 与 fiber.sibling 比拟。

 所以无奈应用双指针优化。

基于以上起因，Diff 算法的整体逻辑会经验两轮遍历：

1. 第一轮遍历：解决更新的节点。2. 第二轮遍历：解决剩下的不属于更新的节点 

第一轮遍历：

第一轮遍历步骤如下：

let i = 0，遍历 newChildren，将 newChildren[i] 与 oldFiber 比拟，判断 DOM 节点是否可复用。如果可复用，i++，持续比拟 newChildren[i] 与 oldFiber.sibling，能够复用则持续遍历。如果不可复用，立刻跳出整个遍历，第一轮遍历完结。如果 newChildren 遍历完（即 i === newChildren.length - 1）或者 oldFiber 遍历完（即 oldFiber.sibling === null）跳出遍历，第一轮遍历完结。下面 3 跳出的遍历

此时 newChildren 没有遍历完，oldFiber 也没有遍历完。

上例子：

 前 2 个节点可复用，遍历到 key === 2 的节点发现 type 扭转，不可复用，跳出遍历。此时 oldFiber 剩下 key === 2 未遍历，newChildren 剩下 key === 2、key === 3 未遍历。下面 4 跳出的遍历

可能 newChildren 遍历完，或 oldFiber 遍历完，或他们同时遍历完。

上例子：

带着第一轮遍历的后果，咱们开始第二轮遍历。

第一轮遍历：（4 种状况）

- 1.newChildren 与 oldFiber 同时遍历完 

那就是最现实的状况：只有组件更新。此时 Diff 完结。

- 2.newChildren 没遍历完，oldFiber 遍历完

已有的 DOM 节点都复用了，这时还有新退出的节点，意味着本次更新有新节点插入
咱们只须要遍历剩下的 newChildren 为生成的 workInProgress fiber 顺次标记 Placement。

- 3.newChildren 遍历完，oldFiber 没遍历完

意味着本次更新比之前的节点数量少，有节点被删除了。所以须要遍历剩下的 oldFiber，顺次标记 Deletion。

- 4.newChildren 与 oldFiber 都没遍历完

这意味着有节点在这次更新中扭转了地位。扭转了地位就须要咱们解决挪动的节点

因为有节点扭转了地位，所以不能再用地位索引 i 比照前后的节点，那么如何能力将同一个节点在两次更新中对应上呢？咱们须要应用 key。为了疾速的找到 key 对应的 oldFiber，咱们将所有还未解决的 oldFiber 存入以 key 为 key，oldFiber 为 value 的 Map 中。

 接下来遍历残余的 newChildren，通过 newChildren[i].key 就能在 existingChildren 中找到 key 雷同的 oldFiber

标记节点是否挪动 

! 既然咱们的指标是寻找挪动的节点，那么咱们须要明确：节点是否挪动是以什么为参照物？

 咱们的参照物是：最初一个可复用的节点在 oldFiber 中的地位索引（用变量 lastPlacedIndex 示意）。

 因为本次更新中节点是按 newChildren 的顺序排列。在遍历 newChildren 过程中，每个遍历到的可复用节点肯定是以后遍历到的所有可复用节点中最靠右的那个
即肯定在 lastPlacedIndex 对应的可复用的节点在本次更新中地位的前面。那么咱们只须要比拟遍历到的可复用节点在上次更新时是否也在 lastPlacedIndex 对应的 oldFiber 前面
就能晓得两次更新中这两个节点的绝对地位扭转没有。咱们用变量 oldIndex 示意遍历到的可复用节点在 oldFiber 中的地位索引。如果 oldIndex < lastPlacedIndex，代表本次更新该节点须要向右挪动。lastPlacedIndex 初始为 0，每遍历一个可复用的节点，如果 oldFiber >= lastPlacedIndex，则 lastPlacedIndex = oldFiber。

上面通过两个 demo 来看一下 react 团队的 diff 算法精华

demo1

// 之前 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 节点被标记为挪动

demo2

// 之前 abcd

// 之后 dabc

=== 第一轮遍历开始 ===

d（之后）vs a（之前）key 扭转，不能复用，跳出遍历 

=== 第一轮遍历完结 ===

=== 第二轮遍历开始 ===

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 节点须要向右挪动 

=== 第二轮遍历完结 ===

! 能够看到，咱们认为从 abcd 变为 dabc，只须要将 d 挪动到后面。 ! 但实际上 React 放弃 d 不变，将 abc 别离挪动到了 d 的前面。

用张陈词滥调的图