快速搞懂Vue2 diff算法详解

什么是Vue2 diff算法

Vue中所谓的diff算法是指虚拟DOM的比对过程，即对新旧虚拟DOM进行差异化对比，使用最小代价去更新视图。Vue2中的diff算法主要基于Snabbdom库实现，其核心算法是利用双指针遍历新旧节点数组，进行比对并更新。

Vue2 diff算法比对方式

Vue2 diff算法的比对过程是通过递归进行的，主要包括以下几个步骤：

function patch (oldVnode, vnode) {
  // 判断oldVnode和vnode是否指向同一个节点
  if (sameVnode(oldVnode, vnode)) {
    patchVnode(oldVnode, vnode)
  } else {
    const oEl = oldVnode.el
    // 创建新节点的DOM元素，并插入到旧节点的位置
    const parent = nodeOps.parentNode(oEl)
    createElm(vnode, parent, nodeOps.nextSibling(oEl))

    // 删除旧节点
    nodeOps.removeChild(parent, oldVnode.el)
  }
}

在比对过程中，通过sameVnode函数进行新旧节点的类型比对，如果类型相同，则进入patchVNode函数进行属性比对、子节点比对等操作；如果类型不同，则创建新节点的DOM元素并插入到旧节点的位置，再删除旧节点。

Vue2 diff算法优化方式

Vue2 diff算法存在着一些优化方式，可以有效提升渲染性能，主要包括以下几点：

// 判断新旧节点是否为相同节点
function sameVnode (a, b) {
  return (
    a.key === b.key && (
      (
        a.tag === b.tag && a.isComment === b.isComment && 
        isDef(a.data) === isDef(b.data)
      ) 
        // 对于元素节点，比较input标签type属性
        ? sameInputType(a, b)
        // 对于文本节点，比较内容是否相同
        : isTrueTextNode(b)
    )
  )
}

function sameInputType (a, b) {
  if (a.tag !== 'input') return true
  let i
  const typeA = isDef(i = a.data) && isDef(i = i.attrs) && i.type
  const typeB = isDef(i = b.data) && isDef(i = i.attrs) && i.type
  return typeA === typeB
}

首先是同层级比较节点时，判断新旧节点的key、tag、isComment和data是否相同，比较过程中，对于元素节点比较input标签的type属性，对于文本节点比较内容是否相同，只有全部相同才能进入patch流程进行节点更新操作。

// 根据新的子节点数组生成map映射表
function createKeyToOldIdx (children, beginIdx, endIdx) {
  const map = {}
  for (let i = beginIdx; i <= endIdx; ++i) {
    const key = children[i].key
    if (isDef(key)) map[key] = i
  }
  return map
}

// 把没有key的子节点插入到oldCh的末尾
function updateDirectly (parentElm, oldCh, newCh) {
  const oldStartIdx = 0
  const oldEndIdx = oldCh.length - 1
  const oldStartVnode = oldCh[0]
  const oldEndVnode = oldCh[oldEndIdx]
  const newStartIdx = 0
  const newEndIdx = newCh.length - 1
  const newStartVnode = newCh[0]
  const newEndVnode = newCh[newEndIdx]

  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    if (isUndef(oldStartVnode)) {
      oldStartVnode = oldCh[++oldStartIdx]
    } else if (isUndef(oldEndVnode)) {
      oldEndVnode = oldCh[--oldEndIdx]
    } else if (sameVnode(oldStartVnode, newStartVnode)) {
      patchVnode(oldStartVnode, newStartVnode)
      oldStartVnode = oldCh[++oldStartIdx]
      newStartVnode = newCh[++newStartIdx]
    } else if (sameVnode(oldEndVnode, newEndVnode)) {
      patchVnode(oldEndVnode, newEndVnode)
      oldEndVnode = oldCh[--oldEndIdx]
      newEndVnode = newCh[--newEndIdx]
    } else if (sameVnode(oldStartVnode, newEndVnode)) {
      // 更新旧节点并移动到oldEndIdx的下一个位置
      patchVnode(oldStartVnode, newEndVnode)
      nodeOps.insertBefore(parentElm, oldStartVnode.el, nodeOps.nextSibling(oldEndVnode.el))
      oldStartVnode = oldCh[++oldStartIdx]
      newEndVnode = newCh[--newEndIdx]
    } else if (sameVnode(oldEndVnode, newStartVnode)) {
      // 更新旧节点并移动到oldStartIdx的前一个位置
      patchVnode(oldEndVnode, newStartVnode)
      nodeOps.insertBefore(parentElm, oldEndVnode.el, oldStartVnode.el)
      oldEndVnode = oldCh[--oldEndIdx]
      newStartVnode = newCh[++newStartIdx]
    } else {
      // 都不匹配则暴力新建
      createElm(newStartVnode, parentElm, oldStartVnode.el)
      newStartVnode = newCh[++newStartIdx]
    }
  }
}

