什么是Virtual DOM

Virtual DOM是对DOM的抽象，本质上是JavaScript对象，这个对象就是更加轻量级的对DOM的描述.

为什么需要Virtual DOM

既然我们已经有了DOM,为什么还需要额外加一层抽象？

首先，我们都知道在前端性能优化的一个秘诀就是尽可能少地操作DOM,不仅仅是DOM相对较慢，更因为频繁变动DOM会造成浏览器的回流或者重回，这些都是性能的杀手，因此我们需要这一层抽象，在patch过程中尽可能地一次性将差异更新到DOM中，这样保证了DOM不会出现性能很差的情况.

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

最后，也是Virtual DOM最初的目的，就是更好的跨平台，比如Node.js就没有DOM,如果想实现SSR(服务端渲染),那么一个方式就是借助Virtual DOM,因为Virtual DOM本身是JavaScript对象.

Virtual DOM的关键要素

Virtual DOM的创建

我们已经知道Virtual DOM是对真实DOM的抽象，根据不同的需求我们可以做出不同的抽象，比如

snabbdom.js的抽象方式是这样的

export interface VNode {
  sel: string I undefined;
  data: VNodeData I undefined;
  children: Array<VNode I string> I undefined;
  elm: Node I undefined;
  text: string I undefined;
  key: Key I undefined;
}

当然，snabbdom.js由于是面向生产环境的库，所以做了大量的抽象各种，我们由于仅仅作为教程理解，因此采用最简单的抽象方法：

{
  type, // String, DoM节点的类型,如"div
  data, // object,包括props, sty1e等等DoM节点的各种属性
  children // Array,子节点
}

在明确了我们抽象的Virtual DOM构造之后，我们就需要一个函数来创建Virtual DOM.

/**
 * 生成 vnode
 * @param {String} type    类型，如'div'
 * @param {String} key    key vnode的唯一id
 * @param {Object} data    data，包括属性，事件等等
 * @param {Array} children    子  vnode
 * @param {Strimg} text    文本
 * @param {Element} elm    对应的dom
 * @param {Object}    vnode
 */

function vnode(type, key, data, children, text, elm) {
  const element = {
    _type: VNODE_TYPE, 
    type, key, data, children, text, elml
  }
  return element
}

这个函数很简单，接受一定的参数，再根据这些参数返回一个对象，这个对象就是DOM的抽象.

Virtual DOM Tree的创建

上面我们已经声明了一个vnode函数用于单个Virtual DOM的创建工作，但是我们都知道DOM其实是一个Tree,我们接下来要做的就是声明一个函数用于创建DOM Tree的抽象 -- Virtual DOM Tree

function h(type, config, ...children) { 
  const props = { }
  let key = null

  // 获取key,填充props对象
  if (config != nu1l) {
    if (hasValidkey(config)){
      key = '' + config.key
    }
    for (let propName in config){
      if (hasownProperty.call(config, propName) && !RESERVED-PROPS [propName]) {
        props [propName] = config[propllame]
      }
    }
  }
  return vnode( 
    type,
    key,
    props,
    flattenArray(children).map(c => {
      return isPrimitive(c) ? vnode(undefined, undefined, undefined, undefined, c): c 
    })
  )
}

Virtual DOM 的更新

Virtual DOM 归根到底是JavaScript对象，我们得想办法将Virtual DOM与真实的DOM对应起来，也就是说，需要我们声明一个函数，此函数可以将vnode转化为真实DOM

