Vue Diff算法原理

Diff 算法是 Vue 中虛擬 DOM（Virtual DOM）渲染器的核心。

其目標(biāo)是：用最小的性能代價，找出新舊虛擬節(jié)點(diǎn)（VNode）之間的差異，并高效地更新真實(shí) DOM。

1. Diff 算法的核心策略

為了將 O ( n 3 ) O(n^3) O(n3) 的通用樹對比算法優(yōu)化至 O ( n ) O(n) O(n)，Vue 遵循了以下三個前提：

• 同層比較：只對同一層級的節(jié)點(diǎn)進(jìn)行比較，不跨層級。
• 類型識別：如果兩個節(jié)點(diǎn)的 tag 不同（如 <div> 變?yōu)?<p>），直接銷毀舊節(jié)點(diǎn)并創(chuàng)建新節(jié)點(diǎn)。
• Key 值復(fù)用：通過 key 屬性唯一標(biāo)識節(jié)點(diǎn)，盡量通過移動而非銷毀來復(fù)用現(xiàn)有 DOM。

2. 核心執(zhí)行流程：patch 函數(shù)

在源碼中，Diff 過程主要由 patch 函數(shù)執(zhí)行，其邏輯如下：

判斷是否為相同節(jié)點(diǎn)：

• 比較 key 和 tag。如果不同，直接替換。

更新屬性 (Props/Attrs)：

• 如果節(jié)點(diǎn)相同，對比并更新 Class、Style、事件等屬性。

對比子節(jié)點(diǎn) (Children)：

• 舊有新無：卸載（Unmount）舊子節(jié)點(diǎn)。
• 舊無新有：掛載（Mount）新子節(jié)點(diǎn)。
• 新舊都有：觸發(fā)核心 Diff 算法（雙端比較 或 最長遞增子序列）。

3. Vue 2 vs Vue 3 算法實(shí)現(xiàn)

Vue 2：雙端 Diff (Double-Ended Diff)

Vue 2 使用四個指針分別指向新舊列表的頭尾，進(jìn)行四種假設(shè)性匹配：

• 頭頭 (oldStart vs newStart)
• 尾尾 (oldEnd vs newEnd)
• 頭尾 (oldStart vs newEnd)：命中則涉及 DOM 移動。
• 尾頭 (oldEnd vs newStart)：命中則涉及 DOM 移動。
• 亂序匹配：若四次都沒中，建立 key 的映射表進(jìn)行查找。

Vue 3：快速 Diff (Quick Diff)

Vue 3 借鑒了 inferno 算法，利用了 靜態(tài)提升 和 預(yù)處理：

• 從頭預(yù)處理：從前向后比對，直到遇到不同節(jié)點(diǎn)。
• 從尾預(yù)處理：從后向前比對，直到遇到不同節(jié)點(diǎn)。

處理未知序列：

• 對于剩余的亂序節(jié)點(diǎn)，構(gòu)建一個最長遞增子序列 (LIS)。
• 子序列中的節(jié)點(diǎn)保持不動，只移動不在序列中的節(jié)點(diǎn)。
• 這是目前最優(yōu)的 DOM 移動方案，減少了真實(shí) DOM 的操作次數(shù)。

4. 為什么 key 很重要？

• 性能提升：key 是節(jié)點(diǎn)的身份標(biāo)識。有了它，算法能精準(zhǔn)匹配新舊節(jié)點(diǎn)，將“銷毀-再創(chuàng)建”變成“低開銷的移動”。
• 狀態(tài)保持：在處理帶有狀態(tài)的組件（如 Input 或切換動畫）時，沒有 key 或使用 index 作為 key 可能會導(dǎo)致 UI 狀態(tài)錯亂。

注意：避免使用 index 作為 key。當(dāng)列表發(fā)生排序、插入、刪除操作時，index 的變化會導(dǎo)致 Vue 誤判節(jié)點(diǎn)，產(chǎn)生不必要的 DOM 更新。

