周一同学Zelina

Appearance

前言 ​

众所周知，在前端的面试中，面试官非常爱考 vdom 和 diff 算法。比如，可能会出现在以下场景 🤏

滴滴滴，面试官发来一个面试邀请。接受邀请 📞

🧑 面试官：你知道 key 的作用吗？

🙎 我：key 的作用是保证数据的唯一性。

🧑 面试官：怎么保证数据的唯一性？

🙎 我：就....

🧑 面试官：你知道虚拟 dom 吗？

🙎 我：虚拟 dom 就是……balabala

🧑 面试官：（好像有点道理）那你知道 diff 算法吗？

🙎 我：（心里：what……diff 算法是什么？？）

🧑 面试官：本次面试结束，回去等面试结果通知。

🙋🙋🙋

我们都知道， key 的作用在前端的面试是一道很普遍的题目，但是呢，很多时候我们都只浮于知识的表面，而没有去深挖其原理所在，这个时候我们的竞争力就在这被拉下了。所以呢，深入学习原理对于提升自身的核心竞争力是一个必不可少的过程。

在接下来的这篇文章中，我们将讲解面试中很爱考的虚拟 DOM 以及其背后的 diff 算法。

一、虚拟 DOM（Vitual DOM） ​

1、虚拟 DOM（Vitual DOM）和 diff 的关系 ​

我们都知道 DOM 操作是非常耗费性能的，早期我们用 JQuery 来自行控制 DOM 操作的时机，也就是手动调整，这样子其实也不是特别方便。因此就出现了虚拟 DOM ，即 Vitual DOM （下文简称为 vdom ），来解决 DOM 操作的问题。 vdom 是现如今的一个热门话题，也是面试中的热门话题，基本上在前端的面试中都会问到 虚拟DOM 的问题。

而为什么会问到 vdom 的问题呢，原因在于现在流行的 vue 和 react 框架，都是数据驱动视图，并且是基于 vdom 实现的，可以说 vdom 是实现 vue 和 react 的重要基石。

谈到 vdom ，我们不明觉厉的还会想到 diff 算法 。那 diff 算法 和 vdom 是什么关系呢？

其实， vdom 是一个大的概念，而 diff算法 是 vdom 的一部分， vdom 的核心价值在于最大程度的减少 DOM 的使用范围， vdom 通过把 DOM 用 JS 的方式进行模拟，之后进行计算和对比，最后找出最小的更新范围去更新。那么这个对比的过程就是 diff 算法 。也就是说他们两者是包含关系，如下图所示：

vdom和diff算法

可以说，diff 算法是 vdom 中最核心、最关键的部分，整个 vdom 的核心包围着大量的 diff 算法 。

有了这几个概念的基础铺垫，接下来我们来开始了解 虚拟 DOM 是什么。

2、真实 DOM 的渲染过程 ​

在开始讲解 虚拟DOM 之前，我们先来了解真实的 DOM 在浏览器中是怎么解析的。浏览器渲染引擎工作流程大致分为以下4 个步骤：

创建 DOM 树 → 创建 CSSOM 树 → 生成 render 树 → 布局 render 树 → 绘制 render 树 。

  • 第一步：创建 DOM 树。渲染引擎首先解析 HTML 代码，并生成 DOM 树。
  • 第二步：创建 CSSOM 树。浏览为获得外部 css 文件的数据后，就会像构建 DOM 树一样开始构建 CSSOM 树，这个过程与第一步没什么差别。
  • 第三步：生成 Render 树。将 DOM 树和 CSSOM 树关联起来，生成一棵 Render （渲染）树。
  • 第四步：布局 Render 树。有了 Render 树之后，浏览器开始对渲染树的每个节点进行布局处理，确定其在屏幕上的显示位置。
  • 第五步：绘制 Render 树。将每个节点绘制到屏幕上。

引用网上的一张图来呈现真实 DOM 的渲染过程：

真实DOM的渲染过程

3、虚拟 DOM 是什么？ ​

当用原生 js 或者 jq 去操作真实 DOM 的时候，浏览器会从构建 DOM 树开始，从头到尾执行一遍流程。那这样的话，就很有可能导致操作次数过多。当操作次数过多时，之前计算的与 DOM 节点相关的坐标值等各种值就......不知不觉的浪费掉了其性能，因此呢，虚拟 DOM 由此产生。

4、解决方案 - vdom ​

（1）问题引出 ​

大家都知道， DOM 树是具有一定的复杂度的，所以，在生成 DOM 树的过程中，会不断的进行计算操作，但难就难在，想要减少计算次数其实还是比较难的。

那换个思路考虑，我们都知道， JS 的执行速度很快很快，那能不能尝试着把这个计算，更多的转为JS 计算呢？答案是肯定的。

（2）vdom 如何解决问题：将真实 DOM 转为 JS 对象的计算 ​

假设在一次操作中有1000 个节点需要更新 DOM ，那么 虚拟 DOM 不会立即去 操作 DOM ，而是将这 1000 次更新的 diff 内容保存到本地的一个 JS 对象当中，之后将这个 JS 对象一次性 attach 到 DOM 树上，最后再进行后续的操作，这样子就避免了大量没有必要的计算。

