React中最神奇的部分莫过于虚拟DOM，以及其高效的Diff算法

　　React中最神奇的部分莫过于虚拟DOM，以及其高效的Diff算法

　　React 最神奇的部分是虚拟 DOM 及其高效的 Diff 算法。这使我们可以随时“刷新”整个页面而不必担心性能问题。虚拟 DOM 确保仅实际更改界面上的实际 DOM 操作。 React 在这部分已经足够透明了。在实际开发中，我们基本不需要关心虚拟 DOM 是如何工作的。然而，作为有态度的程序员，我们总是对技术背后的原理感到好奇。了解其运行机制不仅有助于更好地理解 React 组件的生命周期，而且对于进一步优化 React 程序也有很大帮助。

　　什么是 DOM Diff 算法

　　Web 界面由 DOM 树组成。当它的某一部分发生变化时，实际上是相应的DOM节点发生了变化。在 React 中，构建 UI 界面的想法是当前状态决定界面。前后两个状态对应两组接口，然后React比较两组接口的差异，这需要DOM树的Diff算法分析。

　　给定任意两棵树，找出最少的转换步骤。但是标准的Diff算法复杂度需要O(n^3)，显然不能满足性能要求。要达到每次整体刷新界面的目标，必须对算法进行优化。这看起来很困难但是Facebook工程师做到了，他们结合Web界面的特点，做了两个简单的假设，直接将Diff算法的复杂度降低到O(n)

　　两个相同的组件产生相似的DOM结构，不同的组件产生不同的DOM结构；对于同一层级的一组子节点，可以通过唯一的id来区分。

　　算法优化是 React 整个界面 Render 的基础。事实也证明，这两个假设是合理且准确的，保证了整体接口构建的性能。

　　不同节点类型的比较

　　为了在树之间进行比较，我们首先必须能够比较两个节点。在 React 中，我们比较两个虚拟 DOM 节点。当两个节点不同时我们应该怎么做？这分两种情况：（1）node类型不同，（2）node类型相同，但属性不同。本节先看第一种情况。

　　当树中相同位置前后输出不同类型的节点时，React直接删除之前的节点，然后创建并插入一个新节点。假设我们在树中的同一位置前后两次输出不同类型的节点。

　　复制代码

　　 renderA: renderB: => [removeNode ], [insertNode ]

　　当一个节点从 div 变为 span 时，只需删除 div 节点并插入一个新的 span 节点即可。这符合我们对真实DOM操作的理解。

　　需要注意的是，删除一个节点意味着彻底销毁该节点，而不是在后续的比较中检查是否还有另一个节点等同于被删除的节点。如果删除的节点下还有子节点，这些子节点也会被彻底删除，不会用于后续的比较。这就是为什么算法复杂度可以降低到 O(n) 的原因。

　　上面说的是虚拟DOM节点的操作，同样的逻辑也用在React组件的比较中，例如：

　　复制代码

　　 renderA: renderB: => [removeNode ], [insertNode ]

　　当 React 在同一位置遇到不同的组件时，它只会销毁第一个组件并添加新创建的组件。这是第一个假设的应用。不同的组件通常会产生不同的 DOM 结构。与其浪费时间比较基本不等价的 DOM 结构，不如创建一个新组件并添加它。

　　从这个 React 对不同类型节点的处理逻辑，我们可以很容易地推断出 React 的 DOM Diff 算法实际上只是逐层比较树，如下所述。

　　逐层比较节点

　　说到树，相信大多数同学第一时间想到的是二叉树、遍历、最短路径等复杂的数据结构算法。在 React 中，树算法其实很简单，就是两棵树只会比较同一层级的节点。如下图所示：

　　

　　React 只会比较同一个颜色框中的 DOM 节点，即同一个父节点下的所有子节点。当发现该节点不再存在时，该节点及其子节点将被完全删除，不再用于进一步比较。这样整个DOM树的比较只需遍历一次树即可完成。

　　例如，考虑以下 DOM 结构转换：

　　

　　A节点完全移到D节点，直观考虑DOM Diff操作应该是

　　复制代码

　　 A.parent.remove(A); D.append(A);

　　但是因为React只是简单的考虑了同层节点的位置变换，对于不同层的节点，只有简单的创建和删除。当根节点发现子节点中的A缺失时，直接销毁A；而当D发现自己多了一个子节点A时，就会创建一个新的A作为子节点。因此，这种结构转换的实际操作是：

　　复制代码

　　 A.destroy();A = new A();A.append(new B());A.append(new C());D.append(A);

　　如您所见，完全重新创建了以 A 为根节点的树。