Vue 3：快速 Diff (Quick Diff) 詳解

Vue 3 的快速 Diff 算法（Quick Diff）相比 Vue 2 的雙端 Diff，最大的改進(jìn)在于它通過預(yù)處理盡可能減少了需要參與復(fù)雜比對的節(jié)點(diǎn)數(shù)量，并利用數(shù)學(xué)上的最長遞增子序列來計算出最少的 DOM 移動次數(shù)。

1. 預(yù)處理前置節(jié)點(diǎn)

• 從前到后 對比兩列 新舊 節(jié)點(diǎn)
• 從頭部開始，如果 key 和 type 相同，則直接 patch（更新屬性），直到遇到不同的節(jié)點(diǎn)為止。

定義 i 變量：記錄當(dāng)前前置索引值

• i == 0 ，新舊節(jié)點(diǎn)都為 n1，直接更新節(jié)點(diǎn)
• i == 1，新舊節(jié)點(diǎn)都為 n2，直接更新節(jié)點(diǎn)
• i == 2，新舊節(jié)不一樣，停在這里記錄 i = 2

2. 預(yù)處理后置節(jié)點(diǎn)

• 從后到前 對比兩列 新舊 節(jié)點(diǎn)
• 邏輯同預(yù)處理前置節(jié)點(diǎn)

• 定義 e1 為舊節(jié)點(diǎn)列表的 后置索引值
• 定義 e2 為新節(jié)點(diǎn)列表的 后置索引值

• e1 ==6、e2 == 6，新舊節(jié)點(diǎn)一樣，直接更新
• e1 ==6、e2 == 5，新舊節(jié)點(diǎn)不一樣。記錄下 e1 e2 的位置

3. 處理僅有新增節(jié)點(diǎn)情況

• 假設(shè)只有新增節(jié)點(diǎn)的情況，新舊節(jié)點(diǎn)列表如下圖

僅有新增節(jié)點(diǎn)： i > e1 && i <= e2

• i ：前置索引值（節(jié)點(diǎn)不一樣的那個記錄）
• e1：舊節(jié)點(diǎn)后置索引值（節(jié)點(diǎn)不一樣的那個記錄）
• e2：新節(jié)點(diǎn)后置索引值（節(jié)點(diǎn)不一樣的那個記錄）
• 只需要將新增節(jié)點(diǎn)更新到頁面上

4. 處理僅有卸載節(jié)點(diǎn)情況

• 僅有刪除節(jié)點(diǎn)： i > e2 && i <= e1

5. 處理混合復(fù)雜情況（新增、卸載、移動）

完成 預(yù)處理前置節(jié)點(diǎn)、 預(yù)處理后置節(jié)點(diǎn)、到達(dá)這個狀態(tài)

在這個狀態(tài)下我們需要：

• 新增 n8
• 卸載 n3
• 更新 n4、n5、n6

5.1 各個變量的作用

當(dāng)前最遠(yuǎn)位置 (lastIndex / maxNewIndexSoFar)：

• 初始為 0。記錄在遍歷舊節(jié)點(diǎn)時，對應(yīng)新節(jié)點(diǎn)在 新列表中的最大索引位置。
• 目的：判斷 新舊節(jié)點(diǎn) 在遍歷的過程中是否 同時呈現(xiàn)遞增趨勢。如果不是則證明節(jié)點(diǎn)產(chǎn)生了移動。需要移動表示置為 true 。后續(xù)進(jìn)行移動處理。

移動標(biāo)識 (moved)：

• 初始為 false。一旦發(fā)現(xiàn)新節(jié)點(diǎn)位置映射表中當(dāng)前新節(jié)點(diǎn)的索引小于 lastIndex，說明節(jié)點(diǎn)順序發(fā)生了交叉，該標(biāo)識變?yōu)?true，后續(xù)將觸發(fā)最長遞增子序列（LIS）計算。

• s1 & s2: 分別指向舊子序列和新子序列的起始索引（本圖中均為 2，即從 n3/n6 開始）。

