diff算法是一種通過同層的樹節(jié)點(diǎn)進(jìn)行比較的高效算法，避免了對(duì)樹進(jìn)行逐層搜索遍歷。本篇文章帶大家深入剖析vue2.x中diff算法的原理，希望對(duì)大家有所幫助！

源碼分析文章看了很多,也閱讀了至少兩遍源碼。終歸還是想自己寫寫,作為自己的一種記錄和學(xué)習(xí)。重點(diǎn)看注釋部分和總結(jié),其余不用太關(guān)心,通過總結(jié)對(duì)照源碼回看過程和注釋收獲更大

更新方法的定義

在生成 render 函數(shù)后,就會(huì)調(diào)用掛載方法,在掛載時(shí)就會(huì)經(jīng)過 diff 計(jì)算,在初始化的時(shí)候,由于沒有舊的虛擬節(jié)點(diǎn),所以初次會(huì)將真實(shí)的 dom 節(jié)點(diǎn)與虛擬節(jié)點(diǎn)作對(duì)比,由于虛擬節(jié)點(diǎn)不是原生節(jié)點(diǎn),所以第一次會(huì)做一個(gè)替換操作。（學(xué)習(xí)視頻分享：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 // 當(dāng)前render函數(shù)產(chǎn)生的虛擬節(jié)點(diǎn),保存后以便下次做對(duì)比     if (!prevVnode) {       vm.$el = vm.__patch__(vm.$el, vnode, hydrating, false) //初次渲染     } else {       vm.$el = vm.__patch__(prevVnode, vnode)     }    ...   }

diff 算法兩大主要分支

主體會(huì)有為兩大分支: 前后虛擬節(jié)點(diǎn)一致、前后虛擬節(jié)點(diǎn)不一致

// /src/core/vdom/patch.js export function createPatchFunction (backend) {   ...   return function patch (oldVnode, vnode, hydrating, removeOnly) {     ...       if (!isRealElement && sameVnode(oldVnode, vnode)) {         ...// 前后虛擬節(jié)點(diǎn)一致的方法       } else {         ...// 前后虛擬節(jié)點(diǎn)不一致的方法       }   } }

前后虛擬節(jié)點(diǎn)不一致

分為三個(gè)步驟: 1.創(chuàng)建新的節(jié)點(diǎn)、2.更新父占位符節(jié)點(diǎn)、3.刪除舊節(jié)點(diǎn)
初次進(jìn)行掛載組件時(shí)兩者不相同,之后會(huì)判斷如果是真實(shí)dom,就會(huì)將其轉(zhuǎn)為虛擬節(jié)點(diǎn)并替換掉

