【React进阶系列】虚拟dom与diff算法

zhou_you 发布于2019-08-23 12:24 / 2577人阅读

摘要：通过对树进行层级控制，同一个父节点下的所有子节点。新老集合进行差异化对比，发现，则创建并插入至新集合，删除老集合以此类推，创建并插入和，删除和。

虚拟dom

Jsx 表面写的是html，其实内部执行的是一段js
createElement

React.createElement(
  type,
  [props],
  [...children]
)

createElement把这个树形结构，存在内存里面
Jsx最终以这样的一个个对象递归的存在内存中，执行diff算法

多层结构

简单的createElement实现

reactElement - 生成的是一个对象来描述这个节点

react diff

与传统树的diff的区别

计算一棵树形结构转换成另一棵树形结构的最少操作，是一个复杂且值得研究的问题。传统 diff 算法通过循环递归对节点进行依次对比，效率低下，算法复杂度达到 O(n^3)

react diff策略

Web UI 中 DOM 节点跨层级的移动操作特别少，可以忽略不计。

拥有相同类的两个组件将会生成相似的树形结构，拥有不同类的两个组件将会生成不同的树形结构。

对于同一层级的一组子节点，它们可以通过唯一 id 进行区分。

tree diff

 基于策略一，对树进行分层比较，两棵树只会对同一层次的节点进行比较。  
 React 通过 updateDepth 对 Virtual DOM 树进行层级控制，同一个父节点下的所有子节点。

什么是 DOM 节点跨层级的移动操作？

A 节点（包括其子节点）整个被移动到 D 节点下

如果出现了 DOM 节点跨层级的移动操作，React diff 会有怎样的表现呢？

React 只会简单的考虑同层级节点的位置变换，而对于不同层级的节点，只有创建和删除操作。

当根节点发现子节点中 A 消失了，就会直接销毁 A；当 D 发现多了一个子节点 A，则会创建新的 A（包括子节点）作为其子节点。此时，React diff 的执行情况：create A -> create B -> create C -> delete A。

注意：

在开发组件时，保持稳定的 DOM 结构会有助于性能的提升。例如，可以通过 CSS 隐藏或显示节点，而不是真的移除或添加 DOM 节点。

component diff

依据策略二

如果是同一类型的组件，按照原策略继续比较 virtual DOM tree。

如果不是，则将该组件判断为 dirty component，从而替换整个组件下的所有子节点。

对于同一类型的组件，有可能其 Virtual DOM 没有任何变化，如果能够确切的知道这点那可以节省大量的 diff 运算时间，因此 React 允许用户通过 shouldComponentUpdate() 来判断该组件是否需要进行 diff。

React 判断 D 和 G 是不同类型的组件，就不会比较二者的结构，而是直接删除 component D，重新创建 component G 以及其子节点，即使D 和 G的结构很相似

element diff

当节点处于同一层级时，React diff 提供了三种节点操作，分别为：INSERT_MARKUP（插入）、MOVE_EXISTING（移动）和 REMOVE_NODE（删除）。

INSERT_MARKUP，新的 component 类型不在老集合里，即是全新的节点，需要对新节点执行插入操作。

MOVE_EXISTING，在老集合有新 component 类型，且 element 是可更新的类型，generateComponentChildren 已调用 receiveComponent，这种情况下 prevChild=nextChild，就需要做移动操作，可以复用以前的 DOM 节点。

REMOVE_NODE，老 component 类型，在新集合里也有，但对应的 element 不同则不能直接复用和更新，需要执行删除操作，或者老 component 不在新集合里的，也需要执行删除操作。

eg: 新老集合进行 diff 差异化对比，发现 B != A，则创建并插入 B 至新集合，删除老集合 A；以此类推，创建并插入 A、D 和 C，删除 B、C 和 D。

带来的问题：都是相同的节点，但由于位置发生变化，导致需要进行繁杂低效的删除、创建操作，其实只要对这些节点进行位置移动即可

react优化策略：允许开发者对同一层级的同组子节点，添加唯一 key 进行区分

优化后diff实现：

对新集合的节点进行循环遍历，通过唯一 key 可以判断新老集合中是否存在相同的节点

如果存在相同节点，则进行移动操作，但在移动前需要将当前节点在老集合中的位置child._mountIndex与lastIndex(访问过的节点在老集合中最右的位置即最大的位置)进行比较，if (child._mountIndex < lastIndex)，则进行节点移动操作

分析：

element  _mountIndex  lastIndex  nextIndex  enqueueMove
B        1            0          0          false
A        0            1          1          true
D        3            1          2          false
C        2            3          3          true

step：

从新集合中取得 B，判断老集合中存在相同节点 B
B 在老集合中的位置 B._mountIndex = 1
初始 lastIndex = 0
不满足 child._mountIndex < lastIndex 的条件，因此不对 B 进行移动操作
更新 lastIndex = Math.max(prevChild._mountIndex, lastIndex) lastIndex更新为1
将 B 的位置更新为新集合中的位置prevChild._mountIndex = nextIndex，此时新集合中 B._mountIndex = 0，nextIndex++