新節(jié)點(diǎn)位置映射表 (keyToNewIndexMap)：

• 作用: 存儲 新子序列中節(jié)點(diǎn) 的 key 與其 索引 的對應(yīng)關(guān)系（例如 n6: 2, n4: 3）。
• 目的: 為了在遍歷舊節(jié)點(diǎn)時，能以 O ( 1 ) O(1) O(1) 的復(fù)雜度快速找到該節(jié)點(diǎn)在新列表中是否存在。

新舊節(jié)點(diǎn)位置映射表 (source / newIndexToOldIndexMap)：

• 結(jié)構(gòu): 長度等于新子序列長度的數(shù)組（圖中四個 0 的方塊）。
• 作用: 記錄新節(jié)點(diǎn)在舊列表中的原始位置索引。

值含義:

• 初始全為 0。
• 如果處理后值為 5，代表新子序列該位置的節(jié)點(diǎn)在舊序列中的索引是 5。
• 0 是特殊值，代表該新節(jié)點(diǎn)是全新的（需掛載）。

5.2 Diff 算法位置處理的詳細(xì)流程

第一階段：遍歷新子序列，建立新節(jié)點(diǎn)位置映射表

• 遍歷新子序列（從 s 2 s2 s2 到 e 2 e2 e2），構(gòu)建 keyToNewIndexMap。
• 方便接下來遍歷 舊子序列節(jié)點(diǎn)時候，知道哪些節(jié)點(diǎn)要更新和卸載。

第二階段：遍歷舊子序列，尋找可復(fù)用節(jié)點(diǎn)

遍歷舊子序列（從 s 1 s1 s1 到 e 1 e1 e1），對每一個舊節(jié)點(diǎn)執(zhí)行以下邏輯：

檢查舊節(jié)點(diǎn)是否存在: 通過舊節(jié)點(diǎn)的 key 去 keyToNewIndexMap 中查找。

• 找不到: 說明該舊節(jié)點(diǎn)在新列表中已不存在，直接卸載（Unmount）。
• 找到了: 說明節(jié)點(diǎn)可以復(fù)用。

執(zhí)行 Patch: 對新舊節(jié)點(diǎn)進(jìn)行打補(bǔ)?。ǜ聦傩?、子節(jié)點(diǎn)等）。

填充 新舊節(jié)點(diǎn)位置映射表:

• 遍歷接子序列節(jié)點(diǎn)，當(dāng)前舊節(jié)點(diǎn)在 新節(jié)點(diǎn)位置映射表中找到了，則將舊節(jié)點(diǎn)的下標(biāo)+1，存放到新舊節(jié)點(diǎn)為止映射表中
• （若新舊節(jié)點(diǎn)列表根本 沒有相同的前節(jié)點(diǎn)，那么在進(jìn)行最后一步比對時，s1就會是從0開始的，此時若不進(jìn)行+1，則無法與表示代表該新節(jié)點(diǎn)是全新的 0 區(qū)分了。）

檢測移動:

• 如果當(dāng)前找到的新子序列中新節(jié)點(diǎn)索引 >= lastIndex，則更新 lastIndex = newIndex。
• 如果當(dāng)前找到的舊節(jié)點(diǎn)索引（+1之后的值） >= lastIndex，則更新 lastIndex = newIndex。

如果當(dāng)前找到的新索引 < lastIndex，則說明該節(jié)點(diǎn)“跑到了前面節(jié)點(diǎn)的前面”，將 moved 設(shè)為 true。

第三階段：移動與掛載（最核心）

一旦 moved 為 true，算法會執(zhí)行以下操作：

計算最長遞增子序列 (LIS): 針對 source 數(shù)組計算 LIS。

• 意義: LIS 中的節(jié)點(diǎn)代表了在位置變換中相對順序沒有改變的最大節(jié)點(diǎn)集合。
• 這些節(jié)點(diǎn)是不需要移動的“錨點(diǎn)”。

