编程导航会员会员
登录/注册

关于Vue3 diff算法的三两事


前言


这段时间在学习Vue的渲染相关的知识，通过阅读霍春阳老师的《VueJs设计与实现》以及自己的上手实践，也是对Vue的如何进行渲染有了更深的认识。

Vue的渲染，涉及到页面初始化，以及更新(包括对节点的增删改）等。那么说起更新，就不得不提起Vue的diff算法了。


虚拟DOM


在说diff算法之前，我们首先来了解一下虚拟DOM。

那么什么是虚拟DOM呢？简单来说，虚拟DOM就是一个对象，它是用来描述真实DOM的。

{
type:"div",
props:{
id:"app",
class:"mt_18"
},
children:[]
}

上述给出的伪代码，就是虚拟DOM的庐山真面目了，怎么样？也没有这么神秘吧？

那么Vue为什么要用虚拟DOM来描述真实DOM呢，包括React、Angular等主流框架也采用虚拟DOM，虚拟DOM有什么好处呢？

当我们操作真实DOM时，浏览器都会对整个页面进行重新渲染，如果DOM节点数不多的情况下并不会有什么影响。但在大型项目中，DOM节点数是非常多的，如果我们仅仅修改了一处DOM就要重新渲染整个页面的话，对浏览器来说负担还是比较大的。

而虚拟DOM它能保证渲染性能的下限，让浏览器用最少的操作来渲染真实DOM，只重新滚渲染有差异的DOM节点。那么，在DOM节点数非常庞大的情况下，就可以极大的提升性能，而不是“牵一发动全身”。



快速diff


在Vue3中采用了新的比较新旧两组子节点的算法——快速diff。

那么它的核心是什么呢？

找出新旧子节点中相同的前置以及后置节点，对其进行patch更新，若中间的节点无法进行简单的增删实现更新，则根据节点的索引关系构造出最长递增子序列，尽最大可能减少节点的移动，提高性能。（以上是我根据霍春阳老师的《Vue.JS设计与实现》提炼的）

光看这段话还是比较晦涩难懂的，废话不多说，直接上图！

首先来看看前置和后置的比较，初始大概是这样的：

首先是前置，i指针指向新旧子节点的开头，而e1和e2指针分别指向旧新子节点的结尾，循环遍历，直到节点不相同为止,伪代码如下:

function isSameVNodeType(n1, n2) {
return n1.type === n2.type && n1.key === n2.key;
}
while (i <= e1 && i <= e2) {
const n1 = oldChildren[i];
const n2 = newChildren[i];
if (isSameVNodeType(n1, n2)) {
patch(n1, n2, container);
} else {
break;
}
i++;
}

那么比较两个节点相同的条件是什么呢？首先是节点的类型（比如说都是p或者div等） 得相同，但这样就够了吗？如果两个节点类型相同，但是children不一样的话就会无法确认对应的关系了，所以这也是Vue中key的重要作用，可以把它当作每一个节点的唯一标识，就像我们的身份证一样，都是独一无二的。

那么我们给节点加上key后，经过前置对比的结果如下图：

随后进行后置的对比,伪代码如下：

while (i <= e1 && i <= e2) {
const n1 = oldChildren[e1];
const n2 = newChildren[e2];
if (isSameVNodeType(n1, n2)) {
patch(n1, n2, container);
} else {
break;
}
e1--;
e2--;
}

进行后置对比后，结果如下图：

在上述的前置和后置比较中，为什么节点相同时要对它进行patch呢？因为节点虽然是同一个节点，但是它的children可能会发生变化 (或是文本内容发生更改，或是有了多个子节点） ，所以需要对它进行重新更新，比如下面这种情况。

// oldVNode
{
type:"p",
props:{
key:1
},
children:"hello"
}
//newVNode
{
type:"p",
props:{
key:1
},
children:"hello world"
}

前后置对比完后，在理想情况下，我们只需要对newChildren中多出的节点进行添加，没有的节点进行删除即可。

而在不理想的情况下，需要对节点进行移动，新增和删除。

首先，我们先来看看理想情况。


理想情况

newChildren比oldChildren短


理想情况下，没有需要移动的节点，当newChildren比oldChildren短时，只需要删除掉oldChildren中多余的节点，当i小于等于e1时，进行删除操作，伪代码如下。

if(i > e2 && i <= e1) {
while(i <= e1){
unmount(oldChilren[i++])
}
}


newChildren比oldChildren长


当newChildren比oldChildren长时，只需要新增oldChildren中oldChildren中没有的节点，当i小于等于e2时，进行新增操作，伪代码如下。

else if(i > e1 && i <= e2){
const nextPos = e2 + 1;
const anchor = nextPos > newChildren.length ? null : newChildren[nextPos].el;
while(i <= e2) {
patch(null, newChildren[i],container, anchor);
i++;
}
}

与删除不同的是，新增需要找到锚点，也就是说需要找到元素要新增在哪里。

新增的索引位置位于e2+1(也就是oldChildren和newChildren从末尾到开头最后一个相同的节点)的前面，当它大于newChildren的长度时，说明新元素要新增在节点末尾。

看到这里，如果大家忘了i、e1、e2各自的含义，不妨重新温习一下。

i指向newChildren和oldChildren的前置节点，遍历过后指向newChildren和oldChildren前置节点第一个不同的节点索引；e1和e2指向newChildren和oldChildren的后置节点，遍历过后指向newChildren和oldChildren后置节点第一个不同的节点索引。


复杂情况


接下来就是比较复杂的情况了，就比如开头的那种情况：

可以发现，此时无法单纯的对元素进行简单的增加删除就可以完成的了，此时需要对元素进行移动才能完成更新。

在Vue3中，定义了一个source数组，长度为newChildren未处理的节点数量，也就是e2-i+1，这个数组用于存储newChildren的子节点在oldChildren子节点中的位置索引，后续用其生成最长递增子序列，计算出最少需要移动的节点。

首先，遍历newChildren，通过未处理的节点生成key：value的映射表，key为子节点的key值，value为子节点的索引值，便于在后续查找元素索引（也是为了降低双重for循环带来的时间复杂度）。

else{
const s1 = i;
const s2 = i;
let patched = 0; // 已更新节点的数量
const count = e2 - i + 1; // 表示未处理的节点数量
// 初始值填充为-1，表示需要创建的新节点
const source = new Array(count).fill(-1);
const newIndexMap = new Map();
let moved = false; // 是否需要移动
let maxNewIndex = 0; // 表示遍历时该节点之前最大的索引值
for(let i = s2;i <= e2;i++) {
// 记录
const newChild = newChildren[i];
newIndexMap.set(newChild.key, i);
}
...
}

接着，我们就可以遍历oldChildren，找出可复用的节点，对其进行更新，也去收集它在oldChildren中的索引位置,接着上述代码接着写。

for(let i = s1;i <= e1;i++) {
if(patched >= count){
// 如果已经更新的数量大于了需要更新的总数量，
// 说明剩下的都是多余的节点，直接卸载
unmount(oldChild[i]);
continue;
}
const oldChild = oldChildren[i];
let newIndex; // 可复用节点在newChildren中的索引
if(oldChild.key != null) {
// 找到了，将值赋给newIndex
newIndex = newIndexMap.get(oldChild.key);
}
if(!newIndex) {
// 没找到，直接卸载该节点
unmount(oldChild);
}else{
// 如果获取的子节点索引大于上一个节点索引，
// 则重新赋值,表示节点索引是递增的，不需要移动
if(newIndex >= maxNewIndex) {
newIndex = maxNewIndex;
}else {
//否则，说明节点需要进行移动
moved = true;
}
source[newIndex-s2] = i;
patch(oldChild, newChildren[newIndex], container);
patched++; // 更新的节点数量加一
}
}

接下来，我们来根据图来加深对这段代码的理解。

可以看到，根据代码所生成的source数组为[3,1,2]。

随后，通过最长递增子序列算法生成source的最长递增子序列，结果为[1,2],这里的1和2并不是数组中的值1和2，而是它们数组中对应的下标。

if(moved){
const seq = getSequence(source);
let j = seq - 1;
// 此循环相当于遍历source数组
for(let i = count-1;i >= 0;i--) {
const nextIndex = s2+i; // 获取元素的真实索引
const nextChild = newChildren[nextIndex];
// 获取元素添加的位置
const anchor = nextIndex+1 > newChildren.length ? newChildren[nextIndex+1].el : null;
if(source[i] === -1) {
// 说明该节点并未在oldChildren中，是全新的，需要创建
patch(null, nextChild, container,anchor);
}else {
if(j < 0 || i !== seq[j]) {
// 说明节点是需要移动的，对节点进行移动
insert(nextChild.el, container, anchor);
}else{
// 否则，说明节点不需要移动，j指针往前移
j--;
}
}
}
}

seq数组是根据source数组生成的最长递增子序列，而source数组的值是newChildren未处理节点在oldChildren中的索引,根据上述可以看出D-4是需要移动的，B-2、C-3是不需要移动的。

那么为什么要从后往前遍历呢？是为了保证当前节点的后续节点都处理完成了，避免未处理的节点对当前节点的影响。


总结


以上，就是我个人对diff算法的理解了，如果有讲述的不清楚、错误的地方欢迎大家评论批评。


Vue
前端
算法
0个评论
全部评论
点击登录，快来和大家讨论吧～
表情
图片
暂无评论
吃她喵的花椒
吃她喵的花椒
等级
内容推荐
更多
Django 是什么？
2
Django 的设计哲学有哪些？
3
第1章 LearnWise AI项目介绍
5
2026 年|AI 全栈时代，前端简历别再只写前端技术了~
3
资源 #前端# 求微信小程序的视频教程。最近正在学微信小程序，找的视频教程都不太好，跪求！！
22
作者分享
更多
Vue3快速实现文件上传OSS
4
Vue3快速实现文件上传OSS
23
双非本的我，上岸了！
66
好好好，之前在牛客看到一个专升本大佬快手oc后被卡学历，没想到这种事也发生在我身上了。 其实早就预料到了，但得到这个消息还是挺难受的，但没办法，专升本确实有点差吧。 只能怪自己高中没有好好学习？怪自己还不够强？不管什么原因，就这样了吧。 秋招到这里已经结束了，不管怎样还是收到了一个offer，也算是给自己这段时间学习的一个交代了吧。 春招再见吧，沉淀沉淀。 #求职# 经验
25
问下大家，hr面的时候要跟hr说自己的学历是专升本吗，之前简历上没有写专科经历，好怕自己被学历挂啊[得意]#求职# 提问
12
下载 APP