diff演算法是一種透過(guò)同層的樹(shù)節(jié)點(diǎn)進(jìn)行比較的高效演算法，避免了對(duì)樹(shù)進(jìn)行逐層搜尋遍歷。那麼大家對(duì)diff演算法嗎有多少了解呢？以下這篇文章就來(lái)帶大家深入解析下vue2的diff演算法，希望對(duì)大家有幫助！

看Vue 2 的源代碼已經(jīng)很久了，從用flow 到如今使用TypeScript，我每次都會(huì)打開(kāi)它的源代碼看一看，但是每次都只看到了資料初始化 部分，也就是beforeMount 的階段，對(duì)於如何產(chǎn)生VNode（Visual Dom Node， 也可以直接稱(chēng)為vdom） 以及元件更新時(shí)如何比較VNode（diff ）始終沒(méi)有仔細(xì)研究，只知道採(cǎi)用了雙端diff 演算法，至於這個(gè)雙端是怎麼開(kāi)始怎麼結(jié)束的也一直沒(méi)有去看過(guò)，所以這次趁寫(xiě)文章的機(jī)會(huì)仔細(xì)研究一下。如果內(nèi)容有誤，希望大家能幫我指出，非常感謝~

什麼是diff ?

在我的理解中，diff 指代的是differences，即新舊內(nèi)容之間的區(qū)別計(jì)算；Vue 中的diff 演算法，則是透過(guò)一種簡(jiǎn)單且高效 的手段快速對(duì)比出新舊VNode 節(jié)點(diǎn)數(shù)組之間的差異 以便以最少的dom 操作來(lái)更新頁(yè)面內(nèi)容。 【相關(guān)推薦：vuejs影片教學(xué)、web前端開(kāi)發(fā)】

#此時(shí)這裡有兩個(gè)必須的前提：

• 比較的是VNode 陣列

• 同時(shí)存在新舊兩組VNode 陣列

所以它一般只會(huì)發(fā)生在資料更新造成頁(yè)面內(nèi)容需要更新時(shí)執(zhí)行，即renderWatcher.run()。

為什麼是VNode ?

上面說(shuō)了，diff 中比較的是VNode，而不是真實(shí)的dom 節(jié)點(diǎn)，相信為什麼會(huì)用VNode 大部分人都比較清楚，筆者就簡(jiǎn)單帶過(guò)吧?~

在Vue 中使用VNode 的原因大致有兩個(gè)面向：

• VNode 作為框架設(shè)計(jì)者根據(jù)框架需求設(shè)計(jì)的JavaScript 對(duì)象，本身屬性相對(duì)真實(shí)的dom 節(jié)點(diǎn)要簡(jiǎn)單，且操作時(shí)不需要進(jìn)行dom 查詢(xún)，可以大幅優(yōu)化計(jì)算時(shí)的效能消耗

• 在VNode 到真實(shí)dom 的這個(gè)渲染過(guò)程，可以根據(jù)不同平臺(tái)（web、微信小程式）進(jìn)行不同的處理，產(chǎn)生適配各平臺(tái)的真實(shí)dom 元素

在diff 過(guò)程中會(huì)遍歷新舊節(jié)點(diǎn)資料進(jìn)行對(duì)比，所以使用VNode 能帶來(lái)很大的效能提升。

流程梳理

在網(wǎng)頁(yè)中，真實(shí)的dom 節(jié)點(diǎn)都是以樹(shù) 的形式存在的，根節(jié)點(diǎn)都是 ，為了確保虛擬節(jié)點(diǎn)能與真實(shí)dom 節(jié)點(diǎn)一致，VNode 也一樣採(cǎi)用的是樹(shù)狀結(jié)構(gòu)。

如果在元件更新時(shí)，需要比較全部VNode 節(jié)點(diǎn)的話，新舊兩組節(jié)點(diǎn)都需要進(jìn)行深度遍歷 和比較，會(huì)產(chǎn)生很大的效能開(kāi)銷(xiāo)；所以，Vue 中默認(rèn)同層級(jí)節(jié)點(diǎn)比較，也就是如果新舊VNode 樹(shù)的層級(jí)不同的話，多餘層級(jí)的內(nèi)容會(huì)直接新建或捨棄，只在同層級(jí)進(jìn)行diff 操作。