if (isRealElement) {   ...   //需要diff 所以將第一次的真實(shí)節(jié)點(diǎn)轉(zhuǎn)換成虛擬節(jié)點(diǎn)   oldVnode = emptyNodeAt(oldVnode) //<div id="app"></div> } // 拿到父類的dom節(jié)點(diǎn) const oldElm = oldVnode.elm //app const parentElm = nodeOps.parentNode(oldElm) // body //創(chuàng)建新dom節(jié)點(diǎn) 內(nèi)部包含組件邏輯 createElm(   vnode,   insertedVnodeQueue,   oldElm._leaveCb ? null : parentElm,   nodeOps.nextSibling(oldElm) ) //更新父的占位符節(jié)點(diǎn) (組件更新相關(guān)) if (isDef(vnode.parent)) {   // 在生成render函數(shù)時(shí)會(huì)生成占位符節(jié)點(diǎn)<Dialog>提示</Dialog> => <div>提示</div> <Dialog></Dialog>就是占位符節(jié)點(diǎn)   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   } } // 刪除舊節(jié)點(diǎn) if (isDef(parentElm)) {   removeVnodes([oldVnode], 0, 0) } else if (isDef(oldVnode.tag)) {   invokeDestroyHook(oldVnode) }

前后虛擬節(jié)點(diǎn)一致

• 首先判斷新節(jié)點(diǎn)是否為文本,是則直接設(shè)置文本,不是則繼續(xù)判斷
• 新、舊節(jié)點(diǎn)都有children,深度對(duì)比(重點(diǎn))
• 新節(jié)點(diǎn)有children,老節(jié)點(diǎn)沒有,循環(huán)添加新節(jié)點(diǎn)
• 新節(jié)點(diǎn)沒有,老節(jié)點(diǎn)有children,直接刪除老節(jié)點(diǎn)

function patchVnode (oldVnode,vnode,insertedVnodeQueue,ownerArray,index,removeOnly) {     const elm = vnode.elm = oldVnode.elm      let i     const data = vnode.data      // 是組件vnode,在組件更新會(huì)調(diào)用組件的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)) {       // 新舊節(jié)點(diǎn)都有children       if (isDef(oldCh) && isDef(ch)) {         if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)       // 新有 老沒有 children 循環(huán)創(chuàng)建新節(jié)點(diǎn)       } else if (isDef(ch)) {         if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '')         addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)       // 新沒有 老有 children 直接刪除老節(jié)點(diǎn)       } else if (isDef(oldCh)) {         removeVnodes(oldCh, 0, oldCh.length - 1)       // 新老都沒有 children 老的是文本 就置為空       } else if (isDef(oldVnode.text)) {         nodeOps.setTextContent(elm, '')       }     // 是text 直接設(shè)置文本     } 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)     }   }

新舊節(jié)點(diǎn)都有children情況的對(duì)比

// /src/core/vdom/patch.js  function updateChildren (parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {     let oldStartIdx = 0 // 老節(jié)點(diǎn)開始索引     let newStartIdx = 0 // 新節(jié)點(diǎn)開始索引     let oldEndIdx = oldCh.length - 1 // 老節(jié)點(diǎn)末尾索引     let oldStartVnode = oldCh[0] // 老節(jié)點(diǎn)開始元素     let oldEndVnode = oldCh[oldEndIdx] // 老節(jié)點(diǎn)末尾元素     let newEndIdx = newCh.length - 1 // 新節(jié)點(diǎn)末尾索引     let newStartVnode = newCh[0] // 新節(jié)點(diǎn)開始元素     let newEndVnode = newCh[newEndIdx] // 新節(jié)點(diǎn)末尾元素     let oldKeyToIdx, idxInOld, vnodeToMove, refElm     const canMove = !removeOnly     // 滿足新節(jié)點(diǎn)開始索引小于新節(jié)點(diǎn)結(jié)束索引,舊節(jié)點(diǎn)開始索引小于舊節(jié)點(diǎn)結(jié)束索引     while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {       if (isUndef(oldStartVnode)) { // 是否定義老節(jié)點(diǎn)開始元素         oldStartVnode = oldCh[++oldStartIdx]       } else if (isUndef(oldEndVnode)) {// 是否定義老節(jié)點(diǎn)結(jié)束元素         oldEndVnode = oldCh[--oldEndIdx]         // 頭(舊節(jié)點(diǎn)開始元素)頭(新節(jié)點(diǎn)開始元素)對(duì)比 例如四個(gè)li,末尾新增一個(gè)li,這種情況頭頭對(duì)比性能高       } 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)) { // 尾尾對(duì)比 例如四個(gè)li,頭部新增一個(gè)li,這種情況尾尾對(duì)比性能高         patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)         oldEndVnode = oldCh[--oldEndIdx]         newEndVnode = newCh[--newEndIdx]       } else if (sameVnode(oldStartVnode, newEndVnode)) {// 頭尾對(duì)比 節(jié)點(diǎn)反轉(zhuǎn)優(yōu)化 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)) { // 尾頭對(duì)比         patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)         canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)         oldEndVnode = oldCh[--oldEndIdx]         newStartVnode = newCh[++newStartIdx]       } else { // 亂序?qū)Ρ?核心diff,其他方式為優(yōu)化)         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]       }     }     // 多出來的新節(jié)點(diǎn)直接做插入 多出來的舊節(jié)點(diǎn)刪除     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)     }   }

注意點(diǎn)

• key某些情況下不能使用索引,因?yàn)楦淖兦昂蟮乃饕际且粯拥?當(dāng)在頭部添加元素時(shí),如果用索引做key就會(huì)出現(xiàn)更新錯(cuò)誤問題,vue會(huì)理解為在末尾添加一個(gè)元素(因?yàn)榍昂蟮膋ey都是0)
• 在各種對(duì)比情況下,只要找到兩者相同就會(huì)去遞歸對(duì)比children
• 在亂序?qū)Ρ戎?key的作用是極大的。無key會(huì)出現(xiàn)更新出錯(cuò)問題,同時(shí)達(dá)不到復(fù)用效果
• diff對(duì)比是深度優(yōu)先,同層比較

總結(jié)