所以，用 JS 对象模拟 DOM 节点的好处是，先将页面的更新全部反映到虚拟 DOM 上，这样子就先**操作内存中的 JS 对象**。值得注意的是，操作内存中 JS 对象的速度是相当快的。因此，等到全部 DOM 节点 更新完成之后，再将 最后的 JS 对象 映射到 真实的 DOM 上，交由 浏览器 去绘制。

这样，就解决了真实 DOM 渲染速度慢，性能消耗大的问题。

5、用 JS 模拟一个 DOM 结构 ​

根据下方的 html 代码，用 v-node 模拟出该 html 代码的 DOM 结构。

html 代码：

html
<div id="div1" class="container">
  <p>vdom</p>
  <ul style="font-size:20px;">
    <li>a</li>
  </ul>
</div>
<div id="div1" class="container">
  <p>vdom</p>
  <ul style="font-size:20px;">
    <li>a</li>
  </ul>
</div>

用 JS 模拟出以上代码的 DOM 结构：

js
{
	tag: 'div',
    props:{
        className: 'container',
        id: 'div1'
    },
    children: [
        {
            tag: 'p',
            chindren: 'vdom'
        },
        {
            tag: 'ul',
            props:{ style: 'font-size: 20px' },
            children: [
                {
                    tag: 'li',
                    children: 'a'
                }
                // ....
            ]
        }
    ]
}
{
	tag: 'div',
    props:{
        className: 'container',
        id: 'div1'
    },
    children: [
        {
            tag: 'p',
            chindren: 'vdom'
        },
        {
            tag: 'ul',
            props:{ style: 'font-size: 20px' },
            children: [
                {
                    tag: 'li',
                    children: 'a'
                }
                // ....
            ]
        }
    ]
}

通过以上代码我们可以分析出，我们用 tag ， props 和 children 来模拟 DOM 树结构。用 JS 模拟 DOM 树的结构，这样做的好处在于，可以计算出最小的变更，操作最少的 DOM。

6、通过 snabbdom 学习 vdom ​

vue 的 vdom 和 diff 算法 是参考 github 上的一个开源库 snabbdom 改造过来的，那么我们接下来就用这个库为例，来学习 vdom 的思想。

（1）snabbdom 是什么 ​

  • snabbdom 是一个简洁又强大的 vdom 库，易学易用；
  • Vue 参考它实现的 vdom 和 diff ；
  • Vue3.0 重写了 vdom 的代码，优化了性能。

（2）snabbdom 浅析 ​

我们先来看 snabbdom 首页上的 example ，先简单了解其思想。下面先贴上代码：

js
import {
  init,
  classModule,
  propsModule,
  styleModule,
  eventListenersModule,
  h,
} from 'snabbdom';

const patch = init([
  // Init patch function with chosen modules
  classModule, // makes it easy to toggle classes
  propsModule, // for setting properties on DOM elements
  styleModule, // handles styling on elements with support for animations
  eventListenersModule, // attaches event listeners
]);

const container = document.getElementById('container');
//h函数输入一个标签，之后再输入一个data，最周输入一个子元素
const vnode = h('div#container.two.classes', { on: { click: someFn } }, [
  h('span', { style: { fontWeight: 'bold' } }, 'This is bold'),
  ' and this is just normal text',
  h('a', { props: { href: '/foo' } }, "I'll take you places!"),
]);

//第一个patch函数
// Patch into empty DOM element – this modifies the DOM as a side effect
patch(container, vnode);

const newVnode = h(
  'div#container.two.classes',
  { on: { click: anotherEventHandler } },
  [
    h(
      'span',
      { style: { fontWeight: 'normal', fontStyle: 'italic' } },
      'This is now italic type'
    ),
    ' and this is still just normal text',
    h('a', { props: { href: '/bar' } }, "I'll take you places!"),
  ]
);

//第二个patch函数
// Second `patch` invocation
patch(vnode, newVnode); // Snabbdom efficiently updates the old view to the new state
import {
  init,
  classModule,
  propsModule,
  styleModule,
  eventListenersModule,
  h,
} from 'snabbdom';

const patch = init([
  // Init patch function with chosen modules
  classModule, // makes it easy to toggle classes
  propsModule, // for setting properties on DOM elements
  styleModule, // handles styling on elements with support for animations
  eventListenersModule, // attaches event listeners
]);

const container = document.getElementById('container');
//h函数输入一个标签，之后再输入一个data，最周输入一个子元素
const vnode = h('div#container.two.classes', { on: { click: someFn } }, [
  h('span', { style: { fontWeight: 'bold' } }, 'This is bold'),
  ' and this is just normal text',
  h('a', { props: { href: '/foo' } }, "I'll take you places!"),
]);

//第一个patch函数
// Patch into empty DOM element – this modifies the DOM as a side effect
patch(container, vnode);

const newVnode = h(
  'div#container.two.classes',
  { on: { click: anotherEventHandler } },
  [
    h(
      'span',
      { style: { fontWeight: 'normal', fontStyle: 'italic' } },
      'This is now italic type'
    ),
    ' and this is still just normal text',
    h('a', { props: { href: '/bar' } }, "I'll take you places!"),
  ]
);

//第二个patch函数
// Second `patch` invocation
patch(vnode, newVnode); // Snabbdom efficiently updates the old view to the new state