一般來(lái)說(shuō)，diff 操作一般發(fā)生在v-for 迴圈或有v-if/v-else 、component 這類(lèi)動(dòng)態(tài)產(chǎn)生 的節(jié)點(diǎn)物件上（靜態(tài)節(jié)點(diǎn)一般不會(huì)改變，對(duì)比起來(lái)很快），而這個(gè)過(guò)程是為了更新dom，所以在原始碼中，這個(gè)過(guò)程對(duì)應(yīng)的方法名稱(chēng)是updateChildren ，位於src/core/vdom/patch.ts 中。如下圖：

這裡回顧Vue 元件實(shí)例的建立與更新過(guò)程：

• 首先是 beforeCreate 到created 階段，主要進(jìn)行資料和狀態(tài)以及一些基礎(chǔ)事件、方法的處理

• 然後，會(huì)呼叫$mount(vm .$options.el) 方法進(jìn)入Vnode 與dom 的建立與掛載階段，也就是beforeMount 到mounted 之間（元件更新時(shí)與這裡類(lèi)似）

• 原型上的$mount 會(huì)在platforms/web/runtime-with-compiler.ts 中進(jìn)行一次重寫(xiě)，原始實(shí)作在platforms/web/runtime/index.ts 中；在原始實(shí)作方法中，其實(shí)就是呼叫mountComponent 方法執(zhí)行render；而在web下的runtime-with-compiler 則是增加了模板字串編譯 模組，會(huì)對(duì)options 中的的template# 進(jìn)行一次解析和編譯，轉(zhuǎn)換成一個(gè)函數(shù)綁定到options.render 中

• mountComponent 函數(shù)內(nèi)部就是定義了渲染方法updateComponent = () => (vm._update(vm._render())，實(shí)例化一個(gè)具有before 配置的watcher 實(shí)例（即renderWatcher），透過(guò)定義watch 觀察物件為剛剛定義的updateComponent 方法來(lái)執(zhí)行首次元件渲染與觸發(fā)依賴(lài)收集，其中的before 配置僅配置了觸發(fā)beforeMount/beforeUpdate 鉤子函數(shù)的方法；這也是為什麼在beforeMount 階段取不到真實(shí)dom 節(jié)點(diǎn)與beforeUpdate 階段獲取的是舊dom 節(jié)點(diǎn)的原因

• _update 方法的定義與mountComponent 在同一檔案下，其核心就是讀取元件實(shí)例中的$el（舊dom 節(jié)點(diǎn)）與_vnode（舊VNode）與_render() 函數(shù)產(chǎn)生的vnode 進(jìn)行patch 運(yùn)算

• patch 函式先比較是否有舊節(jié)點(diǎn)，沒(méi)有的話一定是新建的元件，直接進(jìn)行創(chuàng)建和渲染；如果具有舊節(jié)點(diǎn)的話，則透過(guò)patchVnode 進(jìn)行新舊節(jié)點(diǎn)的對(duì)比，並且如果新舊節(jié)點(diǎn)一致並且都具有children 子節(jié)點(diǎn)，則進(jìn)入diff 的核心邏輯— updateChildren 子節(jié)點(diǎn)比較更新，這個(gè)方法也是我們常說(shuō)的diff 演算法

#前置內(nèi)容

既然是比較新舊VNode 數(shù)組，那麼首先肯定有對(duì)比 的判斷方法：sameNode (a, b)、新增節(jié)點(diǎn)的方法addVnodes、移除節(jié)點(diǎn)的方法removeVnodes，當(dāng)然，即使sameNode 判斷了VNode 一致之後，仍會(huì)使用patchVnode 對(duì)單一新舊VNode 的內(nèi)容進(jìn)行深度比較，確認(rèn)內(nèi)部資料是否需要更新。

sameNode(a, b)

這個(gè)方法就一個(gè)目的：比較新舊節(jié)點(diǎn)是否相同。

在這個(gè)方法中，首先比較的是a 和b 的key 是否相同，這也是為什麼Vue 在文件中註明了v-for、v-if、 v-else 等動(dòng)態(tài)節(jié)點(diǎn)必須設(shè)定key 來(lái)標(biāo)識(shí)節(jié)點(diǎn)唯一性，如果key 存在且相同，則只需要比較內(nèi)部是否發(fā)生了改變，一般情況下可以減少很多dom 操作；而如果沒(méi)有設(shè)定的話，則會(huì)直接銷(xiāo)毀重建對(duì)應(yīng)的節(jié)點(diǎn)元素。

然後會(huì)比較是不是非同步元件，這裡會(huì)比較他們的建構(gòu)子是不是一致。

然後會(huì)進(jìn)入兩種不同的情況比較：

• 非非同步元件：標(biāo)籤一樣、都不是註解節(jié)點(diǎn)、都有資料、同類(lèi)型文字輸入框
• #非同步元件：舊節(jié)點(diǎn)佔(zhàn)位符和新節(jié)點(diǎn)的錯(cuò)誤提示都為undefined

#函數(shù)整體過(guò)程如下

addVnodes

顧名思義，新增新的VNode 節(jié)點(diǎn)。

此函數(shù)接收6 個(gè)參數(shù)：parentElm 目前節(jié)點(diǎn)陣列父元素、refElm 指定位置的元素、vnodes 新的虛擬節(jié)點(diǎn)陣列、startIdx 新節(jié)點(diǎn)陣列的插入元素開(kāi)始位置、endIdx 新節(jié)點(diǎn)陣列的插入元素結(jié)束索引、insertedVnodeQueue 需要插入的虛擬節(jié)點(diǎn)隊(duì)列。

函數(shù)內(nèi)部會(huì)從startIdx 開(kāi)始遍歷vnodes 陣列直到endIdx 位置，然後呼叫createElm 依序在refElm 之前建立和插入vnodes[idx] 對(duì)應(yīng)的元素。

當(dāng)然，在這個(gè)vnodes[idx] 中有可能會(huì)有Component 元件，此時(shí)也會(huì)呼叫createComponent 來(lái)建立對(duì)應(yīng)的組件實(shí)例。

因?yàn)檎麄€(gè)VNode 和dom 都是一個(gè)樹(shù)結(jié)構(gòu)，所以在同層級(jí)的比較之後，還需要處理目前層級(jí)下更深層的VNode和dom 處理。

