react diff算法

[laizimo]

前言

之前，有讲述过react的生命周期和setState机制。其实，react还有一个重要的东西，堪称是react的灵魂——diff算法。如果没有它，实现visual DOM的更新，不会那么容易，react的性能也不会那么好。接下来，我们可以来见识一下react的diff算法的特色。

正文

通常来说，计算一棵树形结构转换成另一棵树形结构的算法复杂度在O(n^3)，n表示树中的节点个数。这个结果是经过数学计算论证的。我们可以举个例子来量化这个概念：在整个页面中有1000个node节点，如果一处地方发生改变，整个浏览器需要经过十亿次的计算。这个结果对于客户端来讲，是无法接受的。那么，对于这样一个高复杂度算法来讲，在VDOM模型中使用，明显是不现实的。因此，react团队对于它的优化绝对是点睛之笔。

如何去减少复杂度呢？方法就是通过增加一定的条件，来减少没有必要的比较。react团队在这个方面，做出了三个策略，最终使得diff算法的复杂度降低到了O(n)。

三大策略：

1. 在现实场景中，Web UI发生垮层级移动的概率比较低
2. 具有相同类的组件，生成的树形结构是一致的；具备不同的类的组件，将会生成不同的树形结构
3. 对于同层级的一组子节点，可以通过添加唯一标识的方式，快速甄别

基于这三大策略，我们可以将整颗树的比较分成三部分来进行。在分析前，我们先来看一张经典图：

这是一张react diff的核心图，或许你现在还看不明白，但是看了之后的分析之后，回过头来，你必将有所领悟。

tree diff

react只会对同层级的组件进行比较，如果新树中节点不存在，react会直接删除该节点，不进行后续的比较；同样的，如果新增了子节点，那么react会在该位置新插入一个节点。

那么，如果是上述的少数情况——跨层级移动怎么解决。

举例为证：

react会执行以下操作：创建A——>创建B、C——>删除A

注：这里可以去进行优化的方式是，可以不进行跨层级的移动，而对元素进行可见或隐藏的操作，这样会优化性能。

component diff

react会根据策略二制定的规则来进行比较：

如果是同类型组件，则进行更深层次的比较；如果不是同类型，直接替换掉原先的组件。

那么，如果出现两个组件，类型不同而结构相同的情况下，会对diff算法的性能产生影响，尽量避免此类型的操作。

注：这里可以使用shouldComponentUpdate来进行判断，是否需要更新。如果不需要更新，就可以阻断接下来的子树的比较过程，从而达到优化react性能的效果；同时，使用无状态组件也可以起到这样子的效果

element diff

对于第三种策略，在同一组子节点设置唯一的key来进行识别，也是一种优化非常好的方法。

首先，我们从一张图开始，分析一组子节点之间如何比较不同的。

如图所示，在没有key的情况下，通常会如何进行处理？

1. 在新树中的第一个节点是B，但是旧树中，第一个节点是A，因此，react会将A移除，在将新节点B插入；
2. 同理，第二次比较，会将节点B移除，节点A插入；第三次将节点C移除，节点D插入；第四次将节点D移除，节点C插入。

这样的流程，或许你也发现了，他们所消耗的成本太大，只有移除和插入的操作，远远没有使用到旧的组件。因为，没有唯一key的存在，react无法去判断是否在之前的树中存在着已有的组件，从而无法将旧组件进行复用。

回到如果回到具备key值的情况下，又是另一番场景了。

这里react会到旧树中去查找是否已经具有相同的组件，然后进行移动操作。移动操作会发生在旧树节点的位置下标小于新树节点位置下标时。我们先来看看整个的比较过程。

1. 在新树中第一个节点是节点B，lastIndex记为0，然后react会到旧树中去查找，是否存在key为B的节点，会发现存在节点B，并且它的下标是1，_mountIndex记为1，因为旧树中的下标大于新树中的下标，因此，不必发生移动。
2. 在新树中的第二个节点是A，lastIndex记为1，然后react会去查找旧树中key值为A的节点，发现此节点存在，并且_mountIndex为0，这时，节点A需要发生移动，移动到新树节点一样的位置，即下标为1的位置。

C和D的操作是一样的。那么，我们来看看，如果有新节点变化的图，又是如何进行比较的。

1. 在新树中，第一个节点是B，lastIndex记为0，然后查找旧树中节点情况，会发现存在B节点，且其下标大于新树的下标，因此，不做任何变化
2. 新树中，第二个节点是E，lastIndex记为1，然后查找旧树时，会发现并不存在该节点，因此，react会在下标为1的地方插入节点E。
3. 在新树中，第三个节点是C，lastIndex记为2，之后，会发现旧树中存在节点C，其下标也为2，因此，不进行任何操作
4. 在新树中，第四个节点是A，lastIndex记为3，之后，在旧树中存在节点A，其下标为0，小于新树中的下标，因此，将节点A移至下标3的地方。
5. 完成之后，进行比较新旧树的比较，发现旧树中存在D节点，将至移除。

这样，整个diff比较就完成了，回顾之前不存在key的情况时的操作，这是的性能会相对良好。

当然了，这种比较法则大多数情况下是良好的，但是，如果是最后一个节点移动到第一个节点的极端情况下，会发现之前的节点都得发生移动，会造成一定的性能下降。

总结

diff算法是react的佳作，经过优化的diff，甚至于可以让你在开发时，不用去考虑react性能。当然了，作为一个程序员来说，追求完美是必不可少的。即便于diff算法是优秀的，我们也应该懂得它的原理，然后在一定的基础上对它进行优化，例如，文章最后提到的这种情况。

[laizimo]

react源码剖析——diff算法