diff 算法
#
diff 算法在某一时间节点调用 React 的 render()
方法,会创建一棵由 React 元素组成的树。在下一次 state
或 props
更新时,相同的 render()
方法会返回一棵不同的树。React 需要基于这两棵树之间的差别来判断如何高效的更新 UI
,以保证当前 UI
与最新的树保持同步。
此算法有一些通用的解决方案,即生成将一棵树转换成另一棵树的最小操作次数。然而,即使使用最优的算法,该算法的复杂程度仍为 O(n3)
,其中 n
是树中元素的数量。
如果在 React
中使用该算法,那么展示 1000
个元素则需要 10
亿次的比较。这个开销实在是太过高昂。于是 React
在以下两个假设的基础之上提出了一套 O(n)
的启发式算法:
- 两个不同类型的元素会产生出不同的树;
- 开发者可以通过设置
key
属性,来告知渲染哪些子元素在不同的渲染下可以保存不变;
正是基于此设计概念,所以 React diff
算法只对同层进行比较,故将复杂度降低到 O(n)
而其体现形式即如下:
- 对比不同类型的元素(当根节点为不同类型的元素时,
React
会拆卸原有的树并且建立起新的树) - 对比同一类型的元素(仅对比更新有改变的属性)
- 对比同一类型的组件元素(组件实例会保持不变,因此可以在不同的渲染时保持
state
一致) - 对子节点进行递归(默认情况下,
React
会同时遍历两个子元素的列表;当产生差异时,生成一个mutation
)
对子节点的递归涉及到我们为什么要为子元素设置 key ?即帮助 React 使用 key 来匹配原有树上的子元素以及最新树上的子元素。至于为什么不用下标作为 key ,我想读者加以思考便会知道
由于 React
依赖启发式算法,因此当以下假设没有得到满足,性能会有所损耗。
- 该算法不会尝试匹配不同组件类型的子树。如果你发现你在两种不同类型的组件中切换,但输出非常相似的内容,建议把它们改成同一类型。在实践中,我们没有遇到这类问题。
Key
应该具有稳定,可预测,以及列表内唯一的特质。不稳定的key
(比如通过Math.random()
生成的)会导致许多组件实例和DOM
节点被不必要地重新创建,这可能导致性能下降和子组件中的状态丢失。
更多设计思想与实现细节请查看 协调 [Diff 算法](