domdiff代码 react_react 的domdiff 的算法 - CSDN
精华内容
参与话题
  • React虚拟DOM Diff算法解析

    千次阅读 2017-12-14 15:24:28
    React中最神奇的部分莫过于虚拟DOM,以及其高效的Diff算法。这让我们可以无需担心性能问题而”毫无顾忌”的随时“刷新”整个页面,由虚拟DOM来确保只对界面上真正变化的部分进行实际的DOM操作。React在这一部分已经...

    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)

    1. 两个相同组件产生类似的DOM结构,不同的组件产生不同的DOM结构;
    2. 对于同一层次的一组子节点,它们可以通过唯一的id进行区分。

    算法上的优化是React整个界面Render的基础,事实也证明这两个假设是合理而精确的,保证了整体界面构建的性能。

    不同节点类型的比较

    为了在树之间进行比较,我们首先要能够比较两个节点,在React中即比较两个虚拟DOM节点,当两个节点不同时,应该如何处理。这分为两种情况:(1)节点类型不同 ,(2)节点类型相同,但是属性不同。本节先看第一种情况。

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

    renderA: <div />
    renderB: <span />
    => [removeNode <div />], [insertNode <span />]

    当一个节点从div变成span时,简单的直接删除div节点,并插入一个新的span节点。这符合我们对真实DOM操作的理解。

    需要注意的是,删除节点意味着彻底销毁该节点,而不是再后续的比较中再去看是否有另外一个节点等同于该删除的节点。如果该删除的节点之下有子节点,那么这些子节点也会被完全删除,它们也不会用于后面的比较。这也是算法复杂能够降低到O(n)的原因。

    上面提到的是对虚拟DOM节点的操作,而同样的逻辑也被用在React组件的比较,例如:

    renderA: <Header />
    renderB: <Content />
    => [removeNode <Header />], [insertNode <Content />]

    当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算法息息相关的。例如以下几个方法:

    • constructor: 构造函数,组件被创建时执行;
    • componentDidMount: 当组件添加到DOM树之后执行;
    • componentWillUnmount: 当组件从DOM树中移除之后执行,在React中可以认为组件被销毁;
    • componentDidUpdate: 当组件更新时执行。

    为了演示组件生命周期和DOM Diff算法的关系,笔者创建了一个示例:https://supnate.github.io/react-dom-diff/index.html ,大家可以直接访问试用。这时当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示例代码:https://github.com/supnate/react-dom-diff 。从而可以自己添加其它树结构,试验它们之间是如何转换的。

    相同类型节点的比较

    第二种节点的比较是相同类型的节点,算法就相对简单而容易理解。React会对属性进行重设从而实现节点的转换。例如:

    renderA: <div id="before" />
    renderB: <div id="after" />
    => [replaceAttribute id "after"]

    虚拟DOM的style属性稍有不同,其值并不是一个简单字符串而必须为一个对象,因此转换过程如下:

    renderA: <div style={{color: 'red'}} />
    renderB: <div style={{fontWeight: 'bold'}} />
    => [removeStyle color], [addStyle font-weight 'bold']

    列表节点的比较

    上面介绍了对于不在同一层的节点的比较,即使它们完全一样,也会销毁并重新创建。那么当它们在同一层时,又是如何处理的呢?这就涉及到列表节点的Diff算法。相信很多使用React的同学大多遇到过这样的警告:

    这是React在遇到列表时却又找不到key时提示的警告。虽然无视这条警告大部分界面也会正确工作,但这通常意味着潜在的性能问题。因为React觉得自己可能无法高效的去更新这个列表。

    列表节点的操作通常包括添加、删除和排序。例如下图,我们需要往B和C直接插入节点F,在jQuery中我们可能会直接使用$(B).after(F)来实现。而在React中,我们只会告诉React新的界面应该是A-B-F-C-D-E,由Diff算法完成更新界面。

    这时如果每个节点都没有唯一的标识,React无法识别每一个节点,那么更新过程会很低效,即,将C更新成F,D更新成C,E更新成D,最后再插入一个E节点。效果如下图所示:

    可以看到,React会逐个对节点进行更新,转换到目标节点。而最后插入新的节点E,涉及到的DOM操作非常多。而如果给每个节点唯一的标识(key),那么React能够找到正确的位置去插入新的节点,入下图所示:

    对于列表节点顺序的调整其实也类似于插入或删除,下面结合示例代码我们看下其转换的过程。仍然使用前面提到的示例:https://supnate.github.io/react-dom-diff/index.html ,我们将树的形态从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.

    而如果提供了key,如下面的代码:

    shape5: function() {
      return (
        <Root>
          <A>
            <B key="B" />
            <C key="C" />
          </A>
        </Root>
      );
    },
    
    shape6: function() {
      return (
        <Root>
          <A>
            <C key="C" />
            <B key="B" />
          </A>
        </Root>
      );
    },

    那么控制台输出如下:

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

    可以看到,对于列表节点提供唯一的key属性可以帮助React定位到正确的节点进行比较,从而大幅减少DOM操作次数,提高了性能。

     

    小结

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

    展开全文
  • React中最神奇的部分莫过于虚拟DOM,以及其高效的Diff算法。这让我们可以无需担心性能问题而”毫无顾忌”的随时“刷 新”整个页面,由虚拟DOM来确保只对界面上真正变化的部分进行实际的DOM操作。React在这一部分已经...
    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结构;
    1. 对于同一层次的一组子节点,它们可以通过唯一的id进行区分。

    算法上的优化是React整个界面Render的基础,事实也证明这两个假设是合理而精确的,保证了整体界面构建的性能。

    不同节点类型的比较

    为了在树之间进行比较,我们首先要能够比较两个节点,在React中即比较两个虚拟DOM节点,当两个节点不同时,应该如何处理。这分为两种情况:(1)节点类型不同 ,(2)节点类型相同,但是属性不同。本节先看第一种情况。

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

    renderA: <div />
    renderB: <span />
    => [removeNode <div />], [insertNode <span />]
    
    

    当一个节点从div变成span时,简单的直接删除div节点,并插入一个新的span节点。这符合我们对真实DOM操作的理解。

    需要注意的是,删除节点意味着彻底销毁该节点,而不是再后续的比较中再去看是否有另外一个节点等同于该删除的节点。如果该删除的节点之下有子节点,那么这些子节点也会被完全删除,它们也不会用于后面的比较。这也是算法复杂能够降低到O(n)的原因。

    上面提到的是对虚拟DOM节点的操作,而同样的逻辑也被用在React组件的比较,例如:

    renderA: <Header />
    renderB: <Content />
    => [removeNode <Header />], [insertNode <Content />]
    
    

    当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算法息息相关的。例如以下几个方法:

    • constructor: 构造函数,组件被创建时执行;
    • componentDidMount: 当组件添加到DOM树之后执行;
    • componentWillUnmount: 当组件从DOM树中移除之后执行,在React中可以认为组件被销毁;
    • componentDidUpdate: 当组件更新时执行。

    为了演示组件生命周期和DOM Diff算法的关系,笔者创建了一个示例:https://supnate.github.io/react-dom-diff/index.html ,大家可以直接访问试用。这时当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示例代码:https://github.com/supnate/react-dom-diff 。从而可以自己添加其它树结构,试验它们之间是如何转换的。

    相同类型节点的比较

    第二种节点的比较是相同类型的节点,算法就相对简单而容易理解。React会对属性进行重设从而实现节点的转换。例如:

    renderA: <div id="before" />
    renderB: <div id="after" />
    => [replaceAttribute id "after"]
    
    

    虚拟DOM的style属性稍有不同,其值并不是一个简单字符串而必须为一个对象,因此转换过程如下:

    renderA: <div style={{color: 'red'}} />
    renderB: <div style={{fontWeight: 'bold'}} />
    => [removeStyle color], [addStyle font-weight 'bold']
    
    

    列表节点的比较

    上面介绍了对于不在同一层的节点的比较,即使它们完全一样,也会销毁并重新创建。那么当它们在同一层时,又是如何处理的呢?这就涉及到列表节点的Diff算法。相信很多使用React的同学大多遇到过这样的警告:


    这是React在遇到列表时却又找不到key时提示的警告。虽然无视这条警告大部分界面也会正确工作,但这通常意味着潜在的性能问题。因为React觉得自己可能无法高效的去更新这个列表。

    列表节点的操作通常包括添加、删除和排序。例如下图,我们需要往B和C直接插入节点F,在jQuery中我们可能会直接使用$(B).after(F)来实现。而在React中,我们只会告诉React新的界面应该是A-B-F-C-D-E,由Diff算法完成更新界面。


    这时如果每个节点都没有唯一的标识,React无法识别每一个节点,那么更新过程会很低效,即,将C更新成F,D更新成C,E更新成D,最后再插入一个E节点。效果如下图所示:


    可以看到,React会逐个对节点进行更新,转换到目标节点。而最后插入新的节点E,涉及到的DOM操作非常多。而如果给每个节点唯一的标识(key),那么React能够找到正确的位置去插入新的节点,入下图所示:


    对于列表节点顺序的调整其实也类似于插入或删除,下面结合示例代码我们看下其转换的过程。仍然使用前面提到的示例:https://supnate.github.io/react-dom-diff/index.html ,我们将树的形态从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.
    
    

    而如果提供了key,如下面的代码:

    shape5: function() {
      return (
        <Root>
          <A>
            <B key="B" />
            <C key="C" />
          </A>
        </Root>
      );
    },
    
    shape6: function() {
      return (
        <Root>
          <A>
            <C key="C" />
            <B key="B" />
          </A>
        </Root>
      );
    },
    
    

    那么控制台输出如下:

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

    可以看到,对于列表节点提供唯一的key属性可以帮助React定位到正确的节点进行比较,从而大幅减少DOM操作次数,提高了性能。

     

    小结


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







    展开全文
  • 随着近年来前端行业迅速的崛起 前端已经不仅仅局限于将页面展示出来了,更多的是考虑性能的优化和用户的体验,因而越来越多的框架应运而生,angular,react ,vue 三大开源...下面简单梳理下虚拟domdiff算法 v...

    随着近年来前端行业迅速的崛起 前端已经不仅仅局限于将页面展示出来了,更多的是考虑性能的优化和用户的体验,因而越来越多的框架应运而生,angular,react ,vue 三大开源框架 目前在前端行业三足鼎立,人家站稳脚跟的原因必然是将前端的历史遗留问题解决的彻彻底底,同时在很大程度上还解决了很多其他的问题,当然最主要的还是 页面加载速度 及更新速度上。下面简单梳理下虚拟dom 和 diff算法

    vue

    • vue 是mvvm模式 数据驱动视图 ,本质上是利用观察者模式(订阅者发布者)劫持数据,利用es6 的Object.definePropety()中的访问器属性 将数据进行劫持 实现数据双向绑定 。
    • vue2.0 加入了dom diff 的算法 给vue的性能锦上添花。趋向于react
    • vue 的dom刷新频率 做成与浏览器同步状态(60次/s) ,能最大的减少dom操作次数,来达到速度上的优化.
    • vue中diff 的特点是对dom 进行原地复用,利用key值精准查找虚拟dom 中的不同处 ,来达到高效更新的效果 。

    React

    今天的重点不在vue 而是react 仿写了一个简易的react虚拟dom 和diff 算法的简易版 大致下梳理下 diff 算法原理
    react 框架最开始考虑的就是 性能问题,facebook 团队在react从0开始研发时就在设计这个问题。他是利用虚拟dom+diff算法 实现 dom的高效更新 其中最关键的就设计到一下几点

    • 虚拟dom 的实现
    • dom diff 算法的计算出需要更改的补丁对象
    • 根据补丁对象更新试图
    1.虚拟dom 的实现

    虚拟dom 说白了 就是真实dom树的一个描述,用js的对象去表示真实dom 我们可以创建这样一个方法 用来专门生成虚拟dom
    在这里插入图片描述
    createElement 的具体实现
    在这里插入图片描述
    在这里插入图片描述
    我们通过传入的元素名,元素属性和子节点 函数内部经过 处理 返回一个类对象用于描述 该节点 生成所谓的虚拟dom

    2.映射到真实dom 树上

    通过render 函数 将虚拟dom转成真实dom
    在这里插入图片描述
    render 函数传入 虚拟dom对象 根据documnet。createElement 创建父节点,遍历虚拟dom 节点上每一个props属性和子节点给父节点添加属性描述 (考虑的情况多种多样 需要分情况考虑属性的类型) 这里专门定义一个函数 进行属性的实现
    在这里插入图片描述
    真实dom实现完成后 就需要 追加到试图上 可自定义一个renderDOM 的方法实现 页面的渲染

    DOM Diff 的实现

    虚拟dom 实现完成后 我们要考虑的就是 进行两个类似的虚拟dom的对比,也就是两个对象的对比 而diff 的作用:根据两个虚拟对象创建出 补丁:(描述改变的内容),将这个补丁用来更新dom
    dom diff 差异计算:
    遵循先序深度优先遍历
    代码逻辑:

    1. 用js模拟dom
    2. 把虚拟dom转换为真实dom 并插入页面
    3. 若有事件发生需改虚拟dom 比较两个虚拟dom差异,得到差异对象
    4. 把差异对象 应用到真实dom树上

    domdiff 三种优化策略

    • 更新时只比较平级
    • 绝不会跨级比较
    • 若平级有变动只最小程度去修改dom
      在这里插入图片描述
      首先有一个diff函数 传入新树和老树 比较两者区别
      然后需要个递归树 递归比较将两者不同处 放入补丁包中、

    需要考虑几种情况 也就是补丁规则:

    1. 当节点类型相同时 ,
    • 查看属性 是否相同 属性不同 diff 比较后会产省一个补丁包
      {type : “ATTR”, attrs:{class:list-gourp}}‘
    • 新的dom节点不存在 时
      {type:‘REMOVE’,index:xxx}
    1. 节点类型不相同时,直接采用替换模式
      {type:“REPLACE”,newNode:newNode}
    2. 文本变化时
      {type:“TEXT”,text:1}

    我们定义一个walk方法 递归比较 找出补丁包
    在这里插入图片描述
    然后根据补丁包 给具体的元素打补丁 实现试图更新
    在这里插入图片描述
    其实 diff 算法的本质就是 找出两个dom 对象中的不同的地方,生成补丁包,根据补丁包给元素一层层递归打补丁 实现最终的视图更新

    当然react 内部源码内部实现的diff 功能及情况的考虑要更全面些 大家有时间可以研究下源码
    demo源码 请狂戳 https://github.com/guanguangithub/domDiff-demo

    展开全文
  • React虚拟DOMDiff算法解析

    千次阅读 2018-05-24 00:04:51
    Virtual DOMdiff 的完美结合,特别是其高效的 diff 算法,让用户可以无需顾忌性能问题而”任性自由”的刷新页面,让开发者也可以无需关心 Virtual DOM 背后的运作原理,因为 React diff 会帮助我们计算出 ...

    前言

    React 中最值得称道的部分莫过于 Virtual DOM 与 diff 的完美结合,特别是其高效的 diff 算法,让用户可以无需顾忌性能问题而”任性自由”的刷新页面,让开发者也可以无需关心 Virtual DOM 背后的运作原理,因为 React diff 会帮助我们计算出 Virtual DOM 中真正变化的部分,并只针对该部分进行实际 DOM 操作,而非重新渲染整个页面,从而保证了每次操作更新后页面的高效渲染,因此 Virtual DOM 与 diff 是保证 React 性能口碑的幕后推手。

    行文至此,可能会有读者质疑:React 无非就是引入 diff 这一概念,且 diff 算法也并非其首创,何必吹嘘的如此天花乱坠呢?

    其实,正是因为 diff 算法的普识度高,就更应该认可 React 针对 diff 算法优化所做的努力与贡献,更能体现 React 开发者们的魅力与智慧!

    传统 diff 算法

    计算一棵树形结构转换成另一棵树形结构的最少操作,是一个复杂且值得研究的问题。传统 diff 算法通过循环递归对节点进行依次对比,效率低下,算法复杂度达到 O(n^3),其中 n 是树中节点的总数。O(n^3) 到底有多可怕,这意味着如果要展示1000个节点,就要依次执行上十亿次的比较。这种指数型的性能消耗对于前端渲染场景来说代价太高了!现今的 CPU 每秒钟能执行大约30亿条指令,即便是最高效的实现,也不可能在一秒内计算出差异情况。

    如果 React 只是单纯的引入 diff 算法而没有任何的优化改进,那么其效率是远远无法满足前端渲染所要求的性能。

    因此,想要将 diff 思想引入 Virtual DOM,就需要设计一种稳定高效的 diff 算法,而 React 做到了!

    那么,React diff 到底是如何实现的呢?


    React Diff算法以及虚拟DOM解析

    1. 虚拟DOM

    1.1用JS对象模拟DOM树

    用 JavaScript 来表示一个 DOM 节点是很简单的事情,你只需要记录它的节点类型、属性,还有子节点:

    // a.js
    function Element (tagName, props, children) {
      this.tagName = tagName
      this.props = props
      this.children = children
    }
    
    module.exports = function (tagName, props, children) {
      return new Element(tagName, props, children)
    }

    例如上面的 DOM 结构就可以简单的表示:

    var el = require('./a.js')
    
    var ul = el('ul', {id: 'list'}, [
      el('li', {class: 'item'}, ['Item 1']),
      el('li', {class: 'item'}, ['Item 2']),
      el('li', {class: 'item'}, ['Item 3'])
    ])

    现在ul只是一个 JavaScript 对象表示的 DOM 结构,页面上并没有这个结构。我们可以根据这个ul构建真正的<ul>

    Element.prototype.render = function () {
      var el = document.createElement(this.tagName) // 根据tagName构建
      var props = this.props
    
      for (var propName in props) { // 设置节点的DOM属性
        var propValue = props[propName]
        el.setAttribute(propName, propValue)
      }
    
      var children = this.children || []
    
      children.forEach(function (child) {
        var childEl = (child instanceof Element)
          ? child.render() // 如果子节点也是虚拟DOM,递归构建DOM节点
          : document.createTextNode(child) // 如果字符串,只构建文本节点
        el.appendChild(childEl)
      })
    
      return el
    }

    render方法会根据tagName构建一个真正的DOM节点,然后设置这个节点的属性,最后递归地把自己的子节点也构建起来。所以只需要:

    var ulRoot = ul.render()
    document.body.appendChild(ulRoot)

    上面的ulRoot是真正的DOM节点,把它塞入文档中,这样body里面就有了真正的<ul>的DOM结构:

    <ul id='list'>
      <li class='item'>Item 1</li>
      <li class='item'>Item 2</li>
      <li class='item'>Item 3</li>
    </ul>

    2. diff 策略

    传统 diff 算法的复杂度为 O(n^3),显然这是无法满足性能要求的。React 通过制定大胆的策略,将 O(n^3) 复杂度的问题转换成 O(n) 复杂度的问题。

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

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

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

    这里写图片描述

    简单来说就是上面的div只会和同一层级的div对比,第二层级的只会跟第二层级对比。这样算法复杂度就可以达到 O(n)。

    2.1 深度优先遍历,记录差异

    在实际的代码中,会对新旧两棵树进行一个深度优先的遍历,这样每个节点都会有一个唯一的标记:

    这里写图片描述

    在深度优先遍历的时候,每遍历到一个节点就把该节点和新的的树进行对比。如果有差异的话就记录到一个对象里面。

    // diff 函数,对比两棵树
    function diff (oldTree, newTree) {
      var index = 0 // 当前节点的标志
      var patches = {} // 用来记录每个节点差异的对象
      dfsWalk(oldTree, newTree, index, patches)
      return patches
    }
    
    // 对两棵树进行深度优先遍历
    function dfsWalk (oldNode, newNode, index, patches) {
      // 对比oldNode和newNode的不同,记录下来
      patches[index] = [...]
    
      diffChildren(oldNode.children, newNode.children, index, patches)
    }
    
    // 遍历子节点
    function diffChildren (oldChildren, newChildren, index, patches) {
      var leftNode = null
      var currentNodeIndex = index
      oldChildren.forEach(function (child, i) {
        var newChild = newChildren[i]
        currentNodeIndex = (leftNode && leftNode.count) // 计算节点的标识
          ? currentNodeIndex + leftNode.count + 1
          : currentNodeIndex + 1
        dfsWalk(child, newChild, currentNodeIndex, patches) // 深度遍历子节点
        leftNode = child
      })
    }

    例如,上面的div和新的div有差异,当前的标记是0,那么:

    patches[0] = [{difference}, {difference}, ...] // 用数组存储新旧节点的不同
    

    同理p是patches[1],ul是patches[3],类推。

    2.2 差异类型

    上面说的节点的差异指的是什么呢?
    对 DOM 操作可能会:
    1. 替换掉原来的节点,例如把上面的div换成了section
    2. 移动、删除、新增子节点,例如上面div的子节点,把p和ul顺序互换
    3. 修改了节点的属性
    4. 对于文本节点,文本内容可能会改变。例如修改上面的文本节点2内容为Virtual DOM 2。

    所以我们定义了几种差异类型:

    var REPLACE = 0
    var REORDER = 1
    var PROPS = 2
    var TEXT = 3

    对于节点替换,很简单。判断新旧节点的tagName和是不是一样的,如果不一样的说明需要替换掉。如div换成section,就记录下:

    patches[0] = [{
      type: REPALCE,
      node: newNode // el('section', props, children)
    }]

    如果给div新增了属性id为container,就记录下:

    patches[0] = [{
      type: REPALCE,
      node: newNode // el('section', props, children)
    }, {
      type: PROPS,
      props: {
        id: "container"
      }
    }]
    

    如果是文本节点,如上面的文本节点2,就记录下:

    patches[2] = [{
      type: TEXT,
      content: "Virtual DOM2"
    }]

    那如果把我div的子节点重新排序呢?例如p, ul, div的顺序换成了div, p, ul。这个该怎么对比?如果按照同层级进行顺序对比的话,它们都会被替换掉。如p和div的tagName不同,p会被div所替代。最终,三个节点都会被替换,这样DOM开销就非常大。而实际上是不需要替换节点,而只需要经过节点移动就可以达到,我们只需知道怎么进行移动。

    2.3 列表对比算法

    例子:

    这里写图片描述

    新老集合所包含的节点,如上图图所示,新老集合进行 diff 差异化对比,通过 key 发现新老集合中的节点都是相同的节点,因此无需进行节点删除和创建,只需要将老集合中节点的位置进行移动,更新为新集合中节点的位置,此时 React 给出的 diff 结果为:B、D 不做任何操作,A、C 进行移动操作,即可。

    那么,如此高效的 diff 到底是如何运作的呢?让我们通过源码进行详细分析。

    首先对新集合的节点进行循环遍历,for (name in nextChildren),通过唯一 key 可以判断新老集合中是否存在相同的节点,if (prevChild === nextChild),如果存在相同节点,则进行移动操作,但在移动前需要将当前节点在老集合中的位置与 lastIndex 进行比较,if (child._mountIndex < lastIndex),则进行节点移动操作,否则不执行该操作。这是一种顺序优化手段,lastIndex 一直在更新,表示访问过的节点在老集合中最右的位置(即最大的位置),如果新集合中当前访问的节点比 lastIndex 大,说明当前访问节点在老集合中就比上一个节点位置靠后,则该节点不会影响其他节点的位置,因此不用添加到差异队列中,即不执行移动操作,只有当访问的节点比 lastIndex 小时,才需要进行移动操作。

    以上图为例,可以更为清晰直观的描述 diff 的差异对比过程:

    • 从新集合中取得 B,判断老集合中存在相同节点 B,通过对比节点位置判断是否进行移动操作,B 在老集合中的位置 B._mountIndex = 1,此时 lastIndex = 0,不满足 child._mountIndex < lastIndex 的条件,因此不对 B 进行移动操作;更新 lastIndex = Math.max(prevChild._mountIndex, lastIndex),其中 prevChild._mountIndex 表示 B 在老集合中的位置,则 lastIndex = 1,并将 B 的位置更新为新集合中的位置prevChild._mountIndex = nextIndex,此时新集合中 B._mountIndex = 0,nextIndex++ 进入下一个节点的判断。
    • 从新集合中取得 A,判断老集合中存在相同节点 A,通过对比节点位置判断是否进行移动操作,A 在老集合中的位置 A._mountIndex = 0,此时 lastIndex = 1,满足 child._mountIndex < lastIndex的条件,因此对 A 进行移动操作enqueueMove(this, child._mountIndex, toIndex),其中 toIndex 其实就是 nextIndex,表示 A 需要移动到的位置;更新 lastIndex = Math.max(prevChild._mountIndex, lastIndex),则 lastIndex = 1,并将 A 的位置更新为新集合中的位置 prevChild._mountIndex = nextIndex,此时新集合中A._mountIndex = 1nextIndex++ 进入下一个节点的判断。
    • 从新集合中取得 D,判断老集合中存在相同节点 D,通过对比节点位置判断是否进行移动操作,D 在老集合中的位置 D._mountIndex = 3,此时 lastIndex = 1,不满足 child._mountIndex < lastIndex的条件,因此不对 D 进行移动操作;更新 lastIndex = Math.max(prevChild._mountIndex, lastIndex),则 lastIndex = 3,并将 D 的位置更新为新集合中的位置 prevChild._mountIndex = nextIndex,此时新集合中D._mountIndex = 2nextIndex++ 进入下一个节点的判断。
    • 从新集合中取得 C,判断老集合中存在相同节点 C,通过对比节点位置判断是否进行移动操作,C 在老集合中的位置 C._mountIndex = 2,此时 lastIndex = 3,满足 child._mountIndex < lastIndex 的条件,因此对 C 进行移动操作 enqueueMove(this, child._mountIndex, toIndex);更新 lastIndex = Math.max(prevChild._mountIndex, lastIndex),则 lastIndex = 3,并将 C 的位置更新为新集合中的位置 prevChild._mountIndex = nextIndex,此时新集合中 C._mountIndex = 3nextIndex++ 进入下一个节点的判断,由于 C 已经是最后一个节点,因此 diff 到此完成。

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

    这里写图片描述

    B,E,C,A和上面的步骤一样, 只不过当完成新集合中所有节点 diff 时,最后还需要对老集合进行循环遍历,判断是否存在新集合中没有但老集合中仍存在的节点,发现存在这样的节点 D,因此删除节点 D,到此 diff 全部完成。

    2.3 把差异应用到真正的DOM树上

    因为1.1虚拟dom那一小节所构建的 JavaScript 对象树和render出来真正的DOM树的信息、结构是一样的。所以我们可以对那棵DOM树也进行深度优先的遍历,遍历的时候从2.1 深度优先遍历,记录差异那一节生成的patches对象中找出当前遍历的节点差异,然后进行 DOM 操作。

    function patch (node, patches) {
      var walker = {index: 0}
      dfsWalk(node, walker, patches)
    }
    
    function dfsWalk (node, walker, patches) {
      var currentPatches = patches[walker.index] // 从patches拿出当前节点的差异
    
      var len = node.childNodes
        ? node.childNodes.length
        : 0
      for (var i = 0; i < len; i++) { // 深度遍历子节点
        var child = node.childNodes[i]
        walker.index++
        dfsWalk(child, walker, patches)
      }
    
      if (currentPatches) {
        applyPatches(node, currentPatches) // 对当前节点进行DOM操作
      }
    }
    

    applyPatches,根据不同类型的差异对当前节点进行 DOM 操作:

    function applyPatches (node, currentPatches) {
      currentPatches.forEach(function (currentPatch) {
        switch (currentPatch.type) {
          case REPLACE:
            node.parentNode.replaceChild(currentPatch.node.render(), node)
            break
          case REORDER:
            reorderChildren(node, currentPatch.moves)
            break
          case PROPS:
            setProps(node, currentPatch.props)
            break
          case TEXT:
            node.textContent = currentPatch.content
            break
          default:
            throw new Error('Unknown patch type ' + currentPatch.type)
        }
      })
    }

    总结

    Virtual DOM 算法主要是实现上面步骤的三个函数:element,diff,patch。然后就可以实际的进行使用:

    
    // 1. 构建虚拟DOM
    var tree = el('div', {'id': 'container'}, [
        el('h1', {style: 'color: blue'}, ['simple virtal dom']),
        el('p', ['Hello, virtual-dom']),
        el('ul', [el('li')])
    ])
    
    // 2. 通过虚拟DOM构建真正的DOM
    var root = tree.render()
    document.body.appendChild(root)
    
    // 3. 生成新的虚拟DOM
    var newTree = el('div', {'id': 'container'}, [
        el('h1', {style: 'color: red'}, ['simple virtal dom']),
        el('p', ['Hello, virtual-dom']),
        el('ul', [el('li'), el('li')])
    ])
    
    // 4. 比较两棵虚拟DOM树的不同
    var patches = diff(tree, newTree)
    
    // 5. 在真正的DOM元素上应用变更
    patch(root, patches)

    当然这是非常粗糙的实践,实际中还需要处理事件监听等;生成虚拟 DOM 的时候也可以加入 JSX 语法。这些事情都做了的话,就可以构造一个简单的ReactJS了。

    参考链接:
    https://www.zhihu.com/question/29504639
    https://zhuanlan.zhihu.com/p/20346379

    展开全文
  • React的虚拟DOMdiff算法的理解

    千次阅读 2018-12-20 18:17:44
    什么是虚拟DOM
  • React(四):虚拟DOM Diff算法解析React中最神奇的部分莫过于虚拟DOM,以及其高效的Diff算法。这让我们可以无需担心性能问题而”毫无顾忌”的随时“刷新”整个页面,由虚拟DOM来确保只对界面上真正变化的部分进行...
  • 浅谈React中的diff

    千次阅读 2018-04-03 13:30:35
     React一个很大一个的设计有点就是将diff和V-dom的完美结合,而高效的diff算法可以让用户更加自由的刷新页面,让开发者也能远离原生dom操作,更加开心的撸代码。 但总所周知,普适diff的复杂度对于大量dom对比会...
  • React:虚拟 DOMDOM Diff 算法React高效原因:基本流程图简单案例源代码运行效果总结详细参考博文: React高效原因: 1.虚拟(virtual)DOM:不总是直接操作实际的DOM元素,而是先修改virtual DOM里的对象 当要...
  • 在现代的前端渲染框架中,Virtual DOM 几乎已经成了标配,通过这样一个缓冲层,我们已经能够实现对 Real DOM 的最少操作,在大家的广泛认知中,操作 DOM 是比较慢的,因此 Virtual DOM 可以实现应用程序的性能提升。...
  • React DOM Diff算法详解

    2019-06-10 18:45:33
    React中文文档 doc.react-china.org/ 前端开发中,原生JS对DOM的频繁操作往往是令人头痛并且十分影响性能的; 而React在设计之初就考虑到了这种需求并将其作为重点,于是也就有了这里要说的Diff算法;可以说Diff是...
  • 本文主要梳理一下我对 React 框架基础内容的认识,之后也会总结一些深度内容的认识。当然,笔者水平也有限,如果你发现不妥之处,望斧正!为什么要用 React 等前端框架因为可以进行组件...
  • 1.面试被问到react与vue中diff算法的区别,请大神赐教 2.在网上查到了vue与react虚拟dom的区别是: 网上答案:virtual DOM不一样,vue会跟踪每一个组件的依赖关系, 不需要重新渲染整个组件树.​​ 而对于React而言,...
  • 虚拟DOM Diff算法解析

    千次阅读 2018-07-24 00:01:00
    React中最神奇的部分莫过于虚拟DOM,以及其高效的Diff算法。这让我们可以无需担心性能问题而”毫无顾忌”的随时“刷新”整个页面,由虚拟DOM来确保只对界面上真正变化的部分进行实际的DOM操作。React在这一部分已经...
  • 作者:chenhongdong链接:https://juejin.im/post/5c8e5e4951882545c109ae9c时至今日,前端对于知识...
  • React:DOM Diff算法

    2018-07-12 16:59:26
    React中最神奇的部分莫过于虚拟DOM,以及其高效的Diff算法。这让我们可以无需担心性能问题而”毫无顾忌”的随时“刷新”整个页面,由虚拟DOM来确保只对界面上真正变化的部分进行实际的DOM操作。React在这一部分已经...
  • React DOM Diff

    2017-09-16 22:25:03
    React中最神奇的部分莫过于虚拟DOM,以及其高效的Diff算法。这让我们可以无需担心性能问题而”毫无顾忌”的随时“刷新”整个页面,由虚拟DOM来确保只对界面上真正变化的部分进行实际的DOM操作。React在这一部分已经...
  • React 16 Diff 算法

    2019-08-04 22:29:30
    我相信在看这篇文章的读者一般都已经了解过 React 16 以前的 Diff 算法了,这个算法也算是 React 跨时代或者说最有影响力的一点了,使 React 在保持了可维护性的基础上性能大大的提高,但 Di...
  • 根据 React 的设计,所有的 DOM 变动,都先在虚拟 DOM 上发生,然后再将实际发生变动的部分,反映在真实 DOM上,这种算法叫做DOM diff,它可以极大提高网页的性能表现。 有时候,我们需要从组件中获取真实的DOM节点...
  • react教程之获取真实的DOM节点

    千次阅读 2016-11-30 19:02:55
    获取真实的DOM节点 ...根据 React 的设计,所有的 DOM 变动,都先在虚拟 DOM 上发生,然后再将实际发生变动的部分,反映在真实 DOM上,这种算法叫做 DOM diff ,它可以极大提高网页的性能表现。 但是,有时
  • 虚拟DOM virtual dom,也就是虚拟节点。它是通过JS的Object对象模拟DOM中的节点,然后再通过特定的render方法将其渲染成真实的DOM节点。 创建虚拟DOM 本文基于react来写,但是其实跟react也没多大关系 通过...
1 2 3 4 5 ... 20
收藏数 5,584
精华内容 2,233
关键字:

domdiff代码 react