React diff算法分析和理解

  距离上次研究 React 工作原理以及有一段时间了,最近又在忙着看小程序方面的东西.忙里偷闲来继续回顾下以前看的 React diff 算法方面的知识.

1. 传统的 diff 算法

  传统的 diff 算法的通过循环递归来比对节点的,这里时间复杂度是 O(n^2) 于此同时还需要对 diff 的节点做修改的操作这里的话是 O(n)的时间复杂度,结合到一起就变成了 O(n^3)的时间复杂度.这样的时间复杂度是不能容忍的.因为在你浏览页面的时候如果 1s 内呈现不了内容人就会觉得这个页面卡顿.而 React 中的 diff 算法却能做到只有 O(n)的时间复杂度.

2. React 的 diff 算法

  React 的 diff 策略有这3种,附录有这小节涉及的源码

Tree diff

  DOM 节点跨层级的移动操作特别少, React 会将这种行为忽略,只对 Dom 树同一层级的节点进行比较,也就同一个父节点下的所有子节点,当发现节点已经不存在时,则该节点及其子节点会被完全删除掉,不会用于进一步的比较.这个策略就保证了只需要对树进行一次遍历.如下图3-1所示的新旧Dom树,React这个策略导致的行为是:在遍历第一层的时候不进行操作, 第二层的时候 删除A节点, 第三层的时候 创建 A节点及其子节点. (Delete A => Create A -> create B -> create C)

图3-1

Component diff

  拥有相同类的两个组件将会生成相似的 Dom 结构,拥有不同类的两个组件将会生成不同的 Dom 结构,所以如果是不同类型的两个组件 React 会直接重建新的组件, 对于同类型的组件我们可以使用 shouldComponentUpdate() 来手动判断是否需要进行 diff 运算,如果不进行 diff 运行这显然是可以改善性能的.如下图3-2所示的新旧Dom树,在基于Tree diff 后React这个策略导致的行为是: 发现新旧Dom 树的 D G节点不是同类型的组件,那么就直接删除D节点然后新建G节点及其子节点.(Delete D => Create G -> create E -> create F)

图3-2

Element diff

  element diff 提供了3种节点操作:插入,移动和删除.对比新老元素集合如果新集合存在老集合中没用的元素那么久插入,如果有并且是可以复用的,那么就移动(这期间会有一个if (child._mountIndex < lastIndex)的策略决定是否移动元素位置),剩下的在老集合中存在而新集合没用的元素就删除.

  如图3-3,老集合中包含节点: A,B,C,D,更新后的新集合中包含节点: B,A,D,C,此时新老集合进行 diff 差异化对比,发现 B != A,则创建并插入 B 至新集合,删除老集合 A.以此类推,创建并插入 A,D 和 C,删除 B,C 和 D.这类操作烦琐冗余,因为这些都是相同的节点,但由于位置发生变化,导致需要进行繁杂低效的删除、创建操作,其实只要对这些节点进行位置移动即可.

图3-3

  所以针对图3-3这个情况,React key的作用就体现出来了.加入key 这个策略后 React首先对新集合的节点进行循环遍历,for (name in nextChildren),通过唯一 key 可以判断新老集合中是否存在相同的节点,if (prevChild === nextChild),如果存在相同节点,则进行移动操作,但在移动前需要将当前节点在老集合中的位置与 lastIndex 进行比较,if (child._mountIndex < lastIndex),则进行节点移动操作,否则不执行该操作.这是一种顺序优化手段,lastIndex 一直在更新,表示访问过的节点在老集合中最右的位置（即最大的位置）,如果新集合中当前访问的节点比 lastIndex 大,说明当前访问节点在老集合中就比上一个节点位置靠后,则该节点不会影响其他节点的位置,因此不用添加到差异队列中,即不执行移动操作,只有当访问的节点比 lastIndex 小时,才需要进行移动操作.

  针对如图3-4的新旧Dom集合,React 在key 策略下行为如下:

