快人一步掌握vue源碼解讀，搞定diff算法！（超詳細）
導(dǎo)語 | 最近碰到部分業(yè)務(wù)場景，代碼邏輯需要了解“數(shù)組變更后，具體變更了哪一些元素，以及變更的位置…”。于是仔細研究并覆寫了一遍針對數(shù)組變化的diff算法，在這里做下diff算法的邏輯分享&&源碼解讀。
一、介紹前的準備工作
我們先了解diff方法的運行規(guī)則和前提方法。
（一）虛擬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)過程中，會有兩大類判斷方法：
首尾比較&&首尾序號
邏輯：如圖上所示，首先在循環(huán)遍歷前標記好新，舊節(jié)點數(shù)組的開始位置和結(jié)束位置的序：oldStartIdx、oldEndIdx、newStartIdx、newEndIdx；其次在循環(huán)遍歷的過程中采用“首首比較，尾尾比較，首尾比較”。
源碼如下：
如果數(shù)據(jù)為圖上所示，那么根據(jù)首尾比較方法會有如下圖所示結(jié)果，最終全部執(zhí)行了更新操作：
索引比較--最壞情況，這里的時間復(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é)點，那么進行位置移動:
源碼：
當(dāng)節(jié)點遍歷完之后
會存在兩種情況，“新數(shù)組已經(jīng)遍歷完，但舊數(shù)組沒有遍歷完成” 和 “舊數(shù)組遍歷完成，但新數(shù)組沒有遍歷完成”。
故源代碼的判斷如下:
舊數(shù)組沒有循環(huán)完成：
效果如下圖所示：
這里注意一個點，我們每次的節(jié)點更新會移動序號，即使被刪除的節(jié)點不在一塊最終也會被首尾比較算法 “摞在一塊”，即（oldStartIdx~oldEndIdx）。上圖所示更加明顯一些。
源碼在這里就進行批量刪除：
新數(shù)組沒有循環(huán)完成:
效果如下圖所示:
經(jīng)過前后對比&&索引的過濾后，只會存在新末尾節(jié)點!==舊節(jié)點及之前的連續(xù)的新節(jié)點(!==舊節(jié)點)；所以這里也“摞在一塊”，即（newStartIdx~newEndIdx）。
源碼如下：
這樣，整個diff的對比算法就已經(jīng)走完了。所以核心就是：前后對比+索引。
四、關(guān)鍵點
關(guān)鍵點大概如下:
五、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)容）。
git地址：http://git.code.oa.com/winkchen/diffArr.git
同時tnpm包：tnpmi@tencent/arraydiff
tnpm地址：
http://mirrors.tencent.com/#/private/npm/detail?repo_id=537&project_name=%40tencent%2Farraydiff
作者簡介
陳碧松（winkchen）
騰訊web前端開發(fā)工程師
騰訊web前端開發(fā)工程師。目前負責(zé)騰訊IEG智慧發(fā)行的前端開發(fā)工作，有豐富的游戲內(nèi)活動開發(fā)，游戲內(nèi)視頻直播開發(fā)經(jīng)驗。
推薦閱讀
事務(wù)消息大揭秘！RocketMQ、Kafka、Pulsar全方位對比
Linux入門必看：如何在60秒內(nèi)分析Linux性能？
“Docker VS Kubernetes”是共生還是相愛相殺？
