Vue | diff算法

虚拟DOM(Virtual DOM)

什么是虚拟DOM

一句话总结虚拟DOM就是一个用来描述真实DOM的javaScript对象,这样说可能不够形象,那我们来举个🌰:分别用代码来描述真实DOM以及虚拟DOM

真实DOM:

<ul class="list">
    <li>a</li>
    <li>b</li>
    <li>c</li>
</ul>

对应的虚拟DOM:

let vnode = h('ul.list', [
  h('li','a'),
  h('li','b'),
  h('li','c'),
])

console.log(vnode)

控制台打印出来的Vnode:

当一个节点变更时DOMA->DOMB

举例:当DOM树里面的某个子节点的内容变更时:

总结:复杂视图情况下提升渲染性能,因为虚拟DOM+Diff算法可以精准找到DOM树变更的地方,减少DOM的操作(重排重绘)

虚拟dom库

snabbdom的核心

• init()设置模块.创建patch()函数
• 使用h()函数创建JavaScript对象(Vnode)描述真实DOM
• patch()比较新旧两个Vnode
• 把变化的内容更新到真实DOM树

h函数和init函数：

具体链接： https://juejin.cn/post/7000266544181674014#heading-11

patch方法

这个方法作用就是，对比当前同层的虚拟节点是否为同一种类型的Vnode(同一类型的标准isSameVnode，下面会讲)：

• 是：继续执行patchVnode方法进行深层比对
• 否：没必要比对了，直接整个节点替换成新虚拟节点

patch的核心原理代码：

function patch(oldVnode, newVnode) {
  // 比较是否为一个类型的节点
  if (sameVnode(oldVnode, newVnode)) {
    // 是：继续进行深层比较
    patchVnode(oldVnode, newVnode)
  } else {
    // 否
    const oldEl = oldVnode.el // 旧虚拟节点的真实DOM节点
    const parentEle = api.parentNode(oldEl) // 获取父节点
    createEle(newVnode) // 创建新虚拟节点对应的真实DOM节点
    if (parentEle !== null) {
      api.insertBefore(parentEle, vnode.el, api.nextSibling(oEl)) // 将新元素添加进父元素
      api.removeChild(parentEle, oldVnode.el)  // 移除以前的旧元素节点
      // 设置null，释放内存
      oldVnode = null
    }
  }

  return newVnode
}

sameVnode方法

patch关键的一步就是sameVnode方法判断是否为同一类型节点，那问题来了，怎么才算是同一类型节点呢？这个类型的标准是什么呢？

咱们来看看sameVnode方法的核心原理代码，就一目了然了

function sameVnode(oldVnode, newVnode) {
  return (
    oldVnode.key === newVnode.key && // key值是否一样
    oldVnode.tagName === newVnode.tagName && // 标签名是否一样
    oldVnode.isComment === newVnode.isComment && // 是否都为注释节点
    isDef(oldVnode.data) === isDef(newVnode.data) && // 是否都定义了data，data包含一些具体信息，例如onclick , style
    sameInputType(oldVnode, newVnode) // 当标签为input时，type必须是否相同
  )
}

patchVnode方法

当我们确定两个节点值得比较之后我们会对两个节点指定patchVnode方法。那么这个方法做了什么呢？

这个函数做了以下事情：

• 找到对应的真实DOM，称为el
• 判断newVnode和oldVnode是否指向同一个对象，如果是，那么直接return
• 如果他们都有文本节点并且不相等，那么将el的文本节点设置为newVnode的文本节点。
• 如果oldVnode有子节点而newVnode没有，则删除el的子节点
• 如果oldVnode没有子节点而newVnode有，则将newVnode的子节点真实化之后添加到el
• 如果两者都有子节点，则执行updateChildren函数比较子节点，这一步很重要

function patchVnode(oldVnode, newVnode) {
  const el = newVnode.el = oldVnode.el // 获取真实DOM对象
  // 获取新旧虚拟节点的子节点数组
  const oldCh = oldVnode.children, newCh = newVnode.children
  // 如果新旧虚拟节点是同一个对象，则终止
  if (oldVnode === newVnode) return
  // 如果新旧虚拟节点是文本节点，且文本不一样
  if (oldVnode.text !== null && newVnode.text !== null && oldVnode.text !== newVnode.text) {
    // 则直接将真实DOM中文本更新为新虚拟节点的文本
    api.setTextContent(el, newVnode.text)
  } else {
    // 否则

    if (oldCh && newCh && oldCh !== newCh) {
      // 新旧虚拟节点都有子节点，且子节点不一样

      // 对比子节点，并更新
      updateChildren(el, oldCh, newCh)
    } else if (newCh) {
      // 新虚拟节点有子节点，旧虚拟节点没有

      // 创建新虚拟节点的子节点，并更新到真实DOM上去
      createEle(newVnode)
    } else if (oldCh) {
      // 旧虚拟节点有子节点，新虚拟节点没有

      //直接删除真实DOM里对应的子节点
      api.removeChild(el)
    }
  }
}

