《Vue不看源码懂原理》系列——Vue的diff算法不难懂

4,791 阅读8分钟

虚拟DOM

首先要说diff算法之前,还是稍微解释一下虚拟DOM,虽然大部分人都知道虚拟DOM的概念了。

首先,很多人没有意识到一个问题,现代前端框架为我们解决了什么? 我认为前端现代框架解决的是忽略对DOM的操作,让前端人员注重于维护状态。

对于视图更新以往的解决方式是,不关心任何状态,只需要将所有DOM删掉,然后重新生成一份DOM,但是这种访问DOM的方式会造成相当多的性能浪费。

而虚拟DOM在框架中的任务就是通过状态生成相应结构的虚拟节点树,使用新生成的虚拟节点树和上次的虚拟节点树进行对比,当某个状态发生变化时,然后只更新和渲染不同的部分。

在这里插入图片描述
Vue引入虚拟DOM的原因

在Vue1.0中采用了极高的细粒度,每一个绑定一个对应的watcher实例,进行观察状态的变化,但是当状态越多的节点被使用时,会有一些内存开销以及一些依赖追踪的开销。

在Vue2.0以后,引入了虚拟DOM,为单个组件设置一个watcher实例,即使组件内有10个节点,里面状态发生变化时,只会通知到组件,然后组件内部通过虚拟DOM进行对比和渲染。

虚拟DOM的生成

我们来结合之前《Vue不看源码懂原理》系列——Vue模板编译中提到的模板渲染结合起来看。Vue通过编译将模板转换AST,之后将AST转换成渲染函数,执行渲染函数可以得到一个虚拟节点树(vnode),再拿新生成的虚拟节点树去和旧的虚拟节点树(oldVnode)对比,找出更新部分节点,最后做渲染。

在这里插入图片描述
vnode和AST的区别 看过上一篇文章的应该知道AST的概念,那vnode并不是AST,它是通过AST生成的虚拟DOM的节点,它是虚拟DOM的组成部分,通过AST生成的一个javascript对象版本的HTML结构,它和AST一样是一种节点描述对象,里面放了节点的所有信息。

科普完毕,接下来一段用来解释上述中的vnode与oldVnode对比的过程,也就是大家常说的diff算法。

diff算法

diff算法解决的问题是不是暴力修改DOM,而是通过对象对DOM进行更新替换,一般包括三种主要逻辑:

  1. 创建新增节点
  2. 删除废弃节点
  3. 修改需要更新的节点

前两种都相对比较简单,一个一个来说起。

创建新增节点

新增节点最常见的场景就是,当oldVnode不存在这个节点,而vnode存在时,那么代表它是一个全新的节点,需要使用vnode中的新节点去生成真实DOM插入到页面的DOM中。

在这里插入图片描述
除此之外还存在一种情况,当新的vnode和oldVnode完全不是一个节点时,要知道我们是以vnode来渲染新的视图,因此可以得知新的vnode是一个全新的节点,而oldVnode是一个被废弃的节点。这种情况下我们要做的事是创建一个vnode对应的新的DOM节点,去替换掉之前的DOM节点。
在这里插入图片描述
只有3种类型的节点会被创建和插入到DOM中分别对应AST中的元素节点,注释节点,文本节点。

拿元素节点举例,首先判断它是否带有tag属性,如果有那么它就是一个元素节点,调用对应的appendChild方法,将该节点插入到指定的父节点中。需要注意的是创建子节点是一个递归过程,就像你遍历一个对象树一样,我们需要将vnode的chaildren属性进行循环一遍,为每个父节点的子节点也执行一遍创建节点的逻辑。

在这里插入图片描述

删除节点

删除节点的场景比较简单,即上面说到的当存在一个被废弃的节点时,我们除了要插入新的替换节点,也要删除之前的DOM节点。

删除节点的实现逻辑如下:

function removeVnodes(vnodes,startIdx,endIdx){
    for(;startIdx<=endIdx;++startIdx){
      const ch = vnodes[startIdx]
      if(isDef(ch)){
        removeVnode(ch.elm) // 删除单个节点方法
      }
    }
  }

删除节点的逻辑就是删除vnodes数组中从startIdx指定位置到endIdx的内容即可。