通过官方的例子我们可以知道， h 函数输入一个标签，之后输入一个 data ，最后输入一个子元素。并且 h 函数是一个 vnode 的结构（ vnode 结构见上述第 5 点），层级般的一层一层递进。最后就是 patch 函数，第一个patch 函数用来对元素进行渲染，第二个 patch 函数用来比较新旧节点。

（2）snabbdom 演示 ​

接下来我们用 cdn 的方式引入 snabbdom 的库，来演示一遍 snabbdom 是如何操作 vdom 的。附上代码：

html
<!DOCTYPE html>
<html>
  <head>
    <meta charset="UTF-8" />
    <title>Document</title>
  </head>
  <body>
    <div id="container"></div>
    <button id="btn-change">change</button>

    <script src="https://cdn.bootcss.com/snabbdom/0.7.3/snabbdom.js"></script>
    <script src="https://cdn.bootcss.com/snabbdom/0.7.3/snabbdom-class.js"></script>
    <script src="https://cdn.bootcss.com/snabbdom/0.7.3/snabbdom-props.js"></script>
    <script src="https://cdn.bootcss.com/snabbdom/0.7.3/snabbdom-style.js"></script>
    <script src="https://cdn.bootcss.com/snabbdom/0.7.3/snabbdom-eventlisteners.js"></script>
    <script src="https://cdn.bootcss.com/snabbdom/0.7.3/h.js"></script>

    <script>
      const snabbdom = window.snabbdom;

      // 定义 patch
      const patch = snabbdom.init([
        snabbdom_class,
        snabbdom_props,
        snabbdom_style,
        snabbdom_eventlisteners,
      ]);

      // 定义 h
      const h = snabbdom.h;

      const container = document.getElementById('container');

      // 生成 vnode
      const vnode = h('ul#list', {}, [
        h('li.item', {}, 'Item 1'),
        h('li.item', {}, 'Item 2'),
      ]);
      patch(container, vnode);

      document.getElementById('btn-change').addEventListener('click', () => {
        // 生成 newVnode
        const newVnode = h('ul#list', {}, [
          h('li.item', {}, 'Item 1'),
          h('li.item', {}, 'Item B'),
          h('li.item', {}, 'Item 3'),
        ]);
        patch(vnode, newVnode); // vnode = newVnode → patch 之后，应该用新的覆盖现有的 vnode ，否则每次 change 都是新旧对比
      });
    </script>
  </body>
</html>
<!DOCTYPE html>
<html>
  <head>
    <meta charset="UTF-8" />
    <title>Document</title>
  </head>
  <body>
    <div id="container"></div>
    <button id="btn-change">change</button>

    <script src="https://cdn.bootcss.com/snabbdom/0.7.3/snabbdom.js"></script>
    <script src="https://cdn.bootcss.com/snabbdom/0.7.3/snabbdom-class.js"></script>
    <script src="https://cdn.bootcss.com/snabbdom/0.7.3/snabbdom-props.js"></script>
    <script src="https://cdn.bootcss.com/snabbdom/0.7.3/snabbdom-style.js"></script>
    <script src="https://cdn.bootcss.com/snabbdom/0.7.3/snabbdom-eventlisteners.js"></script>
    <script src="https://cdn.bootcss.com/snabbdom/0.7.3/h.js"></script>

    <script>
      const snabbdom = window.snabbdom;

      // 定义 patch
      const patch = snabbdom.init([
        snabbdom_class,
        snabbdom_props,
        snabbdom_style,
        snabbdom_eventlisteners,
      ]);

      // 定义 h
      const h = snabbdom.h;

      const container = document.getElementById('container');

      // 生成 vnode
      const vnode = h('ul#list', {}, [
        h('li.item', {}, 'Item 1'),
        h('li.item', {}, 'Item 2'),
      ]);
      patch(container, vnode);

      document.getElementById('btn-change').addEventListener('click', () => {
        // 生成 newVnode
        const newVnode = h('ul#list', {}, [
          h('li.item', {}, 'Item 1'),
          h('li.item', {}, 'Item B'),
          h('li.item', {}, 'Item 3'),
        ]);
        patch(vnode, newVnode); // vnode = newVnode → patch 之后，应该用新的覆盖现有的 vnode ，否则每次 change 都是新旧对比
      });
    </script>
  </body>
</html>

此时我们来看浏览器的显示效果：

snabbdom演示

我们可以看到，最终的效果是当我们点击时， DOM 树不会一整棵树重新渲染，而是只针对改变的值进行重新比较，最终只将改变的节点进行渲染。

通过这样的演示，相信大家对真实 DOM 和虚拟 DOM 的区别有了一定的了解。

7、vdom 总结 ​

讲到这里，我们来对 vdom 做一个总结：

  • 可以通过 JS 来模拟 DOM 结构（vnode）；
  • 新旧 vnode 对比，得出最小的更新范围，最后更新 DOM；
  • 数据驱动视图的模式下，可以有效地控制DOM 操作。

二、diff 算法 ​

我们在上述讲 vdom 的时候说过， vdom 的核心价值就在于最大程度的减少 DOM 的使用范围。那 vdom 是通过什么方式呢，它是通过把 DOM 用 JS 来去模拟，之后进行计算和进行对比，最后找出最小的更新范围去更新。那么这个对比的过程对应的就是我们经常听到的 diff 算法。

接下来就让我们一起来了解 vdom 的另外一个内容， diff 算法。