其次是在初次渲染节点时，使用哈希表构建key与旧节点相对应的映射表，在比较过程中使用map表快速定位对应key值的节点进行比对，提升渲染效率。

Vue2 diff算法更新策略

Vue2 diff算法在进行节点更新时，其更新策略表现为以下几个方面：

// 更新节点属性和子节点
function updateChildren (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, vnodeToMove, refElm

  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    if (isUndef(oldStartVnode)) {
      oldStartVnode = oldCh[++oldStartIdx]
    } else if (isUndef(oldEndVnode)) {
      oldEndVnode = oldCh[--oldEndIdx]
    } else if (sameVnode(oldStartVnode, newStartVnode)) {
      // 新旧节点头部匹配，比较属性并更新
      patchVnode(oldStartVnode, newStartVnode)
      oldStartVnode = oldCh[++oldStartIdx]
      newStartVnode = newCh[++newStartIdx]
    } else if (sameVnode(oldEndVnode, newEndVnode)) {
      // 新旧节点尾部匹配，比较属性并更新
      patchVnode(oldEndVnode, newEndVnode)
      oldEndVnode = oldCh[--oldEndIdx]
      newEndVnode = newCh[--newEndIdx]
    } else if (sameVnode(oldStartVnode, newEndVnode)) {
      // 新起点匹配旧终点
      patchVnode(oldStartVnode, newEndVnode)
      nodeOps.insertBefore(parentElm, oldStartVnode.el, nodeOps.nextSibling(oldEndVnode.el))
      oldStartVnode = oldCh[++oldStartIdx]
      newEndVnode = newCh[--newEndIdx]
    } else if (sameVnode(oldEndVnode, newStartVnode)) {
      // 新终点匹配旧起点
      patchVnode(oldEndVnode, newStartVnode)
      nodeOps.insertBefore(parentElm, oldEndVnode.el, oldStartVnode.el)
      oldEndVnode = oldCh[--oldEndIdx]
      newStartVnode = newCh[++newStartIdx]
    } else {
      // 遍历旧节点数组，根据key值查找对应节点索引
      if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
      idxInOld = oldKeyToIdx[newStartVnode.key]
      if (isUndef(idxInOld)) {
        // 没有匹配到旧节点则创建新节点
        createElm(newStartVnode, parentElm, oldStartVnode.el)
      } else {
        // 匹配到旧节点则更新
        vnodeToMove = oldCh[idxInOld]
        if (sameVnode(vnodeToMove, newStartVnode)) {
          patchVnode(vnodeToMove, newStartVnode)
          oldCh[idxInOld] = undefined
          nodeOps.insertBefore(parentElm, vnodeToMove.el, oldStartVnode.el)
        } else {
          createElm(newStartVnode, parentElm, oldStartVnode.el)
        }
      }
      // 将新节点指向当前节点的下一个节点
      newStartVnode = newCh[++newStartIdx]
    }
  }
}

当新旧节点数组存在交叉匹配、出现增删操作时，根据匹配的情况进行节点更新或新建操作，匹配规则与sameVnode类似。