vlambda博客
学习文章列表

请阐述 vue 的 diff 算法

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

⏳ diff 发生的时机

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

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

  • 运行 _render生成一颗新的虚拟dom树（vnode tree）
  • 运行 _updata，传入_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>

对比oldVnode和vnode就行了，对比的目的就是更新真实dom

image.png

接下来，会判断旧树oldVnode是否存在：

  • 不存在：说明这是第一次加载组件，于是通过内部的patch函数，直接遍历新树，为每个节点生成真实DOM，然后挂载到每个节点的 elm属性上
请阐述 vue 的 diff 算法
image.png

简单用代码表示：

<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 算法
image.png

🙌 patch函数的对比流程

术语解释： 一会看到以下字眼，均代表以下意思

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

请阐述 vue 的 diff 算法
image.png

例：两个虚拟节点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 算法
image.png

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

如果两个节点：

  • 「相同」，进入 「更新」 流程
  1. 将旧节点的真实dom赋值到新节点： newVnode.elm = oldVnode.elem，旧节点会被垃圾回收机制回收
  2. 对比新节点和旧节点的属性，有变化的更新到真实dom中
  3. 当前新旧两个节点处理完成，开始 「对比子节点」
  • 不 「相同」
  1. 新节点 递归， 「新建元素」
  2. 旧节点 「销毁元素」

对比子节点

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

  • 尽量啥也别做

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

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

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

对比流程：

请阐述 vue 的 diff 算法
未命名绘图.png

图片说明：

  • 黄色圆圈：表示旧子节点和新子节点所对应的相同节点类型
  • 数字：表示key值，用来区分是不是同一个节点
  • 蓝色方块：表示对比之前旧子节点所对应的真实dom
  • 箭头：分别表示头指针和尾指针

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

步骤：

  1. 首先对比新树和旧树的头指针，瞅瞅两个节点是否一样，从图中可以看到是一样的，如果一样则进入 「更新」 流程：先将旧节点的真实dom赋值到新节点（真实dom连线到新子节点），然后循环对比新旧节点的属性，看看有没有不一样的地方，将有变化的更新到真实dom中，最后还要采用深度优先（一颗树的节点走到尽头，再走另一个节点）的方式递归循环这两个新旧子节点是否还有子节点，如果存在，则同理，这里我们就假设它不存子节点。 灰色表示已经处理完成，然后两个头指针往后移动
请阐述 vue 的 diff 算法
未命名绘图.png
  1. 接下来，继续比较两个头指针，看看两个节点是否一样，很明显，两个节点是不一样的，因为key值不同，不一样的时候它不会销毁删除从建立，吃个🍗压压惊，淡定！前面有提到尽量别操作dom，它一定会找到一样的节点，一条道走到黑，然后会对比尾指针，可以看到尾指针是一样的，跟第一步是一样的： 一顿操作猛如虎，先将旧节点的真实dom赋值到新节点（真实dom连线到新子节点），然后循环对比新旧节点的属性，将有变化的更新到真实dom中，接着还要递归循环这两个新旧子节点是否还有子节点，最后两个尾指针往前移动
请阐述 vue 的 diff 算法
未命名绘图.png
  1. 然后继续比较头指针，很明显不一样，尾指针呢？也不一样，因为key值还是不一样。随后它会比较头指针和尾指针，看看是否一样，可以看到旧节点的圆2头指针和新节点圆2尾指针是一样的，所以操作跟前两步是一样的，又是 一顿操作猛如虎，结果如下图：
请阐述 vue 的 diff 算法
未命名绘图.png

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

请阐述 vue 的 diff 算法
未命名绘图.png
  1. 继续比对，新旧头指针不同，尾指针不同，两个头尾也不同，然后它会以新树头指针为基准，循环旧虚拟子节点，看看新树圆3是否存在于旧虚拟子节点，存在的话在哪个位置，找到之后进行复用，连线，有变化的地方更新到真实dom，操作跟前面几步一样，真实dom也要进行 位置移动，移动到旧树头指针之前。随后新树头指针继续往后移动到圆9位置，如下图:
请阐述 vue 的 diff 算法
未命名绘图.png
  1. 继续比对，新旧头指针不同，尾指针不同，但新树头指针和旧树尾指针相同，操作跟前面几步相同，但依然需要进行位置移动，移动到旧树头指针之前。随后新树头指针往后移动，与新树尾指针重合，旧树尾指针向前移动到圆1位置，如下图：
请阐述 vue 的 diff 算法
未命名绘图.png
  1. 继续比对，新旧两树头指针不同，尾指针不同，两个头尾也不同，然后它以新树头指针为基准，循环旧虚拟子节点，找圆8在旧树中存不存在，从图中可以看出，并不存在，这个时候确实没办法了，只能 「新建元素」。随后新树头指针继续向后移动到圆2位置，如图：
请阐述 vue 的 diff 算法
未命名绘图.png
  1. 当头指针移动到圆2位置时，头指针已经不再是有效的了，当头指针超过尾指针的时候，循环结束，从过程我们可以看到新树先循环完成，但是旧树还有剩余的节点，这说明旧树中剩余的节点都是应该被删除的节点，所对应的真实dom也会被移除
请阐述 vue 的 diff 算法
未命名绘图.png

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

未命名绘图.png

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

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

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

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

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

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

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

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

- EOF -

推荐阅读   点击标题可跳转

1、

2、

3、


觉得本文对你有帮助？请分享给更多人

推荐关注「前端大全」，提升前端技能

点赞和在看就是最大的支持❤️

推荐阅读

[5.05] 暗喻幻想港中35周年限定版1.03+DLC+金手指+王中王存档 [5.05] 暗喻幻想港中35周年限定版1.03+DLC+金手指+王中王存档
苹果开源项目C++代码泄漏疑似AR/VR操作系统的代码引用 苹果开源项目C++代码泄漏疑似AR/VR操作系统的代码引用

相关文章