1、diff 算法 ​

  • diff 算法是前端的一个热门话题，同时也是 vdom 中最核心、最关键的部分。

  • diff 算法在日常使用 vue 和 react 中经常出现（如key）。

2、diff 算法概述 ​

  • diff 即对比，是一个广泛的概念，如linux diff 命令、git diff 命令等。
  • 两个 js 对象也可以做 diff ，如 github 上的jiff 库，这个库可以直接用来给两个 js 对象做 diff。
  • 两棵树做 diff ，如上述所说的 vdom 和 diff 。

我们来看个例子 🌰：

树的对比

看到上面两棵树，我们可以想象下它是如何进行 diff 算法的。我们可以看到，右边这棵树要把左边的 E 改为 X ，同时要新增一个节点 H 。因此如果通过 diff 来实现的话，我们可以对其进行新旧节点的比较，如果比较完一样，则不动它；如果比较完不一样，则对它进行修改。这样处理的话，5 个节点只需要修改 2 次，而不用修改 5 次，效率很是 UpUp。

3、树 diff 的时间复杂度 O(n3) ​

对于树来说，原始的时间复杂度有O(n3)。那么这个 O(n3) 是怎么来的呢？

首先，遍历 tree1；其次，遍历 tree2；最后，对树进行排序。这样 n*n*n ，就达到了O(n3)。

假设现在有 1000 个节点要操作，那 1000 的 3 次方就1 亿次了，因此，树的这个算法不可用。那我们怎么解决呢？继续看下面。

4、优化时间复杂度到 O(n) ​

因为树的时间复杂度是 O(n3)，因此，我们就想办法，优化其时间复杂度从 O(n3)到 O(n)，以达到操作 vdom 节点，那这个优化过程其实我们所说的 diff 算法。通过 diff 算法，我们可以将时间复杂度从 O(n3)优化到 O(n)。diff 算法的具体思想如下：

  • 只比较同一层级，不跨级比较；
  • tag 不相同，则直接删掉重建，不再深度比较；
  • tag 和 key ，两者都相同，则认为是相同节点，不再深度比较。

三、深入 diff 算法源码 ​

1、生成 vnode ​

我们先来回顾下上面讲的 snabbdom ， diff 比较先是在 h 函数里面进行，这个 h 函数输入一个标签，之后输入一个 data ，最后输入一个子元素。并且 h 函数是一个 vnode 的结构，层级般的一层一层递进。最后就是 patch 函数， 第一个patch 函数用来对元素进行渲染，第二个 patch 函数用来比较新旧节点。

接下来我们来看下它是如何生成 vnode 的。

先克隆一份snabbdom的代码下来，打开 src|h.ts 文件，直接来看 h 函数，具体代码如下：

js
export function h(sel: string): VNode;
export function h(sel: string, data: VNodeData | null): VNode;
export function h(sel: string, children: VNodeChildren): VNode;
export function h(
  sel: string,
  data: VNodeData | null,
  children: VNodeChildren
): VNode;
export function h(sel: any, b?: any, c?: any): VNode {
  let data: VNodeData = {};
  let children: any;
  let text: any;
  let i: number;
  if (c !== undefined) {
    if (b !== null) {
      data = b;
    }
    if (is.array(c)) {
      children = c;
    } else if (is.primitive(c)) {
      text = c;
    } else if (c && c.sel) {
      children = [c];
    }
  } else if (b !== undefined && b !== null) {
    if (is.array(b)) {
      children = b;
    } else if (is.primitive(b)) {
      text = b;
    } else if (b && b.sel) {
      children = [b];
    } else {
      data = b;
    }
  }
  if (children !== undefined) {
    for (i = 0; i < children.length; ++i) {
      if (is.primitive(children[i]))
        children[i] = vnode(
          undefined,
          undefined,
          undefined,
          children[i],
          undefined
        );
    }
  }
  if (
    sel[0] === "s" &&
    sel[1] === "v" &&
    sel[2] === "g" &&
    (sel.length === 3 || sel[3] === "." || sel[3] === "#")
  ) {
    addNS(data, children, sel);
  }
  // 返回vnode，这个vnode对应patch下的vnode
  return vnode(sel, data, children, text, undefined);
}
export function h(sel: string): VNode;
export function h(sel: string, data: VNodeData | null): VNode;
export function h(sel: string, children: VNodeChildren): VNode;
export function h(
  sel: string,
  data: VNodeData | null,
  children: VNodeChildren
): VNode;
export function h(sel: any, b?: any, c?: any): VNode {
  let data: VNodeData = {};
  let children: any;
  let text: any;
  let i: number;
  if (c !== undefined) {
    if (b !== null) {
      data = b;
    }
    if (is.array(c)) {
      children = c;
    } else if (is.primitive(c)) {
      text = c;
    } else if (c && c.sel) {
      children = [c];
    }
  } else if (b !== undefined && b !== null) {
    if (is.array(b)) {
      children = b;
    } else if (is.primitive(b)) {
      text = b;
    } else if (b && b.sel) {
      children = [b];
    } else {
      data = b;
    }
  }
  if (children !== undefined) {
    for (i = 0; i < children.length; ++i) {
      if (is.primitive(children[i]))
        children[i] = vnode(
          undefined,
          undefined,
          undefined,
          children[i],
          undefined
        );
    }
  }
  if (
    sel[0] === "s" &&
    sel[1] === "v" &&
    sel[2] === "g" &&
    (sel.length === 3 || sel[3] === "." || sel[3] === "#")
  ) {
    addNS(data, children, sel);
  }
  // 返回vnode，这个vnode对应patch下的vnode
  return vnode(sel, data, children, text, undefined);
}