removeVnodes

與 addVnodes 相反，此方法就是用來(lái)移除 VNode 節(jié)點(diǎn)的。

由於這個(gè)方法只是移除，所以只需要三個(gè)參數(shù)：vnodes 舊虛擬節(jié)點(diǎn)陣列、startIdx 開(kāi)始索引、endIdx 結(jié)束索引。

函數(shù)內(nèi)部會(huì)從startIdx 開(kāi)始遍歷vnodes 陣列直到endIdx 位置，如果vnodes[idx ] 不為undefined 的話，則會(huì)根據(jù)tag 屬性來(lái)區(qū)分處理：

• 存在tag，說(shuō)明是一個(gè)元素或元件，需要遞歸處理vnodes[idx] 的內(nèi)容，觸發(fā)remove hooks 與destroy hooks
• #不存在 tag，說(shuō)明是一個(gè)純文字節(jié)點(diǎn)，直接從dom 移除該節(jié)點(diǎn)即可

patchVnode

節(jié)點(diǎn)比較的實(shí)際完整比較與dom 更新 方法。

在這個(gè)方法中，主要包含九個(gè) 主要的參數(shù)判斷，並對(duì)應(yīng)不同的處理邏輯：

• 新舊VNode 全等，則說(shuō)明沒(méi)有變化，直接退出

• 如果新的VNode 具有真實(shí)的dom 綁定，並且需要更新的節(jié)點(diǎn)集合是一個(gè)數(shù)組的話，則拷貝當(dāng)前的VNode 到集合的指定位置

• 如果舊節(jié)點(diǎn)是一個(gè)非同步元件並且還沒(méi)有載入結(jié)束的話就直接退出，否則透過(guò)hydrate 函數(shù)將新的VNode 轉(zhuǎn)換為真實(shí)的dom 進(jìn)行渲染；兩種情況都會(huì)退出函數(shù)

• 如果新舊節(jié)點(diǎn)都是 靜態(tài)節(jié)點(diǎn) 且key 相等，或是isOnce 指定的不更新節(jié)點(diǎn)，也會(huì)直接重複使用舊節(jié)點(diǎn)的元件實(shí)例 並退出函數(shù)

• 如果新的VNode 節(jié)點(diǎn)具有data 屬性並且有配置prepatch 鉤子函數(shù)，則執(zhí)行prepatch(oldVnode, vnode) 通知進(jìn)入節(jié)點(diǎn)的比較階段，一般這一步驟會(huì)配置效能最佳化

