虚拟 DOM 和 DOM diff

引

作为前端，相信对于 DOM 已经很熟悉了。DOM 就是文档对象模型，是 HTML 和 XML 文档的编程接口，它是一个树结构，提供了对文档的结构化的表述，并定义了一种方式可以使从程序中对该结构进行访问。

那什么是 虚拟 DOM 呢？

虚拟 DOM

虚拟 DOM （Virtual DOM） 是 JavaScript 中的一个对象，使用该对象模拟 DOM 节点，最后使用特定的 Render 方法将该对象渲染为真实的 DOM。

优点

虚拟 DOM 本质是一个 JavaScript 对象，所以它不仅可以映射 HTML 的 DOM，还可以扩展到小程序、原生应用等其他平台。
可以通过 DOM Diff 算法来优化 DOM 操作。通过 Diff 合并多余操作进而提高了性能。

缺点

由于虚拟 DOM 是一个对象，所以它不能直接渲染到页面上，需要使用特定的 Render 方法来渲染。例如 React 中的 createElement 方法，Vue 中的 h 方法等。

React

1
2
3
4
5
6
7
8
9


// createElement(type, props, children)
const element = React.createElement(
  'div',
  { className: 'foo' },
  'Hello World'
);

// jsx
const element = <div className="foo">Hello World</div>;

1
2
3
4


// h(type, props, children)const element = h('div', { className: 'foo' }, 'Hello World');

// jsxconst element =
<div className = "foo">Hello World</div>;

DOM Diff

DOM diff 就是对虚拟 DOM 的对比算法，Dom diff，通过 JS 层面的计算，返回一个 patch 对象，即补丁对象，再通过特定的操作解析 patch 对象，省略不必要的操作，完成页面的重新渲染，提高页面渲染性能。

在 jQuery 时代，都是用我们自己业务的一些算法，手动进行 DOM 的操作，比如我们调用的 .append 和 .remove 之类的方法。

这样的问题很明显，就是业务心智负担太重，对于复杂系统，需要做 Diff 的地方太多，不仅写起来繁琐，当状态存在交错时，手动 Dom Diff 容易出现遗漏，Bug 甚至程序崩溃，代码的可维护性也很差。

解决方案就是数据驱动视图，我们只需要关注数据和 UI 如何映射，具体的 DOM 操作由框架进行操作，这样无论业务逻辑多复杂，我们只需要解决映射关系就可以了。目前前端的框架主流已经从面向操作转变为数据驱动视图，这样框架就必须作 DOM Diff 算法来优化 DOM 操作，否则容易引发性能问题。

理想的 DOM Diff

最理想的 Dom diff 自然是复用所有能复用的，实在遇到新增或删除时，才执行插入或删除。可惜程序无法猜到人的想法，所以想要精确复用的话，在某些情况下时间复杂度会很离谱 - O(n³) ，这显然对于性能的消耗是巨大的，因此无法被使用。

现实的 DOM Diff

Vue 的 DOM Diff 是 深度优先，同层比较 的策略。 Vue 的 Diff

新节点与旧节点的比较主要是围绕三件事来达到渲染目的：

创建新节点

当新树包含旧树没有的节点，此时直接创建新节点。只有元素节点，文本节点，注释节点才能被创建插入到 DOM 中。

删除旧节点

当旧树包含新树没有的节点，意味着新树放弃了旧树的一部分，此时直接删除桕树多出的节点，删除节点会连带的删除节点的子节点。

更新节点

新的节点与旧的的节点都有，那么以新的为准，更新旧节点。如何判断是否需要更新节点呢?

完全一致的话就不需要更新

1
2
3
4


// 判断vnode与oldVnode是否完全一样
if (oldVnode === vnode){
  return;
}

判断新节点与旧节点是否是静态节点，key 是否一样，是否是克隆节点(如果不是克隆节点，那么意味着渲染函数被重置了，这个时候需要重新渲染) 或者是否设置了 once 属性,满足条件的话替换 componentInstance

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


// 是否是静态节点，key是否一样，是否是克隆节点或者是否设置了once属性
if (
  isTrue(vnode.isStatic) &&
  isTrue(oldVnode.isStatic) &&
  vnode.key === oldVnode.key &&
  (isTrue(vnode.isCloned) || isTrue(vnode.isOnce))
){
  vnode.componentInstance = oldVnode.componentInstance;
  return;
}

判断新节点是否有 text，如果有那么需要比较同层级旧节点，如果旧节点文本不同于新节点文本，那么采用新的文本内容。如果新节点没有文本，那么后面需要对子节点的相关情况进行判断

1
2
3
4
5
6
7
8


// 判断新节点是否有文本
if (isUndef(vnode.text)){
  // 如果没有文本，处理子节点的相关代码
  // ......
} else if (oldVnode.text !== vnode.text){
  // 新节点文本替换旧节点文本
  nodeOps.setTextContent(elm, vnode.text)
}

判断新节点与旧节点的子节点相关状况。新增和删除逻辑与上面基本一致，都不存在子节点则不用处理子节点。如果都存在子节点，则需要进行 Diff，这里的重点就是子节点的 比较更新（updateChildren），Vue 主要是双端比较。

比较更新 updateChildren

新旧节点都有子节点的情况下，这个时候是需要调用 updateChildren 方法来比较更新子节点的。所以在数据上，新旧节点子节点，就保存为了两个数组。子节点更新采用的是 双端比较 的策略，就是新旧节点比较是通过互相比较首尾元素，然后向中间靠拢比较（newStartIdx、oldStartIdx递增，newEndIdx、oldEndIdx递减）的策略。

1
2


const oldCh = [oldVnode1, oldVnode2, oldVnode3];
const newCh = [newVnode1, newVnode2, newVnode3];