倒序遍歷新舊節(jié)點(diǎn)位置映射表:

• 情況 A: 如果 source[i] === 0，說明是新節(jié)點(diǎn)，執(zhí)行 掛載（Mount）。
• 情況 B: 如果當(dāng)前索引不在 LIS 中，說明該節(jié)點(diǎn)需要移動，執(zhí)行 移動（Move/Insert）。
• 情況 C: 如果當(dāng)前索引在 LIS 中，跳過，不做任何操作（保持原位）。

最長遞增子序列算法

最長遞增子序列算法

1. 定義

最長遞增子序列是指在一個給定的序列中，找出一個子序列，使得子序列中的元素自左向右依次遞增，且長度盡可能長。

• 子序列：不需要在原數(shù)組中連續(xù)，但必須保持原始的相對順序。
• 嚴(yán)格遞增：子序列中相鄰元素必須滿足 a [ i ] < a [ i + 1 ] a[i] < a[i+1] a[i]<a[i+1]。

2. 示例

假設(shè)輸入數(shù)組：[10, 9, 2, 5, 3, 7, 101, 18]

• 一個遞增子序列是：[2, 3, 7, 18]
• 最長遞增子序列的長度為：4

3. 核心算法實(shí)現(xiàn)

方法一：動態(tài)規(guī)劃 (Dynamic Programming)

這是最經(jīng)典的方法，適合理解問題的本質(zhì)。

• 時間復(fù)雜度： O ( n 2 ) O(n^2) O(n2)
• 空間復(fù)雜度： O ( n ) O(n) O(n)

/**
 * @param {number[]} nums
 * @return {number}
 */
function lengthOfLIS(nums) {
    if (!nums.length) return 0;
    
    // dp[i] 表示以 nums[i] 結(jié)尾的最長遞增子序列的長度
    const dp = new Array(nums.length).fill(1);
    let maxLen = 1;

    for (let i = 1; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            // 如果當(dāng)前值大于前面的值，可以嘗試拼接
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        maxLen = Math.max(maxLen, dp[i]);
    }
    
    return maxLen;
}

方法二：貪心 + 二分查找 (Greedy + Binary Search)

二分查找（Binary Search）：

• 也叫折半查找，是一種效率極高的搜索算法。
• 它的核心思想是：每一步都將搜索范圍縮小一半。
• 但有一個極其重要的前提：目標(biāo)集合必須是有序的（通常是升序）。

貪心算法（Greedy Algorithm）：

• 是一種在每一步選擇中都采取在當(dāng)前狀態(tài)下**最好或最優(yōu)（最有利）**的選擇，從而希望導(dǎo)致結(jié)果是全局最優(yōu)的策略。
• 通俗點(diǎn)說，貪心算法就是“目光短淺”的算法：只看眼前的利益，不考慮長遠(yuǎn)的影響。

4 vue3 diff 算法中的最長遞增子序列

4.1 二分查找 + 貪心算法 存在的問題

• vue采用的是 二分查找 + 貪心算法
• 貪心算法求的是 局部最優(yōu)解，導(dǎo)致 全局最終解 出現(xiàn)偏差
• vue3 新增了一個 回溯修正 步驟

4.2 回溯修正

• 構(gòu)建一個反向列表，每個節(jié)點(diǎn)記錄上一個節(jié)點(diǎn)的位置，最后回溯修正

Vue 2 雙端 Diff 算法詳解

Vue 2 的 雙端 Diff 算法 (Double-Ended Diff) 是基于 snabbdom 修改而來的。它的核心是通過四個指針同時從新舊兩個列表的兩端向中間遍歷，盡可能地復(fù)用 DOM 節(jié)點(diǎn)。

1. 核心指針 (Four Pointers)

在 Diff 開始時，會定義四個索引變量：

