大前端百科全书vue专题之虚拟dom+diff算法 - 掘金

大前端百科全书，前端界的百科全书，记录前端各相关领域知识点，方便后续查阅及面试准备

对虚拟DOM的理解？虚拟DOM主要做了什么？虚拟DOM本身是什么？

什么是虚拟DOM?

从本质上来说，Virtual Dom是一个JS对象，通过对象的方式来表示DOM结构。将页面的状态抽象为JS对象的形式，配合不同的渲染工具，使跨平台渲染成为可能。通过事务处理机制，将多次DOM修改的结果一次性的更新到页面上，从而有效的减少页面渲染的次数，减少修改DOM的重绘重排次数，提高渲染性能。

虚拟dom是对DOM的抽象，这个对象是更加轻量级的对DOM的描述。它设计的最初目的，就是更好的跨平台，比如node.js就没有DOM，如果想实现SSR，那么一个方式就是借助虚拟dom，因为学你dom本身就是js对象。在代码渲染到页面之前，vue或者react会把代码转换成一个对象(虚拟DOM)。以对象的形式来描述真实dom结构，最终渲染到页面。在每次数据发生变化前，虚拟dom都会缓存一份，变化之时，现在的虚拟dom会与缓存的虚拟dom进行比较。

在vue或者react内部封装了diff算法，通过这个算法来进行比较，渲染时修改改变的变化，原先没有发生改变的通过原先的数据进行渲染。

另外现代前端框架的一个基本要求就是无需手动操作DOM，一方面是因为手动操作DOM无法保证程序性能，多人协作的项目中如果review不严格，可能会有开发正写出性能较低的代码，另一方面更重要的是省略手动DOM操作可以大大提升开发效率

为什么要用Virtual Dom？

1. 保证性能下限，再不进行手动优化的情况下，提供能过得去的性能

看一下页面渲染的一个过程

下面对比一下修改DOM时真实DOM操作和Virtual Dom的过程，来看一下它们重排重绘的性能消耗

• 真实DOM：生成HTML字符串 + 重建所有的DOM元素
• Virtual Dom：生成VNode + DOMDiff + 必要的dom更新，Virtual Dom的更新DOM的准备工作耗费更多的时间，也就是js层面，相对于更多的DOM操作它的消费是极其便宜的。尤大大曾说到：框架给你的保证时，你不需要手动优化的情况下，我依然可以给你提供过得去的性能

2. 跨平台

Virtual Dom本质上时JS对象，可以很方便的跨平台操作，比如服务端渲染、uniapp等

Virtual Dom真的比真实DOM性能好么？

• 首次渲染大量DOM时，由于多了一层虚拟DOM的计算，比innerHTML插入慢
• 正如它能保证性能下限，在真实DOM操作的时候进行针对性的优化时，还是更快的。

虚拟dom

虚拟DOM是一个对象，一个什么样的对象呢？一个用来表示真实DOM的对象

let oldVDOM = { // 旧虚拟DOM
        tagName: 'ul', // 标签名
        props: { // 标签属性
            id: 'list'
        },
        children: [ // 标签子节点
            {
                tagName: 'li', props: { class: 'item' }, children: ['哈哈']
            },
            {
                tagName: 'li', props: { class: 'item' }, children: ['呵呵']
            },
            {
                tagName: 'li', props: { class: 'item' }, children: ['嘿嘿']
            },
        ]
    }

跨平台

因为使用了 Virtual DOM 的原因，Vue.js具有了跨平台的能力，例如：weex、小程序、web、h5、等

适配层

Virtual DOM 终归只是一些 JavaScript 对象罢了，那么最终是如何调用不同平台的 API 的呢？

