问答题1题:说说vue中的diff算法

难度:
更新时间:2022-06-25

参考答案:

预览

一、是什么

diff 算法是一种通过同层的树节点进行比较的高效算法

其有两个特点:

  • 比较只会在同层级进行, 不会跨层级比较
  • 在diff比较的过程中,循环从两边向中间比较

diff 算法的在很多场景下都有应用,在 vue 中,作用于虚拟 dom 渲染成真实 dom 的新旧 VNode 节点比较

二、比较方式

diff整体策略为:深度优先,同层比较

  1. 比较只会在同层级进行, 不会跨层级比较

预览

  1. 比较的过程中,循环从两边向中间收拢

预览

下面举个vue通过diff算法更新的例子:

新旧VNode节点如下图所示:

预览

第一次循环后,发现旧节点D与新节点D相同,直接复用旧节点D作为diff后的第一个真实节点,同时旧节点endIndex移动到C,新节点的 startIndex 移动到了 C

预览

第二次循环后,同样是旧节点的末尾和新节点的开头(都是 C)相同,同理,diff 后创建了 C 的真实节点插入到第一次创建的 B 节点后面。同时旧节点的 endIndex 移动到了 B,新节点的 startIndex 移动到了 E

预览

第三次循环中,发现E没有找到,这时候只能直接创建新的真实节点 E,插入到第二次创建的 C 节点之后。同时新节点的 startIndex 移动到了 A。旧节点的 startIndexendIndex 都保持不动

预览

第四次循环中,发现了新旧节点的开头(都是 A)相同,于是 diff 后创建了 A 的真实节点,插入到前一次创建的 E 节点后面。同时旧节点的 startIndex 移动到了 B,新节点的 startIndex 移动到了 B

预览

第五次循环中,情形同第四次循环一样,因此 diff 后创建了 B 真实节点 插入到前一次创建的 A 节点后面。同时旧节点的 startIndex 移动到了 C,新节点的 startIndex 移动到了 F

预览

新节点的 startIndex 已经大于 endIndex 了,需要创建 newStartIdxnewEndIdx 之间的所有节点,也就是节点F,直接创建 F 节点对应的真实节点放到 B 节点后面

预览

三、原理分析

当数据发生改变时,set方法会调用Dep.notify通知所有订阅者Watcher,订阅者就会调用patch给真实的DOM打补丁,更新相应的视图

源码位置:src/core/vdom/patch.js