双端比较

向中间靠拢

子节点比较过程

新前与旧前 比较，如果他们相同，那么进行上面说到的 patch VNode 更新操作，然后新旧节点各向后一步，进行第二项的比较，直到遇到不同则切换下一种比较方式

1
2
3
4
5
6
7
8


if (sameVnode(oldStartVnode, newStartVnode)){
  // 更新子节点
  patchVnode(
    oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
  // 新旧各向后一步
  oldStartVnode = oldCh[++ oldStartIdx]
  newStartVnode = newCh[++ newStartIdx]
}

新后与旧后 比较，如果他们相同，同样进行 patch VNode 更新，然后新旧各向前一步，进行前一项的比较，直到遇到不同则切换下一种比较方式

1
2
3
4
5
6
7


if (sameVnode(oldEndVnode, newEndVnode)){
  //更新子节点
  patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
  // 新旧向前
  oldEndVnode = oldCh[-- oldEndIdx]
  newEndVnode = newCh[-- newEndIdx]
}

新后与旧前 比较，如果它们相同，就进行更新操作，然后将 旧前移动到所有未处理旧节点数组最后面，使旧前与新后位置保持一致，然后新向前，旧向后，一起向中间靠拢。如果不同会继续切换比较方式

1
2
3
4
5
6
7
8
9


if (sameVnode(oldStartVnode, newEndVnode)){
  patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
  //将旧子节点数组第一个子节点移动插入到最后
  canMove && nodeOps.insertBefore(
    parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
  //旧向后
  oldStartVnode = oldCh[++ oldStartIdx]
  //新向前
  newEndVnode = newCh[-- newEndIdx]

新前与旧后 比较，如果他们相同，就进行更新，然后将 旧后移动到所有未处理旧节点数组最前面 ，使旧后与新前位置保持一致，然后新向后，旧向前，一起向中间靠拢，继续比较剩余的节点。如果不同，就使用传统的循环遍历查找。

1
2
3
4
5
6
7
8
9


if (sameVnode(oldEndVnode, newStartVnode)){
  patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
  //将旧后移动插入到最前
  canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
  //旧向前
  oldEndVnode = oldCh[-- oldEndIdx]
  //新向后
  newStartVnode = newCh[++ newStartIdx]
}

循环遍历查找，上面四种都没找到的情况下，会通过key去查找匹配。

进行到这一步对于没有设置 key 的节点，第一次会通过 createKeyToOldIdx 建立 key 与 index 的映射 { key: index }

1
2
3


// 对于没有设置key的节点，第一次会通过createKeyToOldIdx建立key与index的映射 {key:index}
if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(
  oldCh, oldStartIdx, oldEndIdx)

然后拿新节点的key与旧节点进行比较，找到 key 值匹配的节点的位置，这里需要注意的是，如果新节点也没 key，那么就会执行 findIdxInOld 方法，从头到尾遍历匹配旧节点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


//通过新节点的key,找到新节点在旧节点中所在的位置下标,如果没有设置key，会执行遍历操作寻找
idxInOld = isDef(newStartVnode.key)
  ? oldKeyToIdx[newStartVnode.key]
  : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)

//findIdxInOld方法
function findIdxInOld (node, oldCh, start, end){
  for (let i = start; i < end; i ++){
    const c = oldCh[i]
    //找到相同节点下标
    if (isDef(c) && sameVnode(node, c)) return i
  }
}

如果通过上面的方法，依旧没找到新节点与旧节点匹配的下标，那就说明这个节点是新节点，那就执行新增的操作。

1
2
3
4
5
6
7


//如果新节点无法在旧节点中找到自己的位置下标,说明是新元素，执行新增操作
if (isUndef(idxInOld)){
  createElm(
    newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false,
    newCh, newStartIdx
  )
}

如果找到了，那么说明在旧节点中找到了 key 值一样，或者节点和 key 都一样的旧节点。如果节点一样，那么在 patch VNode 之后，需要将旧节点移动到所有未处理节点之前，对于 key 一样，元素不同的节点，将其认为是新节点，执行新增操作。执行完成后，新节点向后一步。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


//如果新节点无法在旧节点中找到自己的位置下标,说明是新元素，执行新增操作
if (isUndef(idxInOld)){
  // 新增元素
  createElm(
    newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false,
    newCh, newStartIdx
  )
} else{
  // 在旧节点中找到了key值一样的节点
  vnodeToMove = oldCh[idxInOld]
  if (sameVnode(vnodeToMove, newStartVnode)){
    // 相同子节点更新操作
    patchVnode(
      vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
    // 更新完将旧节点赋值undefined
    oldCh[idxInOld] = undefined
    //将旧节点移动到所有未处理节点之前
    canMove && nodeOps.insertBefore(
      parentElm, vnodeToMove.elm, oldStartVnode.elm)
  } else{
    // 如果是相同的key，不同的元素，当做新节点，执行创建操作
    createElm(
      newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false,
      newCh, newStartIdx
    )
  }
}
//新节点向后
newStartVnode = newCh[++ newStartIdx]

当完成对旧节点的遍历，但是新节点还没完成遍历，那就说明后续的都是新增节点，执行新增操作，如果完成对新节点遍历，旧节点还没完成遍历，那么说明旧节点出现冗余节点，执行删除操作。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


//完成对旧节点的遍历，但是新节点还没完成遍历，
if (oldStartIdx > oldEndIdx){
  refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm
  // 新增节点
  addVnodes(
    parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
} else if (newStartIdx > newEndIdx){
  // 发现多余的旧节点，执行删除操作
  removeVnodes(oldCh, oldStartIdx, oldEndIdx)
}

上面就是子节点比较更新的一个完整过程

参考资料