• 如果新的VNode 具有data 屬性並且遞歸改節(jié)點(diǎn)的子元件實(shí)例的vnode，還是可用標(biāo)籤的話，cbs 回呼函數(shù)物件中配置的update 鉤子函數(shù)以及data 中配置的update 鉤子函數(shù)

• 如果新的VNode 不是文字節(jié)點(diǎn)的話，會(huì)進(jìn)入核心對(duì)比階段：

  • 如果新舊節(jié)點(diǎn)都有children 子節(jié)點(diǎn)，則進(jìn)入updateChildren 方法對(duì)比子節(jié)點(diǎn)
  • 如果舊節(jié)點(diǎn)沒(méi)有子節(jié)點(diǎn)的話，則直接建立VNode 對(duì)應(yīng)的新的子節(jié)點(diǎn)
  • 如果新節(jié)點(diǎn)沒(méi)有子節(jié)點(diǎn)的話，則移除舊的VNode 子節(jié)點(diǎn)
  • 如果都沒(méi)有子節(jié)點(diǎn)的話，且舊節(jié)點(diǎn)有文字內(nèi)容配置，則清空先前的text 文字

• 如果新的VNode 具有text 文字（是文字節(jié)點(diǎn)），則比較新舊節(jié)點(diǎn)的文字內(nèi)容是否一致，否則進(jìn)行文字內(nèi)容的更新

• 最後呼叫新節(jié)點(diǎn)的data 中配置的postpatch 鉤子函數(shù)，通知節(jié)點(diǎn)更新完畢

#簡(jiǎn)單來(lái)說(shuō)，patchVnode 就是在同一個(gè)節(jié)點(diǎn)更新階段進(jìn)行新內(nèi)容與舊內(nèi)容的對(duì)比，如果發(fā)生改變則更新對(duì)應(yīng)的內(nèi)容；如果有子節(jié)點(diǎn)，則「遞歸」執(zhí)行每個(gè)子節(jié)點(diǎn)的比較和更新。

而 子節(jié)點(diǎn)陣列的比較和更新，則是 diff 的核心邏輯，也是面試時(shí)常被提及的問(wèn)題之一。

下面，就進(jìn)入updateChildren 方法的解析吧~

updateChildren diff 核心解析

#首先，我們先思考一下以新陣列為準(zhǔn)比較兩個(gè)物件陣列元素差異 有哪些方法？

一般來(lái)說(shuō)，我們可以透過(guò) 暴力手段直接遍歷兩個(gè)陣列 來(lái)找出陣列中每個(gè)元素的順序和差異，也就是 簡(jiǎn)單 diff 演算法。

即遍歷新節(jié)點(diǎn)數(shù)組，在每次循環(huán)中再次遍歷舊節(jié)點(diǎn)數(shù)組對(duì)比兩個(gè)節(jié)點(diǎn)是否一致，透過(guò)對(duì)比結(jié)果確定新節(jié)點(diǎn)是新增還是移除還是移動(dòng)，整個(gè)過(guò)程中需要進(jìn)行m*n 次比較，所以預(yù)設(shè)時(shí)間複雜度是On。

這種比較方式在大量節(jié)點(diǎn)更新過(guò)程中是非常消耗性能的，所以Vue 2 對(duì)其進(jìn)行了優(yōu)化，改為雙端對(duì)比演算法，也就是雙端diff。

雙端diff 演算法

顧名思義，雙端 就是從兩端開(kāi)始分別向中間進(jìn)行遍歷對(duì)比 的演算法.

在雙端diff 中，分成五個(gè)比較情況：

• 新舊頭相等

• 新舊尾相等

• 舊頭等於新尾

• 舊尾等於新頭

• 四者互不相等

其中，前四種屬於比較理想的情況，而第五種才是最複雜的對(duì)比情況。

判斷相等即sameVnode(a, b) 等於true

下面我們透過(guò)一種預(yù)設(shè)情況來(lái)進(jìn)行分析。

1. 預(yù)設(shè)新舊節(jié)點(diǎn)狀態(tài)

為了盡量同時(shí)示範(fàn)出以上五種情況，我預(yù)設(shè)了以下的新舊節(jié)點(diǎn)陣列：

• 作為初始節(jié)點(diǎn)順序的舊節(jié)點(diǎn)陣列oldChildren，包含1 - 7 共7 個(gè)節(jié)點(diǎn)
• 作為亂序後的新節(jié)點(diǎn)陣列newChildren，也有7 個(gè)節(jié)點(diǎn)，但是相比舊節(jié)點(diǎn)減少了一個(gè)vnode 3 並增加了一個(gè)vnode 8