function createElm(vnode, insertedVnodeQueue) {
  let data = vnode.data
  let i
  // 省略hook 调用
  let children = vnode. children 
  let type = vnode, type

  // 根据type来分别生成 DOM
  // 处理comment
  if (type === 'comment') {
    if (vnode.text == null){
      vnode.text = ''
    }
    vnode.elm = api.createComment (vnode.text)
  }
  // 处理其它type
  else if (type) {
    const elm = vnode.elm = data.ns
      ? api.createElementNs (data.ns, type) 
      : api.createElement (type)

    // 调用create hook
    for (let i = e; i < cbs.create. length; ++i) cbs.create[i] (emptyNode, vnode)

    // 分别处理children和text
    // 这里隐含一个逻辑: vnode的children和text不会/应该同时存在。
    if (isArrey(cnildren)) {
      // 递归chidren,保证vnode tree 中每个vnode都有自己对应的dom
      // 即构vnode tree对应的dom tree
      children.forEach(ch => {
        ch && api.appendChild(elm, createfln(ch, insertedVnodequeue))
      })
    }
    else if (isPrimitive(vnode.text)) {
      api.appendChild(eim, api.createTextNode (vnode.text))
    }
    // 调用create hooki为insert hook填充insertedVnodeQueue
    i = vnode.data.hook
    if (1){
      i.create s& i.create(emptyfiode, vnode)
      i.insert && insertedVnodeQueue.push(vnode)
    }
  }
  // 处理text (text的type 是空)
  else{
  vnode.elm = api.createTextNode(vnode .text)
  }
  return vnode.elm
}

上述函数其实工作很简单，就是根据 type 生成对应的 DOM，把 data 里定义的 各种属性设置到 DOM 上.

Virtual DOM 的diff

Virtual DOM 的 diff才是整个Virtual DOM 中最难理解也最核心的部分，diff的目的就是比较新旧Virtual DOM Tree找出差异并更新.

可见diff是直接影响Virtual DOM 性能的关键部分.

要比较Virtual DOM Tree的差异，理论上的时间复杂度高达O(n^3),这是一个奇高无比的时间复杂度，很显然选择这种低效的算法是无法满足我们对程序性能的基本要求的.

好在我们实际开发中，很少会出现跨层级的DOM变更，通常情况下的DOM变更是同级的，因此在现代的各种Virtual DOM库都是只比较同级差异，在这种情况下我们的时间复杂度是O(n).

那么我们接下来需要实现一个函数，进行具体的diff运算，函数updateChildren的核心算法如下：

