关于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中状况的一种或多种。

参考：前端react面试题具体解答

• 状况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的前面。

用张陈词滥调的图

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中状况的一种或多种。

参考：前端react面试题具体解答

• 状况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的前面。

用张陈词滥调的图