由淺入深讀透vue原始碼：diff演算法

導語 | 開發者工作中，研究程式碼邏輯常需要思考這個問題：陣列變更後，具體變更了哪一些元素？變更的位置如何？本文作者陳碧鬆解析並覆寫了針對陣列變化的diff演算法邏輯。希望本文對你有幫助。

diff方法的執行規則和前提方法

為了瞭解diff方法的執行規則和前提方法，首先我們通過幾個圖快速區別虛擬node進行深度優先和同級對比。

深度優先:

同級對比：

如上面圖所示，每次vnode都是執行同級對比。（對應dom同一個父元素）

程式碼邏輯如下圖：

第二，簡單判斷：sameVnode函式用來進行判斷是否是同一個vnode元素。原始碼如下：

如圖所示：

這裡有兩個重要元素：key : 開發者定義的“:key”；sel :  元素tagName+元素id+元素class。

sel的定義原始碼如下：

vNode構建函式：

第三是構建索引。

邏輯如圖：

如何處理元素

儘量不新增/刪除dom。如圖下所示:

如果是相同vnode，原始碼如下：

開始比較

首先會進行時間複雜度O(n)的while迴圈，迴圈條件為“遍歷舊節點陣列&&遍歷新節點陣列，誰先遍歷完迴圈就結束”。原始碼如下圖:

在每次的迴圈過程中，會有兩大類判斷方法：

1）首尾比較&首尾序號

邏輯：如圖上所示。首先在迴圈遍歷前標記好新，舊節點陣列的開始位置和結束位置的序號：oldStartIdx、oldEndIdx、newStartIdx、newEndIdx；其次在迴圈遍歷的過程中採用“首首比較，尾尾比較，首尾比較"。

原始碼如下：

如果資料為圖上所示，那麼根據首尾比較方法會有如下圖所示結果，最終全部執行了更新操作：

2）索引比較

最壞情況,這裡的時間複雜度也是O(n)，即整個演算法複雜度O(n)+O(n)。每次遍歷的過程中可能存在"新陣列節點新增/舊陣列節點刪除"，那麼前後對比就滿足不了條件。這裡邏輯會進入索引比較：比如這種情況：

那麼迴圈中會執行一遍，建立舊陣列的索引物件。從建立到比較的整個邏輯圖如下：

這裡的原始碼如下:

• 當舊節點不存在新增的節點時,進行當前oldStartIdx位置的新增

  

原始碼如下:

• 當舊陣列存在節點，那麼進行位置移動

  

原始碼：

3）當節點遍歷完之後

會存在兩種情況：新陣列已經遍歷完，但舊陣列沒有遍歷完成；舊陣列遍歷完成，但新陣列沒有遍歷完成。故原始碼的判斷如下:

• 舊陣列沒有迴圈完成

舊陣列沒有迴圈完成的效果如下圖所示：

這裡注意一個點，我們每次的節點更新會移動序號，即使被刪除的節點不在一塊最終也會被首尾比較演算法“摞在一塊”（oldStartIdx~oldEndIdx）。上圖所示更加明顯。原始碼在這裡就進行批量刪除：

• 新陣列沒有迴圈完成

效果如下圖所示:

整體來說，有幾個關鍵點：簡單對比；建立舊陣列的索引表；首位對比&首尾索引&vnode位置移動；索引新增/位移；剩餘部分批量處理新增/刪除。

經過前後對比&索引的過濾後，只會存在新.末尾節點!==舊節點及之前的連續的新節點(!==舊節點)，所以這裡也被“摞在一塊”，即 （newStartIdx~newEndIdx）。原始碼如下。這樣，整個diff的對比演算法就已經走完了。核心就是：前後對比+索引。

vue3.0對於diff比較前的優化

vue3.0針對“無腦”patchVnode進行了過濾--靜態型別Vnode老版的原始碼:

這裡，我們再重複下vue2.x系列的對比更新邏輯:

新版的vue3.0增加了靜態型別Vnode。如果是靜態型別的vnode，直接跳過更新，修改新節點引用即可。

comment型別目前翻到它的原始碼也只是更改引用，原始碼作者加上了一行註釋。

補充一下，flagment碎片型別為新增的vnode型別，即：

vue3.0的過濾判斷原始碼如下:

陣列比較的應用

由於我們想監聽陣列的變化，參考了diff演算法覆寫類似的邏輯，用來在update,add,dels時，程式碼層面獲取操作的具體節點明細（新舊節點的位置，內容）。希望本文對你有幫助。

你可能感興趣的騰訊工程師作品

| 優雅應對故障：QQ音樂怎麼做高可用架構體系？

| 最全Go select底層原理，一文學透高頻用法

| 十億人都在用的健康碼，運維體系是怎麼設計的

|詳解全網最快Go泛型跳錶【內附原始碼】

技術盲盒：前端｜後端｜AI與演算法｜運維｜工程師文化