Virtual DOM diff算法原理

以前在解决一次flatlist没有局部刷新的问题时写了一篇博客里面提到了官方的一篇文档叫做reconciliation。前阵子有人问我react的virtualDomTree的diff算法是怎么实现的有没做什么优化点。我知道是这篇文章里的内容但当时却说不清楚这让我觉得我对这篇文章其实理解的并不够所以把它再看一遍然后把自己的理解记录下来但这并不是翻译完全是按照我自己的理解来写的并不会非常严谨但应该不会有误如果有不同看法欢迎讨论。

正常来说Dom树的diff算法复杂度是O(n^3)如果页面很复杂时性能就非常低了比如有1000个节点的树需要比较一亿次。React进行优化后实际的复杂度降低到了O(n)它基于两个原则

1. 两个节点类型不同的话以其为根节点的树也完全不同

2. 通过节点的key属性可以定位新旧Dom树上对应的节点来判定是否需要rerender

首先看如何比较假定我们已经确定了要比较的节点

1. 如果节点类型不同比如原来是Image现在是View。那么以这个节点为根节点的整个Dom树都需要新建。它本身的属性以及所有的子节点都没有比较的必要了。

2. 如果节点类型相同那么就比较它的属性只有那些发生了变化的属性会被记录下来然后进行更新没有发生变化的属性也就保持不变。然后循环遍历它的所有子孙节点进行比较。

需要注意一下一旦一个节点比较有了diff也就是变得dirty那么它本身以及所有的子孙节点都会变成dirty。diff会生成但是否触发re-render取决于具体实现。不要误认为只要有diff必然会导致re-render或者只要没触发re-render就没有diff。

然后就是我们怎么确定某个节点在新旧Dom树上如何对应的假设下面这种场景

//old    1    2//new1    1    2    3//new2    3    1    2

old指老的Dom树new1在它的末尾插入了一个新的子节点根据上面的原则根节点View和Text1,Text2都没有变化只是新增了Text3而已。但new2就不一样了它在起始插入了一个Text3这就导致Text1变成了Text3Text2变成了Text1然后新加了一个Text2这显然是不太合适的明明只增加了一个子节点但三个都重绘了。例子中Text是一个很简单的组件实际上它可以是一个非常复杂的根节点那样的话可能就导致一整个Dom树的变动了。

解决这个问题的方案就是给Component添加了key属性。一个节点的所有子节点拥有一个唯一的key注意这个唯一并不是全局的唯一只需要跟它的兄弟节点区分开来就行。加上key之后再看上面的例子

//old    1     2//new2    3     1     2

现在在进行diff时就知道了key为1和2的Text节点内容没有变化不会生成diff只需要增加Text3就可以了。

文档里提到在项目开发中key的设置不要太过随意例如直接使用index如果这样当子控件顺序发生变化时可能就产生了额外的diff。我在使用flatlist时keyExtractor直接使用index导致在数组起始插入一个数据时整个flatlist全部进行了刷新而不是局部刷新就是这个原因。

最后有两个结论

1. 如果没有必要不要轻易改变一个节点的类型。也就是说显示效果没变却改变节点类型。这在实际情况中很少发生。

2. 使用一个稳定和唯一的key来让组件和它的兄弟组件区分不使用或者不合理的使用可能造成性能问题。

本文转载自异步社区

原文链接https://www.epubit.com/articleDetails?id=N63b8e9b0-5353-4705-8b02-6bc5d290c7e4