Vue中diff算法的理解

前端开发作者： 2024-08-21 16:25:01

Vue中diff算法的理解 diff算法用来计算出Virtual DOM中改变的部分，然后针对该部分进行DOM操作，而不用重新渲染整个页面，渲染整个DOM结构的过程中开销是很大的，需要浏览器对DOM结

Vue中diff算法的理解

<div class="root" name="root">
    <p>1</p>
    <div>11</div>
</div>

{
    type: "tag",tagName: "div",attr: {
        className: "root"
        name: "root"
    },parent: null,children: [{
        type: "tag",tagName: "p",attr: {},parent: {} /* 父节点的引用 */,children: [{
            type: "text",tagName: "text",content: "1"
        }]
    },{
        type: "tag",content: "11"
        }]
    }]
}

时间复杂度

diff策略

两个不同类型的元素将产生不同的树。
通过渲染器附带key属性，开发者可以示意哪些子元素可能是稳定的。

只进行统一层级的比较，如果跨层级的移动则视为创建和删除操作。
如果是不同类型的元素，则认为是创建了新的元素，而不会递归比较他们的孩子。
如果是列表元素等比较相似的内容，可以通过key来唯一确定是移动还是创建或删除操作。

此节点被添加或移除->添加或移除新的节点。
属性被改变->旧属性改为新属性。
文本内容被改变->旧内容改为新内容。
节点tag或key是否改变->改变则移除后创建新元素。

分析

// line 714
const isRealElement = isDef(oldVnode.nodeType)
if (!isRealElement && sameVnode(oldVnode,vnode)) {
    // patch existing root node
    patchVnode(oldVnode,vnode,insertedVnodeQueue,null,removeOnly)
}else{
    // ...
}

// line 35
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)
      ) || (
        isTrue(a.isAsyncPlaceholder) &&
        a.asyncFactory === b.asyncFactory &&
        isUndef(b.asyncFactory.error)
      )
    )
  )
}

key必须相同，如果都是undefined则也是相同的。
DOM元素的标签必须相同。

// line 501
function patchVnode (oldVnode,removeOnly) {
    // ...
    if (isDef(data) && isPatchable(vnode)) {
      for (i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode,vnode)
      if (isDef(i = data.hook) && isDef(i = i.update)) i(oldVnode,vnode)
    }
    //...
}

如果孩子不是textNode，那么需要再分三种情况处理。
如果当前孩子是textNode那么直接更新text即可。

有新孩子无旧孩子，直接创建新的。
有旧孩子无新孩子，直接删除旧的。
新旧孩子都有，那么调用updateChildren。

if (isUndef(vnode.text)) {
  if (isDef(oldCh) && isDef(ch)) {
    if (oldCh !== ch) updateChildren(elm,oldCh,ch,removeOnly)
  } else if (isDef(ch)) {
    if (process.env.NODE_ENV !== 'production') {
      checkDuplicateKeys(ch)
    }
    if (isDef(oldVnode.text)) nodeOps.setTextContent(elm,'')
    addVnodes(elm,ch.length - 1,insertedVnodeQueue)
  } else if (isDef(oldCh)) {
    removeVnodes(oldCh,oldCh.length - 1)
  } else if (isDef(oldVnode.text)) {
    nodeOps.setTextContent(elm,'')
  }
} else if (oldVnode.text !== vnode.text) {
  nodeOps.setTextContent(elm,vnode.text)
}

更新了节点
删除了节点
增加了节点
移动了节点