• 从新集合中取得第一个元素B,然后判断旧集合中是否存在相同节点 B,此时发现存在节点 B,接着通过对比节点位置判断是否进行移动操作.B 在旧集合中的位置 B._mountIndex = 1,此时 lastIndex = 0,不满足 child._mountIndex: 1 < lastIndex: 0 的条件,因此不对 B 进行移动操作.更新 lastIndex = Math.max(prevChild._mountIndex: 1, lastIndex: 0), 其中prevChild._mountIndex: 1 表示B在旧集合中的位置,则lastIndex = 1,并将B的位置更新为新集合中的位置 prevChild._mountIndex = nextIndex: 0,此时新集合中 B._mountIndex = 0, nextIndex++(nextIndex = 1)接着进入下一个节点的判断

• 拿到新集合下一个元素A,发现新老集合都存在节点 A,接着对比节点位置判断是否进行移动操作.A 在旧集合中的位置 A._mountIndex = 0,此时 lastIndex = 1,满足 child._mountIndex: 0 < lastIndex: 1的条件,因此对 A 进行移动操作enqueueMove(this, child._mountIndex, toIndex),看附录源码可以知道 toIndex 其实就是 nextIndex,其表示 A 需要移动到的新集合中的位置.更新 lastIndex = Math.max(prevChild._mountIndex: , lastIndex),则这个时候 lastIndex = 1,并将 A 的位置更新为新集合中的位置 prevChild._mountIndex = nextIndex: 1,此时新集合中 A._mountIndex = 1,nextIndex++(nextIndex = 2) 进入下一个节点的判断

• 拿到下一个元素D,新老集合都存在,D 在旧集合中的位置 D._mountIndex = 3,此时 lastIndex = 1,不满足 child._mountIndex: 2 < lastIndex: 1的条件,因此不对 D 进行移动操作(… 接下来的动作和B节点操作类似,更新一些变量的值,最终 lastIndex = 3, prevChild._mountIndex = nextIndex: 2, D._mountIndex = 2,nextIndex++(nextIndex = 3))

• 拿到元素C,新老集合都存在 C,C 在旧集合中的位置 C._mountIndex = 2,此时 lastIndex = 3,不满足 child._mountIndex: 2 < lastIndex: 3的条件,对 C 进行移动操作(… 接下来的动作和A节点操作类似,更新一些变量的值,最终 lastIndex = 3, prevChild._mountIndex = nextIndex: 3, C._mountIndex = 3,nextIndex++(nextIndex = 4))

图3-4

  针对如图3-5的新旧Dom集合,React 在key 策略下行为如下:

• 拿到元素B,其在旧集合中的位置 B._mountIndex = 1,此时 lastIndex = 0,不满足 child._mountIndex: 1 < lastIndex: 0 的条件,因此不对 B 进行移动操作.最终 lastIndex = 1,B._mountIndex = 0,nextIndex++(nextIndex = 1)

• 拿到元素E,发现老集合不存在元素E,于是插入节点E, 然后nextIndex++(nextIndex = 2), lastIndex 没有变化还是 1

• 拿到元素C,其在旧集合中的位置 C._mountIndex = 2,不满足 child._mountIndex: 2 < lastIndex: 1 的条件,所以不移动, 最终 lastIndex = 2, prevChild._mountIndex = nextIndex: 2, C._mountIndex = 3,nextIndex++(nextIndex = 3)

• 拿到元素A,其在旧集合中的位置 A._mountIndex = 0,满足 child._mountIndex: 0 < lastIndex: 2 的条件,所以移动A节点, 最终 lastIndex = 2, prevChild._mountIndex = nextIndex: 3, A._mountIndex = 3,nextIndex++(nextIndex = 4)

• 当完成新集合中所有节点的差异化对比后,还需要对旧集合进行循环遍历,判断是否存在新集合中没有但旧集合中仍存在的节点,此时发现存在这样的节点 D,因此删除节点 D

图3-5

  当然,diff 还存在些许不足与待优化的地方针对.如图3-6的新旧Dom集合,若新集合的节点更新为 D、A、B、C,与旧集合相比只有 D 节点移动,而 A、B、C 仍然保持原有的顺序,理论上 diff 应该只需对 D 执行移动操作,然而由于 D 在旧集合中的位置是最大的,导致其他节点的 _mountIndex < lastIndex,造成 D 没有执行移动操作,而是 A、B、C 全部移动到 D 节点后面的现象

