虚拟DOM&diff

什么是虚拟DOM

Virtual DOM 虚拟dom 是对DOM 的抽象，本质上是javascript对象，这个对象就是更加轻量的描述DOM。简写vdom；

真实DOM (真正的DOM 元素是非常庞大的，因为浏览器的标准就把DOM设计的非常复杂)

<ul id='list'>
  <li class='item'>itemB</li>
</ul>

虚拟DOM

{  
    tag:'ul',  // 元素的标签类型
    attrs:{  //  表示指定元素身上的属性
        id:'list'
    },
    children:[  // ul元素的子节点
        {
            tag: 'li',
            attrs:{
                className:'item'
            },
            children:['itemA']
        }
    ]
}

虚拟DOM这个对象的参数分析：

• tag: 指定元素的标签类型，案例为：'ul' （react中用type）
• attrs: 表示指定元素身上的属性，如id,class, style, 自定义属性等（react中用props）
• children: 表示指定元素是否有子节点，参数以数组的形式传入,如果是文本就是数组中为字符串

为啥需要虚拟DOM

• 前端性能优化（减少操作DOM）， 因为频繁操作DOM会造成浏览器的回流或者重绘，因此需要这一层抽象，在patch更新过程中尽可能地一次性将差异更新到DOM中。
• 无需手动操作DOM，统一patch更新。
• 打开函数式UI编程的大门。
• 更好的跨平台，比如Node.js就没有DOM,如果想实现SSR(服务端渲染),那么一个方式就是借助Virtual DOM, 在ReactNative，React VR、weex都是使用了虚拟dom。

虚拟DOM的缺点

• 首次渲染大量 DOM 时，多了一层虚拟 DOM 的计算，会比innerHTML 插入慢。（内存中多了一份DOM副本）
• 如果你的场景是虚拟 DOM 大量更改，这是合适的。但是单一的，频繁的更新的话，虚拟 DOM 将会花费更多的时间处理计算的工作。

虚拟DOM总结

• 1、虚拟DOM 是一个js 对象。
• 2、DOM 操作是非常昂贵的。

利用snabbdom.js来看虚拟dom 的实现流程

虚拟dom主要有以下三个过程：

• compile, 如何把真实dom 编译成vnode 虚拟dom对象。
• diff, 如何知道oldVnode 和newVnode 的变化
• patch, 如何把变化用补丁的方式更新到真实dom 上。（patch(vnode, newVnode)）

diff 算法

diff算法是一种通过同层的树节点进行比较的高效算法，避免了对树进行逐层搜索遍历，所以时间复杂度是 O(n) （vue之前的源码是采用 先 diff，得到差异，然后根据差异在去 patch 真实 dom）

Vue的diff算法是基于snabbdom改造过来的

这是一张很经典的图，出自《React’s diff algorithm》，Vue的diff算法也同样，即仅在同级的vnode间做diff，递归地进行同级vnode的diff，最终实现整个DOM树的更新。

具体diff 过程参照文章和下文的vue 的patchChild 源码。

function patchChildren(parentElm, oldCh, newCh) {
  let oldStartIdx = 0;
  let oldEndIdx = oldCh.length - 1;
  let oldStartVnode = oldCh[0];
  let oldEndVnode = oldCh[oldEndIdx];

  let newStartIdx = 0;
  let newEndIdx = newCh.length - 1;
  let newStartVnode = newCh[0];
  let newEndVnode = newCh[newEndIdx];
  let oldKeyToIdx, idxInOld, elmToMove, refElm;

  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    if (!oldStartVnode) {
      oldStartVnode = oldCh[++oldStartIdx];
    } else if (!oldEndVnode) {
      oldEndVnode = oldCh[--oldEndIdx];
    }

    else if (sameVnode(oldStartVnode, newStartVnode)) { //旧首 和 新首相同
      patchVnode(oldStartVnode.elm, oldStartVnode, newStartVnode);
      oldStartVnode = oldCh[++oldStartIdx];
      newStartVnode = newCh[++newStartIdx];
    }

    else if (sameVnode(oldEndVnode, newEndVnode)) { //旧尾 和 新尾相同
      patchVnode(oldEndVnode.elm, oldEndVnode, newEndVnode);
      oldEndVnode = oldCh[--oldEndIdx];
      newEndVnode = newCh[--newEndIdx];
    }

    else if (sameVnode(oldStartVnode, newEndVnode)) { //旧首 和 新尾相同,将旧首移动到 最后面
      patchVnode(oldStartVnode.elm, oldStartVnode, newEndVnode);
      nodeOps.insertBefore(parentElm, oldStartVnode.elm, oldEndVnode.elm.nextSibling)//将 旧首 移动到最后一个节点后面
      oldStartVnode = oldCh[++oldStartIdx];
      newEndVnode = newCh[--newEndIdx];
    }

    else if (sameVnode(oldEndVnode, newStartVnode)) {//旧尾 和 新首相同 ,将 旧尾 移动到 最前面
      patchVnode(oldEndVnode.elm, oldEndVnode, newStartVnode);
      nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm);
      oldEndVnode = oldCh[--oldEndIdx];
      newStartVnode = newCh[++newStartIdx];
    }

    else {//首尾对比 都不 符合 sameVnode 的话
      //1. 尝试 用 newCh 的第一项在 oldCh 内寻找 sameVnode
      let elmToMove = oldCh[idxInOld];
      if (!oldKeyToIdx) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
      idxInOld = newStartVnode.key ? oldKeyToIdx[newStartVnode.key] : null;
      if (!idxInOld) {//如果 oldCh 不存在 sameVnode 则直接创建一个
        nodeOps.createElm(newStartVnode, parentElm);
        newStartVnode = newCh[++newStartIdx];
      } else {
        elmToMove = oldCh[idxInOld];
        if (sameVnode(elmToMove, newStartVnode)) {
          patchVnode(elmToMove, newStartVnode);
          oldCh[idxInOld] = undefined;
          nodeOps.insertBefore(parentElm, newStartVnode.elm, oldStartVnode.elm);
          newStartVnode = newCh[++newStartIdx];
        } else {
          nodeOps.createElm(newStartVnode, parentElm);
          newStartVnode = newCh[++newStartIdx];
        }
      }
    }
  }

  if (oldStartIdx > oldEndIdx) {
    refElm = (newCh[newEndIdx + 1]) ? newCh[newEndIdx + 1].elm : null;
    nodeOps.addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx);
  } else if (newStartIdx > newEndIdx) {
    nodeOps.removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx);
  }
}

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)
      )
    )
  )
}