在進(jìn)行比較之前，首先需要定義兩組節(jié)點(diǎn)的雙端索引：

let oldStartIdx = 0
let oldEndIdx = oldCh.length - 1
let oldStartVnode = oldCh[0]
let oldEndVnode = oldCh[oldEndIdx]

let newStartIdx = 0
let newEndIdx = newCh.length - 1
let newStartVnode = newCh[0]
let newEndVnode = newCh[newEndIdx]

複製的原始程式碼，其中oldCh 在圖中為oldChildren，newCh 為newChildren

然後，我們定義遍歷對(duì)比操作的停止條件：

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx)

這裡的停止條件是只要新舊節(jié)點(diǎn)數(shù)組任一個(gè)遍歷結(jié)束，則立即停止遍歷。

此時(shí)節(jié)點(diǎn)狀態(tài)如下：

2. 確認(rèn)vnode 存在才進(jìn)行對(duì)比

為了保證新舊節(jié)點(diǎn)數(shù)組在對(duì)比時(shí)不會(huì)進(jìn)行無(wú)效對(duì)比，會(huì)先排除掉舊節(jié)點(diǎn)數(shù)組起始部分與末尾部分連續(xù)且值為Undefined 的資料。

if (isUndef(oldStartVnode)) {
  oldStartVnode = oldCh[++oldStartIdx]
} else if (isUndef(oldEndVnode)) {
  oldEndVnode = oldCh[--oldEndIdx]

當(dāng)然我們的例子中沒(méi)有這種情況，可以忽略。

3. 舊頭等於新頭

此時(shí)相當(dāng)於新舊節(jié)點(diǎn)陣列的兩個(gè)起始索引 指向的節(jié)點(diǎn)是基本上一致的，那麼此時(shí)會(huì)呼叫patchVnode 對(duì)兩個(gè)vnode 進(jìn)行深層比較和dom 更新，並且將兩個(gè)起始索引向後移動(dòng)。即：

if (sameVnode(oldStartVnode, newStartVnode)) {
  patchVnode(
    oldStartVnode,
    newStartVnode,
    insertedVnodeQueue,
    newCh,
    newStartIdx
  )
  oldStartVnode = oldCh[++oldStartIdx]
  newStartVnode = newCh[++newStartIdx]
}

這時(shí)的節(jié)點(diǎn)和索引變化如圖所示：

4. 舊尾等於新尾

與頭結(jié)點(diǎn)相等類(lèi)似，這種情況代表新舊節(jié)點(diǎn)數(shù)組的最後一個(gè)節(jié)點(diǎn)基本上一致，此時(shí)一樣調(diào)用patchVnode 比較兩個(gè)尾結(jié)點(diǎn)和更新dom，然後將兩個(gè)末尾索引向前移動(dòng)。

if (sameVnode(oldEndVnode, newEndVnode)) {
  patchVnode(
    oldEndVnode,
    newEndVnode,
    insertedVnodeQueue,
    newCh,
    newEndIdx
  )
  oldEndVnode = oldCh[--oldEndIdx]
  newEndVnode = newCh[--newEndIdx]
}

這時(shí)的節(jié)點(diǎn)和索引變化如圖所示：

#5. 舊頭等於新尾

#這裡表示的是舊節(jié)點(diǎn)數(shù)組目前起始索引指向的vnode 與新節(jié)點(diǎn)數(shù)組目前末尾索引指向的vnode 基本上一致，一樣調(diào)用patchVnode 對(duì)兩個(gè)節(jié)點(diǎn)進(jìn)行處理。

但與上述兩種有差別的地方在於：這種情況會(huì)造成節(jié)點(diǎn)的移動(dòng)，所以此時(shí)也會(huì)在patchVnode 結(jié)束之後 透過(guò)nodeOps.insertBefore 將舊的頭節(jié)點(diǎn) 重新插入到目前舊的尾結(jié)點(diǎn)之後。

然後，會(huì)將 舊節(jié)點(diǎn)的起始索引後移、新節(jié)點(diǎn)的結(jié)尾索引前移。

看到這裡大家可能會(huì)有一個(gè)疑問(wèn)，為什麼這裡移動(dòng)的是舊的節(jié)點(diǎn)數(shù)組，這裡因?yàn)関node 節(jié)點(diǎn)中有一個(gè)屬性elm ，會(huì)指向該vnode 對(duì)應(yīng)的實(shí)際dom 節(jié)點(diǎn)，所以這裡移動(dòng)舊節(jié)點(diǎn)數(shù)組其實(shí)就是側(cè)面去移動(dòng)實(shí)際的dom 節(jié)點(diǎn)順序；並且注意這裡是當(dāng)前的尾結(jié)點(diǎn)，在索引改變之後，這裡不一定就是原始舊節(jié)點(diǎn)數(shù)組的最末尾。