图3-6

Patch 操作

  diff 操作都还是在 Virtual DOM 中进行的.然而浏览器中并未能显示出更新的数据, 所以就需要Pathch 操作来把tree diff 计算出来的 DOM差异队列更新到真实的 DOM 节点上,最终让浏览器能够渲染出更新后的数据.这主要是通过遍历差异队列实现的.遍历差异队列时,通过更新类型(插入,删除,移动)进行相应的操作.React之所以可以直接依次插入节点是因为在就是在 diff 阶段添加差异节点到差异队列时,本身就是有序添加.也就是说,移动节点和新增节点在队列里的顺序就是最终真实DOM的顺序,因此可以直接依次根据 index 去插入节点.而且,React 并不是计算出一个差异就去执行一次 Patch,而是计算出全部差异并放入差异队列后,再一次性地去执行 Patch 方法完成真实DOM 的更新.

3.我的思考

  关于第二节部分下划线的那段话一开始我不是很理解.为什么要加一个if (child._mountIndex < lastIndex)条件来判断是否移动节点呢?加上这个条件是一种顺序优化手段,也就是说这是一种策略,那么是不是可以有别的策略也能达到这个效果?所以目前我想了一个看起来比较简单的办法来判断是否移动元素位置,就是拿到老元素在新集合中的索引位置,然后直接交换元素在老集合中的位置.

针对图3-4 这个情况来说([A, B, C, D] => [B, A, D, C])如果按我想的办法,行为是这样的:

• 对于新集合元素B,新集合中的索引是0,交换元素位置老集合变化得到[B, A, C, D]
• 对于新集合元素A,当前新老集合中的索引都是1,无变化
• 对于新集合元素D,新集合中的索引是2,于是移动D的位置得到,交换元素位置老集合变化得到[B, A, D, C]
• 对于新集合元素C,当前新老集合中的索引都是3,无变化

针对图3-5 这个情况来说([A, B, C, D] => [B, E, C, A])行为是这样的:

• 对于新集合元素B,新集合中的索引是0,交换元素位置老集合变化得到[B, A, C, D]
• 对于新集合元素E,老集合无,新集合中索引是1,插入元素老集合变化得到[B, E, A, C, D]
• 对于新集合元素C,新集合中的索引是2,交换元素位置老集合变化得到[B, E, C, A, D]
• 对于新集合元素A,当前新老集合中的索引都是3,无变化
• 对于老集合元素D,新集合中不存在,删除,老集合变化得到[B, E, C, A]

针对图3-6 这个情况来说([A, B, C, D] => [D, A, B, C])行为是这样的:

• 对于新集合元素D,新集合中的索引是0,交换元素老集合变化得到[D, B, C, A]
• 对于新集合元素A,新集合中索引是1,交换元素老集合变化得到[D, A, C, B]
• 对于新集合元素B,新集合中索引是2,交换元素老集合变化得到[D, A, B, C]
• 对于新集合元素C,当前新老集合中的索引都是3,无变化

再考虑一种删除和插入都同时存在的情况这个情况来说([A, B, C, D] => [A, E, D, C])行为是这样的:

• 对于新集合元素A,当前新老集合中的索引都是0,无变化
• 对于新集合元素E,新集合中索引是1,插入元素,老集合变化得到[A, E, B, C, D]
• 对于新集合元素D,新集合中索引是2,交换元素老集合变化得到[A, E, D, C, B]
• 对于新集合元素C,当前新老集合中的索引都是3,无变化
• 对于老集合元素B,新集合中不存在,删除,老集合变化得到[A, E, D, C]

  所以目前看起来我的这个策略看起来确是可行的.不过相信React的开发人员肯定比我聪明,我这个策略一定有比不上原策略的地方.比如这个情况[C, A, B, D] => [A, B, C, D]

原策略:

• 拿到元素A,其在旧集合中的位置 A._mountIndex = 1,此时 lastIndex = 0,不满足 child._mountIndex: 1 < lastIndex: 0 的条件,因此不对 A 进行移动操作.最终 lastIndex = 1, A._mountIndex = 0,nextIndex++(nextIndex = 1)