以上主要分析新老集合中存在相同节点但位置不同时，对节点进行位置移动的情况，如果新集合中有新加入的节点且老集合存在需要删除的节点，那么 React diff 又是如何对比运作的呢？

    element  _mountIndex  lastIndex  nextIndex  enqueueMove
    B        1            0          0          false
    E        no exist
    C        2            1          2          false
    A        0            2          3          true

step

新建：从新集合中取得 E，判断老集合中不存在相同节点 E，则创建新节点 E
     lastIndex不做处理
     E 的位置更新为新集合中的位置，nextIndex++
删除：当完成新集合中所有节点 diff 时，最后还需要对老集合进行循环遍历，判断是否存在新集合中没有但老集合中仍存在的节点，发现存在这样的节点 D，因此删除节点 D

react diff的问题

理论上 diff 应该只需对 D 执行移动操作，然而由于 D 在老集合的位置是最大的，导致其他节点的 _mountIndex < lastIndex，造成 D 没有执行移动操作，而是 A、B、C 全部移动到 D 节点后面的现象

建议：在开发过程中，尽量减少类似将最后一个节点移动到列表首部的操作，当节点数量过大或更新操作过于频繁时，在一定程度上会影响 React 的渲染性能。

总结：

React 通过制定大胆的 diff 策略，将 O(n3) 复杂度的问题转换成 O(n) 复杂度的问题；

React 通过分层求异的策略，对 tree diff 进行算法优化；

React 通过相同类生成相似树形结构，不同类生成不同树形结构的策略，对 component diff 进行算法优化；

React 通过设置唯一 key的策略，对 element diff 进行算法优化；

建议，在开发组件时，保持稳定的 DOM 结构会有助于性能的提升；

建议，在开发过程中，尽量减少类似将最后一个节点移动到列表首部的操作，当节点数量过大或更新操作过于频繁时，在一定程度上会影响 React 的渲染性能。

https://zhuanlan.zhihu.com/p/...

idc机房托管专线服务 react dom cdn react-dom 算法系列数据分析与数据分析系列教材

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/98461.html

React系列 --- virtualdom diff算法实现分析(三)

摘要：所以只针对同层级节点做比较，将复杂度的问题转换成复杂度的问题。 React系列 React系列 --- 简单模拟语法(一)React系列 --- Jsx, 合成事件与Refs(二)React系列 --- virtualdom diff算法实现分析(三)React系列 --- 从Mixin到HOC再到HOOKS(四)React系列 --- createElement, ReactElem...

sunsmell 2019-08-26 10:37 评论0 收藏0
从零开始实现一个React（三）：diff算法

摘要：而对比变化，找出需要更新部分的算法我们称之为算法。整个系列大概会有四篇，我每周会更新一到两篇，我会第一时间在上更新，有问题需要探讨也请在上回复我博客地址关注点，订阅点上一篇文章从零开始实现一个二组件和生命周期前言在上一篇文章，我们已经实现了React的组件功能，从功能的角度来说已经实现了React的核心功能了。但是我们的实现方式有很大的问题：每次更新都重新渲染整个应用或者整个组件...

The question 2019-08-22 16:12 评论0 收藏0
从零开始实现一个React（三）：diff算法

摘要：而对比变化，找出需要更新部分的算法我们称之为算法。整个系列大概会有四篇，我每周会更新一到两篇，我会第一时间在上更新，有问题需要探讨也请在上回复我博客地址关注点，订阅点上一篇文章从零开始实现一个二组件和生命周期前言在上一篇文章，我们已经实现了React的组件功能，从功能的角度来说已经实现了React的核心功能了。但是我们的实现方式有很大的问题：每次更新都重新渲染整个应用或者整个组件...

YPHP 2019-08-05 13:30 评论0 收藏0
【React进阶系列】从零开始手把手教你实现一个Virtual DOM（一）

摘要：可实际上并不是创造的，将这个概念拿过来以后融会贯通慢慢地成为目前前端最炙手可热的框架之一。则是将再抽象一层生成的简化版对象，这个对象也拥有上的一些属性，比如等，但它是完全脱离于浏览器而存在的。所以今天我要手把手教大家怎么从零开始实现。假如你的项目使用了React，你知道怎么做性能优化吗？你知道为什么React让你写shouldComponentUpdate或者React.PureCo...

PumpkinDylan 2019-08-22 16:40 评论0 收藏0
react进阶漫谈

摘要：父组件向子组件之间非常常见，通过机制传递即可。我们应该听说过高阶函数，这种函数接受函数作为输入，或者是输出一个函数，比如以及等函数。在传递数据的时候，我们可以用进一步提高性能。本文主要谈自己在react学习的过程中总结出来的一些经验和资源，内容逻辑参考了深入react技术栈一书以及网上的诸多资源，但也并非完全照抄，代码基本都是自己实践，主要为平时个人学习做一个总结和参考。本文的关键...

neuSnail 2019-08-20 14:16 评论0 收藏0