1function patch(oldVnode, vnode, hydrating, removeOnly) { 2 if (isUndef(vnode)) { // 没有新节点,直接执行destory钩子函数 3 if (isDef(oldVnode)) invokeDestroyHook(oldVnode) 4 return 5 } 6 7 let isInitialPatch = false 8 const insertedVnodeQueue = [] 9 10 if (isUndef(oldVnode)) { 11 isInitialPatch = true 12 createElm(vnode, insertedVnodeQueue) // 没有旧节点,直接用新节点生成dom元素 13 } else { 14 const isRealElement = isDef(oldVnode.nodeType) 15 if (!isRealElement && sameVnode(oldVnode, vnode)) { 16 // 判断旧节点和新节点自身一样,一致执行patchVnode 17 patchVnode(oldVnode, vnode, insertedVnodeQueue, null, null, removeOnly) 18 } else { 19 // 否则直接销毁及旧节点,根据新节点生成dom元素 20 if (isRealElement) { 21 22 if (oldVnode.nodeType === 1 && oldVnode.hasAttribute(SSR_ATTR)) { 23 oldVnode.removeAttribute(SSR_ATTR) 24 hydrating = true 25 } 26 if (isTrue(hydrating)) { 27 if (hydrate(oldVnode, vnode, insertedVnodeQueue)) { 28 invokeInsertHook(vnode, insertedVnodeQueue, true) 29 return oldVnode 30 } 31 } 32 oldVnode = emptyNodeAt(oldVnode) 33 } 34 return vnode.elm 35 } 36 } 37}

patch函数前两个参数位为oldVnodeVnode ,分别代表新的节点和之前的旧节点,主要做了四个判断:

  • 没有新节点,直接触发旧节点的destory钩子
  • 没有旧节点,说明是页面刚开始初始化的时候,此时,根本不需要比较了,直接全是新建,所以只调用 createElm
  • 旧节点和新节点自身一样,通过 sameVnode 判断节点是否一样,一样时,直接调用 patchVnode 去处理这两个节点
  • 旧节点和新节点自身不一样,当两个节点不一样的时候,直接创建新节点,删除旧节点

下面主要讲的是patchVnode部分

1function patchVnode (oldVnode, vnode, insertedVnodeQueue, removeOnly) { 2 // 如果新旧节点一致,什么都不做 3 if (oldVnode === vnode) { 4 return 5 } 6 7 // 让vnode.el引用到现在的真实dom,当el修改时,vnode.el会同步变化 8 const elm = vnode.elm = oldVnode.elm 9 10 // 异步占位符 11 if (isTrue(oldVnode.isAsyncPlaceholder)) { 12 if (isDef(vnode.asyncFactory.resolved)) { 13 hydrate(oldVnode.elm, vnode, insertedVnodeQueue) 14 } else { 15 vnode.isAsyncPlaceholder = true 16 } 17 return 18 } 19 // 如果新旧都是静态节点,并且具有相同的key 20 // 当vnode是克隆节点或是v-once指令控制的节点时,只需要把oldVnode.elm和oldVnode.child都复制到vnode上 21 // 也不用再有其他操作 22 if (isTrue(vnode.isStatic) && 23 isTrue(oldVnode.isStatic) && 24 vnode.key === oldVnode.key && 25 (isTrue(vnode.isCloned) || isTrue(vnode.isOnce)) 26 ) { 27 vnode.componentInstance = oldVnode.componentInstance 28 return 29 } 30 31 let i 32 const data = vnode.data 33 if (isDef(data) && isDef(i = data.hook) && isDef(i = i.prepatch)) { 34 i(oldVnode, vnode) 35 } 36 37 const oldCh = oldVnode.children 38 const ch = vnode.children 39 if (isDef(data) && isPatchable(vnode)) { 40 for (i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode) 41 if (isDef(i = data.hook) && isDef(i = i.update)) i(oldVnode, vnode) 42 } 43 // 如果vnode不是文本节点或者注释节点 44 if (isUndef(vnode.text)) { 45 // 并且都有子节点 46 if (isDef(oldCh) && isDef(ch)) { 47 // 并且子节点不完全一致,则调用updateChildren 48 if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly) 49 50 // 如果只有新的vnode有子节点 51 } else if (isDef(ch)) { 52 if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '') 53 // elm已经引用了老的dom节点,在老的dom节点上添加子节点 54 addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue) 55 56 // 如果新vnode没有子节点,而vnode有子节点,直接删除老的oldCh 57 } else if (isDef(oldCh)) { 58 removeVnodes(elm, oldCh, 0, oldCh.length - 1) 59 60 // 如果老节点是文本节点 61 } else if (isDef(oldVnode.text)) { 62 nodeOps.setTextContent(elm, '') 63 } 64 65 // 如果新vnode和老vnode是文本节点或注释节点 66 // 但是vnode.text != oldVnode.text时,只需要更新vnode.elm的文本内容就可以 67 } else if (oldVnode.text !== vnode.text) { 68 nodeOps.setTextContent(elm, vnode.text) 69 } 70 if (isDef(data)) { 71 if (isDef(i = data.hook) && isDef(i = i.postpatch)) i(oldVnode, vnode) 72 } 73 }

patchVnode主要做了几个判断:

  • 新节点是否是文本节点,如果是,则直接更新dom的文本内容为新节点的文本内容
  • 新节点和旧节点如果都有子节点,则处理比较更新子节点
  • 只有新节点有子节点,旧节点没有,那么不用比较了,所有节点都是全新的,所以直接全部新建就好了,新建是指创建出所有新DOM,并且添加进父节点
  • 只有旧节点有子节点而新节点没有,说明更新后的页面,旧节点全部都不见了,那么要做的,就是把所有的旧节点删除,也就是直接把DOM 删除

子节点不完全一致,则调用updateChildren

1function updateChildren (parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) { 2 let oldStartIdx = 0 // 旧头索引 3 let newStartIdx = 0 // 新头索引 4 let oldEndIdx = oldCh.length - 1 // 旧尾索引 5 let newEndIdx = newCh.length - 1 // 新尾索引 6 let oldStartVnode = oldCh[0] // oldVnode的第一个child 7 let oldEndVnode = oldCh[oldEndIdx] // oldVnode的最后一个child 8 let newStartVnode = newCh[0] // newVnode的第一个child 9 let newEndVnode = newCh[newEndIdx] // newVnode的最后一个child 10 let oldKeyToIdx, idxInOld, vnodeToMove, refElm 11 12 // removeOnly is a special flag used only by <transition-group> 13 // to ensure removed elements stay in correct relative positions 14 // during leaving transitions 15 const canMove = !removeOnly 16 17 // 如果oldStartVnode和oldEndVnode重合,并且新的也都重合了,证明diff完了,循环结束 18 while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) { 19 // 如果oldVnode的第一个child不存在 20 if (isUndef(oldStartVnode)) { 21 // oldStart索引右移 22 oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left 23 24 // 如果oldVnode的最后一个child不存在 25 } else if (isUndef(oldEndVnode)) { 26 // oldEnd索引左移 27 oldEndVnode = oldCh[--oldEndIdx] 28 29 // oldStartVnode和newStartVnode是同一个节点 30 } else if (sameVnode(oldStartVnode, newStartVnode)) { 31 // patch oldStartVnode和newStartVnode, 索引左移,继续循环 32 patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue) 33 oldStartVnode = oldCh[++oldStartIdx] 34 newStartVnode = newCh[++newStartIdx] 35 36 // oldEndVnode和newEndVnode是同一个节点 37 } else if (sameVnode(oldEndVnode, newEndVnode)) { 38 // patch oldEndVnode和newEndVnode,索引右移,继续循环 39 patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue) 40 oldEndVnode = oldCh[--oldEndIdx] 41 newEndVnode = newCh[--newEndIdx] 42 43 // oldStartVnode和newEndVnode是同一个节点 44 } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right 45 // patch oldStartVnode和newEndVnode 46 patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue) 47 // 如果removeOnly是false,则将oldStartVnode.eml移动到oldEndVnode.elm之后 48 canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm)) 49 // oldStart索引右移,newEnd索引左移 50 oldStartVnode = oldCh[++oldStartIdx] 51 newEndVnode = newCh[--newEndIdx] 52 53 // 如果oldEndVnode和newStartVnode是同一个节点 54 } else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left 55 // patch oldEndVnode和newStartVnode 56 patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue) 57 // 如果removeOnly是false,则将oldEndVnode.elm移动到oldStartVnode.elm之前 58 canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm) 59 // oldEnd索引左移,newStart索引右移 60 oldEndVnode = oldCh[--oldEndIdx] 61 newStartVnode = newCh[++newStartIdx] 62 63 // 如果都不匹配 64 } else { 65 if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx) 66 67 // 尝试在oldChildren中寻找和newStartVnode的具有相同的key的Vnode 68 idxInOld = isDef(newStartVnode.key) 69 ? oldKeyToIdx[newStartVnode.key] 70 : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx) 71 72 // 如果未找到,说明newStartVnode是一个新的节点 73 if (isUndef(idxInOld)) { // New element 74 // 创建一个新Vnode 75 createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm) 76 77 // 如果找到了和newStartVnodej具有相同的key的Vnode,叫vnodeToMove 78 } else { 79 vnodeToMove = oldCh[idxInOld] 80 /* istanbul ignore if */ 81 if (process.env.NODE_ENV !== 'production' && !vnodeToMove) { 82 warn( 83 'It seems there are duplicate keys that is causing an update error. ' + 84 'Make sure each v-for item has a unique key.' 85 ) 86 } 87 88 // 比较两个具有相同的key的新节点是否是同一个节点 89 //不设key,newCh和oldCh只会进行头尾两端的相互比较,设key后,除了头尾两端的比较外,还会从用key生成的对象oldKeyToIdx中查找匹配的节点,所以为节点设置key可以更高效的利用dom。 90 if (sameVnode(vnodeToMove, newStartVnode)) { 91 // patch vnodeToMove和newStartVnode 92 patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue) 93 // 清除 94 oldCh[idxInOld] = undefined 95 // 如果removeOnly是false,则将找到的和newStartVnodej具有相同的key的Vnode,叫vnodeToMove.elm 96 // 移动到oldStartVnode.elm之前 97 canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm) 98 99 // 如果key相同,但是节点不相同,则创建一个新的节点 100 } else { 101 // same key but different element. treat as new element 102 createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm) 103 } 104 } 105 106 // 右移 107 newStartVnode = newCh[++newStartIdx] 108 } 109 }

while循环主要处理了以下五种情景:

  • 当新老 VNode 节点的 start 相同时,直接 patchVnode ,同时新老 VNode 节点的开始索引都加 1
  • 当新老 VNode 节点的 end相同时,同样直接 patchVnode ,同时新老 VNode 节点的结束索引都减 1
  • 当老 VNode 节点的 start 和新 VNode 节点的 end 相同时,这时候在 patchVnode 后,还需要将当前真实 dom 节点移动到 oldEndVnode 的后面,同时老 VNode 节点开始索引加 1,新 VNode 节点的结束索引减 1
  • 当老 VNode 节点的 end 和新 VNode 节点的 start 相同时,这时候在 patchVnode 后,还需要将当前真实 dom 节点移动到 oldStartVnode 的前面,同时老 VNode 节点结束索引减 1,新 VNode 节点的开始索引加 1
  • 如果都不满足以上四种情形,那说明没有相同的节点可以复用,则会分为以下两种情况:
    • 从旧的 VNodekey 值,对应 index 序列为 value 值的哈希表中找到与 newStartVnode 一致 key 的旧的 VNode 节点,再进行patchVnode ,同时将这个真实 dom 移动到 oldStartVnode 对应的真实 dom 的前面
    • 调用 createElm 创建一个新的 dom 节点放到当前 newStartIdx 的位置

小结

  • 当数据发生改变时,订阅者watcher就会调用patch给真实的DOM打补丁
  • 通过isSameVnode进行判断,相同则调用patchVnode方法
  • patchVnode做了以下操作:
    • 找到对应的真实dom,称为el
    • 如果都有都有文本节点且不相等,将el文本节点设置为Vnode的文本节点
    • 如果oldVnode有子节点而VNode没有,则删除el子节点
    • 如果oldVnode没有子节点而VNode有,则将VNode的子节点真实化后添加到el
    • 如果两者都有子节点,则执行updateChildren函数比较子节点
  • updateChildren主要做了以下操作:
    • 设置新旧VNode的头尾指针
    • 新旧头尾指针进行比较,循环向中间靠拢,根据情况调用patchVnode进行patch重复流程、调用createElem创建一个新节点,从哈希表寻找 key一致的VNode 节点再分情况操作
预览

小程序刷题更方便

预览

关注公众号获取最新面经

预览

加面试交流群

赞赏支持

预览

题库维护不易,您的支持就是我们最大的动力!