const nodeOps = {
    setTextContent (text) {
        if (platform === 'weex') {
            node.parentNode.setAttr('value', text);
        } else if (platform === 'web') {
            node.textContent = text;
        }
    },
    parentNode () { //...... },
    removeChild () { //...... },
    nextSibling () { //...... },
    insertBefore () { //...... }
}

举个例子，现在我们有上述一个 nodeOps 对象做适配，根据 platform 区分不同平台来执行当前平台对应的API，而对外则是提供了一致的接口，供 Virtual DOM 来调用。

那么我们直接拿新虚拟DOM去渲染成真实DOM的话，效率真的会比直接操作真实DOM高吗？那肯定是不会的

由上图，一看便知，肯定是第2种方式比较快，因为第1种方式中间还夹着一个虚拟DOM的步骤，所以虚拟DOM比真实DOM快这句话其实是错的，或者说是不严谨的。那正确的说法是什么呢？虚拟DOM算法操作真实DOM，性能高于直接操作真实DOM，虚拟DOM和虚拟DOM算法是两种概念。虚拟DOM算法 = 虚拟DOM + Diff算法

为什么要使用虚拟dom

• 当然是前端优化方面，避免频繁操作DOM，频繁操作DOM会可能让浏览器回流和重绘，性能也会非常低，还有就是手动操作DOM还是比较麻烦的，要考虑浏览器兼容性问题，当前jQuery等库简化了 DOM操作，但是项目复杂了，DOM操作还是会变得复杂，数据操作也变得复杂
• 并不是所有情况使用虚拟DOM都提高性能，是针对在复杂的的项目使用。如果简单的操作，使用虚拟DOM,要创建虚拟DOM对象等等一系列操作，还不如普通的DOM`操作
• 虚拟DOM可以实现跨平台渲染，服务器渲染 、小程序、原生应用都使用了虚拟DOM
• 使用虚拟DOM改变了当前的状态不需要立即的去更新DOM，而且更新的内容进行更新，对于没有改变的内容不做任何操作，通过前后两次差异进行比较
• 虚拟 DOM 可以维护程序的状态，跟踪上一次的状态

patch

通过 patch 进行比较两个虚拟 DOM 然后添加的真实的 DOM 树上，中间比较就是我们等下要说的 diff算法

操作DOM常用api

• insertBefore、appendChild
• createElement、createTextNode
• removeChild
• ……

diff算法

Diff同层对比

新旧虚拟DOM对比的时候，Diff算法比较只会在同层级进行, 不会跨层级比较。 所以Diff算法是:深度优先算法。 时间复杂度:O(n)

patch+diff详细过程

一、patch新旧虚拟dom

patch(app, vnode);

1. 如果不是虚拟dom，转成虚拟dom
2. 如果是sameVnode，进行patchVnode
3. 否则删掉旧虚拟dom，插入新虚拟dom

二、patchVnode新旧虚拟dom

1. 如果相等 ===，直接return，不做处理
2. 如果新虚拟dom是文本节点且文本内容与旧虚拟dom文本内容不一样，改变文本内容
3. 如果新旧虚拟dom都存在children，进行updateChildren
4. 否则将新虚拟dom的children，插入到旧的虚拟dom当中

三、updateChildren进行虚拟dom子元素children的比较

新旧虚拟节点比对（对撞指针）

在这里要使用 4 个指针,从1-4的顺序来开始命中优化策略，命中一个，指针进行移动(新前和旧前向下移动，新后和旧后向上移动)，没有命中，就使用下一个策略，如果四个策略都没有命中，只能靠循环来找

两两比对

命中：两个节点标签和key一样

1. 两组对撞指针不对向中间移动
2. 如果值为undefined，跳过
3. 如果 oldStart/newStart 或者 oldEnd/newEnd 是 sameVnode，进行patchVnode，继续移动
4. 如果 oldStart/newEnd 是 sameVnode，进行patchVnode，将 oldStart 的真实dom元素，插入到oldEnd 的真实dom元素之后
5. 如果 oldEnd/newStart 是 sameVnode，进行patchVnode，将 oldEnd 的真实dom元素，插入到oldStart 的真实dom元素之前
6. 如果都没有命中，遍历oldStartIndex与oldEndIndex之间的元素，将它们的key与索引映射关系，放入一个Map中
7. 如果Map中有newStartVnode的key，将对应的真实dom插入到 oldStartVnode 的前面
8. 如果没有，创建元素，也插入到 oldStartVnode 的前面
9. 如果while循环结束，oldChildren 还没有走完，全部删除
10. 如果while循环结束，newChildren 还没有遍历完，插入到 newEndVnode 之前
11. 结束

用index做key

按理说，a，b，c三个li标签都是复用之前的，因为他们三个根本没改变，改变的只是前面新增了一个林三心

但是我们前面说了，在进行子节点的 diff算法 过程中，会进行 旧首节点和新首节点的sameNode对比，这一步命中了逻辑，因为现在新旧两次首部节点 的 key 都是 0了，同理，key为1和2的也是命中了逻辑，导致相同key的节点会去进行patchVnode更新文本，而原本就有的c节点，却因为之前没有key为4的节点，而被当做了新节点，所以很搞笑，使用index做key，最后新增的居然是本来就已有的c节点。所以前三个都进行patchVnode更新文本，最后一个进行了新增，那就解释了为什么所有li标签都更新了。

对比节点O(n²) + 删除/添加节点O(n)，合起来O(n³)

1. 将两颗树中所有的节点一一对比需要O(n²)的复杂度

2. 在对比过程中发现旧节点在新的树中未找到，那么就需要把旧节点删除，删除一棵树的一个节点(找到一个合适的节点放到被删除的位置)的时间复杂度为O(n)

3. 同理添加新节点的复杂度也是O(n),合起来diff两个树的复杂度就是O(n³)

1. 只比较同一层级，不跨级比较

2. tag不相同，则直接删掉重建，不再深度比较

3. tag和key，两者都相同，则认为是同一节点，不再深度比较

snabbdom实现

index.html

<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>虚拟dom</title>
</head>
<body>
  <button class="btn">策略3</button>
  <button class="btn">复杂</button>
  <button class="btn">删除</button>
  <button class="btn">复杂</button>
  <button class="btn">复杂</button>
  <ul id="app">
    虚拟dom
  </ul>
</body>
</html>

index.js

入口文件

import h from "./my-snabbdom/h";
import patch from "./my-snabbdom/patch";

let app = document.querySelector("#app");

// js 函数执行，先执行最里面的函数
// 1.h('li', {}, '我是一个li')第一个执行 返回的 {sel,data,children,text,elm} 连续三个 li 都是这个
// 2.接着就是 h('ul', {}, []) 进入到了第二个判断是否为数组，然后 把每一项 进行判断是否对象 和 有sel 属性，然后添加到 children 里面又返回了出去 {sel,data,children,text,elm}
// 3.第三就是执行 h('div', {},h()) 了， 第三个参数 直接是 h()函数 = {sel,data,children,text,elm} ，他的 children 把他用 [ ] 包起来
// 再返回给 vnode
let vnode = h("ul", {}, [
  h("li", { key: "A" }, "A"),
  h("li", { key: "B" }, "B"),
  h("li", { key: "C" }, "C"),
  h("li", { key: "D" }, "D"),
  h("li", { key: "E" }, "E"),
]);

patch(app, vnode);

console.log('vnode~~~~~~~~~~', vnode)

let vnode2 = h("ul", {}, [
  h("li", { key: "E" }, "E"),
  h("li", { key: "D" }, "D"),
  h("li", { key: "C" }, "C"),
  h("li", { key: "B" }, "B"),
  h("li", { key: "A" }, "A"),
]);
let vnode3 = h("ul", {}, [
  // h("li", { key: "E" }, "E"),
  h("li", { key: "Z" }, "Z"),
  h("li", { key: "D" }, "D"),
  h("li", { key: "C" }, "C"),
  h("li", { key: "A" }, "A"),
  h("li", { key: "V" }, "V"),
  h("li", { key: "B" }, "B"),
  h("li", { key: "K" }, "K"),
]);
let vnode4 = h("ul", {}, [
  h("li", { key: "A" }, "A"),
  h("li", { key: "B" }, "B"),
  h("li", { key: "C" }, "C"),
]);
let vnode5 = h("ul", {}, [
  h("li", { key: "E" }, "E"),
  h("li", { key: "C" }, "C"),
  h("li", { key: "V" }, "V"),
]);
let vnode6 = h("ul", {}, [
  h("li", { key: "A" }, "A"),
  h("li", { key: "B" }, "B"),
  h("li", { key: "C" }, "C"),
  h("li", { key: "D" }, "D"),
  h(
    "li",
    { key: "E" },
    h("ul", {}, [
      h("li", { key: "A" }, "A"),
      h("li", { key: "B" }, "B"),
      h("li", { key: "C" }, "C"),
      h("li", { key: "D" }, "D"),
      h("li", { key: "E" }, h("div", { key: "R" }, "R")),
    ])
  ),
]);
let vnodeList = [vnode2, vnode3, vnode4, vnode5, vnode6];
let btn = document.querySelectorAll(".btn");
for (let i = 0; i < btn.length; i++) {
  // 存在深浅拷贝的问题
  // 会对原数组进行修改
  btn[i].onclick = () => {
    // 深拷贝，解决patch修改原数据问题
    // 此方法不能拷贝dom元素
    console.log('~~~~~~~~~~~~~~~ ', vnode)
    vnode = patch(vnode, JSON.parse(JSON.stringify(vnodeList[i])));
  };
}

createElm.js

创建真实dom

/**
 * 创建元素
 * @param {vnode} vnode 要创建的节点
 */
export default function createElm(vnode) {
  // 拿出 新创建的 vnode 中的 sel
  let node = document.createElement(vnode.sel);
  // 存在子节点
  // 子节点是文本
  if (
    vnode.text !== "" &&
    (vnode.children === undefined || vnode.children.length === 0)
  ) {
    // 直接添加文字到 node 中
    node.textContent = vnode.text;
    // 子节点是数组
  } else if (Array.isArray(vnode.children) && vnode.children.length > 0) {
    let children = vnode.children;
    // 遍历数组
    for (let i = 0; i < children.length; i++) {
      // 获取到每一个数组中的 子节点
      let ch = children[i];
      // 递归的方式 创建节点
      let chDom = createElm(ch);
      // 把子节点添加到 自己身上
      node.appendChild(chDom);
    }
  }
  // 更新vnode 中的 elm
  vnode.elm = node;
  // 返回 DOM
  return node;
}

h.js

根据 vnode 构建 render function

不是递归，像是一种嵌套

import vnode from "./vnode";

// 可能存在多种入参类型
// export declare function h(sel: string): VNode;
// export declare function h(sel: string, data: VNodeData): VNode;
// export declare function h(sel: string, children: VNodeChildren): VNode;
// export declare function h(sel: string, data: VNodeData, children: VNodeChildren): VNode;

// 导出 h 方法
// 这里就实现简单3个参数 参数写死
/**
 *
 * @param {string} a sel
 * @param {object} b data
 * @param {any} c 是子节点 可以是文本，数组
 */
export default function h(a, b, c) {
  // 先判断是否有三个参数
  if (arguments.length < 3) throw new Error("请检查参数个数");
  // 第三个参数有不确定性 进行判断
  // 1.第三个参数是文本节点
  if (typeof c === "string" || typeof c === "number") {
    // 调用 vnode 这直接传 text 进去
    // 返回值 {sel,data,children,text,elm} 再返回出去
    return vnode(a, b, undefined, c, undefined);
  } // 2.第三个参数是数组 [h(),h()] [h(),text] 这些情况
  else if (Array.isArray(c)) {
    // 然而 数组里必须是 h() 函数
    // children 用收集返回结果
    let children = [];
    // 先判断里面是否全是 h()执行完的返回结果 是的话添加到 chilren 里
    for (let i = 0; i < c.length; i++) {
      // h() 的返回结果 是{} 而且 包含 sel
      if (!(typeof c[i] === "object" && c[i].sel))
        throw new Error("第三个参数为数组时只能传递 h() 函数");
      // 满足条件进行push [{sel,data,children,text,elm},{sel,data,children,text,elm}]
      children.push(c[i]);
    }
    // 调用 vnode 返回 {sel,data,children,text,elm} 再返回
    return vnode(a, b, children, undefined, undefined);
  } // 3.第三个参数直接就是函数 返回的是 {sel,data,children,text,elm}
  else if (typeof c === "object" && c.sel) {
    // 这个时候在 使用h()的时候 c = {sel,data,children,text,elm} 直接放入children
    let children = [c];
    // 调用 vnode 返回 {sel,data,children,text,elm} 再返回
    return vnode(a, b, children, undefined, undefined);
  }
}

patch.js

patch入口文件，比对两个虚拟dom

import vnode from "./vnode";
import createElm from "./createElm";
import patchVnode from './patchVnode'
import sameVnode from "./sameVnode";

// 导出 patch
/**
 *
 * @param {vnode/DOM} oldVnode
 * @param {vnode} newVnode
 */
export default function patch(oldVnode, newVnode) {
  // 1.判断oldVnode 是否为虚拟 DOM 这里判断是否有 sel
  if (!oldVnode.sel) {
    // 转为虚拟DOM
    oldVnode = emptyNodeAt(oldVnode);
  }
  // 判断 oldVnode 和 newVnode 是否为同一虚拟节点
  // 通过 key 和 sel 进行判断
  if (sameVnode(oldVnode, newVnode)) {
    // 是同一个虚拟节点 调用我们写的 patchVnode.js 中的方法
    patchVnode(oldVnode, newVnode)
  } else {
    // 不是同一虚拟个节点 直接暴力拆掉老节点，换上新的节点
    // 这里通过 createElm 递归 转为 真实的 DOM 节点
    let newNode = createElm(newVnode);
    // 旧节点的父节点
    if (oldVnode.elm.parentNode) {
      let parentNode = oldVnode.elm.parentNode;
      // 添加节点到真实的DOM 上
      parentNode.insertBefore(newNode, oldVnode.elm);
      // 删除旧节点
      parentNode.removeChild(oldVnode.elm);
    }
  }
  newVnode.elm = oldVnode.elm;

  console.log('+++++++++++++++ ', newVnode)

  // 返回newVnode作为 旧的虚拟节点
  return newVnode;
}

/**
 * 转为 虚拟 DOM
 * @param {DOM} elm DOM节点
 * @returns {object}
 */
function emptyNodeAt(elm) {
  // 把 sel 和 elm 传入 vnode 并返回
  // 这里主要选择器给转小写返回vnode
  // 这里功能做的简陋，没有去解析 # .
  // data 也可以传 ID 和 class
  return vnode(elm.tagName.toLowerCase(), undefined, undefined, undefined, elm);
}

patchVnode.js

比对两个虚拟节点

import createElm from "./createElm";
import updateChildren from "./updateChildren";

/**
 *
 * @param {vnode} oldVnode 老的虚拟节点
 * @param {vnode} newVnode 新的虚拟节点
 * @returns
 */
// 对比同一个虚拟节点
export default function patchVnode(oldVnode, newVnode) {
  // 1.判断是否相同对象
  console.log("同一个虚拟节点");
  if (oldVnode === newVnode) return;
  // 2.判断newVnode上有没有text
  // 这里为啥不考虑 oldVnode呢，因为 newVnode有text说明就没children
  if (newVnode.text && !newVnode.children) {
    // 判断是text否相同
    if (oldVnode.text !== newVnode.text) {
      console.log("文字不相同");
      // 不相同就直接把 newVnode中text 给 elm.textContent
      oldVnode.elm.textContent = newVnode.text;
    }
  } else {
    // 3.判断oldVnode有children, 这个时候newVnode 没有text但是有 children
    if (oldVnode.children) {
      // ...这里新旧节点都存在children 这里要使用 updateChildren 下面进行实现
      updateChildren(oldVnode.elm, oldVnode.children, newVnode.children)
    } else {
      console.log("old没有children，new有children");
      // oldVnode没有 children ,newVnode 有children
      // 这个时候oldVnode 只有text 我们把 newVnode 的children拿过来
      // 先清空 oldVnode 中text
      oldVnode.elm.innerHTML = "";
      // 遍历 newVnode 中的 children
      let newChildren = newVnode.children;
      for (let i = 0; i < newChildren.length; i++) {
        // 通过递归拿到了 newVnode 子节点
        let node = createElm(newChildren[i]);
        // 添加到 oldVnode.elm 中
        oldVnode.elm.appendChild(node);
      }
    }
  }
}

sameVnode.js

/**
 * 判断两个虚拟节点是否是同一节点
 * @param {vnode} vnode1 虚拟节点1
 * @param {vnode} vnode2 虚拟节点2
 * @returns boolean
 */
export default function sameVnode(vnode1, vnode2) {
  return (
    (vnode1.data ? vnode1.data.key : undefined) ===
      (vnode2.data ? vnode2.data.key : undefined) && vnode1.sel === vnode2.sel
  );
}

/*
 * 较为完善的版本
function sameVnode(oldVnode, newVnode) {
  return (
    oldVnode.key === newVnode.key && // key值是否一样
    oldVnode.tagName === newVnode.tagName && // 标签名是否一样
    oldVnode.isComment === newVnode.isComment && // 是否都为注释节点
    isDef(oldVnode.data) === isDef(newVnode.data) && // 是否都定义了data
    sameInputType(oldVnode, newVnode) // 当标签为input时，type必须是否相同
  )
}
*/

updateChildren.js

diff算法核心方法

import createElm from "./createElm";
import patchVnode from "./patchVnode";
import sameVnode from "./sameVnode";

// 导出 updateChildren
/**
 *
 * @param {dom} parentElm 父节点
 * @param {array} oldCh 旧子节点
 * @param {array} newCh 新子节点
 */
export default function updateChildren(parentElm, oldCh, newCh) {
  // 下面先来定义一下之前讲过的 diff 的几个指针 和 指针指向的 节点
  // 旧前 和 新前
  let oldStartIdx = 0,
    newStartIdx = 0;
  let oldEndIdx = oldCh.length - 1; //旧后
  let newEndIdx = newCh.length - 1; //新后
  let oldStartVnode = oldCh[0]; //旧前 节点
  let oldEndVnode = oldCh[oldEndIdx]; //旧后节点
  let newStartVnode = newCh[0]; //新前节点
  let newEndVnode = newCh[newEndIdx]; //新后节点
  let keyMap = null; //用来做缓存
  // 写循环条件
  while (newStartIdx <= newEndIdx && oldStartIdx <= oldEndIdx) {
    console.log("---进入diff---");

    // 下面按照 diff 的4种策略来写 这里面还得调用 pathVnode
    // patchVnode 和 updateChildren 是互相调用的关系，不过这可不是死循环
    // 指针走完后就不调用了

    // 这一段都是为了忽视我们加过 undefined 节点，这些节点实际上已经移动了
    if (oldCh[oldStartIdx] == undefined) {
      oldStartVnode = oldCh[++oldStartIdx];
    } else if (oldCh[oldEndIdx] == undefined) {
      oldEndVnode = oldCh[--oldEndIdx];
    } else if (newCh[newStartIdx] == undefined) {
      newStartVnode = newCh[++newStartIdx];
    } else if (newCh[newEndIdx] == undefined) {
      newEndVnode = newCh[--newEndIdx];
    }
    // 忽视了所有的 undefined 我们这里来 判断四种diff优化策略
    // 1.新前 和 旧前
    else if (sameVnode(oldStartVnode, newStartVnode)) {
      console.log("1命中");
      // 调用 patchVnode 对比两个节点的 对象 文本 children
      patchVnode(oldStartVnode, newStartVnode);
      newStartVnode.elm = oldStartVnode.elm
      // 指针移动
      newStartVnode = newCh[++newStartIdx];
      oldStartVnode = oldCh[++oldStartIdx];
    } // 2.新后 和 旧后
    else if (sameVnode(oldEndVnode, newEndVnode)) {
      console.log("2命中");
      // 调用 patchVnode 对比两个节点的 对象 文本 children
      patchVnode(oldEndVnode, newEndVnode);
      newEndVnode.elm = oldEndVnode.elm
      // 指针移动
      newEndVnode = newCh[--newEndIdx];
      oldEndVnode = oldCh[--oldEndIdx];
    } // 3.新后 和 旧前
    else if (sameVnode(oldStartVnode, newEndVnode)) {
      console.log("3命中");
      // 调用 patchVnode 对比两个节点的 对象 文本 children
      patchVnode(oldStartVnode, newEndVnode);
      // 策略3是需要移动节点的 把旧前节点 移动到 旧后 之后
      // insertBefore 如果参照节点为空，就插入到最后 和 appendChild一样
      parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling);
      newEndVnode.elm = oldStartVnode.elm
      // 指针移动
      newEndVnode = newCh[--newEndIdx];
      oldStartVnode = oldCh[++oldStartIdx];
    }
    // 4.新前 和 旧后
    else if (sameVnode(oldEndVnode, newStartVnode)) {
      console.log("4命中");
      // 调用 patchVnode 对比两个节点的 对象 文本 children
      patchVnode(oldEndVnode, newStartVnode);
      // 策略4是也需要移动节点的 把旧后节点 移动到 旧前 之前
      parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm);
      newStartVnode.elm = oldEndVnode.elm
      // 指针移动
      newStartVnode = newCh[++newStartIdx];
      oldEndVnode = oldCh[--oldEndIdx];
    } else {
      console.log("diff四种优化策略都没命中");
      // 当四种策略都没有命中
      // keyMap 为缓存，这样就不用每次都遍历老对象
      if (!keyMap) {
        // 初始化 keyMap
        keyMap = {};
        // 从oldStartIdx到oldEndIdx进行遍历
        for (let i = oldStartIdx; i <= oldEndIdx; i++) {
          // 拿个每个子对象 的 key
          const key = oldCh[i].data ? oldCh[i].data.key : undefined;
          // 如果 key 存在， 添加到缓存中
          if (key) keyMap[key] = i;
        }
      }

      // 判断当前项是否存在 keyMap 中 ,当前项时 新前(newStartVnode)
      let idInOld = newStartVnode.data && newStartVnode.data.key
        ? keyMap[newStartVnode.data.key]
        : undefined;
      // let idInOld = keyMap[newStartIdx.data]
      //   ? keyMap[newStartIdx.data.key]
      //   : undefined;

      // 存在的话就是移动操作
      if (idInOld || idInOld === 0) {
        console.log("移动节点");
        // 从 老子节点 取出要移动的项
        let moveElm = oldCh[idInOld];
        // 调用 patchVnode 进行对比 修改
        patchVnode(moveElm, newStartVnode);
        // 将这一项设置为 undefined
        oldCh[idInOld] = undefined;
        // 移动 节点 ,对于存在的节点使用 insertBefore移动
        // 移动的 旧前 之前 ，因为 旧前 与 旧后 之间的要被删除
        newStartVnode.elm = moveElm.elm;
        parentElm.insertBefore(moveElm.elm, oldStartVnode.elm);
      } else {
        console.log("添加新节点");
        // 不存在就是要新增的项
        // 添加的节点还是虚拟节点要通过 createElm 进行创建 DOM
        // 同样添加到 旧前 之前
        parentElm.insertBefore(createElm(newStartVnode), oldStartVnode.elm);
      }

      // 处理完上面的添加和移动 我们要 新前 指针继续向下走
      newStartVnode = newCh[++newStartIdx];
    }
  }
  // 我们添加和删除操作还没做呢
  // 首先来完成添加操作 新前 和 新后 中间是否还存在节点
  if (newStartIdx <= newEndIdx) {
    console.log("进入添加剩余节点");
    // 这是一个标识
    let beforeFlag = newCh[newEndIdx + 1] ? newCh[newEndIdx + 1].elm : null;
    // new 里面还有剩余节点 遍历添加
    for (let i = newStartIdx; i <= newEndIdx; i++) {
      // newCh里面的子节点还需要 从虚拟DOM 转为 DOM
      parentElm.insertBefore(createElm(newCh[i]), beforeFlag);
    }
  } else if (oldStartIdx <= oldEndIdx) {
    console.log("进入删除多余节点");
    // old 里面还有剩余 节点 ,旧前 和 旧后 之间的节点需要删除
    for (let i = oldStartIdx; i <= oldEndIdx; i++) {
      // 删除 剩余节点之前 先判断下是否存在
      if (oldCh[i] && oldCh[i].elm) parentElm.removeChild(oldCh[i].elm);
    }
  }
}

vnode.js

创建虚拟dom中的虚拟节点

/**
 * 把传入的 参数 作为 对象返回
 * @param {string} sel 选择器
 * @param {object} data 数据
 * @param {array} children 子节点
 * @param {string} text 文本
 * @param {dom} elm DOM
 * @returns object
 */
export default function (sel, data, children, text, elm) {
  return { sel, data, children, text, elm };
}