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

diff是什么？diff就是比拟两棵树，render 会生成两颗树，一棵新树 newVnode，一棵旧树 oldVnode，而后两棵树进行比照更新找差别就是diff，全称difference，在 vue 外面 diff 算法是通过 patch 函数来实现的，所以有的时候也叫patch 算法

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

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 函数的比照流程

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

具体流程

⏳ diff 产生的机会

🙌 patch 函数的比照流程

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

具体流程

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