Vuejs diff 算法

`diff`的时机

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

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

核心代码如下：

1// vue构造函数
2function Vue() {
3  // ... 其他代码
4  var updateComponent = () => {
5    this._update(this._render());
6  };
7  new Watcher(updateComponent);
8  // ... 其他代码
9}

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

`_update`函数在干什么

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

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

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

不存在

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

1function update(vnode) {
2  // vnode: 新
3  // this._vnode: 旧
4  var oldVnode = this._vnode;
5  this._vnode = vnode;
6  // 对比的目的：更新真实dom
7  if (!oldVnode) {
8    this.__patch__(this.$el, vnode); //el：元素位置
9  }
10}

存在

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

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

`patch`函数的对比流程

术语解释：

「相同」：是指两个虚拟节点的标签类型、key值均相同，但input元素还要看type属性

1/**
2 * 什么叫「相同」是指两个虚拟节点的标签类型、`key`值均相同，但`input`元素还要看`type`属性
3 *
4 * <h1>asdfdf</h1>        <h1>asdfasfdf</h1>    相同
5 *
6 * <h1 key="1">adsfasdf</h1>   <h1 key="2">fdgdf</h1> 不同
7 *
8 * <input type="text" />    <input type="radio" /> 不同
9 *
10 * abc        bcd  相同
11 *
12 * {
13 *  tag: undefined,
14 *  key: undefined,
15 *  text: "abc"
16 * }
17 *
18 * {
19 *  tag: undefined,
20 *  key: undefined,
21 *  text: "bcd"
22 * }
23 */
24
25// 这里的判断相同使用到的是sameVnode函数：源码
26function sameVnode(a, b) {
27  return (
28    a.key === b.key &&
29    ((a.tag === b.tag &&
30      a.isComment === b.isComment &&
31      isDef(a.data) === isDef(b.data) &&
32      sameInputType(a, b)) ||
33      (isTrue(a.isAsyncPlaceholder) &&
34        a.asyncFactory === b.asyncFactory &&
35        isUndef(b.asyncFactory.error)))
36  );
37}

「新建元素」：是指根据一个虚拟节点提供的信息，创建一个真实 dom 元素，同时挂载到虚拟节点的elm属性上
「销毁元素」：是指：vnode.elm.remove()
「更新」：是指对两个虚拟节点进行对比更新，它仅发生在两个虚拟节点「相同」的情况下。具体过程稍后描述。
「对比子节点」：是指对两个虚拟节点的子节点进行对比，具体过程稍后描述(深度优先)

详细流程：

根节点比较

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

如果两个节点：

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

「对比子节点」

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

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

流程

对比旧树和新树的头指针，一样就进入更新流程(递归)新旧相连，对比有没有属性变化，对比子节点(递归)
两个头指针往后移动，如果不一样，就比较尾指针，尾指针一样，递归。
两个尾指针往前移动，再次比较头指针，还是不一样，尾指针也不一样，就比较旧树的头和新树的尾，一样的话，连接，复用真实都 dom，更新属性，再把真实 dom 的位置移动到旧树的尾指针后
新指针的尾指针往前移动，旧指针的头指针往后移动，头头不同，尾尾不同，两边的头尾不同，则以新树的头为基准，看一下在旧树里面存不存在，存在则复用，真实 dom 的位置调到前面。
继续，头头不同，尾尾不同，头尾相同，同理交换，交换后把真实 dom 移动到头指针前面。
继续，都不相同了，找 8 在旧树里面存不存在，不存在就新建。继续移动，头指针>尾指针，循环结束。
销毁旧树剩下的对应的真实 dom。

对开发的影响：

加 key

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

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

为什么不用 index 作为 key

1<template>
2  <div id="app">
3    <ul>
4      <li v-for="item in list" :key="item.index">{{ item }}</li>
5    </ul>
6    <button @click="add">添加</button>
7  </div>
8</template>
9<script setup>
10import { ref } from "vue";
11// 我们发现添加操作导致的整个列表的重新渲染，按道理来说，Diff 算法会复用后面的三项，
12// 因为它们只是位置发生了变化，内容并没有改变。但是我们回过头来发现，
13// 我们在前面添加了一项，导致后面三项的 index 变化，从而导致 key 值发生变化。Diff 算法失效了
14const list = ref(["html", "css", "js"]);
15const add = () => {
16  list.value.unshift("阳阳羊");
17};
18</script>

解决：只要不是索引即可，比如，直接使用 item。这样，key 就是永远不变的，更新前后都是一样的，并且又由于节点的内容本来就没变，所以 Diff 算法完美生效，只需将新节点添加到真实 DOM 就行了。

总结

当组件创建和更新时，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 有了提升。该算法中还运用了动态规划的思想求解最长递归子序列。

模拟题一

模拟题二

模拟题三

模拟题四

Vuejs diff 算法

`diff`的时机

`_update`函数在干什么

不存在

存在

`patch`函数的对比流程

详细流程：

根节点比较

「对比子节点」

对开发的影响：

加 key

为什么不用 index 作为 key

总结

注意：

对比 Vue3

Vuejs diff 算法#

diff的时机#

_update函数在干什么#

不存在#

存在#

patch函数的对比流程#

详细流程：#

根节点比较#

「对比子节点」#

对开发的影响：#

加 key#

为什么不用 index 作为 key#

总结#

注意：#

对比 Vue3#

Vuejs diff 算法

`diff`的时机

`_update`函数在干什么

不存在

存在

`patch`函数的对比流程

详细流程：

根节点比较

「对比子节点」

对开发的影响：

加 key

为什么不用 index 作为 key

总结

注意：

对比 Vue3