即：

if (sameVnode(oldStartVnode, newEndVnode)) {
  patchVnode(
    oldStartVnode,
    newEndVnode,
    insertedVnodeQueue,
    newCh,
    newEndIdx
  )
  canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
  oldStartVnode = oldCh[++oldStartIdx]
  newEndVnode = newCh[--newEndIdx]
}

此時(shí)狀態(tài)如下：

6. 舊尾等于新頭

這里與上面的 舊頭等于新尾 類(lèi)似，一樣要涉及到節(jié)點(diǎn)對(duì)比和移動(dòng)，只是調(diào)整的索引不同。此時(shí) 舊節(jié)點(diǎn)的 末尾索引 前移、新節(jié)點(diǎn)的 起始索引 后移，當(dāng)然了，這里的 dom 移動(dòng)對(duì)應(yīng)的 vnode 操作是 將舊節(jié)點(diǎn)數(shù)組的末尾索引對(duì)應(yīng)的 vnode 插入到舊節(jié)點(diǎn)數(shù)組 起始索引對(duì)應(yīng)的 vnode 之前。

if (sameVnode(oldEndVnode, newStartVnode)) {
  patchVnode(
    oldEndVnode,
    newStartVnode,
    insertedVnodeQueue,
    newCh,
    newStartIdx
  )
  canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
  oldEndVnode = oldCh[--oldEndIdx]
  newStartVnode = newCh[++newStartIdx]
}

此時(shí)狀態(tài)如下：

7. 四者均不相等

在以上情況都處理之后，就來(lái)到了四個(gè)節(jié)點(diǎn)互相都不相等的情況，這種情況也是 最復(fù)雜的情況。

當(dāng)經(jīng)過(guò)了上面幾種處理之后，此時(shí)的 索引與對(duì)應(yīng)的 vnode 狀態(tài)如下：

可以看到四個(gè)索引對(duì)應(yīng)的 vnode 分別是：vnode 3、vnode 5、 vnode 4、vnode 8，這幾個(gè)肯定是不一樣的。

此時(shí)也就意味著 雙端對(duì)比結(jié)束。

后面的節(jié)點(diǎn)對(duì)比則是 將舊節(jié)點(diǎn)數(shù)組剩余的 vnode （oldStartIdx 到 oldEndIdx 之間的節(jié)點(diǎn)）進(jìn)行一次遍歷，生成由 vnode.key 作為鍵，idx 索引作為值的對(duì)象 oldKeyToIdx，然后 遍歷新節(jié)點(diǎn)數(shù)組的剩余 vnode（newStartIdx 到 newEndIdx 之間的節(jié)點(diǎn)），根據(jù)新的節(jié)點(diǎn)的 key 在 oldKeyToIdx 進(jìn)行查找。此時(shí)的每個(gè)新節(jié)點(diǎn)的查找結(jié)果只有兩種情況：

• 找到了對(duì)應(yīng)的索引，那么會(huì)通過(guò) sameVNode 對(duì)兩個(gè)節(jié)點(diǎn)進(jìn)行對(duì)比：

  • 相同節(jié)點(diǎn)，調(diào)用 patchVnode 進(jìn)行深層對(duì)比和 dom 更新，將 oldKeyToIdx 中對(duì)應(yīng)的索引 idxInOld 對(duì)應(yīng)的節(jié)點(diǎn)插入到 oldStartIdx 對(duì)應(yīng)的 vnode 之前；并且，這里會(huì)將 舊節(jié)點(diǎn)數(shù)組中 idxInOld 對(duì)應(yīng)的元素設(shè)置為 undefined
  • 不同節(jié)點(diǎn)，則調(diào)用 createElm 重新創(chuàng)建一個(gè)新的 dom 節(jié)點(diǎn)并將 新的 vnode 插入到對(duì)應(yīng)的位置