我们看到最后一行， h 函数返回的是一个 vnode 函数。之后我们继续找 vnode 的文件，在 src|vnode.ts 文件中。附上最关键部分代码：

js
export function vnode(
  sel: string | undefined,
  data: any | undefined,
  children: Array<VNode | string> | undefined,
  text: string | undefined,
  elm: Element | Text | undefined
): VNode {
  const key = data === undefined ? undefined : data.key;
  // 返回一个对象
  // elm表示vnode结构对应的是哪一个DOM元素
  // key可以理解为v-for时我们使用的key
  return { sel, data, children, text, elm, key };
}
export function vnode(
  sel: string | undefined,
  data: any | undefined,
  children: Array<VNode | string> | undefined,
  text: string | undefined,
  elm: Element | Text | undefined
): VNode {
  const key = data === undefined ? undefined : data.key;
  // 返回一个对象
  // elm表示vnode结构对应的是哪一个DOM元素
  // key可以理解为v-for时我们使用的key
  return { sel, data, children, text, elm, key };
}

同样定位到最后一行，大家可以发现， vnode 实际上是返回一个对象。而这个对象里，有 6 个元素。其中， sel, data, children, text 四个元素对应我们上面讲 vnode 时对应的结构（第一点的第 5 点）。而 elm 表示 vnode 结构对应的是哪一个 DOM 元素，最后的 key 大家可以理解为是我们使用 v-for 时用的 key ，同时需要注意是， key 不一定只有在 v-for 时可以使用，在定义组件等各种场景时均可使用。

2、patch 函数 ​

看完 vnode ，我们来看下如何用 patch 函数来对比 vnode 。从官方文档中我们可以定位到， patch 函数在 src|init.ts 文件下，我们找到 init.ts 文件。同样，我们定位到 patch 函数部分，具体代码如下：

js
// 返回一个patch函数
  return function patch(oldVnode: VNode | Element, vnode: VNode): VNode {
    let i: number, elm: Node, parent: Node;
    const insertedVnodeQueue: VNodeQueue = [];
    // 执行pre hook，hook 即 DOM 节点的生命周期
    for (i = 0; i < cbs.pre.length; ++i) cbs.pre[i]();

    // 第一个参数不是vnode，是一个DOM元素
    if (!isVnode(oldVnode)) {
      // 创建一个空的 vnode，关联到这个DOM元素
      oldVnode = emptyNodeAt(oldVnode);
    }

    // 相同的vnode（key 和 sel 都相等）
    if (sameVnode(oldVnode, vnode)) {
      // vnode进行对比
      patchVnode(oldVnode, vnode, insertedVnodeQueue);
    }
    // 不同的 vnode ， 直接删掉重建
    else {
      elm = oldVnode.elm!;
      parent = api.parentNode(elm) as Node;

      // 重建
      createElm(vnode, insertedVnodeQueue);

      if (parent !== null) {
        api.insertBefore(parent, vnode.elm!, api.nextSibling(elm));
        removeVnodes(parent, [oldVnode], 0, 0);
      }
    }

    for (i = 0; i < insertedVnodeQueue.length; ++i) {
      insertedVnodeQueue[i].data!.hook!.insert!(insertedVnodeQueue[i]);
    }
    for (i = 0; i < cbs.post.length; ++i) cbs.post[i]();
    return vnode;
  };
// 返回一个patch函数
  return function patch(oldVnode: VNode | Element, vnode: VNode): VNode {
    let i: number, elm: Node, parent: Node;
    const insertedVnodeQueue: VNodeQueue = [];
    // 执行pre hook，hook 即 DOM 节点的生命周期
    for (i = 0; i < cbs.pre.length; ++i) cbs.pre[i]();

    // 第一个参数不是vnode，是一个DOM元素
    if (!isVnode(oldVnode)) {
      // 创建一个空的 vnode，关联到这个DOM元素
      oldVnode = emptyNodeAt(oldVnode);
    }

    // 相同的vnode（key 和 sel 都相等）
    if (sameVnode(oldVnode, vnode)) {
      // vnode进行对比
      patchVnode(oldVnode, vnode, insertedVnodeQueue);
    }
    // 不同的 vnode ， 直接删掉重建
    else {
      elm = oldVnode.elm!;
      parent = api.parentNode(elm) as Node;

      // 重建
      createElm(vnode, insertedVnodeQueue);

      if (parent !== null) {
        api.insertBefore(parent, vnode.elm!, api.nextSibling(elm));
        removeVnodes(parent, [oldVnode], 0, 0);
      }
    }

    for (i = 0; i < insertedVnodeQueue.length; ++i) {
      insertedVnodeQueue[i].data!.hook!.insert!(insertedVnodeQueue[i]);
    }
    for (i = 0; i < cbs.post.length; ++i) cbs.post[i]();
    return vnode;
  };