　　虽然这个算法看起来有点“简单化”，但它基于第一个假设：两个不同的组件通常会产生不同的 DOM 结构。根据官方 React 博客，到目前为止，这种假设还没有造成严重的性能问题。这当然也给了我们一个提示，即在实现自己的组件时，保持稳定的 DOM 结构将有助于提高性能。例如，我们有时可以通过 CSS 隐藏或显示某些节点​​，而不是实际删除或添加 DOM 节点。

　　通过DOM Diff算法了解组件的生命周期

　　在上一篇文章中，我们介绍了React组件的生命周期。它的每个阶段实际上都与 DOM Diff 算法密切相关。例如以下方法：

　　为了演示组件生命周期和DOM Diff算法的关系，作者创建了一个例子：，可以直接访问试用。这时候，当DOM树经历了如下的转变，也就是从“shape1”转变为“shape2”的时候。让我们观察这些方法的实现：

　　

　　浏览器开发工具控制台输出如下结果：

　　复制代码

　　 C will unmount.C is created.B is updated.A is updated.C did mount.D is updated.R is updated.

　　如您所见，C 节点完全重建，然后添加到 D 节点，而不是“移动”它。如果有兴趣，也可以fork示例代码：。所以你可以自己添加其他树结构，并尝试如何在它们之间进行转换。

　　同类型节点对比

　　第二类节点的比较是同类型的节点，算法比较简单易懂。 React 会重置属性来实现节点转换。例如：

　　复制代码

　　 renderA: renderB: => [replaceAttribute id "after"]

　　虚拟DOM的style属性略有不同。它的值不是简单的字符串而是必须是一个对象，所以转换过程如下：

　　复制代码

　　 renderA: renderB: => [removeStyle color], [addStyle font-weight 'bold']

　　列表节点对比

　　不在同一层上的节点的比较如上所述。即使它们完全相同，它们也会被破坏和重新创建。那么当它们在同一层时是如何处理的呢？这就涉及到链表节点的Diff算法。相信很多使用React的同学都遇到过这个警告：

　　

　　这是React遇到list但找不到key时提示的警告。尽管即使您忽略此警告，大多数接口也能正常工作，但这通常意味着潜在的性能问题。因为 React 觉得可能无法高效更新这个列表。

　　列表节点的操作通常包括添加、删除和排序。比如下图中，我们需要直接将节点F插入到B和C中。在jQuery中，我们可以直接使用$(B).after(F)来实现。在 React 中，我们只告诉 React 新的接口应该是 A-B-F-C-D-E，接口通过 Diff 算法更新。

　　

　　这时候如果每个节点都没有唯一标识符，而React无法识别每个节点，更新过程会非常低效，即更新C到F，D到C，E到D，最后Insert E 节点。效果如下图所示：

　　

　　如您所见，React 会一一更新节点并切换到目标节点。最后插入一个新的节点 E 涉及到很多 DOM 操作。而如果给每个节点一个唯一的键（key），那么React就能找到正确的位置插入新节点，如下图：

　　

　　调整列表节点的顺序，其实和插入或删除类似。让我们用下面的示例代码来看看转换过程。仍然使用前面提到的例子：，我们将树的形状从 shape5 转换为 shape6：

　　

　　同层节点的位置会有所调整。如果没有提供key，那么React认为B和C后面对应的组件类型是不同的，所以彻底删除并重建。控制台输出如下：

　　复制代码

　　 B will unmount.C will unmount.C is created.B is created.C did mount.B did mount.A is updated.R is updated.

　　如果提供了密钥，如以下代码：

　　复制代码

　　 shape5: function() { return ( );}, shape6: function() { return ( );},

　　然后控制台输出如下：

　　复制代码

　　 C is updated.B is updated.A is updated.R is updated.

　　如您所见，为列表节点提供唯一的key属性可以帮助React定位到正确的节点进行比较，从而大大减少DOM操作次数，提高性能。

　　总结

　　本文分析了 React 的 DOM Diff 算法是如何工作的，其复杂度控制在 O(n)。这让我们每次都可以根据状态考虑 UI 来渲染整个界面，而不必担心性能问题。简化 UI 开发的复杂性。算法优化的基础是文章开头提到的两个假设，而React的UI是基于组件等机制的。了解虚拟DOM Diff算法不仅可以帮助我们了解组件的生命周期，而且对我们在实现自定义组件时进一步优化性能具有指导意义。

　　感谢徐川对本文的审阅。

　　如需为InfoQ中文站投稿或参与内容翻译，请发邮件至。也欢迎您关注我们的新浪微博（@InfoQ，@丁晓昀）、微信（微信ID：InfoQChina），与我们的编辑和其他读者朋友交流（欢迎加入InfoQ读者交流群

　　

　　).