• 拿到元素B,其在旧集合中的位置 B._mountIndex = 2,此时 lastIndex = 1,不满足 child._mountIndex: 2 < lastIndex: 1 的条件,因此不对 B 进行移动操作.最终 lastIndex = 2, B._mountIndex = 1,nextIndex++(nextIndex = 2)

• 拿到元素C,其在旧集合中的位置 C._mountIndex = 0,此时 lastIndex = 2,满足 child._mountIndex: 0 < lastIndex: 2 的条件,所以移动C, 最终 lastIndex = 2, prevChild._mountIndex = nextIndex: 2, C._mountIndex = 2,nextIndex++(nextIndex = 3)

• 拿到元素D,其在旧集合中的位置 D._mountIndex = 3,此时 lastIndex = 2,不满足 child._mountIndex: 3 < lastIndex: 2 的条件,,因此不对 D 进行移动操作.最终 lastIndex = 3, D._mountIndex = 3,nextIndex++(nextIndex = 4)

我的策略:

• 对于新集合元素A,新集合中的索引是0,老集合变化得到[A, C, B, D]
• 对于新集合元素B,新集合中索引是1,老集合变化得到[A, B, C, D]
• 对于新集合元素C,当前新老集合中的索引都是2,无变化
• 对于新集合元素D,当前新老集合中的索引都是3,无变化

  总体来看,原策略只移动了C这1个节点.而我的策略移动了2个节点,可以说优于我的策略的.所以看起来是因为React的策略可以保证不改变当前节点与上次处理的节点的相对位置(新旧集合中A, B都是连续的),而我的策略就不能保证这点,所以导致最终需要多移动一次.而且我的策略也并没有解决3-6中的极端情况.

4.为什么不推荐用数组的index 作为Key

  我们或许都有写过和下面这段代码类型的代码,就是用数组的index作用元素的Key.这样的代码会产生什么问题呢?举个例子: 我们有一个下拉框,下拉选项有4个选项 A, B, C, D.我们首先选中了C,然后删掉了B, 那么这个时候预期状态是不是还是应该还是选中C.但是实际上效果是浏览器会重新渲染然后你看到的就是选中了D.

1
2
3
4
5
6
7
8
9
10
11
12

 <ul>
    {
      list.map((item, index) => (
        <li
          key={index}
          onClick={() => this.deleteThisItem(index)}
        >
          {item}
        </li>
      ))
    }
  </ul>

  这是因为一开始 A,B,C,D(对应的key 为 0, 1, 2, 3) 我们删掉了B,新的dom 节点就变成了 A,C,D (对于的key 为0, 1, 2) 发现了没, 两次的key = 2的元素分别是 C 和 D.最终React因为认为key = 2的节点依然存在,重新渲染后依然选中的是key = 2的元素

  我们不妨根据Element diff中描述的策略diff分析下这样的操作diff 算法是怎么做的: 首先新节点A 发现旧的有且key 相同,不操作; 然后拿到C(key = 1)发现旧的中key = 1的文本内容是B,这个时候文本内容就被被替换成C;接着拿到D发现旧的中key = 1的文本内容是C被替换成D;在遍历一遍旧集合,发现D是多余的,删掉.所以我们其实要删掉的B结果最终其实会把key = 3的D删掉, 在这个情况下只有A 没有被重新渲染.

  方便理解图3-7可视化的描述了上面这个代码块的执行过程.

图3-7

  图3-8 可视化的描述了如果我们用唯一的标识来设置key的执行过程

1
2
3
4
5
6
7
8
9
10
11
12
13

// 用唯一的标识来设置key
 <ul>
    {
      list.map((item) => (
        <li
          key={item}
          onClick={() => this.deleteThisItem(item)}
        >
          {item}
        </li>
      ))
    }
  </ul>

图3-8

  当然我们可以用别的办法来设置唯一的key, 设置一个全局变量,采用类似于数据库自增主键的策略,只增不减.或者使用第三方库(shortid)生成一个唯一的值.

5.Ref

1. «深入React技术栈» 第三章
2. 互联网文章
3. 互联网文章

6.附录

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

