前言

今天分享一下我對vue的diff的探究，跟我一起深入底層，看一看vue是怎么進行diff的，它的復雜度如何，為什么性能這么高，diff的目標是盡可能的復用原來的真實dom，減少刪除真實dom和創建真實的dom的開銷，我們圍繞這個目標展開。

---

diff發生的時刻以及目的

首先我們要明確的是diff發生在什么時候，它是發生在updateComponent的時刻，也就是比對新舊虛擬dom，最小化變化真實dom的過程。

---

過程深究

現在我們來模擬整個過程，執行完render以后的虛擬dom是一顆樹結構，整個過程其實是一個dfs的過程，首先是從跟根節點開始，比對根節點，接著會到下一層節點（注意是一層節點），如果只有一個節點（可能是組件節點或者普通的元素節點，我們都叫節點），那么就會直接比較它們的key和類型，比如他可能是一個組件類型也可能是一個div，如果有一個不一樣就會直接把整個子樹卸載，然后遞歸生成正確的真實dom，當如果不是一個節點，那么其實就是兩組虛擬dom的比對，這個過程是最關鍵的：
因為是兩個列表，vue會為舊虛擬dom列表創建兩個指針，指向頭尾，然后同理，新的也是頭尾兩個指針，然后他會按照：舊列表的頭指針和新列表的頭比較、舊尾和新尾，如果有發現key一樣且類型一樣的，直接復用，如果沒有匹配上，就會按照舊頭和新尾和舊尾新頭就進行對比，有的就直接復用，沒有的話直接進入一個關鍵環節diff的精髓所在：
首先對剩下的沒有處理的新虛擬dom點進行一個映射，map[虛擬dom節點] = id，這個id其實是它在新虛擬dom節點列表中的下標，然后會遍歷舊的dom樹，并且用map[虛擬dom節點] = id記錄下來。接下來，對舊dom列表進行一個匹配，匹配新dom列表中key和類型匹配，因為索引（map的映射值）是遞增的，所以我們會對舊dom列表求一個LIS（最長上升子序列），源碼中的話是通過二分+貪心找到的：

<template>
<div class="app"><h2>最長上升子序列</h2>
</div>
</template><script setup lang="ts">
const arr: Array<number> = [10, 30, 2, 1, 5, 5, 7] 
const inf: number = Math.floor(1e9) 
const lastIdx: Array<number> = new Array(arr.length).fill(-1)   
const q: Array<Array<number>> = [[-inf, 0, -1, -1]]
let c: number = 0 
let idx: number = 1 
let maxLen: number = 0 
for(let n of arr) {if(n > q[idx - 1][0]) {maxLen = Math.max(maxLen, q[idx - 1][1] + 1) q[idx] = [n, q[idx - 1][1] + 1, q[idx - 1][3], c]  lastIdx[c] = q[idx-1][3] idx += 1 c += 1continue }else if(n == q[idx - 1][0]) {c += 1 continue; }let l: number = 0, r: number = q.length - 1while(l < r) {let mid: number = Math.floor((l + r + 1) / 2) if(q[mid][0] <= n) l = mid else r = mid - 1  }let [v, le, last, Idx] = q[l] let va = n, curLen = 1, curLast = -1, curIdx = c if(v < n) {maxLen = Math.max(maxLen, le + 1) curLen = le + 1 curLast = Idx }else if(v === n) {curLen = le curLast = last }l = 0, r = q.length - 1 while(l < r) {let mid = Math.floor((l + r) / 2) if(q[mid][0] > n) r = mid else l = mid + 1  }lastIdx[curIdx] = curLast q[l] = [va, curLen, curLast, curIdx]c += 1 
}console.log(arr); 
console.log(maxLen, q);//比如說找最后一個：
let cur = arr.length - 1 
let res = Array<number>() 
while(cur != -1) {res.push(arr[cur]) cur = lastIdx[cur] 
}
res.reverse() 
console.log(res); </script><style scoped></style>

簡單的二分+貪心只能夠把最長的長度找出來，但是具體的序列找不出來，根據上面的改進能找到具體的序列，源碼大概也是差不多實現方式。
因為這一部分其實就可以保持不動了，然后我們將剩下的新dom點拿出。接著，繼續diff，從舊dom列表從后往前并且從剩下的新dom列表從后往前看，遇到直接匹配的，直接跳過，如果沒有匹配，如果舊dom的map中有，則會通過瀏覽器的方法$insertBefore$直接將這個真實dom點移動到該點位置前面，如果沒有就直接創建然后調用insertBefore方法，關鍵點來了，當前先保留這個點。然后一直進行，最后才將多余的點清空。

總的時間復雜度就是O(n + nlogn) * O(insertBefore)

這里講幾個為什么，也是我在寫博客的時候，引發的一些思考：

（1） 為什么不直接全部刪除，然后一次性創建，時間復雜度不是O（n）嗎，如果涉及真實dom移動不是看起來會更慢嗎？
刪除和創建dom的效率是極其慢的，但是移動dom是用瀏覽器底層的方法insertBefore，它是非常高效率的方法，所以我們盡可能避免讓dom創建和刪除，移動是可以接受的。

（2）為什么最后才將多余的點清空。
因為當我們從后往前遍歷的時候，如果我們在當前點操作完了，并且舊點沒用到，如果馬上刪除，并且前面的點可以復用他，但是沒復用到，就可能要刪除這個點，還要創建一個點，代價多了非常大，所以我們最后清除，可以盡可能的復用。

(3) 為什么不直接刪除舊dom列表中不存在于新dom列表中的點?
因為要保留insertBefore的參考位置，保證dom整體結構的穩定性，才會選擇最后刪除，它們的作用其實是作為參照物的作用，也是vue做出的取舍。

筆者水平有限，不夠嚴謹之處勿噴，多多賜教。