updateChildren方法

这是patchVnode里最重要的一个方法，新旧虚拟节点的子节点对比，就是发生在updateChildren方法中

首尾指针法，新的子节点集合和旧的子节点集合，各有首尾两个指针，举个例子：

：

<ul>
    <li>a</li>
    <li>b</li>
    <li>c</li>
</ul>

修改数据后

<ul>
    <li>b</li>
    <li>c</li>
    <li>e</li>
    <li>a</li>
</ul>

复制代码

那么新旧两个子节点集合以及其首尾指针为：

总共有同级别节点比较的五种情况：

• 1、oldS 和 newS 使用sameVnode方法(key和sel相同)进行比较，sameVnode(oldS, newS)，相同则执行patchVnode找出两者之间的差异，没差异则不操作，有差异则更新
• 2、oldS 和 newE 使用sameVnode方法(key和sel相同)进行比较，sameVnode(oldS, newE)，相同则执行patchVnode找出两者之间的差异，没差异则不操作，有差异则更新
• 3、oldE 和 newS 使用sameVnode方法(key和sel相同)进行比较，sameVnode(oldE, newS)，相同则执行patchVnode找出两者之间的差异，没差异则不操作，有差异则更新，oldCh[oldStartIdx]对应的真实dom位移到oldCh[oldEndIdx]对应的真实dom后
• 4、oldE 和 newE 使用sameVnode方法(key和sel相同)进行比较，sameVnode(oldE, newE)，相同则执行patchVnode找出两者之间的差异，oldCh[oldEndIdx]对应的真实dom位移到oldCh[oldStartIdx]对应的真实dom前
• 5、如果以上逻辑都匹配不到，再把所有旧子节点的 key 做一个映射到旧节点下标的 key -> index 表，然后用新 vnode 的 key 去找出在旧节点中可以复用的位置

循环结束的收尾工作:直到oldStartIdx>oldEndIdx || newStartIdx>newEndIdx(代表旧节点或者新节点已经遍历完)

情况1：

若情况1符合:

• (从新旧节点的开始节点开始对比,oldCh[oldStartIdx]和newCh[newStartIdx]进行sameVnode(key和sel相同)判断是否相同节点)
• 则执行patchVnode找出两者之间的差异,更新图;如没有差异则什么都不操作,结束一次循环 oldStartIdx++/newStartIdx++
  

情况3：

若情况1,2都不符合,就会尝试情况3:

• (旧节点的开始节点与新节点的结束节点开始对比,oldCh[oldStartIdx]和newCh[newEndIdx]对比,执行sameVnode(key和sel相同)判断是否相同节点)
• 执行patchVnode找出两者之间的差异,更新视图,如没有差异则什么都不操作,结束一次循环 oldCh[oldStartIdx]对应的真实dom位移到oldCh[oldEndIdx]对应的真实dom后
• oldStartIdx++/newEndIdx--;
  

情况5：

• 从旧节点里面寻找,若寻找到与newCh[newStartIdx]相同的节点(且叫对应节点[1]),
• 执行patchVnode找出两者之间的差异,更新视图,如没有差异则什么都不操作,结束一次循环
• 对应节点[1]对应的真实dom位移到oldCh[oldStartIdx]对应的真实dom前
  

附上源码(已加上注释便于阅读)：