在掛載時(shí)會(huì)經(jīng)過diff算法后進(jìn)行模板更新,初次會(huì)將真實(shí)dom節(jié)點(diǎn)和生成的虛擬節(jié)點(diǎn)進(jìn)行對(duì)比,并將生成的虛擬節(jié)點(diǎn)儲(chǔ)存起來,以便之后更新做對(duì)比。diff算法只要分兩發(fā)分支,前后虛擬節(jié)點(diǎn)一致和前后虛擬節(jié)點(diǎn)不一致。當(dāng)前后虛擬節(jié)點(diǎn)不一致時(shí),會(huì)創(chuàng)建新節(jié)點(diǎn)、更新父占位符、刪除舊節(jié)點(diǎn)。如果舊節(jié)點(diǎn)是真實(shí)節(jié)點(diǎn),就將其轉(zhuǎn)為虛擬節(jié)點(diǎn),拿到舊節(jié)點(diǎn)的父節(jié)點(diǎn)后替換舊節(jié)點(diǎn)。當(dāng)前后虛擬節(jié)點(diǎn)一致時(shí),會(huì)先判斷新節(jié)點(diǎn)是否為文本,如果值則直接添加,如果不是先比較屬性,再判斷如果新節(jié)點(diǎn)有children,舊節(jié)點(diǎn)沒children,就直接添加新節(jié)點(diǎn)children,如果新節(jié)點(diǎn)沒有,舊節(jié)點(diǎn)有,就會(huì)將舊節(jié)點(diǎn)的children移除,如果新舊節(jié)點(diǎn)都有children,利用雙指針同層對(duì)比,通過頭頭對(duì)比、尾尾對(duì)比、頭尾對(duì)比、尾頭對(duì)比、亂序?qū)Ρ炔粩嗟鷮?duì)其進(jìn)行判斷更新,最大程度的利用舊節(jié)點(diǎn),之后如果有多余的新節(jié)點(diǎn)就會(huì)將其添加,多余的舊節(jié)點(diǎn)將其刪除,最后將對(duì)比后的虛擬節(jié)點(diǎn)返回儲(chǔ)存起來,作為下次對(duì)比的舊節(jié)點(diǎn)。

• 頭頭對(duì)比
  如果新舊開始元素是相同vnode,遞歸調(diào)用patchVnode方法進(jìn)行深層對(duì)比,之后移動(dòng)索引至下一個(gè)元素
• 尾尾對(duì)比
  如果新舊結(jié)束元素是相同vnode,遞歸調(diào)用patchVnode方法進(jìn)行深層對(duì)比,之后移動(dòng)索引至上一個(gè)元素
• 頭尾對(duì)比
  將老節(jié)點(diǎn)開始元素和舊節(jié)點(diǎn)尾元素進(jìn)行對(duì)比,相同就遞歸調(diào)用patchVnode方法進(jìn)行深層對(duì)比,之后將舊節(jié)點(diǎn)元素移動(dòng)至最后,舊節(jié)點(diǎn)頭指針移動(dòng)到下一個(gè),新節(jié)點(diǎn)的尾指針移動(dòng)至上一個(gè)。例如舊:A,B,C,新:C,B,A,第一次對(duì)比將舊A移動(dòng)到C后邊
• 尾頭對(duì)比
  將老節(jié)點(diǎn)尾元素和舊節(jié)點(diǎn)開始元素進(jìn)行對(duì)比,相同就遞歸調(diào)用patchVnode方法進(jìn)行深層對(duì)比,之后將舊節(jié)點(diǎn)元素移動(dòng)至最前,舊節(jié)點(diǎn)尾指針移動(dòng)到上一個(gè),新節(jié)點(diǎn)的頭指針移動(dòng)至下一個(gè)。例如舊:A,B,C,新:C,B,A,D第一次對(duì)比將舊C移動(dòng)到A前邊
• 亂序?qū)Ρ?br />在做比較前會(huì)根據(jù)key和對(duì)應(yīng)的索引將舊節(jié)點(diǎn)生成映射表。在亂序?qū)Ρ葧r(shí)會(huì)用當(dāng)前的key去找舊節(jié)點(diǎn)的key,如果能復(fù)用,就將節(jié)點(diǎn)移動(dòng)到舊的節(jié)點(diǎn)開頭處并遞歸對(duì)比children,如果不能復(fù)用就創(chuàng)建新的差入到舊的節(jié)點(diǎn)開頭處。之后將新的索引移至下一個(gè)元素

（學(xué)習(xí)視頻分享：web前端開發(fā)、編程基礎(chǔ)視頻）