前言

今天分享一下我对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做出的取舍。

笔者水平有限，不够严谨之处勿喷，多多赐教。