Vue - diff 算法

Souleigh ✨ 等级 101 0 1

diff是什么?diff就是比较两棵树,render会生成两颗树,一棵新树newVnode,一棵旧树oldVnode,然后两棵树进行对比更新找差异就是diff,全称difference,在vue里面 diff 算法是通过patch函数来完成的,所以有的时候也叫patch算法

⏳ diff 发生的时机

diff发生在什么时候呢?当然我们可以说在数据更新的时候发生diff,因为数据更新会运行render函数得到虚拟dom树,最后页面重新渲染。

当组件创建的时候,组件所依赖的属性或者数据变化时,会运行一个函数 (下面代码中的updateComponent),该函数会做两件事:

  • 运行_render生成一颗新的虚拟dom树(vnode tree)

  • 运行_update,传入_render生成的虚拟dom树的根节点,对新旧两棵树进行对比,最终完成对真实dom的更新

核心代码如下,跟原代码有所差异,但都差不多,是这么个意思:

// vue构造函数  
function Vue(){  
  // ... 其他代码  
  var updateComponent = () => {  
    this._update(this._render());  
  }  
  new Watcher(updateComponent);  
  // ... 其他代码  
}  

diff就发生在_update函数的运行过程中

代码中先调用_render函数得到虚拟dom根节点,然后传入_update函数中,在将updateComponent传入Watcher中,watcher可以监听函数执行的过程,监测函数执行期间用到了哪些响应式数据并且进行依赖收集,关于watcher可以瞅瞅我上一篇文章:一文带你了解vue2之响应式原理

🔨 _update函数在干什么?

_update函数会接收到一个vonde参数,这就是生成的虚拟dom树,同时,_update函数通过当前组件的_vnode属性,拿到的虚拟dom树。_update函数首先会给组件的_vnode属性重新赋值,让它指向新树

简单用代码表示:

function update(vnode){  
    //vnode新树  
    //this._vnode旧树  
    this._vnode = vnode  
}  

如果只考虑更新虚拟dom树,这一步已经完成了,但是最终目的是要更新页面,所以就要用到diff进行树的节点对比,所以可以保存下旧树oldVnode用于对比

简单用代码表示:

<body>  
    <div id="app"></div>  
    <script src="./vue.js"></script>  
    <script> const vm = new Vue({  
        el: "#app",  
      });  


      function update(vnode) {  
        //vnode新树  
        //this._vnode旧树  

        let oldVnode = vm._vnode; //保存旧树  

        this._vnode = vnode; //更新新树  
      } </script>  
  </body>

对比oldVnodevnode就行了,对比的目的就是更新真实dom

Vue - diff 算法

接下来,会判断旧树oldVnode是否存在:

  • 不存在:说明这是第一次加载组件,于是通过内部的patch函数,直接遍历新树,为每个节点生成真实DOM,然后挂载到每个节点的elm属性上

Vue - diff 算法

简单用代码表示:

<body>  
    <div id="app"></div>  
    <script src="./vue.js"></script>  
    <script> const vm = new Vue({  
        el: "#app",  
      });  
      console.log(vm);  

      function update(vnode) {  
        //vnode新树  
        //this._vnode旧树  
        let oldVnode = vm._vnode; //保存旧树  
        this._vnode = vnode; //更新新树  

        //如果旧树oldVnode不存在  
        if(!oldVnode){  
            this.__patch__(vm.$el,vnode);  
        }  
      } </script>  
  </body>  
  • 存在:说明之前已经渲染过该组件,于是通过内部的patch函数,对新旧两棵树进行对比,从而达到下面两个目标:
  1. 完成对所有真实dom的最小化处理

  2. 让新树的节点对应合适的真实dom

Vue - diff 算法

🙌 patch函数的对比流程

术语解释

一会看到以下字眼,均代表以下意思

1.「相同」:是指两个虚拟节点的标签类型和key值均相同,但input元素还要看type属性。这个术语在vue源码中叫sameVnode,它是一个函数,用来判断两个虚拟节点是不是同一个节点

Vue - diff 算法

例:两个虚拟节点div是否相同

<div>法医</div>  
<div>前端猎手</div>  

标签类型都为div,key值不仅仅在v-for遍历中,也可以用在任何标签中,上面两个div中没有key值,所以都为undefined,所以标签类型和key值都相同,不用看内容是否相同,它是另一个节点:文本节点

<div key="fayi">法医</div>  
<div key="qdls">前端猎手</div>  

上面两个虚拟节点是不同的,因为key值不同

<input type="text">  
<input type="radio">

上面两个虚拟节点是不同的,因为input不仅仅要看key值和标签类型,还要看type是否相同

2.「新建元素」:是指根据一个虚拟节点提供的信息,创建一个真实dom元素,同时挂载到虚拟节点的elm属性上

3.「销毁元素」:是指:vnode.elm.remove()

4.「更新」:是指对两个虚拟节点进行对比更新,它仅发生在两个虚拟节点「相同」的情况下。具体过程稍后描述。

5.「对比子节点」:是指对两个虚拟节点的子节点进行对比,具体过程稍后描述

详细流程

根节点比较

Vue - diff 算法

patch函数首先对根节点进行对比

如果两个节点:

  • 「相同」,进入 「更新」 流程
  1. 将旧节点的真实dom赋值到新节点:newVnode.elm = oldVnode.elem,旧节点会被垃圾回收机制回收

  2. 对比新节点和旧节点的属性,有变化的更新到真实dom中

  3. 当前新旧两个节点处理完成,开始 「对比子节点」

  • 「相同」
  1. 新节点递归「新建元素」

  2. 旧节点 「销毁元素」

对比子节点

