React diff 算法

Author Avatar
Hongxu 6月 21, 2018

React diff 算法浅析

之前在学习 React 的时候了解到 React 的 diff 算法可以帮助我们实现最小化的 DOM 操作。

今天我们来看看 React 的 diff 算法的处理方式。

传统的 diff 算法

传统的 diff 算法通过循环递归对节点一次对比，效率很低，复杂度达到 O(n3), 其中 n 是树中节点的总数。这意味着如果要展示 1000 个节点，那么就要计算上十亿次。而真实的页面中节点的数量是不可知的。所以如果使用传统的 diff 算法代价太高了。

React 的 diff 算法。

传统 diff 算法的复杂度为 O(n3)，而 React 通过对于前端页面结构的理解，定制了特殊的策略，将复杂度转化成 O(n)。

diff 策略

Facebook 的工程师基于现实中前端开发的经验制定了以下3条策略

  1. 同级比较
  2. 同组件比较
  3. 子元素比较

1. 同级比较

对于两个 DOM tree 只比较同一层次的节点，忽略 DOM 中节点跨层级的移动操作。当发现节点已经不存在，则该节点及其子节点会被完全删除掉，不会用于进一步的比较。这样只需要对树进行一次遍历，便能完成整个 DOM 树的比较。

同级比较

Note: 保证稳定的 DOM 结构有利于提升性能，尽量不去修改标签类型。

2. 同组件比较

diff 算法当遇到组件变化时，不会比较两个组件的不同，因为这种比较几乎没有意义。

同组件比较

Note: 对于同一类型组件合理使用 shouldComponentUpdate()，应该避免结构相同类型不同的组件。

3. 子元素比较

当节点处于同一层级时，React diff 提供了三种节点操作，分别是 INSERT_MARKUP、MOVE_EXISTING、REMOVE_NODE。

  • INSERT_MARKUP，新的 component 类型不在老集合里， 即是全新的节点，需要对新节点执行插入操作。
  • MOVE_EXISTING，在老集合有新 component 类型，且 element 是可更新的类型就需要做移动操作，可以复用以前的 DOM 节点。
  • REMOVE_NODE，老 component 类型，在新集合里也有，但对应的 element 不同则不能直接复用和更新，需要执行删除操作，或者老 component 不在新集合里的，也需要执行删除操作。

通常情况下 diff 在比较集合 [A, B, C, D] 和 [D, A, B,C] 时，会按位置逐个对比，发现每个位置的元素都有更新，就把旧集合全部移除替换成新的集合。这种比较是不合理的，合理的方式是复用 A，B，C 而将末尾的 D 移动到集合最前面。

React对这一现象做出了一个高效的策略：允许开发者对同一层级的同组子节点添加唯一key值进行区分。

子元素比较

Note: 在开发过程中，同层级的节点添加唯一key值可以极大提升性能，尽量减少将最后一个节点移动到列表首部的操作，当节点达到一定的数量以后或者操作过于频繁，在一定程度上会影响React的渲染性能。

React 通过上面3种策略将原本 O(n3) 的算法复杂度降低到 O(n)

事件代理

把事件绑到 DOM 节点很慢，消耗内存。而 React 采用更好的技术称之为“事件代理”。React 走的更远，采用 W3C 兼容的事件系统。这意味着 IE8 的事件操作 Bugs 已经成为过去。所有的事件在不同浏览器中是一致的。
React 并不会真正的绑定事件到每一个具体的元素上，而是采用事件代理的模式：在根节点document上为每种事件添加唯一的 Listener，然后通过事件的 target 找到真实的触发元素。这样从触发元素到顶层节点之间的所有节点如果有绑定这个事件，React 都会触发对应的事件处理函数。

渲染（批量处理）

当在组件中调用了 setState, React 讲吧这个组件标记为 dirty，在时间循环结束后，React 会找到所有被标记的组件并统一渲染他们。而不是每次调用 setState 都去重新渲染。

批量渲染

子树渲染

当 setState 调用时，组件会重新 build 其子虚拟 DOM。如果你在根节点上调用 setState，那么整个应用都会重新渲染，所有的组件，即使它没有改变也会调用它的 render 方法。这听起来很低效，但实际中，它工作很好应为我们没有操作实际的 DOM。
首先，我们谈论的是显示用户界面。应为屏幕空间是有限的，通常我们只会同时显示几百到上千个 elements。Javascript 有足够快的业务逻辑管理整个界面。
另一个很重要的是，当你写 React 代码时，不要一出现变化就在根节点上调用 setState 方法。你应该在接收变化事件的组件或其上面的组件上调用 setState，你应该极少的在上层中调。这意味着变化只会在用户交互的地方。

子树渲染

有选择的渲染

我们可以通过下面的方法选择子树是否渲染：

boolean shouldComponentUpdate(object nextProps, object nextState)

通过判断先前组件和下一个组件的属性/状态，你能够告诉 React 这个组件是否需要重新渲染。当合适的处理这将会显著提高性能。
为了使用它，你必须能比较对象的差异，这里就牵扯到一些问题，如是否应该深度比较，如果深度比较，我么是否应该固定数据的结构，或是做深度拷贝。
而且你应该记住，这个函数总会被调用，所以你要确保自己写的函数的调用时间要比默认的启发式比较的时间少。

有选择的渲染

总结

  1. 通过diff策略，将算法从O(n^3)简化为O(n)
  2. 分层求异，对tree diff进行优化
  3. 分组件求异，相同类生成相似树形结构、不同类生成不同树形结构，对component diff进行优化
  4. 设置key，对element diff进行优化
  5. 尽量保持稳定的DOM结构、避免将最后一个节点移动到列表首部、避免节点数量过大或更新过于频繁