阅读以上代码我们可以知道，我们刚开始创建时，第一个参数不是 vnode ，而是一个 DOM 元素，这个时候我们需要先创建一个空的 vnode ，来关联到这个 DOM 元素上。

有了第一个 vnode 之后，我们在第二次 patch 时，就可以对新旧节点进行比较。而新旧节点的比较是先判断 key 和 sel 是否相同，如果相同，则用 pathVNode 函数对新旧节点进行比较。如果是不同的 vnode ，则直接删掉重建。

3、patchVnode 函数 ​

上面我们说到了 patchVnode 函数进行新旧节点的比较，下面来对 patchVnode 进行详细剖析。同样在 src|init.ts 文件中，附上 patchVnode 函数的代码：

js
function patchVnode(
    oldVnode: VNode,
    vnode: VNode,
    insertedVnodeQueue: VNodeQueue
  ) {
    // 执行prepatch hook
    const hook = vnode.data?.hook;
    hook?.prepatch?.(oldVnode, vnode);

    // 设置vnode.elem
    const elm = (vnode.elm = oldVnode.elm)!;

    // 旧的 children
    const oldCh = oldVnode.children as VNode[];
    // 新的children
    const ch = vnode.children as VNode[];

    // 当新旧节点相等时则返回
    if (oldVnode === vnode) return;

    // hook 相关
    if (vnode.data !== undefined) {
      for (let i = 0; i < cbs.update.length; ++i)
        cbs.update[i](oldVnode, vnode);
      vnode.data.hook?.update?.(oldVnode, vnode);
    }

    // vnode.text === undefined (vnode.children 一般有值；children和text只能存在一个，不能共存)
    if (isUndef(vnode.text)) {
      // 新旧vnode都有children
      if (isDef(oldCh) && isDef(ch)) {
        // updateChildren 两者都有children时要进行对比
        if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue);
        // 新的vnode有chindren，旧的vnode没有children （旧的vnode有text）
      } else if (isDef(ch)) {
        // 清空旧的vnode的text
        if (isDef(oldVnode.text)) api.setTextContent(elm, "");
        // 添加children
        addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue);
        // 旧的vnode有children，新的vnode没有children
      } else if (isDef(oldCh)) {
        // 移除旧vnode的children
        removeVnodes(elm, oldCh, 0, oldCh.length - 1);
        // 旧的vnode有text
      } else if (isDef(oldVnode.text)) {
        api.setTextContent(elm, "");
      }

      // else: vnode.text != undefined (说明 vnode.text 有值，旧的vnode.children 没有值)
    } else if (oldVnode.text !== vnode.text) {
      // 移除旧vnode的children
      if (isDef(oldCh)) {
        removeVnodes(elm, oldCh, 0, oldCh.length - 1);
      }
      // 设置新的text
      api.setTextContent(elm, vnode.text!);
    }
    hook?.postpatch?.(oldVnode, vnode);
  }
function patchVnode(
    oldVnode: VNode,
    vnode: VNode,
    insertedVnodeQueue: VNodeQueue
  ) {
    // 执行prepatch hook
    const hook = vnode.data?.hook;
    hook?.prepatch?.(oldVnode, vnode);

    // 设置vnode.elem
    const elm = (vnode.elm = oldVnode.elm)!;

    // 旧的 children
    const oldCh = oldVnode.children as VNode[];
    // 新的children
    const ch = vnode.children as VNode[];

    // 当新旧节点相等时则返回
    if (oldVnode === vnode) return;

    // hook 相关
    if (vnode.data !== undefined) {
      for (let i = 0; i < cbs.update.length; ++i)
        cbs.update[i](oldVnode, vnode);
      vnode.data.hook?.update?.(oldVnode, vnode);
    }

    // vnode.text === undefined (vnode.children 一般有值；children和text只能存在一个，不能共存)
    if (isUndef(vnode.text)) {
      // 新旧vnode都有children
      if (isDef(oldCh) && isDef(ch)) {
        // updateChildren 两者都有children时要进行对比
        if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue);
        // 新的vnode有chindren，旧的vnode没有children （旧的vnode有text）
      } else if (isDef(ch)) {
        // 清空旧的vnode的text
        if (isDef(oldVnode.text)) api.setTextContent(elm, "");
        // 添加children
        addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue);
        // 旧的vnode有children，新的vnode没有children
      } else if (isDef(oldCh)) {
        // 移除旧vnode的children
        removeVnodes(elm, oldCh, 0, oldCh.length - 1);
        // 旧的vnode有text
      } else if (isDef(oldVnode.text)) {
        api.setTextContent(elm, "");
      }

      // else: vnode.text != undefined (说明 vnode.text 有值，旧的vnode.children 没有值)
    } else if (oldVnode.text !== vnode.text) {
      // 移除旧vnode的children
      if (isDef(oldCh)) {
        removeVnodes(elm, oldCh, 0, oldCh.length - 1);
      }
      // 设置新的text
      api.setTextContent(elm, vnode.text!);
    }
    hook?.postpatch?.(oldVnode, vnode);
  }

阅读以上源码我们可以知道：

（1） 当旧的 vnode 有 text 时，则说明旧的 children 没有值，且新的 vnode 的 text 有值。这个时候我们就把旧的 vnode 的 children 进行删除，删除结束给新的 vnode 设置 text ；

