Sunny's blog

Appearance

Return to top
On this page

Vuejs diff 算法

diff的时机

当组件创建时，以及依赖的属性或数据变化时，会运行一个函数，该函数会做两件事：

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

核心代码如下：

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

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

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

_update函数在干什么

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

javascript
function update(vnode) {
  // vnode:新
  // this._vnode:旧
  var oldVnode = this._vnode;
  this._vnode = vnode; //虚拟dom其实在这一步就已经更新了，所以对比的木得是更新真实DOM
}

function update(vnode) {
  // vnode:新
  // this._vnode:旧
  var oldVnode = this._vnode;
  this._vnode = vnode; //虚拟dom其实在这一步就已经更新了，所以对比的木得是更新真实DOM
}

然后会判断旧树是否存在：

不存在

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

javascript
function update(vnode) {
  // vnode: 新
  // this._vnode: 旧
  var oldVnode = this._vnode;
  this._vnode = vnode;
  // 对比的目的：更新真实dom
  if (!oldVnode) {
    this.__patch__(this.$el, vnode); //el：元素位置
  }
}

function update(vnode) {
  // vnode: 新
  // this._vnode: 旧
  var oldVnode = this._vnode;
  this._vnode = vnode;
  // 对比的目的：更新真实dom
  if (!oldVnode) {
    this.__patch__(this.$el, vnode); //el：元素位置
  }
}

存在

说明之前已经渲染过该组件，于是通过内部的patch函数，对新旧两棵树进行对比，以达到下面两个目标：

  • 完成对所有真实 dom 的最小化处理
  • 让新树的节点对应合适的真实 dom

patch函数的对比流程

术语解释：

  1. 「相同」：是指两个虚拟节点的标签类型、key值均相同，但input元素还要看type属性
javascript
/**
 * 什么叫「相同」是指两个虚拟节点的标签类型、`key`值均相同，但`input`元素还要看`type`属性
 *
 * <h1>asdfdf</h1>        <h1>asdfasfdf</h1>    相同
 *
 * <h1 key="1">adsfasdf</h1>   <h1 key="2">fdgdf</h1> 不同
 *
 * <input type="text" />    <input type="radio" /> 不同
 *
 * abc        bcd  相同
 *
 * {
 *  tag: undefined,
 *  key: undefined,
 *  text: "abc"
 * }
 *
 * {
 *  tag: undefined,
 *  key: undefined,
 *  text: "bcd"
 * }
 */

// 这里的判断相同使用到的是sameVnode函数：源码
function sameVnode(a, b) {
  return (
    a.key === b.key &&
    ((a.tag === b.tag &&
      a.isComment === b.isComment &&
      isDef(a.data) === isDef(b.data) &&
      sameInputType(a, b)) ||
      (isTrue(a.isAsyncPlaceholder) &&
        a.asyncFactory === b.asyncFactory &&
        isUndef(b.asyncFactory.error)))
  );
}

/**
 * 什么叫「相同」是指两个虚拟节点的标签类型、`key`值均相同，但`input`元素还要看`type`属性
 *
 * <h1>asdfdf</h1>        <h1>asdfasfdf</h1>    相同
 *
 * <h1 key="1">adsfasdf</h1>   <h1 key="2">fdgdf</h1> 不同
 *
 * <input type="text" />    <input type="radio" /> 不同
 *
 * abc        bcd  相同
 *
 * {
 *  tag: undefined,
 *  key: undefined,
 *  text: "abc"
 * }
 *
 * {
 *  tag: undefined,
 *  key: undefined,
 *  text: "bcd"
 * }
 */

// 这里的判断相同使用到的是sameVnode函数：源码
function sameVnode(a, b) {
  return (
    a.key === b.key &&
    ((a.tag === b.tag &&
      a.isComment === b.isComment &&
      isDef(a.data) === isDef(b.data) &&
      sameInputType(a, b)) ||
      (isTrue(a.isAsyncPlaceholder) &&
        a.asyncFactory === b.asyncFactory &&
        isUndef(b.asyncFactory.error)))
  );
}
  1. 「新建元素」：是指根据一个虚拟节点提供的信息，创建一个真实 dom 元素，同时挂载到虚拟节点的elm属性上
  2. 「销毁元素」：是指：vnode.elm.remove()
  3. 「更新」：是指对两个虚拟节点进行对比更新，它仅发生在两个虚拟节点「相同」的情况下。具体过程稍后描述。
  4. 「对比子节点」：是指对两个虚拟节点的子节点进行对比，具体过程稍后描述(深度优先)

详细流程：

根节点比较

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

如果两个节点：

  • 「相同」，进入「更新」流程
    1. 将旧节点的真实 dom 赋值到新节点：newVnode.elm = oldVnode.elm
    2. 对比新节点和旧节点的属性，有变化的更新到真实 dom 中
    3. 当前两个节点处理完毕，开始「对比子节点」
  • 不「相同」 （直接看成旧树不存在）
    1. 新节点递归「新建元素」
    2. 旧节点「销毁元素」

「对比子节点」

在「对比子节点」时，vue 一切的出发点，都是为了：

  • 尽量啥也别做
  • 不行的话，尽量仅改动元素属性
  • 还不行的话，尽量移动元素，而不是删除和创建元素
  • 还不行的话，删除和创建元素

