关于前端:请阐述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

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

不存在：阐明这是第一次加载组件，于是通过外部的patch函数，间接遍历新树，为每个节点生成实在DOM，而后挂载到每个节点的elm属性上

简略用代码示意：

<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函数，对新旧两棵树进行比照，从而达到上面两个指标：

实现对所有实在dom的最小化解决
让新树的节点对应适合的实在dom

🙌 patch函数的比照流程

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

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

例：两个虚构节点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.「比照子节点」：是指对两个虚构节点的子节点进行比照，具体过程稍后形容

具体流程

根节点比拟

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

如果两个节点：

「雷同」，进入 「更新」 流程

将旧节点的实在dom赋值到新节点：newVnode.elm = oldVnode.elem，旧节点会被垃圾回收机制回收
比照新节点和旧节点的属性，有变动的更新到实在dom中
以后新旧两个节点解决实现，开始 「比照子节点」

不 「雷同」

新节点递归， 「新建元素」
旧节点 「销毁元素」

比照子节点

虚构dom树曾经实现，就剩批改实在dom了，然而批改实在dom的效率是比拟耗时的，vue的准则是能不改就不改，尽量啥也别做，在「比照子节点」时，vue所有的出发点，都是为了：

尽量啥也别做
不行的话，尽量仅改变元素属性
还不行的话，尽量挪动元素，而不是删除和创立元素
切实不行的话，删除和创立元素

比照流程：

图片说明：

黄色圆圈：示意旧子节点和新子节点所对应的雷同节点类型
数字：示意key值，用来辨别是不是同一个节点
蓝色方块：示意比照之前旧子节点所对应的实在dom
箭头：别离示意头指针和尾指针

接下来，咱们要做的就是比照旧子节点和新子节点之间的差别，指标是扭转实在dom，并且将新虚构子节点对应到实在dom外面去，vue应用两个指针别离指向新旧子节点树的头和尾

步骤：

首先比照新树和旧树的头指针，瞅瞅两个节点是否一样，从图中能够看到是一样的，如果一样则进入 「更新」 流程：先将旧节点的实在dom赋值到新节点（实在dom连线到新子节点），而后循环比照新旧节点的属性，看看有没有不一样的中央，将有变动的更新到实在dom中，最初还要采纳深度优先（一颗树的节点走到止境，再走另一个节点）的形式递归循环这两个新旧子节点是否还有子节点，如果存在，则同理，这里咱们就假如它不存子节点。灰色示意曾经解决实现，而后两个头指针往后挪动

接下来，持续比拟两个头指针，看看两个节点是否一样，很显著，两个节点是不一样的，因为key值不同，不一样的时候它不会销毁删除从建设，吃个🍗压压惊，淡定！后面有提到尽量别操作dom，它肯定会找到一样的节点，一条道走到黑，而后会比照尾指针，能够看到尾指针是一样的，跟第一步是一样的：一顿操作猛如虎，先将旧节点的实在dom赋值到新节点（实在dom连线到新子节点），而后循环比照新旧节点的属性，将有变动的更新到实在dom中，接着还要递归循环这两个新旧子节点是否还有子节点，最初两个尾指针往前挪动

而后持续比拟头指针，很显著不一样，尾指针呢？也不一样，因为key值还是不一样。随后它会比拟头指针和尾指针，看看是否一样，能够看到旧节点的圆2头指针和新节点圆2尾指针是一样的，所以操作跟前两步是一样的，又是一顿操作猛如虎，后果如下图：

这里咱们要留神的是实在dom必须和新虚构子节点要一一对应上的，所以除了更新变动的中央之外还要进行地位挪动，挪动到旧树尾指针的前面，最初旧树头指针往后挪动，新树尾指针往前挪动，如下图：

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

持续比对，新旧头指针不同，尾指针不同，但新树头指针和旧树尾指针雷同，操作跟后面几步雷同，但仍然须要进行地位挪动，挪动到旧树头指针之前。随后新树头指针往后挪动，与新树尾指针重合，旧树尾指针向前挪动到圆1地位，如下图：

持续比对，新旧两树头指针不同，尾指针不同，两个头尾也不同，而后它以新树头指针为基准，循环旧虚构子节点，找圆8在旧树中存不存在，从图中能够看出，并不存在，这个时候的确没方法了，只能 「新建元素」。随后新树头指针持续向后挪动到圆2地位，如图：

当头指针挪动到圆2地位时，头指针曾经不再是无效的了，当头指针超过尾指针的时候，循环完结，从过程咱们能够看到新树先循环实现，然而旧树还有残余的节点，这阐明旧树中残余的节点都是应该被删除的节点，所对应的实在dom也会被移除

最终实在dom生成结束，整个过程咱们只新建了一个元素，如下图：

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

当组件创立和更新时，vue会执行外部的update函数，该函数应用render函数生成的虚构dom树，将新旧两树进行比照，找到差别点，最终更新到实在dom

比照差别的过程叫diff，vue在外部通过一个叫patch的函数实现该过程

在比照时，vue采纳深度优先、同级比拟的形式进行比对。同级比拟就是说它不会逾越构造进行比拟

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

具体来说，首先对根节点进行比照，如果雷同则将旧节点关联的实在dom的援用挂到新节点上，而后依据须要更新属性到实在dom，而后再比照其子节点数组；如果不雷同，则依照新节点的信息递归创立所有实在dom，同时挂到对应虚构节点上，而后移除掉旧的dom。

在比照其子节点数组时，vue对每个子节点数组应用了两个指针，别离指向头尾，而后一直向两头聚拢来进行比照，这样做的目标是尽量复用实在dom，尽量少的销毁和创立实在dom。如果发现雷同，则进入和根节点一样的比照流程，如果发现不同，则挪动实在dom到适合的地位。

这样始终递归的遍历上来，直到整棵树实现比照。

😊 好了，以上就是我的分享，大家对于diff算法还有其它了解的话能够在评论区探讨鸭～

心愿小伙伴们点赞 👍 反对一下哦～ 😘，我会更有能源的 🤞

关于前端:请阐述vue的diff算法

⏳ diff 产生的机会

🙌 patch函数的比照流程

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

具体流程

评论

发表回复取消回复

更多文章

DDN HPC 存储硬件架构设计深度分析

探秘IO500：从Lustre并行文件系统出发，开启HPC存储性能新征程

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

关于前端:请阐述vue的diff算法

⏳ diff 产生的机会

🙌 patch函数的比照流程

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

具体流程

评论

发表回复 取消回复

更多文章

DDN HPC 存储硬件架构设计深度分析

探秘IO500：从Lustre并行文件系统出发，开启HPC存储性能新征程

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

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

发表回复取消回复