高级前端
react
【Q403】React 中的 dom diff 算法如何从 O(n3) 优化到 O(n) 的

React 中的 dom diff 算法如何从 O(n3) 优化到 O(n) 的

Issue 欢迎在 Gtihub Issue 中回答此问题: Issue 410 (opens in a new tab)

Author 回答者: shfshanyue (opens in a new tab)

参考官方文档: 协调的设计动机 (opens in a new tab)

此算法有一些通用的解决方案,即生成将一棵树转换成另一棵树的最小操作次数。然而,即使使用最优的算法,该算法的复杂程度仍为 O(n 3 ),其中 n 是树中元素的数量。

如果在 React 中使用该算法,那么展示 1000 个元素则需要 10 亿次的比较。这个开销实在是太过高昂。于是 React 在以下两个假设的基础之上提出了一套 O(n) 的启发式算法:

  1. 两个不同类型的元素会产生出不同的树;
  2. 开发者可以通过设置 key 属性,来告知渲染哪些子元素在不同的渲染下可以保存不变;

在实践中,我们发现以上假设在几乎所有实用的场景下都成立。