React中Diff算法又称为调和算法，对应函数名为reconcileChildren，它的主要作用是标记更新过程中那些元素发生了变化，这些变化包括新增、移动、删除。过程发生在beginWork阶段，只有非初次渲染才会Diff。
以前看过一些文章将Diff算法表述为两颗Fiber树的比较，这是不正确的，实际的Diff过程是一组现有的Fiber节点和新的由JSX生成的ReactElement的比较，然后生成新的Fiber节点的过程，这个过程中也会尝试复用现有Fiber节点。
节点Diff又分为两种：
-
单节点Diff ——
Element、Portal、string、number。 -
多节点Diff ——
Array、Iterator。
以下React版本为17.0.1，代码文件为ReactChildFiber.old.js。
单节点Diff
单节点Diff比较简单，只有key相同并且type相同的情况才会尝试复用节点，否则会返回新的节点。
单节点大部分情况下我们都不会去赋值key，所以它们默认为null，也是相同的。
reconcileSingleElement
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
// 单节点比较function reconcileSingleElement( returnFiber: Fiber, currentFirstChild: Fiber | null, element: ReactElement, lanes: Lanes,): Fiber { // 当前新的reactElement的key const key = element.key; // 当前的child fiber节点 let child = currentFirstChild; while (child !== null) { // key相同的情况才diff if (child.key === key) { switch (child.tag) { // ... default: { // 当前fiber和reactElement的type相同时 if (child.elementType === element.type) { // 删除同级的其他节点 deleteRemainingChildren(returnFiber, child.sibling); // 复用当前child fiber const existing = useFiber(child, element.props); existing.ref = coerceRef(returnFiber, child, element); existing.return = returnFiber; // 返回可复用的child fiber return existing; } break; } } // 不匹配删除节点 deleteRemainingChildren(returnFiber, child); break; } else { // key不同直接删除节点 deleteChild(returnFiber, child); } child = child.sibling; } // 新的Fiber节点 const created = createFiberFromElement(element, returnFiber.mode, lanes); created.ref = coerceRef(returnFiber, currentFirstChild, element); created.return = returnFiber; return created;} |
多节点Diff
源码中将多节点分为了数组节点和可迭代节点。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
if (isArray(newChild)) { return reconcileChildrenArray( returnFiber, currentFirstChild, newChild, lanes, );}if (getIteratorFn(newChild)) { return reconcileChildrenIterator( returnFiber, currentFirstChild, newChild, lanes, );} |
对应的Diff函数分别是reconcileChildrenArray和reconcileChildrenIterator。它们的核心Diff逻辑是相同的，所以只分析数组节点的Diff —— reconcileChildrenArray函数。
这一段的代码比较长，但逻辑很清晰，从分割线分为两轮遍历。
- 第一轮遍历的是顺序相同且key也相同的节点，这些节点需要做更新操作。
- 第二轮遍历的是顺序不同，可能key也不同的节点，这些节点需要做新增、移动或删除操作。
第一轮遍历只针对key和顺序都相同的情况，这些key对应的节点位置没有发生改变，只需要做更新操作，一旦遍历遇到key不同的情况就需要跳出循环。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
// 旧节点<li key="0"/><li key="1"/><li key="2"/>// 新节点<li key="0"/><li key="1"/><li key="5"/>// key="5"不同，跳出遍历// 第一轮遍历的节点<li key="0"/><li key="1"/>// <li key="2"/>和<li key="5"/>留在第二轮遍历比较。 |
在第一轮遍历完后也分为两种情况。
- 新节点数量少于旧节点数量，这时候需要把多余的旧节点标记为删除。
- 新节点数量大于旧节点数量，这时候需要把多余的新节点标记为新增。
第二轮遍历针对key不同或顺序不同的情况，可能情况如下：
|
1
2
3
4
5
6
7
8
9
10
|
// 旧节点<li key="0"/><li key="1"/><li key="2"/>// 新节点<li key="0"/><li key="2"/><li key="1"/>// 第二轮遍历对比<li key="2"/>、<li key="1"/>这两个节点 |
第二轮的遍历会稍微复杂一点，后文在细讲。
详细的代码如下。
reconcileChildrenArray
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
|
function reconcileChildrenArray( returnFiber: Fiber, currentFirstChild: Fiber | null, newChildren: Array<*>, lanes: Lanes,): Fiber | null { // 函数返回的Fiber节点 let resultingFirstChild: Fiber | null = null; let previousNewFiber: Fiber | null = null; // oldFiber为链表 let oldFiber = currentFirstChild; // 用来判断节点是否移动 let lastPlacedIndex = 0; let newIdx = 0; let nextOldFiber = null; // 第一轮遍历，只遍历key相同的节点 for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) { if (oldFiber.index > newIdx) { nextOldFiber = oldFiber; oldFiber = null; } else { // 每次循环旧的fiber节点都会指向兄弟元素也就是下次循环的fiber节点 nextOldFiber = oldFiber.sibling; } // key相同返回fiber节点，key不同返回null // 如果type相同复用节点，不同返回新节点 const newFiber = updateSlot( returnFiber, oldFiber, newChildren[newIdx], lanes, ); // newFiber为null表示key不同，跳出循环 if (newFiber === null) { if (oldFiber === null) { oldFiber = nextOldFiber; } break; } // newFiber.alternate为null就是新节点，说明type不同创建了新fiber节点 if (oldFiber && newFiber.alternate === null) { // 需要把oldFiber标记删除 deleteChild(returnFiber, oldFiber); } // 放置节点,更新lastPlacedIndex lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx); // 组成新fiber节点链 if (previousNewFiber === null) { resultingFirstChild = newFiber; } else { previousNewFiber.sibling = newFiber; } previousNewFiber = newFiber; oldFiber = nextOldFiber; } /* 第一轮遍历完后新节点数量少于旧节点数量 newChildren已经遍历完，删除掉剩下的fiber节点，可能情况如下 ⬇️ 以前 <li key="0"/> <li key="1"/> <li key="2"/> 新的 <li key="0"/> <li key="1"/> 就会把<li key="2"/>删除 */ if (newIdx === newChildren.length) { deleteRemainingChildren(returnFiber, oldFiber); return resultingFirstChild; } /* 第一轮遍历完新节点数量大于旧节点数量 oldFiber已经遍历完，可能情况如下 ⬇️ 以前 <li key="0"/> <li key="1"/> 新的 <li key="0"/> <li key="1"/> <li key="2"/> 就会添加新的<li key="2"/>，这一段是新节点的插入逻辑 */ if (oldFiber === null) { for (; newIdx < newChildren.length; newIdx++) { const newFiber = createChild(returnFiber, newChildren[newIdx], lanes); if (newFiber === null) { continue; } lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx); // 组成新fiber节点链 if (previousNewFiber === null) { resultingFirstChild = newFiber; } else { previousNewFiber.sibling = newFiber; } previousNewFiber = newFiber; } return resultingFirstChild; } // --------------------------------------------------------------------- // 用剩余的oldFiber创建一个key->fiber节点的Map，方便用key来获取对应的旧fiber节点 const existingChildren = mapRemainingChildren(returnFiber, oldFiber); // 第二轮遍历，继续遍历剩余的节点，这些节点可能是需要移动或者删除的 for (; newIdx < newChildren.length; newIdx++) { // 从map中获取对应对应key的旧节点，返回更新后的新节点 const newFiber = updateFromMap( existingChildren, returnFiber, newIdx, newChildren[newIdx], lanes, ); if (newFiber !== null) { // 复用的新节点，从map里删除老的节点，对应的情况可能是位置的改变 if (newFiber.alternate !== null) { // 复用的节点要移除map，因为map里剩余的节点都会被标记Deletion删除 existingChildren.delete( newFiber.key === null ? newIdx : newFiber.key, ); } // 放置节点同时节点判断是否移动 lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx); if (previousNewFiber === null) { resultingFirstChild = newFiber; } else { previousNewFiber.sibling = newFiber; } previousNewFiber = newFiber; } } // 删除剩下的无用节点 existingChildren.forEach(child => deleteChild(returnFiber, child)); return resultingFirstChild;} |
第一轮遍历比较好理解，这里再细分析一下第二轮遍历，因为第二轮会出现复用是否需要移动的问题。
第二轮遍历首先遍历剩余的oldFiber，组成一个key -> 旧fiber节点的Map，这用可以通过key来快速的获取旧节点。
接下来的遍历依然是使用的新节点为遍历对象，每次遍历使用新节点的key从Map中取出旧节点来对比是否能复用，对应的函数为updateFromMap。
如果节点存在alternate属性，则是复用的节点，这时候需要将它从existingChildren里移除，后续会把第二轮遍历完后依然存在在existingChildren里的节点标记为删除。
如何判断节点移动了？
这里存在一个变量lastPlacedIndex用来判断节点是否移动，每次将节点添加到新的Fiber链表中，都会更新这个值。
当复用的节点oldIndex小于lastPlacedIndex时，则为移动，如果不需要移动，则会将lastPlacedIndex更新为较大的oldIndex，下一个节点会以新值判断，代码如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
function placeChild( newFiber: Fiber, lastPlacedIndex: number, newIndex: number,): number { newFiber.index = newIndex; const current = newFiber.alternate; if (current !== null) { const oldIndex = current.index; if (oldIndex < lastPlacedIndex) { // 节点移动 newFiber.flags = Placement; return lastPlacedIndex; } else { // 节点位置无变化 return oldIndex; } } else { // 插入的新节点 newFiber.flags = Placement; return lastPlacedIndex; }} |
举个例子：
|
1
2
3
4
|
// 旧abcd// 新acbd |
abcd均为key值。
第一轮遍历后剩下的需要对比节点:
|
1
2
3
4
|
// 旧bcd// 新cbd |
a节点在第一轮已经复用，并且调用过placeChild，这时lastPlacedIndex值为0。
进入第二轮遍历，依然是以新节点为遍历对象。
|
1
2
3
|
c => 在旧节点中存在，可复用，它的index在旧节点中为2，2 > lastPlacedIndex(0)，不需要移动,将lastPlacedIndex赋值为2。b => 在旧节点中存在，可复用，它的index在旧节点中为1，1 < lastPlacedIndex(2)，需要移动，标记Placement。d => 在旧节点中存在，可复用，它的index在旧节点中为3，3 > lastPlacedIndex(2)，不需要移动。 |
由这个例子可以看出，React中将右侧不需要移动的节点作为参照，将需要移动的节点都是统一从左向右移动的。
在后续Layout阶段会将这里标记了Placement的节点做insertBefore操作。
总结
React中的Diff算法核心代码不算很长，但是却引入key巧妙的将复杂度由O(n3 )变为了O(n)。
码农内卷太严重，所以不得不学习源码了。
以上就是react diff算法源码解析的详细内容，更多关于react diff算法的资料请关注服务器之家其它相关文章！
原文链接：https://juejin.cn/post/6949092569275957256