（2） 当新旧节点都有 children 时，我们需要对其进行更新操作，也就是操作 updateChildren 函数。这个我们将在下面进行讲解。

（3） 如果新的 vnode 有 children ，旧的 vnode 没有 children ，则说明旧的 vnode 有 text ，所以此时需要清空旧的 vnode 的 text ，并添加新的 children 上去。

（4） 如果旧的 vnode 有 children ，新的 vnode 没有 children ，则移除旧的 vnode 的 children 。

（5） 如果新旧节点都有 text ，则直接把新的 vnode 的 text 值赋值给旧的 vnode 的 text 。

来看下图的呈现：

新旧节点的对比

4、updateChildren 函数 ​

上面分析 pathVnode 时我们讲到了用 updateChildren 函数来更新新旧节点的 children 。接下来我们来看下这个函数：

js
function updateChildren(
    parentElm: Node,
    oldCh: VNode[],
    newCh: VNode[],
    insertedVnodeQueue: VNodeQueue
  ) {
    let oldStartIdx = 0;
    let newStartIdx = 0;
    let oldEndIdx = oldCh.length - 1;
    let oldStartVnode = oldCh[0];
    let oldEndVnode = oldCh[oldEndIdx];
    let newEndIdx = newCh.length - 1;
    let newStartVnode = newCh[0];
    let newEndVnode = newCh[newEndIdx];
    let oldKeyToIdx: KeyToIndexMap | undefined;
    let idxInOld: number;
    let elmToMove: VNode;
    let before: any;

    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
      if (oldStartVnode == null) {
        oldStartVnode = oldCh[++oldStartIdx]; // Vnode might have been moved left
      } else if (oldEndVnode == null) {
        oldEndVnode = oldCh[--oldEndIdx];
      } else if (newStartVnode == null) {
        newStartVnode = newCh[++newStartIdx];
      } else if (newEndVnode == null) {
        newEndVnode = newCh[--newEndIdx];

        // 开始和开始进行对比
      } else if (sameVnode(oldStartVnode, newStartVnode)) {
        patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue);
        oldStartVnode = oldCh[++oldStartIdx];
        newStartVnode = newCh[++newStartIdx];

        // 结束和结束进行对比
      } else if (sameVnode(oldEndVnode, newEndVnode)) {
        patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue);
        oldEndVnode = oldCh[--oldEndIdx];
        newEndVnode = newCh[--newEndIdx];

        // 开始和结束做对比
      } else if (sameVnode(oldStartVnode, newEndVnode)) {
        // Vnode moved right
        patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue);
        api.insertBefore(
          parentElm,
          oldStartVnode.elm!,
          api.nextSibling(oldEndVnode.elm!)
        );
        oldStartVnode = oldCh[++oldStartIdx];
        newEndVnode = newCh[--newEndIdx];

        // 结束和开始做对比
      } else if (sameVnode(oldEndVnode, newStartVnode)) {
        // Vnode moved left
        patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue);
        api.insertBefore(parentElm, oldEndVnode.elm!, oldStartVnode.elm!);
        oldEndVnode = oldCh[--oldEndIdx];
        newStartVnode = newCh[++newStartIdx];

        // 以上四个都未命中
      } else {
        if (oldKeyToIdx === undefined) {
          oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
        }

        // 拿新节点的key，能否对应上oldCh中的某个节点的key
        idxInOld = oldKeyToIdx[newStartVnode.key as string];

        // 没有对应上
        if (isUndef(idxInOld)) {
          // New element
          api.insertBefore(
            parentElm,
            createElm(newStartVnode, insertedVnodeQueue),
            oldStartVnode.elm!
          );

          // 对应上了
        } else {
          // 对应上key的节点
          elmToMove = oldCh[idxInOld];

          // sel是否相等（sameVnode的条件）
          if (elmToMove.sel !== newStartVnode.sel) {
            // sel不相等，可能只是key相等；那也没有用，只能重建 New Element
            api.insertBefore(
              parentElm,
              createElm(newStartVnode, insertedVnodeQueue),
              oldStartVnode.elm!
            );

            // sel 相等，key 相等；执行patchVnode函数
          } else {
            patchVnode(elmToMove, newStartVnode, insertedVnodeQueue);
            oldCh[idxInOld] = undefined as any;
            api.insertBefore(parentElm, elmToMove.elm!, oldStartVnode.elm!);
          }
        }
        newStartVnode = newCh[++newStartIdx];
      }
    }
    if (oldStartIdx <= oldEndIdx || newStartIdx <= newEndIdx) {
      if (oldStartIdx > oldEndIdx) {
        before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].elm;
        addVnodes(
          parentElm,
          before,
          newCh,
          newStartIdx,
          newEndIdx,
          insertedVnodeQueue
        );
      } else {
        removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx);
      }
    }
  }