// line 404
function updateChildren (parentElm,newCh,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]
    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]
      } else if (sameVnode(oldStartVnode,newStartVnode)) {
        patchVnode(oldStartVnode,newStartVnode,newStartIdx)
        oldStartVnode = oldCh[++oldStartIdx]
        newStartVnode = newCh[++newStartIdx]
      } else if (sameVnode(oldEndVnode,newEndVnode)) {
        patchVnode(oldEndVnode,newEndVnode,newEndIdx)
        oldEndVnode = oldCh[--oldEndIdx]
        newEndVnode = newCh[--newEndIdx]
      } else if (sameVnode(oldStartVnode,newEndVnode)) { // Vnode moved right
        patchVnode(oldStartVnode,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,newStartIdx)
        canMove && nodeOps.insertBefore(parentElm,oldEndVnode.elm,oldStartVnode.elm)
        oldEndVnode = oldCh[--oldEndIdx]
        newStartVnode = newCh[++newStartIdx]
      } else {
        if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh,oldStartIdx,oldEndIdx)
        idxInOld = isDef(newStartVnode.key)
          ? oldKeyToIdx[newStartVnode.key]
          : findIdxInOld(newStartVnode,oldEndIdx)
        if (isUndef(idxInOld)) { // New element
          createElm(newStartVnode,parentElm,false,newStartIdx)
        } else {
          vnodeToMove = oldCh[idxInOld]
          if (sameVnode(vnodeToMove,newStartVnode)) {
            patchVnode(vnodeToMove,newStartIdx)
            oldCh[idxInOld] = undefined
            canMove && nodeOps.insertBefore(parentElm,vnodeToMove.elm,oldStartVnode.elm)
          } else {
            // same key but different element. treat as new element
            createElm(newStartVnode,newStartIdx)
          }
        }
        newStartVnode = newCh[++newStartIdx]
      }
    }
    if (oldStartIdx > oldEndIdx) {
      refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm
      addVnodes(parentElm,refElm,newStartIdx,newEndIdx,insertedVnodeQueue)
    } else if (newStartIdx > newEndIdx) {
      removeVnodes(oldCh,oldEndIdx)
    }
}

old VNode: a(oldStartIdx) b c d e f(oldEndIdx)
new VNode: b(newStartIdx) f g(newEndIdx)
DOM Node:  a b c d e f

old VNode: a(oldStartIdx) undefined c d e f(oldEndIdx)
new VNode: b f(newStartIdx) g(newEndIdx)
DOM Node:  b a c d e f

old VNode: a(oldStartIdx) undefined c d e(oldEndIdx) f
new VNode: b f g(newStartIdx)(newEndIdx)
DOM Node:  b f a c d e

old VNode: a(oldStartIdx) undefined c d e(oldEndIdx) f
new VNode: b f g(newEndIdx) (newStartIdx)
DOM Node:  b f g a c d e

如果oldStartldx > oldEndldx，说明老节点遍历完成了，新的节点比较多，所以多出来的这些新节点，需要创建出来并添加到真实DOM Node后面。
如果newStartldx >newEndldx，说明新节点遍历完成了，老的节点比较多，所以多出来的这些老节点，需要从真实DOM Node中删除这些节点。

old VNode: a(oldStartIdx) undefined c d e(oldEndIdx) f
new VNode: b f g(newEndIdx) (newStartIdx)
DOM Node:  b f g

https://github.com/WindrunnerMax/EveryDay

https://github.com/aooy/blog/issues/2
https://www.zhihu.com/question/66851503
https://juejin.im/post/6844903607913938951
https://juejin.im/post/6844903592483094535
https://reactjs.org/docs/reconciliation.html
https://www.cnblogs.com/lilicat/p/13448827.html
https://www.cnblogs.com/lilicat/p/13448915.html
https://github.com/lihongxun945/myblog/issues/33
https://www.cnblogs.com/xujiazheng/p/12101764.html
https://blog.csdn.net/dongcehao/article/details/106987886
https://blog.csdn.net/qq2276031/article/details/106407647
https://github.com/Advanced-Frontend/Daily-Interview-Question/issues/151
https://leetcode-cn.com/problems/edit-distance/solution/bian-ji-ju-chi-by-leetcode-solution/

原创声明

本站部分文章基于互联网的整理，我们会把真正“有用/优质”的文章整理提供给各位开发者。本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。

本文链接：http://www.jiecseo.com/news/show_66183.html

相关资讯： Vue中diff算法的理解