VUE DIFF原理以及核心代码

VUE DIFF :

● 对于同层级节点首先对比新旧节点的头尾，头与头、尾与尾分别进行对比，寻找未移动的节点。

● 新旧节点头尾对比完后，然后进行头与尾、尾与头的交叉对比，这一步的目的是寻找可复用的节点。

● 在交叉对比结束后，因为有可能还有可复用的节点，所以创建一个老节点 keyToIndex 的哈希表 map 记录 key，然后继续遍历新节点索引通过 key 查找可以复用的旧的节点。

● 节点遍历完成后，通过新老索引，移除多余旧节点或者增加新节点。

核心代码

Vue2 的 diff 算法是一种用来比较新旧虚拟 DOM 的算法，它的目的是找出最少的 DOM 操作来更新视图。

Vue2 的 diff 算法的核心思想是 双端比较，也就是同时从新旧虚拟 DOM 的头部和尾部开始比较，通过四个指针来移动和匹配节点，从而减少不必要的遍历。

Vue2 的 diff 算法的核心代码如下：

// patchVnode 函数用来对比两个节点是否相同，如果相同则进行更新，如果不同则直接替换
function patchVnode(oldVnode, vnode, insertedVnodeQueue, removeOnly) {
  // 如果两个节点完全相同，直接返回
  if (oldVnode === vnode) {
    return
  }
  // 获取旧节点的真实 DOM 元素
  const elm = vnode.elm = oldVnode.elm

  // 如果两个节点都是静态的，且 key 相同，并且新节点已经被克隆或者有标记位
  // 则可以认为两个节点相同，直接跳过
  if (isTrue(vnode.isStatic) &&
    isTrue(oldVnode.isStatic) &&
    vnode.key === oldVnode.key &&
    (isTrue(vnode.isCloned) || isTrue(vnode.isOnce))
  ) {
    return
  }

  // 如果新节点是文本节点，直接更新文本内容
  if (isUndef(vnode.text)) {
    if (isDef(oldVnode.text)) {
      nodeOps.setTextContent(elm, '')
    }
    // 如果新节点不是文本节点，且有子节点
    if (isDef(vnode.children)) {
      // 如果旧节点也有子节点，则对子节点进行 diff
      if (isDef(oldVnode.children)) {
        updateChildren(elm, oldVnode.children, vnode.children, insertedVnodeQueue, removeOnly)
      } else {
        // 如果旧节点没有子节点，则添加新节点的子节点到 DOM 中
        addVnodes(elm, null, vnode.children, 0, vnode.children.length - 1, insertedVnodeQueue)
      }
    } else if (isDef(oldVnode.children)) {
      // 如果新节点没有子节点，但旧节点有子节点，则移除旧节点的子节点
      removeVnodes(elm, oldVnode.children, 0, oldVnode.children.length - 1)
    }
  } else if (oldVnode.text !== vnode.text) {
    // 如果新旧节点都是文本节点，但内容不同，则更新文本内容
    nodeOps.setTextContent(elm, vnode.text)
  }
}

// updateChildren 函数用来对比两个虚拟 DOM 数组，找出最小的 DOM 操作
function updateChildren(parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {
  // 定义四个指针分别指向新旧数组的头部和尾部
  let oldStartIdx = 0
  let newStartIdx = 0
  let oldEndIdx = oldCh.length - 1
  let oldStartVnode = oldCh[0]
  let oldEndVnode = oldCh[oldEndIdx]
  let newEndIdx = newCh.length - 1
  let newStartVnode = newCh[0]
  let newEndVnode = newCh[newEndIdx]
  
  // 定义一个 map 对象用来存储旧数组中每个节点的 key 和索引的映射关系，方便查找
  let oldKeyToIdx, idxInOld, vnodeToMove, refElm

  
  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    // 跳过已经被处理过的空节点
    if (isUndef(oldStartVnode)) {
      oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left
    } else if (isUndef(oldEndVnode)) {
      oldEndVnode = oldCh[--oldEndIdx]
    } else if (sameVnode(oldStartVnode, newStartVnode)) {
      // 如果新旧数组的头部节点相同，就对比并更新这两个节点，然后头部指针后移
      patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
      oldStartVnode = oldCh[++oldStartIdx]
      newStartVnode = newCh[++newStartIdx]
    } else if (sameVnode(oldEndVnode, newEndVnode)) {
      // 如果新旧数组的尾部节点相同，就对比并更新这两个节点，然后尾部指针前移
      patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
      oldEndVnode = oldCh[--oldEndIdx]
      newEndVnode = newCh[--newEndIdx]
    } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
      // 如果旧数组的头部节点和新数组的尾部节点相同，就对比并更新这两个节点，然后把旧节点移动到右边，然后头尾指针都移动
      patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
      canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
      oldStartVnode = oldCh[++oldStartIdx]
      newEndVnode = newCh[--newEndIdx]
    } else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
      // 如果旧数组的尾部节点和新数组的头部节点相同，就对比并更新这两个节点，然后把旧节点移动到左边，然后头尾指针都移动
      patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
      canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
      oldEndVnode = oldCh[--oldEndIdx]
      newStartVnode = newCh[++newStartIdx]
    } else {
      // 如果以上四种情况都不满足，就需要用 map 对象来查找新节点在旧数组中是否存在
      if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
      idxInOld = isDef(newStartVnode.key)
        ? oldKeyToIdx[newStartVnode.key]
        : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
      
      // 如果不存在，说明是新创建的节点，就把它插入到旧头节点的前面
      if (isUndef(idxInOld)) { // New element
        createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm)
      } else {
        // 如果存在，就拿到对应的旧节点
        vnodeToMove = oldCh[idxInOld]
        // 如果两个节点相同，就对比并更新这两个节点，然后把旧节点移动到旧头节点的前面，并把原来的位置置空
        if (sameVnode(vnodeToMove, newStartVnode)) {
          patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
          canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
          oldCh[idxInOld] = undefined
        } else {
          // 如果两个节点不同，说明 key 相同但是元素不同，就创建一个新的元素，并插入到旧头节点的前面
          createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm)
        }
      }
      // 新数组的头指针后移
      newStartVnode = newCh[++newStartIdx]
    }
  }
  // 如果旧数组先遍历完，说明有新的节点需要添加
  if (oldStartIdx > oldEndIdx){
      // 把新数组中剩余的节点添加到 DOM 中
    addVnodes(parentElm, null, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
  } else if (newStartIdx > newEndIdx) {
    // 如果新数组先遍历完，说明有旧的节点需要移除
    removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
  }
}

代码总结

• 定义四个指针，分别指向新旧虚拟 DOM 数组的头部和尾部。
• 从两端开始比较，如果头部或尾部的节点相同，就对比并更新这两个节点，然后移动指针。
• 如果头尾交叉的节点相同，就对比并更新这两个节点，然后把旧节点移动到合适的位置，然后移动指针。
• 如果以上情况都不满足，就用一个 map 对象来存储旧数组中每个节点的 key 和索引的映射关系，然后根据新节点的 key 来查找旧节点是否存在。
• 如果存在，就对比并更新这两个节点，然后把旧节点移动到合适的位置，并把原来的位置置空。
• 如果不存在，就创建一个新的节点，并插入到合适的位置。
• 重复以上步骤，直到有一个数组遍历完。
• 如果旧数组先遍历完，说明有新的节点需要添加，就把新数组中剩余的节点添加到 DOM 中。
• 如果新数组先遍历完，说明有旧的节点需要移除，就把旧数组中剩余的节点从 DOM 中移除。

这样就可以实现最小化的 DOM 操作，提高渲染性能。