站長資訊網diff算法是一種通過同層的樹節點進行比較的高效算法，避免了對樹進行逐層搜索遍歷。本篇文章帶大家深入剖析vue2.x中diff算法的原理，希望對大家有所幫助！
源碼分析文章看了很多,也閱讀了至少兩遍源碼。終歸還是想自己寫寫,作為自己的一種記錄和學習。重點看注釋部分和總結,其余不用太關心,通過總結對照源碼回看過程和注釋收獲更大
更新方法的定義
在生成 render 函數后,就會調用掛載方法,在掛載時就會經過 diff 計算,在初始化的時候,由于沒有舊的虛擬節點,所以初次會將真實的 dom 節點與虛擬節點作對比,由于虛擬節點不是原生節點,所以第一次會做一個替換操作。（學習視頻分享：vue視頻教程）
// /src/core/instance/lifecycle.js Vue.prototype._update = function (vnode: VNode, hydrating?: boolean) { const vm: Component = this const prevEl = vm.$el const prevVnode = vm._vnode const restoreActiveInstance = setActiveInstance(vm) vm._vnode = vnode // 當前render函數產生的虛擬節點,保存后以便下次做對比 if (!prevVnode) { vm.$el = vm.__patch__(vm.$el, vnode, hydrating, false) //初次渲染 } else { vm.$el = vm.__patch__(prevVnode, vnode) } ... }
diff 算法兩大主要分支
主體會有為兩大分支: 前后虛擬節點一致、前后虛擬節點不一致
// /src/core/vdom/patch.js export function createPatchFunction (backend) { ... return function patch (oldVnode, vnode, hydrating, removeOnly) { ... if (!isRealElement && sameVnode(oldVnode, vnode)) { ...// 前后虛擬節點一致的方法 } else { ...// 前后虛擬節點不一致的方法 } } }
前后虛擬節點不一致
分為三個步驟: 1.創建新的節點、2.更新父占位符節點、3.刪除舊節點
初次進行掛載組件時兩者不相同,之后會判斷如果是真實dom,就會將其轉為虛擬節點并替換掉
if (isRealElement) { ... //需要diff 所以將第一次的真實節點轉換成虛擬節點 oldVnode = emptyNodeAt(oldVnode) //<div id="app"></div> } // 拿到父類的dom節點 const oldElm = oldVnode.elm //app const parentElm = nodeOps.parentNode(oldElm) // body //創建新dom節點 內部包含組件邏輯 createElm( vnode, insertedVnodeQueue, oldElm._leaveCb ? null : parentElm, nodeOps.nextSibling(oldElm) ) //更新父的占位符節點 (組件更新相關) if (isDef(vnode.parent)) { // 在生成render函數時會生成占位符節點<Dialog>提示</Dialog> => <div>提示</div> <Dialog></Dialog>就是占位符節點 let ancestor = vnode.parent // 判斷是否可掛載 const patchable = isPatchable(vnode) while (ancestor) { for (let i = 0; i < cbs.destroy.length; ++i) { cbs.destroy[i](ancestor) } //更新父占位符的element ancestor.elm = vnode.elm if (patchable) { ... } else { registerRef(ancestor) } ancestor = ancestor.parent } } // 刪除舊節點 if (isDef(parentElm)) { removeVnodes([oldVnode], 0, 0) } else if (isDef(oldVnode.tag)) { invokeDestroyHook(oldVnode) }
前后虛擬節點一致
- 首先判斷新節點是否為文本,是則直接設置文本,不是則繼續判斷
- 新、舊節點都有children,深度對比(重點)
- 新節點有children,老節點沒有,循環添加新節點
- 新節點沒有,老節點有children,直接刪除老節點
function patchVnode (oldVnode,vnode,insertedVnodeQueue,ownerArray,index,removeOnly) { const elm = vnode.elm = oldVnode.elm let i const data = vnode.data // 是組件vnode,在組件更新會調用組件的prepatch方法 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) } // 是否是text if (isUndef(vnode.text)) { // 新舊節點都有children if (isDef(oldCh) && isDef(ch)) { if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly) // 新有 老沒有 children 循環創建新節點 } else if (isDef(ch)) { if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '') addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue) // 新沒有 老有 children 直接刪除老節點 } else if (isDef(oldCh)) { removeVnodes(oldCh, 0, oldCh.length - 1) // 新老都沒有 children 老的是文本 就置為空 } else if (isDef(oldVnode.text)) { nodeOps.setTextContent(elm, '') } // 是text 直接設置文本 } 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) } }
新舊節點都有children情況的對比
// /src/core/vdom/patch.js 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] // 新節點末尾元素 let oldKeyToIdx, idxInOld, vnodeToMove, refElm const canMove = !removeOnly // 滿足新節點開始索引小于新節點結束索引,舊節點開始索引小于舊節點結束索引 while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) { if (isUndef(oldStartVnode)) { // 是否定義老節點開始元素 oldStartVnode = oldCh[++oldStartIdx] } else if (isUndef(oldEndVnode)) {// 是否定義老節點結束元素 oldEndVnode = oldCh[--oldEndIdx] // 頭(舊節點開始元素)頭(新節點開始元素)對比 例如四個li,末尾新增一個li,這種情況頭頭對比性能高 } else if (sameVnode(oldStartVnode, newStartVnode)) { // sameVnode判斷key和tag是否相同 patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx) oldStartVnode = oldCh[++oldStartIdx] newStartVnode = newCh[++newStartIdx] } else if (sameVnode(oldEndVnode, newEndVnode)) { // 尾尾對比 例如四個li,頭部新增一個li,這種情況尾尾對比性能高 patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx) oldEndVnode = oldCh[--oldEndIdx] newEndVnode = newCh[--newEndIdx] } else if (sameVnode(oldStartVnode, newEndVnode)) {// 頭尾對比 節點反轉優化 reverse 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)) { // 尾頭對比 patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx) canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm) oldEndVnode = oldCh[--oldEndIdx] newStartVnode = newCh[++newStartIdx] } else { // 亂序對比(核心diff,其他方式為優化) if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx) idxInOld = isDef(newStartVnode.key) ? oldKeyToIdx[newStartVnode.key] : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx) if (isUndef(idxInOld)) { createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx) } else { vnodeToMove = oldCh[idxInOld] if (sameVnode(vnodeToMove, newStartVnode)) { patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx) oldCh[idxInOld] = undefined canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm) } else { createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx) } } newStartVnode = newCh[++newStartIdx] } } // 多出來的新節點直接做插入 多出來的舊節點刪除 if (oldStartIdx > oldEndIdx) { refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue) } else if (newStartIdx > newEndIdx) { removeVnodes(oldCh, oldStartIdx, oldEndIdx) } }
注意點
- key某些情況下不能使用索引,因為改變前后的索引都是一樣的,當在頭部添加元素時,如果用索引做key就會出現更新錯誤問題,vue會理解為在末尾添加一個元素(因為前后的key都是0)
- 在各種對比情況下,只要找到兩者相同就會去遞歸對比children
- 在亂序對比中,key的作用是極大的。無key會出現更新出錯問題,同時達不到復用效果
- diff對比是深度優先,同層比較
總結
在掛載時會經過diff算法后進行模板更新,初次會將真實dom節點和生成的虛擬節點進行對比,并將生成的虛擬節點儲存起來,以便之后更新做對比。diff算法只要分兩發分支,前后虛擬節點一致和前后虛擬節點不一致。當前后虛擬節點不一致時,會創建新節點、更新父占位符、刪除舊節點。如果舊節點是真實節點,就將其轉為虛擬節點,拿到舊節點的父節點后替換舊節點。當前后虛擬節點一致時,會先判斷新節點是否為文本,如果值則直接添加,如果不是先比較屬性,再判斷如果新節點有children,舊節點沒children,就直接添加新節點children,如果新節點沒有,舊節點有,就會將舊節點的children移除,如果新舊節點都有children,利用雙指針同層對比,通過頭頭對比、尾尾對比、頭尾對比、尾頭對比、亂序對比不斷迭代對其進行判斷更新,最大程度的利用舊節點,之后如果有多余的新節點就會將其添加,多余的舊節點將其刪除,最后將對比后的虛擬節點返回儲存起來,作為下次對比的舊節點。
- 頭頭對比
如果新舊開始元素是相同vnode,遞歸調用patchVnode方法進行深層對比,之后移動索引至下一個元素 - 尾尾對比
如果新舊結束元素是相同vnode,遞歸調用patchVnode方法進行深層對比,之后移動索引至上一個元素 - 頭尾對比
將老節點開始元素和舊節點尾元素進行對比,相同就遞歸調用patchVnode方法進行深層對比,之后將舊節點元素移動至最后,舊節點頭指針移動到下一個,新節點的尾指針移動至上一個。例如舊:A,B,C,新:C,B,A,第一次對比將舊A移動到C后邊 - 尾頭對比
將老節點尾元素和舊節點開始元素進行對比,相同就遞歸調用patchVnode方法進行深層對比,之后將舊節點元素移動至最前,舊節點尾指針移動到上一個,新節點的頭指針移動至下一個。例如舊:A,B,C,新:C,B,A,D第一次對比將舊C移動到A前邊 - 亂序對比
在做比較前會根據key和對應的索引將舊節點生成映射表。在亂序對比時會用當前的key去找舊節點的key,如果能復用,就將節點移動到舊的節點開頭處并遞歸對比children,如果不能復用就創建新的差入到舊的節點開頭處。之后將新的索引移至下一個元素
（學習視頻分享：web前端開發、編程基礎視頻）