• 沒(méi)有找到對(duì)應(yīng)的索引，則直接 createElm 創(chuàng)建新的 dom 節(jié)點(diǎn)并將新的 vnode 插入到對(duì)應(yīng)位置

注：這里 只有找到了舊節(jié)點(diǎn)并且新舊節(jié)點(diǎn)一樣才會(huì)將舊節(jié)點(diǎn)數(shù)組中 idxInOld 中的元素置為 undefined。

最后，會(huì)將 新節(jié)點(diǎn)數(shù)組的 起始索引 向后移動(dòng)。

if (isUndef(oldKeyToIdx)) {
    oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
  }
  idxInOld = isDef(newStartVnode.key)
    ? oldKeyToIdx[newStartVnode.key]
    : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
  if (isUndef(idxInOld)) {
    // New element
    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 {
      // same key but different element. treat as new element
      createElm(
        newStartVnode,
        insertedVnodeQueue,
        parentElm,
        oldStartVnode.elm,
        false,
        newCh,
        newStartIdx
      )
    }
  }
  newStartVnode = newCh[++newStartIdx]
}

大致邏輯如下圖：

剩余未比較元素處理

經(jīng)過(guò)上面的處理之后，根據(jù)判斷條件也不難看出，遍歷結(jié)束之后 新舊節(jié)點(diǎn)數(shù)組都剛好沒(méi)有剩余元素 是很難出現(xiàn)的，當(dāng)且僅當(dāng)遍歷過(guò)程中每次新頭尾節(jié)點(diǎn)總能和舊頭尾節(jié)點(diǎn)中總能有兩個(gè)新舊節(jié)點(diǎn)相同時(shí)才會(huì)發(fā)生，只要有一個(gè)節(jié)點(diǎn)發(fā)生改變或者順序發(fā)生大幅調(diào)整，最后 都會(huì)有一個(gè)節(jié)點(diǎn)數(shù)組起始索引和末尾索引無(wú)法閉合。

那么此時(shí)就需要對(duì)剩余元素進(jìn)行處理：

• 舊節(jié)點(diǎn)數(shù)組遍歷結(jié)束、新節(jié)點(diǎn)數(shù)組仍有剩余，則遍歷新節(jié)點(diǎn)數(shù)組剩余數(shù)據(jù)，分別創(chuàng)建節(jié)點(diǎn)并插入到舊末尾索引對(duì)應(yīng)節(jié)點(diǎn)之前
• 新節(jié)點(diǎn)數(shù)組遍歷結(jié)束、舊節(jié)點(diǎn)數(shù)組仍有剩余，則遍歷舊節(jié)點(diǎn)數(shù)組剩余數(shù)據(jù)，分別從節(jié)點(diǎn)數(shù)組和 dom 樹(shù)中移除

即：

小結(jié)

Vue 2 的 diff 算法相對(duì)于簡(jiǎn)單 diff 算法來(lái)說(shuō)，通過(guò) 雙端對(duì)比與生成索引 map 兩種方式 減少了簡(jiǎn)單算法中的多次循環(huán)操作，新舊數(shù)組均只需要進(jìn)行一次遍歷即可將所有節(jié)點(diǎn)進(jìn)行對(duì)比。

其中雙端對(duì)比會(huì)分別進(jìn)行四次對(duì)比和移動(dòng)，性能不算最優(yōu)解，所以Vue 3 中引入了最長(zhǎng)遞增子序列 的方式來(lái)替代雙端對(duì)比，而其餘部分則依然透過(guò)轉(zhuǎn)換為索引map 的形式利用空間擴(kuò)展來(lái)減少時(shí)間複雜度，從而更高的提升計(jì)算效能。

當(dāng)然本文的圖表中沒(méi)有給出 vnode 對(duì)應(yīng)的 elm 真實(shí) dom 節(jié)點(diǎn)，兩者的移動(dòng)關(guān)係可能會(huì)給大家?guī)?lái)誤解，建議配合 《Vue.js 設(shè)計(jì)與實(shí)現(xiàn)》一起閱讀。

整體流程如下：

（學(xué)習(xí)影片分享：vuejs入門(mén)教學(xué)、程式設(shè)計(jì)基礎(chǔ)影片）

以上是快速搞懂Vue2 diff演算法（圖文詳解）的詳細(xì)內(nèi)容。更多資訊請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！