流程

  • 对比旧树和新树的头指针，一样就进入更新流程(递归)新旧相连，对比有没有属性变化，对比子节点(递归)

  • 两个头指针往后移动，如果不一样，就比较尾指针，尾指针一样，递归。

  • 两个尾指针往前移动，再次比较头指针，还是不一样，尾指针也不一样，就比较旧树的头和新树的尾，一样的话，连接，复用真实都 dom，更新属性，再把真实 dom 的位置移动到旧树的尾指针后

  • 新指针的尾指针往前移动，旧指针的头指针往后移动，头头不同，尾尾不同，两边的头尾不同，则以新树的头为基准，看一下在旧树里面存不存在，存在则复用，真实 dom 的位置调到前面。

  • 继续，头头不同，尾尾不同，头尾相同，同理交换，交换后把真实 dom 移动到头指针前面。

  • 继续，都不相同了，找 8 在旧树里面存不存在，不存在就新建。继续移动，头指针>尾指针，循环结束。

  • 销毁旧树剩下的对应的真实 dom。

对开发的影响：

加 key

为什么要 key？如果不加，会把所有子元素直接改动，浪费效率；如果加上，变成了指针，dom 移动(没有改动真实 dom 内部)，对真实 dom 几乎没有改动

html
<div id="app" style="width: 500px; margin: 0 auto; line-height: 3">
  <div>
    <a href="" @click.prevent="accoutLogin=true">账号登录</a>
    <span>|</span>
    <a href="" @click.prevent="accoutLogin=false">手机号登录</a>
  </div>
  <!-- 根据accoutLogin是否显示，如果没有key，默认key:undefined,新旧树的div没变，进入里面对比，里面也相同，会导致文本框里的内容不消失 -->
  <div v-if="accoutLogin" key="1">
    <label>账号</label>
    <input type="text" />
  </div>
  <div v-else key="2">
    <label>手机号</label>
    <input type="text" />
  </div>
</div>

<div id="app" style="width: 500px; margin: 0 auto; line-height: 3">
  <div>
    <a href="" @click.prevent="accoutLogin=true">账号登录</a>
    <span>|</span>
    <a href="" @click.prevent="accoutLogin=false">手机号登录</a>
  </div>
  <!-- 根据accoutLogin是否显示，如果没有key，默认key:undefined,新旧树的div没变，进入里面对比，里面也相同，会导致文本框里的内容不消失 -->
  <div v-if="accoutLogin" key="1">
    <label>账号</label>
    <input type="text" />
  </div>
  <div v-else key="2">
    <label>手机号</label>
    <input type="text" />
  </div>
</div>

总结

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

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

在对比时，vue 采用深度优先、同层比较的方式进行比对。

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

具体来说

  • 首先对根节点进行对比，如果相同则将旧节点关联的真实 dom 的引用挂到新节点上，然后根据需要更新属性到真实 dom

  • 然后再对比其子节点数组；如果不相同，则按照新节点的信息递归创建所有真实 dom，同时挂到对应虚拟节点上，然后移除掉旧的 dom。

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

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

注意：

  • 在给 vue 中的元素设置 key 值时可以使用 Math 的 random 方法么？

random 是生成随机数，有一定概率多个 item 会生成相同的值，不能保证唯一。

如果是根据数据来生成 item，数据具有 id 属性，那么就可以使用 id 来作为 key。

如果不是根据数据生成 item，那么最好的方式就是使用时间戳来作为 key。或者使用诸如 uuid 之类的库来生成唯一的 id。

  • 为什么不建议用 index 作为 key?

使用 index 作为 key 和没写基本上没区别，因为不管数组的顺序怎么颠倒，index 都是 0, 1, 2...这样排列， 导致 Vue 会复用错误的旧子节点，做很多额外的工作。

对比 Vue3

简单来说，diff 算法有以下过程

  • 同级比较，再比较子节点
  • 先判断一方有子节点一方没有子节点的情况(如果新的 children 没有子节点，将旧的子节点移除)
  • 比较都有子节点的情况(核心 diff)
  • 递归比较子节点

正常 Diff 两个树的时间复杂度是 O(n^3)，但实际情况下我们很少会进行跨层级的移动 DOM，所以 Vue 将 Diff 进行了优化，从O(n^3) -> O(n)，只有当新旧 children 都为多个子节点时才需要用核心的 Diff 算法进行同层级比较。

Vue2 的核心 Diff 算法采用了双端比较的算法，同时从新旧 children 的两端开始进行比较，借助 key 值找到可复用的节点，再进行相关操作。相比 React 的 Diff 算法，同样情况下可以减少移动节点次数，减少不必要的性能损耗，更加的优雅。

Vue3.x 借鉴了 ivi 算法和 inferno 算法

在创建 VNode 时就确定其类型，以及在 mount/patch 的过程中采用位运算来判断一个 VNode 的类型，在这个基础之上再配合核心的 Diff 算法，使得性能上较 Vue2.x 有了提升。该算法中还运用了动态规划的思想求解最长递归子序列。

Copyright © 2022-present sunny-117