function updateChildren(
    parentElm: Node,
    oldCh: VNode[],
    newCh: VNode[],
    insertedVnodeQueue: VNodeQueue
  ) {
    let oldStartIdx = 0;
    let newStartIdx = 0;
    let oldEndIdx = oldCh.length - 1;
    let oldStartVnode = oldCh[0];
    let oldEndVnode = oldCh[oldEndIdx];
    let newEndIdx = newCh.length - 1;
    let newStartVnode = newCh[0];
    let newEndVnode = newCh[newEndIdx];
    let oldKeyToIdx: KeyToIndexMap | undefined;
    let idxInOld: number;
    let elmToMove: VNode;
    let before: any;

    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
      if (oldStartVnode == null) {
        oldStartVnode = oldCh[++oldStartIdx]; // Vnode might have been moved left
      } else if (oldEndVnode == null) {
        oldEndVnode = oldCh[--oldEndIdx];
      } else if (newStartVnode == null) {
        newStartVnode = newCh[++newStartIdx];
      } else if (newEndVnode == null) {
        newEndVnode = newCh[--newEndIdx];

        // 开始和开始进行对比
      } else if (sameVnode(oldStartVnode, newStartVnode)) {
        patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue);
        oldStartVnode = oldCh[++oldStartIdx];
        newStartVnode = newCh[++newStartIdx];

        // 结束和结束进行对比
      } else if (sameVnode(oldEndVnode, newEndVnode)) {
        patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue);
        oldEndVnode = oldCh[--oldEndIdx];
        newEndVnode = newCh[--newEndIdx];

        // 开始和结束做对比
      } else if (sameVnode(oldStartVnode, newEndVnode)) {
        // Vnode moved right
        patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue);
        api.insertBefore(
          parentElm,
          oldStartVnode.elm!,
          api.nextSibling(oldEndVnode.elm!)
        );
        oldStartVnode = oldCh[++oldStartIdx];
        newEndVnode = newCh[--newEndIdx];

        // 结束和开始做对比
      } else if (sameVnode(oldEndVnode, newStartVnode)) {
        // Vnode moved left
        patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue);
        api.insertBefore(parentElm, oldEndVnode.elm!, oldStartVnode.elm!);
        oldEndVnode = oldCh[--oldEndIdx];
        newStartVnode = newCh[++newStartIdx];

        // 以上四个都未命中
      } else {
        if (oldKeyToIdx === undefined) {
          oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
        }

        // 拿新节点的key，能否对应上oldCh中的某个节点的key
        idxInOld = oldKeyToIdx[newStartVnode.key as string];

        // 没有对应上
        if (isUndef(idxInOld)) {
          // New element
          api.insertBefore(
            parentElm,
            createElm(newStartVnode, insertedVnodeQueue),
            oldStartVnode.elm!
          );

          // 对应上了
        } else {
          // 对应上key的节点
          elmToMove = oldCh[idxInOld];

          // sel是否相等（sameVnode的条件）
          if (elmToMove.sel !== newStartVnode.sel) {
            // sel不相等，可能只是key相等；那也没有用，只能重建 New Element
            api.insertBefore(
              parentElm,
              createElm(newStartVnode, insertedVnodeQueue),
              oldStartVnode.elm!
            );

            // sel 相等，key 相等；执行patchVnode函数
          } else {
            patchVnode(elmToMove, newStartVnode, insertedVnodeQueue);
            oldCh[idxInOld] = undefined as any;
            api.insertBefore(parentElm, elmToMove.elm!, oldStartVnode.elm!);
          }
        }
        newStartVnode = newCh[++newStartIdx];
      }
    }
    if (oldStartIdx <= oldEndIdx || newStartIdx <= newEndIdx) {
      if (oldStartIdx > oldEndIdx) {
        before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].elm;
        addVnodes(
          parentElm,
          before,
          newCh,
          newStartIdx,
          newEndIdx,
          insertedVnodeQueue
        );
      } else {
        removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx);
      }
    }
  }

我们先来看两张图：

updateChildren图示1

updateChildren图示2

大家先看图 1， updateChildren 要做得事情就是，将新旧节点进行对比，如果相同则不进行更新，如果不同则对其进行更新操作。

再看图 2，而更新的方式就是，通过对oldStartIdx，newStartIdx，oldEndIdx和newEndIdx这四个值进行比较，来得出是否需要更新操作。

那这四个值如何进行比较呢？接下来我们继续看。

阅读源码我们可以分析出，通过对4 种类型的节点进行比较，来判断如何更新节点。

第一种，旧的开始节点 oldStartIdx 和新的开始节点 newStartIdx 比较。第二种，旧的开始节点 oldStartIdx 和新的结束节点 newEndIdx 比较。第三种，旧的结束节点 oldEndIdx 和新的开始节点 newStartIdx 比较。第四种，旧的结束节点 oldEndIdx 和新的结束节点 newEndIdx 比较。

如果以上这四种比较都没有命中，则拿取新节点的key ，之后将这个 key 查看是否对应上 oldCh 中某个节点的 key 。如果没有对应上，则直接重建元素。如果对应上了，还要再判断 sel 和 key 是否相等，如果相等，则执行 patchVnode 函数，如果不相等，那跟前面一样，也只能重建元素。

四、结束语 ​

vdom 的核心概念主要在 h 、 vnode 、 patch 、 diff 、 key 这几个内容，个人觉得，整个 diff 的比较都在围绕着这几个函数进行，所以了解这几个核心概念很重要。同时，vdom 存在的另一个更重要的价值莫过于数据驱动视图了， vdom 通过控制 DOM 的操作来使得数据可以去驱动视图。

关于虚拟 DOM 和 diff 的讲解到此就结束啦！希望对大家有帮助~

Released under the MIT License.

Copyright © 2021-present 周一