• oldStartIdx: 指向舊子節(jié)點(diǎn)列表的第一個節(jié)點(diǎn)。
• oldEndIdx: 指向舊子節(jié)點(diǎn)列表的最后一個節(jié)點(diǎn)。
• newStartIdx: 指向新子節(jié)點(diǎn)列表的第一個節(jié)點(diǎn)。
• newEndIdx: 指向新子節(jié)點(diǎn)列表的最后一個節(jié)點(diǎn)。

2. 五步查找策略

算法在一個 while 循環(huán)中運(yùn)行（條件：oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx）。每一步都會按順序進(jìn)行以下五種匹配：

① 頭-頭匹配 (oldStart vs newStart)

• 邏輯：檢查兩個列表的第一個節(jié)點(diǎn)是否相同（key 和 sel 相同）。
• 操作：調(diào)用 patchVnode 更新；兩個 Start 指針同時后移（+1）。

② 尾-尾匹配 (oldEnd vs newEnd)

• 邏輯：檢查兩個列表的最后一個節(jié)點(diǎn)是否相同。
• 操作：調(diào)用 patchVnode 更新；兩個 End 指針同時前移（-1）。

③ 舊頭-新尾匹配 (oldStart vs newEnd)

• 場景：原來的第一個節(jié)點(diǎn)現(xiàn)在跑到了最后。
• 操作：更新節(jié)點(diǎn)，并將 oldStart 指向的真實(shí) DOM 移動到當(dāng)前 oldEnd 對應(yīng)的 DOM 之后。
• 指針：oldStartIdx++，newEndIdx–。

④ 舊尾-新頭匹配 (oldEnd vs newStart)

• 場景：原來的最后一個節(jié)點(diǎn)現(xiàn)在跑到了最前面。
• 操作：更新節(jié)點(diǎn)，并將 oldEnd 指向的真實(shí) DOM 移動到當(dāng)前 oldStart 對應(yīng)的 DOM 之前。
• 指針：oldEndIdx–，newStartIdx++。

⑤ 亂序匹配 (Key Map Lookup)

如果以上四種假設(shè)全都不成立：

生成映射表：建立舊列表所有節(jié)點(diǎn)的 { key: index } 哈希表。

查找：用 newStart 的 key 去表里查。

• 沒找到：它是新節(jié)點(diǎn)，創(chuàng)建并插入到 oldStart DOM 之前。
• 找到了：如果是相同節(jié)點(diǎn)，將其對應(yīng)的真實(shí) DOM 移動到 oldStart 之前，并將舊列表該位置設(shè)為 undefined。

指針：newStartIdx++。

3. 循環(huán)結(jié)束后的處理

頭尾指針交叉循環(huán)結(jié)束，頭指針 <= 尾指針 循環(huán)繼續(xù)。

當(dāng)其中一個列表遍歷完時，循環(huán)停止：

舊列表先完 (oldStartIdx > oldEndIdx)：

• 說明新列表中 newStartIdx 到 newEndIdx 之間的節(jié)點(diǎn)是新增的。
• 處理：批量創(chuàng)建并插入。

新列表先完 (newStartIdx > newEndIdx)：

• 說明舊列表中 oldStartIdx 到 oldEndIdx 之間的節(jié)點(diǎn)是多余的。
• 處理：批量從 DOM 中移除。

4. 為什么雙端 Diff 更快？

• 減少移動次數(shù)：通過 舊頭-新尾 和 舊尾-新頭 的檢測，能極大地優(yōu)化“倒序”或“首尾互換”的場景。
• 命中率高：在實(shí)際開發(fā)中，列表往往只是在兩端增刪節(jié)點(diǎn)，雙端對比能迅速收窄范圍。
• 空間換時間：通過 Key 映射表將 O(n²) 的暴力查找降為 O(n) 的線性處理。

注意：Vue 3 進(jìn)一步引入了“靜態(tài)標(biāo)記”和“最長遞增子序列”算法，處理亂序匹配的性能比 Vue 2 的雙端 Diff 更加極致。

總結(jié)

以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。

最新評論