虚拟dom树已经完成,就剩修改真实dom了,但是修改真实dom的效率是比较耗时的,vue的原则是能不改就不改,尽量啥也别做,在「对比子节点」时,vue一切的出发点,都是为了:

  • 尽量啥也别做

  • 不行的话,尽量仅改动元素属性

  • 还不行的话,尽量移动元素,而不是删除和创建元素

  • 实在不行的话,删除和创建元素

对比流程:

Vue - diff 算法

图片说明:

  • 黄色圆圈:表示旧子节点和新子节点所对应的相同节点类型

  • 数字:表示key值,用来区分是不是同一个节点

  • 蓝色方块:表示对比之前旧子节点所对应的真实dom

  • 箭头:分别表示头指针和尾指针

接下来,我们要做的就是对比旧子节点新子节点之间的差异,目标是改变真实dom,并且将新虚拟子节点对应到真实dom里面去,vue使用两个指针分别指向新旧子节点树的头和尾

步骤:

  1. 首先对比新树和旧树的头指针,瞅瞅两个节点是否一样,从图中可以看到是一样的,如果一样则进入 「更新」 流程:先将旧节点的真实dom赋值到新节点(真实dom连线到新子节点),然后循环对比新旧节点的属性,看看有没有不一样的地方,将有变化的更新到真实dom中,最后还要采用深度优先(一颗树的节点走到尽头,再走另一个节点)的方式递归循环这两个新旧子节点是否还有子节点,如果存在,则同理,这里我们就假设它不存子节点。灰色表示已经处理完成,然后两个头指针往后移动

Vue - diff 算法

  1. 接下来,继续比较两个头指针,看看两个节点是否一样,很明显,两个节点是不一样的,因为key值不同,不一样的时候它不会销毁删除从建立,吃个🍗压压惊,淡定!前面有提到尽量别操作dom,它一定会找到一样的节点,一条道走到黑,然后会对比尾指针,可以看到尾指针是一样的,跟第一步是一样的:一顿操作猛如虎,先将旧节点的真实dom赋值到新节点(真实dom连线到新子节点),然后循环对比新旧节点的属性,将有变化的更新到真实dom中,接着还要递归循环这两个新旧子节点是否还有子节点,最后两个尾指针往前移动

Vue - diff 算法

  1. 然后继续比较头指针,很明显不一样,尾指针呢?也不一样,因为key值还是不一样。随后它会比较头指针和尾指针,看看是否一样,可以看到旧节点的圆2头指针和新节点圆2尾指针是一样的,所以操作跟前两步是一样的,又是一顿操作猛如虎,结果如下图:

Vue - diff 算法

这里我们要注意的是真实dom必须和新虚拟子节点要一一对应上的,所以除了更新变化的地方之外还要进行位置移动,移动到旧树尾指针的后面,最后旧树头指针往后移动,新树尾指针往前移动,如下图:

Vue - diff 算法

  1. 继续比对,新旧头指针不同,尾指针不同,两个头尾也不同,然后它会以新树头指针为基准,循环旧虚拟子节点,看看新树圆3是否存在于旧虚拟子节点,存在的话在哪个位置,找到之后进行复用,连线,有变化的地方更新到真实dom,操作跟前面几步一样,真实dom也要进行位置移动,移动到旧树头指针之前。随后新树头指针继续往后移动到圆9位置,如下图:

Vue - diff 算法

  1. 继续比对,新旧头指针不同,尾指针不同,但新树头指针和旧树尾指针相同,操作跟前面几步相同,但依然需要进行位置移动,移动到旧树头指针之前。随后新树头指针往后移动,与新树尾指针重合,旧树尾指针向前移动到圆1位置,如下图:

Vue - diff 算法

  1. 继续比对,新旧两树头指针不同,尾指针不同,两个头尾也不同,然后它以新树头指针为基准,循环旧虚拟子节点,找圆8在旧树中存不存在,从图中可以看出,并不存在,这个时候确实没办法了,只能 「新建元素」。随后新树头指针继续向后移动到圆2位置,如图:

Vue - diff 算法

  1. 当头指针移动到圆2位置时,头指针已经不再是有效的了,当头指针超过尾指针的时候,循环结束,从过程我们可以看到新树先循环完成,但是旧树还有剩余的节点,这说明旧树中剩余的节点都是应该被删除的节点,所对应的真实dom也会被移除

Vue - diff 算法

最终真实dom生成完毕,整个过程我们只新建了一个元素,如下图:

Vue - diff 算法

在面试的时候也会被问到关于diff算法的问题,以下是参考回答:

当组件创建和更新时,vue会执行内部的update函数,该函数使用render函数生成的虚拟dom树,将新旧两树进行对比,找到差异点,最终更新到真实dom

对比差异的过程叫diff,vue在内部通过一个叫patch的函数完成该过程

在对比时,vue采用深度优先、同级比较的方式进行比对。同级比较就是说它不会跨越结构进行比较

在判断两个节点是否相同时,vue是通过虚拟节点的key和tag来进行判断的

具体来说,首先对根节点进行对比,如果相同则将旧节点关联的真实dom的引用挂到新节点上,然后根据需要更新属性到真实dom,然后再对比其子节点数组;如果不相同,则按照新节点的信息递归创建所有真实dom,同时挂到对应虚拟节点上,然后移除掉旧的dom。

在对比其子节点数组时,vue对每个子节点数组使用了两个指针,分别指向头尾,然后不断向中间靠拢来进行对比,这样做的目的是尽量复用真实dom,尽量少的销毁和创建真实dom。如果发现相同,则进入和根节点一样的对比流程,如果发现不同,则移动真实dom到合适的位置。

这样一直递归的遍历下去,直到整棵树完成对比。

收藏
评论区