導(dǎo)語(yǔ) 最近碰到部分業(yè)務(wù)場(chǎng)景，代碼邏輯需要了解"數(shù)組變更后，具體變更了哪一些元素，以及變更的位置.."。于是仔細(xì)研究并覆寫(xiě)了一遍針對(duì)數(shù)組變化的diff算法，在這里做下diff算法的邏輯分享&&源碼解讀

一.介紹前的準(zhǔn)備工作

我們先了解diff方法的運(yùn)行規(guī)則和前提方法.

1.虛擬node進(jìn)行深度優(yōu)先 && 同級(jí)對(duì)比

深度優(yōu)先:

同級(jí)對(duì)比

如上面圖所示：

每次vnode都是執(zhí)行同級(jí)對(duì)比(對(duì)應(yīng)dom同一個(gè)父元素)

代碼邏輯如下圖：

2.簡(jiǎn)單判斷

sameVnode函數(shù)用來(lái)進(jìn)行判斷是否是同一個(gè)vnode元素。

源代碼：

如圖所示：

這里有兩個(gè)重要元素：

key : 開(kāi)發(fā)者定義的”:key”

sel: 元素tagName+元素id+元素class

sel的定義源碼如下：

vNode構(gòu)建函數(shù)：

3.構(gòu)建索引

邏輯如圖：

二.如何處理元素

盡量不新增/刪除dom，如圖下所示:

如果是相同vnode，源碼如下：

三.開(kāi)始比較

1.首先會(huì)進(jìn)行時(shí)間復(fù)雜度 O(n)的while循環(huán)，循環(huán)條件為 "遍歷舊節(jié)點(diǎn)數(shù)組&&遍歷新節(jié)點(diǎn)數(shù)組，誰(shuí)先遍歷完循環(huán)就結(jié)束" ，源碼如下圖:

在每次的循環(huán)過(guò)程中，會(huì)有兩大類(lèi)判斷方法：

1-1.首尾比較 && 首尾序號(hào)

邏輯：如圖上所示，首先在循環(huán)遍歷前 標(biāo)記好新，舊節(jié)點(diǎn)數(shù)組的開(kāi)始位置和結(jié)束位置的序號(hào)：oldStartIdx、oldEndIdx、newStartIdx、newEndIdx；其次在循環(huán)遍歷的過(guò)程中采用 "首首比較，尾尾比較，首尾比較"；

源碼如下：

如果數(shù)據(jù)為圖上所示，那么根據(jù)首尾比較方法會(huì)有如下圖所示結(jié)果，最終全部執(zhí)行了更新操作：

1-2.索引比較 -- 最壞情況,這里的時(shí)間復(fù)雜度也是O(n)，即整個(gè)算法復(fù)雜度O(n)+O(n)

每次遍歷的過(guò)程中可能存在"新數(shù)組節(jié)點(diǎn)新增/舊數(shù)組節(jié)點(diǎn)刪除"，那么前后對(duì)比就滿(mǎn)足不了條件。這里邏輯會(huì)進(jìn)入索引比較;

比如這種情況：

那么，循環(huán)中會(huì)執(zhí)行一遍 創(chuàng)建舊數(shù)組的索引對(duì)象。

那么從創(chuàng)建到比較的整個(gè)邏輯圖如下：

這里的源碼如下:

1-2.1 當(dāng)舊節(jié)點(diǎn)不存在新增的節(jié)點(diǎn)時(shí),進(jìn)行當(dāng)前oldStartIdx位置的添加:

源碼如下:

1-2.2 當(dāng)舊數(shù)組存在節(jié)點(diǎn)，那么進(jìn)行位置移動(dòng):

源碼：

1.3 當(dāng)節(jié)點(diǎn)遍歷完之后：

會(huì)存在兩種情況，“新數(shù)組已經(jīng)遍歷完，但舊數(shù)組沒(méi)有遍歷完成” || “舊數(shù)組遍歷完成，但新數(shù)組沒(méi)有遍歷完成”.

故源代碼的判斷如下:

1.3.1 舊數(shù)組沒(méi)有循環(huán)完成：

舊數(shù)組沒(méi)有循環(huán)完成的效果如下圖所示：

這里注意一個(gè)點(diǎn)，我們每次的節(jié)點(diǎn)更新會(huì)移動(dòng)序號(hào)，即使被刪除的節(jié)點(diǎn)不在一塊 最終也會(huì)被 首尾比較算法 "摞在一塊" 即 (oldStartIdx~oldEndIdx)。上圖所示更加明顯一些。

源碼在這里就進(jìn)行批量刪除：

1.3.2 新數(shù)組沒(méi)有循環(huán)完成:

效果如下圖所示:

經(jīng)過(guò) 前后對(duì)比&&索引 的過(guò)濾后，只會(huì)存在 新.末尾節(jié)點(diǎn)!==舊節(jié)點(diǎn) 及之前的連續(xù)的新節(jié)點(diǎn)(!==舊節(jié)點(diǎn));

所以這里也被 "摞在一塊" ，即 (newStartIdx~newEndIdx)

源碼如下：

這樣，整個(gè)diff的對(duì)比算法就已經(jīng)走完了。所以核心就是：前后對(duì)比+索引

四.關(guān)鍵點(diǎn)

關(guān)鍵點(diǎn)大概如下

五.vue3.0對(duì)于diff比較前的優(yōu)化

vue3.0針對(duì)"無(wú)腦"patchVnode進(jìn)行了過(guò)濾 -- 靜態(tài)類(lèi)型Vnode：

老版的源碼:

這里，我們?cè)僦貜?fù)下vue2.x系列的對(duì)比更新邏輯:

新版的vue3.0增加了 靜態(tài)類(lèi)型Vnode，如果是靜態(tài)類(lèi)型的vnode 那么直接跳過(guò)更新，修改新節(jié)點(diǎn)引用即可:

備注:comment類(lèi)型 目前翻到它的源碼也只是更改引用，源碼作者加上了一行注釋：

這里再多插一句，fragment 碎片類(lèi)型 為新增的vnode類(lèi)型， 即：

vue3.0的過(guò)濾判斷源碼如下:

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的diff算法_vue源码解读 diff算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。