Vue通过以下措施来提升diff的性能：

• 优先处理特殊场景(头部\尾部, 头尾/尾头等情况) 好处是：（一方面一些不需要做移动的DOM得到快速处理，另一方面待处理节点变少，缩小了后续操作的处理范围，性能也得到提升）
• “原地复用” ，Vue在判断更新前后指针是否指向同一个节点，其实不要求它们真实引用同一个DOM节点，实际上它仅判断指向的是否是同类节点（比如2个不同的div，在DOM上它们是不一样的，但是它们属于同类节点），如果是同类节点，那么Vue会直接复用DOM，这样的好处是不需要移动DOM。

案例：有1 - 9 个子节点，变化过程

• 头部相同、尾部相同的节点：如1、10
• 头尾相同的节点：如2、9（处理完头部相同、尾部相同节点之后）
• 新增的节点：11
• 删除的节点：8
• 其他节点：3、4、5、6、7

[案例] cloud.tencent.com/developer/a…

其他：当进行跨层级的移动操作，并不是简单的进行移动，而是进行了删除和创建的操作。 案例： 当根节点发现子节点中 A 消失了，就会直接销毁 A；当 D 发现多了一个子节点 A，则会创建新的 A（包括子节点）作为其子节点。此时，diff 的执行情况：create A -> create B -> create C -> delete A。

总结

• ps：vue中将数据维护成了可观察的数据，数据的每一项都通过getter来收集依赖，然后将依赖转化成watcher保存在闭包中，数据修改后，触发数据的setter方法，然后调用所有的watcher修改旧的虚拟dom，从而生成新的虚拟dom，然后就是运用diff算法 ，得出新旧dom不同，根据不同更新真实dom。

整个虚拟dom的实现流程：

• 用JavaScript对象模拟DOM
• 把此虚拟DOM转成真实DOM插入到页面中
• 如果有事件发生修改了，需生成新的虚拟DOM
• 比较两颗虚拟dom树的差异，得到差异对象 （也可称为补丁）
• 把差异对象应用到真是的DOM树上

知道了这一过程之后的注意点

• 尽量不要跨层级的修改dom
• 在开发组件时，保持稳定的 DOM 结构会有助于性能的提升
• 设置key可以让diff更高效

面试 聊一聊 diff 算法

传统 diff 算法的时间复杂度是 O(n^3)，这在前端 render 中是不可接受的。为了降低时间复杂度，react 的 diff 算法做了一些妥协，放弃了最优解，最终将时间复杂度降低到了 O(n)。 参考如下：

• 1、tree diff：只对比同一层的 dom 节点，忽略 dom 节点的跨层级移动

如下图，react 只会对相同颜色方框内的 DOM 节点进行比较，即同一个父节点下的所有子节点。当发现节点不存在时，则该节点及其子节点会被完全删除掉，不会用于进一步的比较。

这样只需要对树进行一次遍历，便能完成整个 DOM 树的比较。 这就意味着，如果 dom 节点发生了跨层级移动，react 会删除旧的节点，生成新的节点，而不会复用。

• 2、component diff：如果不是同一类型的组件，会删除旧的组件，创建新的组件。
• 3、element diff：对于同一层级的一组子节点，需要通过唯一 id 进行来区分

如果没有 id 来进行区分，一旦有插入动作，会导致插入位置之后的列表全部重新渲染。这也是为什么渲染列表时为什么要使用唯一的 key。

snabbdom.js

virtual-dom

github.com/aooy/blog/i… juejin.cn/post/684490… juejin.cn/post/684490… juejin.cn/post/684490…