圖碼詳解vue源碼：diff算法
導(dǎo)語 | 開發(fā)者工作中，研究代碼邏輯常需要思考這個問題：數(shù)組變更后，具體變更了哪一些元素？變更的位置如何？本文作者陳碧松解析并覆寫了針對數(shù)組變化的diff算法邏輯。希望本文對你有幫助。
diff方法的運行規(guī)則和前提方法
為了了解diff方法的運行規(guī)則和前提方法，首先我們通過幾個圖快速區(qū)別虛擬node進行深度優(yōu)先和同級對比。
深度優(yōu)先:
同級對比：
如上面圖所示，每次vnode都是執(zhí)行同級對比。（對應(yīng)dom同一個父元素）
代碼邏輯如下圖：
第二，簡單判斷：`sameVnode`函數(shù)用來進行判斷是否是同一個vnode元素。源代碼如下：
如圖所示：
這里有兩個重要元素：`key` : 開發(fā)者定義的”:key”；`sel `: 元素tagName+元素id+元素class。
sel的定義源碼如下：
vNode構(gòu)建函數(shù)：
第三是構(gòu)建索引。
邏輯如圖：
如何處理元素
盡量不新增/刪除dom。如圖下所示:
如果是相同vnode，源碼如下：
開始比較
首先會進行時間復(fù)雜度O(n)的while循環(huán)，循環(huán)條件為“遍歷舊節(jié)點數(shù)組&&遍歷新節(jié)點數(shù)組，誰先遍歷完循環(huán)就結(jié)束”。源碼如下圖:
在每次的循環(huán)過程中，會有兩大類判斷方法：
1）首尾比較&首尾序號
邏輯：如圖上所示。首先在循環(huán)遍歷前標(biāo)記好新，舊節(jié)點數(shù)組的開始位置和結(jié)束位置的序號：oldStartIdx、oldEndIdx、newStartIdx、newEndIdx；其次在循環(huán)遍歷的過程中采用“首首比較，尾尾比較，首尾比較"。
源碼如下：
如果數(shù)據(jù)為圖上所示，那么根據(jù)首尾比較方法會有如下圖所示結(jié)果，最終全部執(zhí)行了更新操作：
2）索引比較
最壞情況,這里的時間復(fù)雜度也是O(n)，即整個算法復(fù)雜度O(n)+O(n)。每次遍歷的過程中可能存在"新數(shù)組節(jié)點新增/舊數(shù)組節(jié)點刪除"，那么前后對比就滿足不了條件。這里邏輯會進入索引比較：比如這種情況：
那么循環(huán)中會執(zhí)行一遍，創(chuàng)建舊數(shù)組的索引對象。從創(chuàng)建到比較的整個邏輯圖如下：
這里的源碼如下:
當(dāng)舊節(jié)點不存在新增的節(jié)點時,進行當(dāng)前oldStartIdx位置的添加
源碼如下:
當(dāng)舊數(shù)組存在節(jié)點，那么進行位置移動
源碼：
3）當(dāng)節(jié)點遍歷完之后
會存在兩種情況：新數(shù)組已經(jīng)遍歷完，但舊數(shù)組沒有遍歷完成；舊數(shù)組遍歷完成，但新數(shù)組沒有遍歷完成。故源代碼的判斷如下:
舊數(shù)組沒有循環(huán)完成
舊數(shù)組沒有循環(huán)完成的效果如下圖所示：
這里注意一個點，我們每次的節(jié)點更新會移動序號，即使被刪除的節(jié)點不在一塊最終也會被首尾比較算法“摞在一塊”（oldStartIdx~oldEndIdx）。上圖所示更加明顯。源碼在這里就進行批量刪除：
新數(shù)組沒有循環(huán)完成
效果如下圖所示:
整體來說，有幾個關(guān)鍵點：簡單對比；創(chuàng)建舊數(shù)組的索引表；首位對比&首尾索引&vnode位置移動；索引添加/位移；剩余部分批量處理添加/刪除。
經(jīng)過前后對比&索引的過濾后，只會存在新.末尾節(jié)點!==舊節(jié)點及之前的連續(xù)的新節(jié)點(!==舊節(jié)點)，所以這里也被“摞在一塊”，即 （newStartIdx~newEndIdx）。源碼如下。這樣，整個diff的對比算法就已經(jīng)走完了。核心就是：前后對比+索引。
vue3.0對于diff比較前的優(yōu)化
vue3.0針對“無腦”patchVnode進行了過濾--靜態(tài)類型Vnode老版的源碼:
這里，我們再重復(fù)下vue2.x系列的對比更新邏輯:
新版的vue3.0增加了靜態(tài)類型Vnode。如果是靜態(tài)類型的vnode，直接跳過更新，修改新節(jié)點引用即可。
comment類型目前翻到它的源碼也只是更改引用，源碼作者加上了一行注釋。
補充一下，flagment碎片類型為新增的vnode類型，即：
vue3.0的過濾判斷源碼如下:
數(shù)組比較的應(yīng)用
由于我們想監(jiān)聽數(shù)組的變化，參考了diff算法覆寫類似的邏輯，用來在update,add,dels時，代碼層面獲取操作的具體節(jié)點明細（新舊節(jié)點的位置，內(nèi)容）。希望本文對你有幫助。