function makeInsertMarkup(markup, afterNode, toIndex) {
  return {
    type: ReactMultiChildUpdateTypes.INSERT_MARKUP,
    content: markup,
    fromIndex: null,
    fromNode: null,
    toIndex: toIndex,
    afterNode: afterNode,
  };
}
function makeMove(child, afterNode, toIndex) {
  return {
    type: ReactMultiChildUpdateTypes.MOVE_EXISTING,
    content: null,
    fromIndex: child._mountIndex,
    fromNode: ReactReconciler.getNativeNode(child),
    toIndex: toIndex,
    afterNode: afterNode,
  };
}
function makeRemove(child, node) {
  return {
    type: ReactMultiChildUpdateTypes.REMOVE_NODE,
    content: null,
    fromIndex: child._mountIndex, 
    fromNode: node,
    toIndex: null,
    afterNode: null,
  };
} 

// 处理队列的更新
function processQueue(inst, updateQueue) {
  ReactComponentEnvironment.processChildrenUpdates(inst, updateQueue);
}

// 移动节点
moveChild: function(child, afterNode, toIndex, lastIndex) {
  // 如果子节点的 index 小于 lastIndex,则移动该节点
  if (child._mountIndex < lastIndex) {
    return makeMove(child, afterNode, toIndex);
  }
}

// 创建节点
createChild: function(child, afterNode, mountImage) {
  return makeInsertMarkup(mountImage, afterNode, child._mountIndex);
}

// 删除节点
removeChild: function(child, node) {
  return makeRemove(child, node);
}

// 卸载已经渲染的子节点
_unmountChild: function(child, node) {
  var update = this.removeChild(child, node);
  child._mountIndex = null;
  return update;
}

// 通过提供的名称实例化子节点
_mountChildAtIndex: function(child, afterNode, index, transaction, context) {
  var mountImage = ReactReconciler.mountComponent(child, transaction, this, this._nativeContainerInfo,context);
  child._mountIndex = index;
  return this.createChild(child, afterNode, mountImage);
}

_updateChildren: function(nextNestedChildrenElements, transaction, context) {
  var prevChildren = this._renderedChildren;
  var removedNodes = {};
  var nextChildren = this._reconcilerUpdateChildren(prevChildren, nextNestedChildrenElements,removedNodes, transaction, context);
  // 如果不存在 prevChildren 和 nextChildren,则不做 diff 处理
  if (!nextChildren && !prevChildren) {
    return;
  }
  var updates = null;
  var name;
  // lastIndex 是 prevChildren 中最后的索引,nextIndex 是 nextChildren 中每个节点的索引
  var lastIndex = 0;
  var nextIndex = 0;
  var lastPlacedNode = null;

  for (name in nextChildren) {
    if (!nextChildren.hasOwnProperty(name)) {
      continue;
    }
    var prevChild = prevChildren && prevChildren[name];
    var nextChild = nextChildren[name];
    // prevChildren 老节点, nextChildren 新节点
    if (prevChild === nextChild) {
      // 移动节点
      updates = enqueue(updates, this.moveChild(prevChild, lastPlacedNode, nextIndex, lastIndex));
      lastIndex = Math.max(prevChild._mountIndex, lastIndex);
      prevChild._mountIndex = nextIndex;
    } else {
      if (prevChild) {
        lastIndex = Math.max(prevChild._mountIndex, lastIndex);
        // 通过遍历 removedNodes 删除子节点 prevChild
      }
      // 初始化并创建节点
      updates = enqueue(updates, this._mountChildAtIndex(nextChild, lastPlacedNode, nextIndex, transaction, context));
    }
    nextIndex++;
    lastPlacedNode = ReactReconciler.getNativeNode(nextChild);
  } 
  // 如果父节点不存在,则将其子节点全部移除
  for (name in removedNodes) {
    if (removedNodes.hasOwnProperty(name)) {
      updates = enqueue(updates, this._unmountChild(prevChildren[name], removedNodes[name]));
    }
  }
  // 如果存在更新,则处理更新队列
  if (updates) {
    processQueue(this, updates);
  }
    this._renderedChildren = nextChildren;
}

function enqueue(queue, update) {
  // 如果有更新,将其存入 queue
  if (update) { 
    queue = queue || [];
    queue.push(update);
  }
  return queue;
}