導語 | 開發者工作中，研究代碼邏輯常需要思考這個問題：數組變更后，具體變更了哪一些元素？變更的位置如何？本文作者陳碧松解析并覆寫了針對數組變化的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時，代碼層面獲取操作的具體節點明細（新舊節點的位置，內容）。希望本文對你有幫助。
作者:陳碧松
出處:https://mp.weixin.qq.com/s/-8-AkMqwXJX54r6Lzbr5rA
