站長資訊網diff算法是一種通過同層的樹節點進行比較的高效算法，避免了對樹進行逐層搜索遍歷。那么大家對diff算法嗎有多少了解？下面本篇文章就來帶大家深入解析下vue的diff算法，希望對大家有所幫助！
一、是什么
diff 算法是一種通過同層的樹節點進行比較的高效算法。（學習視頻分享：vue視頻教程）
其有兩個特點：
- 比較只會在同層級進行, 不會跨層級比較
- 在diff比較的過程中，循環從兩邊向中間比較
diff 算法在很多場景下都有應用，在 vue 中，作用于虛擬 dom 渲染成真實 dom 的新舊 VNode 節點比較
二、比較方式
diff整體策略為：深度優先，同層比較
-
比較只會在同層級進行, 不會跨層級比較
-
比較的過程中，循環從兩邊向中間收攏
下面舉個vue通過diff算法更新的例子：
新舊VNode節點如下圖所示：
第一次循環后，發現舊節點D與新節點D相同，直接復用舊節點D作為diff后的第一個真實節點，同時舊節點endIndex移動到C，新節點的 startIndex 移動到了 C
第二次循環后，同樣是舊節點的末尾和新節點的開頭(都是 C)相同，同理，diff 后創建了 C 的真實節點插入到第一次創建的 D 節點后面。同時舊節點的 endIndex 移動到了 B，新節點的 startIndex 移動到了 E
第三次循環中，發現E沒有找到，這時候只能直接創建新的真實節點 E，插入到第二次創建的 C 節點之后。同時新節點的 startIndex 移動到了 A。舊節點的 startIndex 和 endIndex 都保持不動
第四次循環中，發現了新舊節點的開頭(都是 A)相同，于是 diff 后創建了 A 的真實節點，插入到前一次創建的 E 節點后面。同時舊節點的 startIndex 移動到了 B，新節點的startIndex 移動到了 B
第五次循環中，情形同第四次循環一樣，因此 diff 后創建了 B 真實節點 插入到前一次創建的 A 節點后面。同時舊節點的 startIndex移動到了 C，新節點的 startIndex 移動到了 F
新節點的 startIndex 已經大于 endIndex 了，需要創建 newStartIdx 和 newEndIdx 之間的所有節點，也就是節點F，直接創建 F 節點對應的真實節點放到 B 節點后面
三、原理分析
當數據發生改變時，set方法會調用Dep.notify通知所有訂閱者Watcher，訂閱者就會調用patch給真實的DOM打補丁，更新相應的視圖
源碼位置：src/core/vdom/patch.js
function patch(oldVnode, vnode, hydrating, removeOnly) { if (isUndef(vnode)) { // 沒有新節點，直接執行destory鉤子函數 if (isDef(oldVnode)) invokeDestroyHook(oldVnode) return } let isInitialPatch = false const insertedVnodeQueue = [] if (isUndef(oldVnode)) { isInitialPatch = true createElm(vnode, insertedVnodeQueue) // 沒有舊節點，直接用新節點生成dom元素 } else { const isRealElement = isDef(oldVnode.nodeType) if (!isRealElement && sameVnode(oldVnode, vnode)) { // 判斷舊節點和新節點自身一樣，一致執行patchVnode patchVnode(oldVnode, vnode, insertedVnodeQueue, null, null, removeOnly) } else { // 否則直接銷毀及舊節點，根據新節點生成dom元素 if (isRealElement) { if (oldVnode.nodeType === 1 && oldVnode.hasAttribute(SSR_ATTR)) { oldVnode.removeAttribute(SSR_ATTR) hydrating = true } if (isTrue(hydrating)) { if (hydrate(oldVnode, vnode, insertedVnodeQueue)) { invokeInsertHook(vnode, insertedVnodeQueue, true) return oldVnode } } oldVnode = emptyNodeAt(oldVnode) } return vnode.elm } } }
patch函數前兩個參數位為oldVnode 和 Vnode ，分別代表新的節點和之前的舊節點，主要做了四個判斷：
- 沒有新節點，直接觸發舊節點的
destory鉤子 - 沒有舊節點，說明是頁面剛開始初始化的時候，此時，根本不需要比較了，直接全是新建，所以只調用
createElm - 舊節點和新節點自身一樣，通過
sameVnode判斷節點是否一樣，一樣時，直接調用patchVnode去處理這兩個節點 - 舊節點和新節點自身不一樣，當兩個節點不一樣的時候，直接創建新節點，刪除舊節點
下面主要講的是patchVnode部分
function patchVnode (oldVnode, vnode, insertedVnodeQueue, removeOnly) { // 如果新舊節點一致，什么都不做 if (oldVnode === vnode) { return } // 讓vnode.el引用到現在的真實dom，當el修改時，vnode.el會同步變化 const elm = vnode.elm = oldVnode.elm // 異步占位符 if (isTrue(oldVnode.isAsyncPlaceholder)) { if (isDef(vnode.asyncFactory.resolved)) { hydrate(oldVnode.elm, vnode, insertedVnodeQueue) } else { vnode.isAsyncPlaceholder = true } return } // 如果新舊都是靜態節點，并且具有相同的key // 當vnode是克隆節點或是v-once指令控制的節點時，只需要把oldVnode.elm和oldVnode.child都復制到vnode上 // 也不用再有其他操作 if (isTrue(vnode.isStatic) && isTrue(oldVnode.isStatic) && vnode.key === oldVnode.key && (isTrue(vnode.isCloned) || isTrue(vnode.isOnce)) ) { vnode.componentInstance = oldVnode.componentInstance return } let i const data = vnode.data if (isDef(data) && isDef(i = data.hook) && isDef(i = i.prepatch)) { i(oldVnode, vnode) } const oldCh = oldVnode.children const ch = vnode.children 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) } // 如果vnode不是文本節點或者注釋節點 if (isUndef(vnode.text)) { // 并且都有子節點 if (isDef(oldCh) && isDef(ch)) { // 并且子節點不完全一致，則調用updateChildren if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly) // 如果只有新的vnode有子節點 } else if (isDef(ch)) { if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '') // elm已經引用了老的dom節點，在老的dom節點上添加子節點 addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue) // 如果新vnode沒有子節點，而vnode有子節點，直接刪除老的oldCh } else if (isDef(oldCh)) { removeVnodes(elm, oldCh, 0, oldCh.length - 1) // 如果老節點是文本節點 } else if (isDef(oldVnode.text)) { nodeOps.setTextContent(elm, '') } // 如果新vnode和老vnode是文本節點或注釋節點 // 但是vnode.text != oldVnode.text時，只需要更新vnode.elm的文本內容就可以 } else if (oldVnode.text !== vnode.text) { nodeOps.setTextContent(elm, vnode.text) } if (isDef(data)) { if (isDef(i = data.hook) && isDef(i = i.postpatch)) i(oldVnode, vnode) } }
patchVnode主要做了幾個判斷：
- 新節點是否是文本節點，如果是，則直接更新
dom的文本內容為新節點的文本內容 - 新節點和舊節點如果都有子節點，則處理比較更新子節點
- 只有新節點有子節點，舊節點沒有，那么不用比較了，所有節點都是全新的，所以直接全部新建就好了，新建是指創建出所有新
DOM，并且添加進父節點 - 只有舊節點有子節點而新節點沒有，說明更新后的頁面，舊節點全部都不見了，那么要做的，就是把所有的舊節點刪除，也就是直接把
DOM刪除
子節點不完全一致，則調用updateChildren
function updateChildren (parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) { let oldStartIdx = 0 // 舊頭索引 let newStartIdx = 0 // 新頭索引 let oldEndIdx = oldCh.length - 1 // 舊尾索引 let newEndIdx = newCh.length - 1 // 新尾索引 let oldStartVnode = oldCh[0] // oldVnode的第一個child let oldEndVnode = oldCh[oldEndIdx] // oldVnode的最后一個child let newStartVnode = newCh[0] // newVnode的第一個child let newEndVnode = newCh[newEndIdx] // newVnode的最后一個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 // 如果oldStartVnode和oldEndVnode重合，并且新的也都重合了，證明diff完了，循環結束 while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) { // 如果oldVnode的第一個child不存在 if (isUndef(oldStartVnode)) { // oldStart索引右移 oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left // 如果oldVnode的最后一個child不存在 } else if (isUndef(oldEndVnode)) { // oldEnd索引左移 oldEndVnode = oldCh[--oldEndIdx] // oldStartVnode和newStartVnode是同一個節點 } else if (sameVnode(oldStartVnode, newStartVnode)) { // patch oldStartVnode和newStartVnode， 索引左移，繼續循環 patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue) oldStartVnode = oldCh[++oldStartIdx] newStartVnode = newCh[++newStartIdx] // oldEndVnode和newEndVnode是同一個節點 } else if (sameVnode(oldEndVnode, newEndVnode)) { // patch oldEndVnode和newEndVnode，索引右移，繼續循環 patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue) oldEndVnode = oldCh[--oldEndIdx] newEndVnode = newCh[--newEndIdx] // oldStartVnode和newEndVnode是同一個節點 } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right // patch oldStartVnode和newEndVnode patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue) // 如果removeOnly是false，則將oldStartVnode.eml移動到oldEndVnode.elm之后 canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm)) // oldStart索引右移，newEnd索引左移 oldStartVnode = oldCh[++oldStartIdx] newEndVnode = newCh[--newEndIdx] // 如果oldEndVnode和newStartVnode是同一個節點 } else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left // patch oldEndVnode和newStartVnode patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue) // 如果removeOnly是false，則將oldEndVnode.elm移動到oldStartVnode.elm之前 canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm) // oldEnd索引左移，newStart索引右移 oldEndVnode = oldCh[--oldEndIdx] newStartVnode = newCh[++newStartIdx] // 如果都不匹配 } else { if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx) // 嘗試在oldChildren中尋找和newStartVnode的具有相同的key的Vnode idxInOld = isDef(newStartVnode.key) ? oldKeyToIdx[newStartVnode.key] : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx) // 如果未找到，說明newStartVnode是一個新的節點 if (isUndef(idxInOld)) { // New element // 創建一個新Vnode createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm) // 如果找到了和newStartVnodej具有相同的key的Vnode，叫vnodeToMove } else { vnodeToMove = oldCh[idxInOld] /* istanbul ignore if */ if (process.env.NODE_ENV !== 'production' && !vnodeToMove) { warn( 'It seems there are duplicate keys that is causing an update error. ' + 'Make sure each v-for item has a unique key.' ) } // 比較兩個具有相同的key的新節點是否是同一個節點 //不設key，newCh和oldCh只會進行頭尾兩端的相互比較，設key后，除了頭尾兩端的比較外，還會從用key生成的對象oldKeyToIdx中查找匹配的節點，所以為節點設置key可以更高效的利用dom。 if (sameVnode(vnodeToMove, newStartVnode)) { // patch vnodeToMove和newStartVnode patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue) // 清除 oldCh[idxInOld] = undefined // 如果removeOnly是false，則將找到的和newStartVnodej具有相同的key的Vnode，叫vnodeToMove.elm // 移動到oldStartVnode.elm之前 canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm) // 如果key相同，但是節點不相同，則創建一個新的節點 } else { // same key but different element. treat as new element createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm) } } // 右移 newStartVnode = newCh[++newStartIdx] } }
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 - 如果都不滿足以上四種情形，那說明沒有相同的節點可以復用，則會分為以下兩種情況：
- 從舊的
VNode為key值，對應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節點再分情況操作
- 設置新舊
（學習視頻分享：web前端開發、編程基礎視頻）