更新节点

  1. 在更新节点时,我们首先需要判断两个虚拟节点是否是静态节点,如果是,则直接跳过更新过程。
  2. 如果不是,且两个节点有不同属性时,要以新的vnode为标准进行渲染更新。当节点为text属性时,name不论之前子节点内容是什么,直接调用textContent方法将视图中的DOM节点改成新的vnode所保存的文字。 43 如果没有text属性,那么他一定是一个元素节点(不理解的可以参考上一篇中的AST类型《Vue不看源码懂原理》系列——Vue模板编译)。我们再将更新节点分为两种:1有children。当新的vnode中存在children属性时,我们要先看oldVnode中是否也存在children属性。如果oldVnode中也存在children属性,那么我们要对各个children进行更详细的递归对比。2没有children。如果一个新创建的节点没有text属性也没有children属性时,那么说明这新创建的节点是一个空节点,这时候如果oldVnode中有子节点,就执行子节点的删除操作,有文本就执行文本的删除操作,最后完成视图中空标签的效果。

子节点更新策略

Vue更新子节点的策略基于在比对子节点数组的时候,将接收的参数oldVnode的子节点构成的数组和nvnode的子节点构成的数组进行比较。

两个数组作比较只需要一个双层循环就搞定了,例如现在对oldVnode数组的第一个元素做判断,我要拿着这个元素去和vnode里面的元素一个个比过去,假设在对比到vnode中第三个元素的时候发现连个元素一样,则表示oldVNode数组的第一个元素的位置发生了变化,在新数组中它变到了第三的位置。此时我们可以知道ldVnode数组的第一个元素位置变成了第三。    上面这种方式唯一存在的问题是效率太低。假设oldVnode和vnode有100个子元素,当我们在比较oldVnode的最后一个元素的时候,发现它和vnode中的最后一个元素相同,这其实浪费了很多的计算资源。   因此vue对子节点更新进行了策略优化,Vue为oldVnode和vnode分别添加了一对游标,默认指向数组的第一个和最后一个元素,它实现的是一种从两边向中间查找的一种方式,全量查找至少在时间复杂度上减少了一倍。   

在这里插入图片描述

  • 如果oldStartIdx指向的元素为undefined则oldStartIdx右移,同样的如果oldEndIdx指向的元素不存在则oldEndIdx左移。这个操作的目的是快速去掉vnode左右两端的无效数据。为什么会出现元素值为undefined呢?往下看就知道了。
  • 如果oldStartIdx和newStartIdx是相同元素则对其调用patchVnode。oldStartIdx和newStartIdx都向右移动。 同样的,如果newEndIdx和oldEndIdx是相同元素对其调用patchVNode。newEndIdx和oldEndIdx都向左移动。我们认为很多时候节点变化前后它的子节点数组的首尾元素仍是相同元素。
  • 如果oldStartIdx和newEndIdx是相同元素则对其调用patchVnode,oldStartIdx右移,newEndIdx左移。如果oldEndIdx和newStartIdx是相同元素则对其调用patchVnode,oldEndIdx左移,newStartIdx右移。

diff的核心是递归比较子节点

正常Diff两个树的时间复杂度是O(n * 3),但实际情况下我们很少会进行跨层级的移动DOM,所以Vue将Diff进行了优化,从O(n * 3)> -> O(n),只有当新旧children都为多个子节点时才需要用核心的Diff算法进行同层级比较。 Vue2的核心Diff算法采用了双端比较的算法,同时从新旧children的两端开始进行比较,借助key值找到可复用的节点,再进行相关操作。相比React的Diff算法,同样情况下可以减少移动节点次数,减少不必要的性能损耗,更加的优雅。

key在虚拟DOM的作用

新旧 children 中的节点只有顺序是不同的时候,最佳的操作应该是通过移动元素的位置来达到更新的目的。 需要在新旧 children 的节点中保存映射关系,以便能够在旧children的节点中找到可复用的节点。key也就是children中节点的唯一标识。

到这呢就算把Vue中的节点更新过程就简单讲述一遍,可能有些逻辑讲述的一般,文笔有限。

最好可以结合上一篇一起看《Vue不看源码懂原理》系列——Vue模板编译

感谢点赞鼓励,

也欢迎讨论。