// 遍历oldch和newch来比较和更新
while (oldstartIdx <= oldEndIdx & newstartIdx <= newEndIdx) {
  // 首先检查4种情况,保证oldstart/oldEnd/newstart/newEnd
  // 这4个vnode非空,左侧的vnode为空就右移下标,右侧的vnode为空就左移下标。
  if (oldstartVnode == null) {
    oldStartVnode = oldch[++oldstartIdx]} 
  } else if (oldEndVnode == null){ 
    oldEndVnode = oldch[--oldEndIdx]
  } else if(newStartVnode == null){
    newStartVnode = newCh[++newStartIdx]
  } else if (newEndVnode == null){
    newEndVnode = newCh[--newEndIdx]
  }
  /**
   * 然后oldStartVnode/oldEndVnode/newStartVnode/newEndVnode两两比较,
   * 对有相同vnode的4种情况执行对应的patch逻辑。
   * - 如果同start或同end的两个vnode是相同的(情况1和2) ,
   * 说明不用移动实际dom,直接更新dom属性/children即可;
   * - 如果start和end两个vnode相同(情况3和4) ,
   * 那说明发生了 vnode的移动,同理我们也要移动dom
   */
  // 1,如果oldStartVnode和newstartVnode相同(key相同) ,执行patch
  else if (isSameVnode(oldStartVnode, newStartVnode)) {
    //不需要移动dom
    patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue)
    oldstartVnode = oldcht[++o1dStartIdx]
    newstartVnode = newCh[++newStartIdx]
  }
  // 2.如果oldEndVnode和newEndVnode相同,执行patch
  else if (isSameVnode(o1dEndVnode, newEndVnode)){
    // 不需要移动dom
    patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue) 
    oldEndVnode = oldCh[--oldEndIdx]
    newEndVnode = newChf[--newEndIdx]
  }
  else if (isSameVnode(oldStartVnode, newEndVnode)) { 
    patchVnode(oldstartVnode, newEndVnode, insertedVnodeQueue)
    //把获得更新后的(oldStartVnode/newEndVnode)的dom右移,移动到
    // oldEndVnode对应的dom的右边。为什么这么右移了
    // (1) oldStartVnode和newEndVnode相同,显然是vnode右移了。
    // (2)若while循环刚开始,那移到o1dEndVnode. e1m右边就是最右边,是合理的
    // (3)若循环不是刚开始,因为比较过程是两头向中间,那么两头的dom的位置已经是1/合理的了,移动到o1dEndVnode.eln右边是正确的位置
    // (4)记住, oldVnode和vnode是相同的才patch,且oldVnode自己对应的dom1总是已经存在的, vnode的dom是不存在的,直接夏用oldVnode对应的dom
    api.insertBefoce(narentE1m,oldstartVnode,elm,api,nextsibline(oldEndVnode.eim))
    oldstartVnode = oldch[++oldstartIdx] 
    newEndVnode = newCh[--nevEndIdx]
  }
  // 4.如果0ldEndVnode和newstartVnode相同,执行patch
  else if (isSamevnode(oldEndVnode, newStartVnode)){ 
    patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue)
    //这里是左移更新后的dom,原因参考上面的右移。
    api. insertBefore (parentElm, oldEnaVnode.elm, oldstartVnode.elm)
    oldEndVnode = oldCh[--oldEndIdx]
    newstartVnade = newCh[++newstartTdx]
  }
  // 最后一种情况:4个vnode都不相同,那么我们就要
  // 1.从oldch数组建立key --> index的map
  // 2.只处理newstartVnode (简化逻辑,有循环我们最终还是会处理到所有vnode)以它的key从上面的map里拿到indexs
  // 3.如果index存在,那么说明有对应的old vnode, patch就好了
  // 4.如果index不存在,那么说明newstartVnode是全新的vnode,直接创健对应的dom并插入
  else {
    // 如果oldkeyToldx不存在,创建old children 中vnode的key到index的
    // 映射,方便我们之后通过key去拿下标
    if (olaKeyToldx === undefined){
      oldKeyToldx = createKeyTo0ldIdx(oldCh, oldStartIdx, oldEngIdx)
    }
    // 尝试通过newstartVnode的key去拿下标
    idxInold = olakeyToldx[newStartVnode.key]
    //下标不存在,说明newStartVnode是全新的vnode。
    if (idxInold == null) {
      // 那么为newstartVnode 创建dom并插入到oldStartVnode.elm的前面。
      api.insertBefore(parentElm, createE1n(newstartVnode, insertedVnodeQueue),newStartVnode = nevch[--newstartIdx]
    }
    // 下标存在,说明o1d chiidren中有相同key的vnode,
    else {   
      elmToMove = oldch[idxInold]
      // 如果type不同,没办法,只能创建新dom
      if (elTollove.type !== nenstartVnode. type) {
        api.insertBefore(parentElm, createElm(neuStartVnode, insertedVnodeQueue), olastartVnc
      }
      // type相网(且key相同) ,那么说明是相同的vmode,执行patch
      else {
        patchVnode(elmTolove, nevstartVnode, insertedVnodeQueue) 
        olach[idxInold] = undefined 
        api.insertBefore(parentElm, elmToMove.elm, oldStartVnode. elm)
      }
      newStartVnode = newch[++nevstartIdx]
    }
  }
}
// 上面的翻结束后(循环条件有两个) ,处理可能的未处理的 vnode
// 如果是new vnodes里有未处理的(oldstartIdx > oldEndIdx
// 说明old vnodes先处理完毕)
if (olastartldx > oldEndIdx){
  before = newch[newndIdx+1] == null ? null : newCntnewEndIdx+1].e1m
  adavnodes (parentElm, before, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
}
//相反,如果old vnodes有未处理的,删除(为处理vnodes对应的)多余的dom
else if (newstartIdx > newEndIdx) {
  removevnodes(parentEm, oldch, oldstartIdx, oldEndlax)
}

我们可以假设有旧的Vnode数组和新的Vnode数组这两个数组,而且有四个变量充当指针分别指到两个数组的头尾.

重复下面的对比过程，直到两个数组中任一数组的头指针超过尾指针，循环结束:

• 头头对比: 对比两个数组的头部，如果找到，把新节点patch到旧节点，头指针后移

• 尾尾对比: 对比两个数组的尾部，如果找到，把新节点patch到旧节点，尾指针前移

• 旧尾新头对比: 交叉对比，旧尾新头，如果找到，把新节点patch到旧节点，旧尾指针前移，新头指针后移

• 旧头新尾对比: 交叉对比，旧头新尾，如果找到，把新节点patch到旧节点，新尾指针前移，旧头指针后移

• 利用key对比: 用新指针对应节点的key去旧数组寻找对应的节点,这里分三种情况,当没有对应的key，那么创建新的节点,如果有key并且是相同的节点，把新节点patch到旧节点,如果有key但是不是相同的节点，则创建新节点我们假设有新旧两个数组:

• 旧数组:[1, 2, 3, 4, 5]

• 新数组:[1, 4, 6, 1000, 100, 5]

首先我们进行头头对比,新旧数组的头部都是1,因此将双方的头部指针后移.

我们继续头头对比,但是2 !== 4导致对比失败,我进入尾尾对比,5 === 5,那么尾部指针则可前移.

现在进入新的循环,头头对比2 !== 4,尾尾对比4 !== 100,此时进入交叉对比,先进行旧尾新头对比,即4 === 4,旧尾前移且新头后移.

接着再进入一个轮新的循环,头头对比2 !== 6,尾尾对比3 !== 100,交叉对比2 != 100 3 != 6,四种对比方式全部不符合,如果这个时候需要通过key去对比,然后将新头指针后移

继续重复上述对比的循环方式直至任一数组的头指针超过尾指针，循环结束.

在上述循环结束后,两个数组中可能存在未遍历完的情况:循环结束后

先对比旧数组的头尾指针，如果旧数组遍历完了（可能新数组没遍历完，有漏添加的问题），添加新数组中漏掉的节点

if (oldStartIdx > oldEndIdx) {
  before= newch[newEndidx+11] == null ? null: newch [newEndidx+11.elm
  addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
}

再对比新数组的头尾指针，如果新数组遍历完了（可能旧数组没遍历完，有漏删除的问题），删除旧数组中漏掉的节点

else if (newStartIdx > newEndIdx){ 
  removeVnodes (parentElm, oldCh, oldStartIdx, oldEndIdx)
}

Virtual DOM的优化

上一节我们的Virtual DOM实现是参考了snabbdom.js的实现,当然Vue.js也同样参考了snabbdom.js,我们省略了大量边缘状态和svg等相关的代码,仅仅实现了其核心部分.

snabbdom.js已经是社区内主流的Virtual DOM实现了,vue 2.0阶段与snabbdom.js一样都采用了上面讲解的「双端比较算法」,那么有没有一些优化方案可以使其更快?

其实，社区内有更快的算法，例如inferno.js就号称最快react-like框架(虽然inferno.js性能强悍的原因不仅仅是算法,但是其diff算法的确是目前最快的),而vue 3.0就会借鉴inferno.js的算法进行优化.

我们可以等到Vue 3.0发布后再一探究竟,具体的优化思想可以先参考diff 算法原理概述,其中一个核心的思想就是利用LIS(最长递增子序列)的思想做动态规划,找到最小的移动次数.

例如以下两个新旧数组,React的算法会把 a, b, c 移动到他们的相应的位置 + 1共三步操作,而inferno.js则是直接将d移动到最前端这一步操作.