function updateChildren(parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {

   // 定义变量
   let oldStartIdx = 0  // 老节点Child头下标
   let newStartIdx = 0  // 新节点Child头下标
   let oldEndIdx = oldCh.length - 1  // 老节点Child尾下标
   let oldStartVnode = oldCh[0]      // 老节点Child头结点
   let oldEndVnode = oldCh[oldEndIdx] // 老节点Child尾结点
   let newEndIdx = newCh.length - 1   // 新节点Child尾下标
   let newStartVnode = newCh[0]       // 新节点Child头结点
   let newEndVnode = newCh[newEndIdx]  // 新节点Child尾结点
   let oldKeyToIdx, idxInOld, vnodeToMove, refElm  

   // removeOnly is a special flag used only by <transition-group>
   // to ensure removed elements stay in correct relative positions
   // during leaving transitions
   const canMove = !removeOnly

   if (process.env.NODE_ENV !== 'production') {
     checkDuplicateKeys(newCh)
   }

   // 定义循环
   while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
     // 存在检测
     if (isUndef(oldStartVnode)) {
       oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left
     } else if (isUndef(oldEndVnode)) {
       oldEndVnode = oldCh[--oldEndIdx]

     // 如果老结点Child头和新节点Child头是同一个节点
     } else if (sameVnode(oldStartVnode, newStartVnode)) {
       // patch差异
       patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue)
       // patch完成  移动节点位置  继续比对下一个节点
       oldStartVnode = oldCh[++oldStartIdx]
       newStartVnode = newCh[++newStartIdx]

     // 如果老结点Child尾和新节点Child尾是同一个节点
     } else if (sameVnode(oldEndVnode, newEndVnode)) {
       // patch差异
       patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue)
       // patch完成  移动节点位置 继续比对下一个节点
       oldEndVnode = oldCh[--oldEndIdx]
       newEndVnode = newCh[--newEndIdx]

     // 如果老结点Child头和新节点Child尾是同一个节点
     } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
        // patch差异
       patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue)
       // 把oldStart节点放到oldEnd节点后面
       canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
       // patch完成  移动节点位置 继续比对下一个节点
       oldStartVnode = oldCh[++oldStartIdx]
       newEndVnode = newCh[--newEndIdx]
     // 如果老结点Child尾和新节点Child头是同一个节点
     } else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
        // patch差异
       patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue)
       // 把oldEnd节点放到oldStart节点前面
       canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
       // patch完成  移动节点位置 继续比对下一个节点
       oldEndVnode = oldCh[--oldEndIdx]
       newStartVnode = newCh[++newStartIdx]
     } else {
       // 如果没有相同的Key，执行createElm方法创建元素
       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, false, newCh, newStartIdx)
       } else {
         // 有相同的Key，判断这两个节点是否为sameNode
         vnodeToMove = oldCh[idxInOld]
         if (sameVnode(vnodeToMove, newStartVnode)) {
           // 如果是相同节点，进行patch  然后举将oldStart插入到oldStart之前，newStart下标继续移动
           patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue)
           oldCh[idxInOld] = undefined
           canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
         } else {
           // 如果不是相同节点，需要执行createElm创建新元素
           createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
         }
       }
       newStartVnode = newCh[++newStartIdx]
     }
   }

   // oldStartIdx > oldEndIdx说明oldChild先遍历完，使用addVnode方法添加newStartIdx指向的节点到newEndIdx的节点
   if (oldStartIdx > oldEndIdx) {
     refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm
     addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
   } else if (newStartIdx > newEndIdx) {
     // 如果newStartIdx > newEndIdx说明newChild先遍历完，remove掉oldChild未遍历完的节点
     removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
   }
 }

key的作用

• Diff操作可以更加快速;
• Diff操作可以更加准确;(避免渲染错误)
• 不推荐使用索引作为key

Diff操作可以更加准确;(避免渲染错误):

未设置key

设置key

用索引当作key：

在进行子结点的diff算法中，会用sameNode方法(判断key，sel值是否一致)对结点进行对比，每个结点都会命中sameNode方法(key:索引一样)，每个结点都会执行patchVnode来更新文本，因为文本不一样。

下图中执行patchVnode但不会更新文本。

总结

• 正确使用key，可以快速执行sameVnode比对，加速Diff效率，可以作为性能优化的一个点。
• DIff只做同级比较，使用sameVnode函数比对，文本节点直接替换文本内容。
• 子元素列表的Diff，进行头对头、尾对尾、头对尾等系列比较，直到遍历完两个元素的子元素列表。
• 或一个列表先遍历完了，直接addVnode / removeVnode。

个人总结：

• 数据更新触发订阅者setter函数，setter函数中触发Dep.notify函数，notify触发Dep容器中的所有订阅者watcher执行update()函数，
• 用patch对h函数生成新旧虚拟Dom对象进行对比，patch中先用SameVnode判断是不是同一类结点(即判断key，标签，iscompoment，data中的onclick，style属性等，input的type)，不是的话则直接将整个结点替换新虚拟Dom，
• 是同一类的话进入patchVnode方法进行深层比对，先找到真实结点el，判断是否同一对象，判断文本，文本不一致则替换el的文本，判断旧dom有子节点，新没有，新有子节点，旧没有。
• 都有子节点则进入updateChildren方法，采用首尾指针方法比对，5种情况，进行头对头、尾对尾、头对尾等系列比较，直到遍历完两个元素的子元素列表，遍历的时候两边的指针往中间移动，当首指针大于尾指针则代表遍历完，将剩余的addVnode / removeVnode进入真实dom。

 

参考：

https://www.lebronchao.com/2021/03/24/Vue%E8%BF%9B%E9%98%B6-Diff%E7%AE%97%E6%B3%95%E8%AF%A6%E8%A7%A3-%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/

https://juejin.cn/post/7000266544181674014#heading-11

https://juejin.cn/post/6994959998283907102#heading-8

https://juejin.cn/post/6844903607913938951#heading-6