Open laizimo opened 6 years ago
之前，有讲述过react的生命周期和setState机制。其实，react还有一个重要的东西，堪称是react的灵魂——diff算法。如果没有它，实现visual DOM的更新，不会那么容易，react的性能也不会那么好。接下来，我们可以来见识一下react的diff算法的特色。
通常来说，计算一棵树形结构转换成另一棵树形结构的算法复杂度在O(n^3)，n表示树中的节点个数。这个结果是经过数学计算论证的。我们可以举个例子来量化这个概念：在整个页面中有1000个node节点，如果一处地方发生改变，整个浏览器需要经过十亿次的计算。这个结果对于客户端来讲，是无法接受的。那么，对于这样一个高复杂度算法来讲，在VDOM模型中使用，明显是不现实的。因此，react团队对于它的优化绝对是点睛之笔。
如何去减少复杂度呢？方法就是通过增加一定的条件，来减少没有必要的比较。react团队在这个方面，做出了三个策略，最终使得diff算法的复杂度降低到了O(n)。
三大策略：
基于这三大策略，我们可以将整颗树的比较分成三部分来进行。在分析前，我们先来看一张经典图：
这是一张react diff的核心图，或许你现在还看不明白，但是看了之后的分析之后，回过头来，你必将有所领悟。
tree diff
react只会对同层级的组件进行比较，如果新树中节点不存在，react会直接删除该节点，不进行后续的比较；同样的，如果新增了子节点，那么react会在该位置新插入一个节点。
那么，如果是上述的少数情况——跨层级移动怎么解决。
举例为证：
react会执行以下操作：创建A——>创建B、C——>删除A
注：这里可以去进行优化的方式是，可以不进行跨层级的移动，而对元素进行可见或隐藏的操作，这样会优化性能。
component diff
react会根据策略二制定的规则来进行比较：
如果是同类型组件，则进行更深层次的比较；如果不是同类型，直接替换掉原先的组件。
那么，如果出现两个组件，类型不同而结构相同的情况下，会对diff算法的性能产生影响，尽量避免此类型的操作。
注：这里可以使用shouldComponentUpdate来进行判断，是否需要更新。如果不需要更新，就可以阻断接下来的子树的比较过程，从而达到优化react性能的效果；同时，使用无状态组件也可以起到这样子的效果
element diff
对于第三种策略，在同一组子节点设置唯一的key来进行识别，也是一种优化非常好的方法。
首先，我们从一张图开始，分析一组子节点之间如何比较不同的。
如图所示，在没有key的情况下，通常会如何进行处理？
这样的流程，或许你也发现了，他们所消耗的成本太大，只有移除和插入的操作，远远没有使用到旧的组件。因为，没有唯一key的存在，react无法去判断是否在之前的树中存在着已有的组件，从而无法将旧组件进行复用。
回到如果回到具备key值的情况下，又是另一番场景了。
这里react会到旧树中去查找是否已经具有相同的组件，然后进行移动操作。移动操作会发生在旧树节点的位置下标小于新树节点位置下标时。我们先来看看整个的比较过程。
C和D的操作是一样的。那么，我们来看看，如果有新节点变化的图，又是如何进行比较的。
这样，整个diff比较就完成了，回顾之前不存在key的情况时的操作，这是的性能会相对良好。
当然了，这种比较法则大多数情况下是良好的，但是，如果是最后一个节点移动到第一个节点的极端情况下，会发现之前的节点都得发生移动，会造成一定的性能下降。
diff算法是react的佳作，经过优化的diff，甚至于可以让你在开发时，不用去考虑react性能。当然了，作为一个程序员来说，追求完美是必不可少的。即便于diff算法是优秀的，我们也应该懂得它的原理，然后在一定的基础上对它进行优化，例如，文章最后提到的这种情况。
react源码剖析——diff算法
laizimo
commented
6 years ago laizimo
commented
6 years ago
前言
之前，有讲述过react的生命周期和setState机制。其实，react还有一个重要的东西，堪称是react的灵魂——diff算法。如果没有它，实现visual DOM的更新，不会那么容易，react的性能也不会那么好。接下来，我们可以来见识一下react的diff算法的特色。
正文
通常来说，计算一棵树形结构转换成另一棵树形结构的算法复杂度在O(n^3)，n表示树中的节点个数。这个结果是经过数学计算论证的。我们可以举个例子来量化这个概念：在整个页面中有1000个node节点，如果一处地方发生改变，整个浏览器需要经过十亿次的计算。这个结果对于客户端来讲，是无法接受的。那么，对于这样一个高复杂度算法来讲，在VDOM模型中使用，明显是不现实的。因此，react团队对于它的优化绝对是点睛之笔。
如何去减少复杂度呢？方法就是通过增加一定的条件，来减少没有必要的比较。react团队在这个方面，做出了三个策略，最终使得diff算法的复杂度降低到了O(n)。
三大策略：
基于这三大策略，我们可以将整颗树的比较分成三部分来进行。在分析前，我们先来看一张经典图：
这是一张react diff的核心图，或许你现在还看不明白，但是看了之后的分析之后，回过头来，你必将有所领悟。
tree diff
react只会对同层级的组件进行比较，如果新树中节点不存在，react会直接删除该节点，不进行后续的比较；同样的，如果新增了子节点，那么react会在该位置新插入一个节点。
那么，如果是上述的少数情况——跨层级移动怎么解决。
举例为证：
react会执行以下操作：创建A——>创建B、C——>删除A
component diff
react会根据策略二制定的规则来进行比较：
如果是同类型组件，则进行更深层次的比较；如果不是同类型，直接替换掉原先的组件。
那么，如果出现两个组件，类型不同而结构相同的情况下，会对diff算法的性能产生影响，尽量避免此类型的操作。
element diff
对于第三种策略，在同一组子节点设置唯一的key来进行识别，也是一种优化非常好的方法。
首先，我们从一张图开始，分析一组子节点之间如何比较不同的。
如图所示，在没有key的情况下，通常会如何进行处理？
这样的流程，或许你也发现了，他们所消耗的成本太大，只有移除和插入的操作，远远没有使用到旧的组件。因为，没有唯一key的存在，react无法去判断是否在之前的树中存在着已有的组件，从而无法将旧组件进行复用。
回到如果回到具备key值的情况下，又是另一番场景了。
这里react会到旧树中去查找是否已经具有相同的组件，然后进行移动操作。移动操作会发生在旧树节点的位置下标小于新树节点位置下标时。我们先来看看整个的比较过程。
C和D的操作是一样的。那么，我们来看看，如果有新节点变化的图，又是如何进行比较的。
这样，整个diff比较就完成了，回顾之前不存在key的情况时的操作，这是的性能会相对良好。
当然了，这种比较法则大多数情况下是良好的，但是，如果是最后一个节点移动到第一个节点的极端情况下，会发现之前的节点都得发生移动，会造成一定的性能下降。
总结
diff算法是react的佳作，经过优化的diff，甚至于可以让你在开发时，不用去考虑react性能。当然了，作为一个程序员来说，追求完美是必不可少的。即便于diff算法是优秀的，我们也应该懂得它的原理，然后在一定的基础上对它进行优化，例如，文章最后提到的这种情况。