关于vue.js:diff算法核心原理精讲

大家好，我是爱水文的苏学生，一名从业 5 年 + 的前端爱好者，致力于用最艰深的文字分享前端常识的酸菜鱼

手撕 vue 响应式
一文搞懂 vue 编译器原理与实现
手写 vue 响应式之 Object 类型的解决
typescript 中如何优雅的扩大第三方库的类型
据说你还在应用原生 localStorage？
npm 包插件化方案设计与实现

不论是 vue2 中实现的双端比拟算法，还是 vue3 中优化过的疾速比拟算法，它们的外围痛点都是相通的：存在哪些必须要解决的问题

咱们只有通晓了实现 diff 要解决哪些问题，能力在实现过程中去一点点优化

这世界就是一个因果轮回，没有平白无故的爱，你可能喜爱他有钱，也可能心愿他能给你工作中带来帮忙，又或者，他总是能逗你笑，反正，总要图点什么

因为操作虚构 dom 带来的性能损耗肯定是大于间接操作实在 dom 的，所以才要尽可能的缩小虚构 dom 操作的次数以达到性能更优

由此 diff 算法诞生

当须要对一组节点进行更新时，为了以最小的性能开销实现更新操作，须要对新旧两组节点进行比拟，用于比拟的算法就是 diff 算法

假如有如下两组新旧节点

const olds = {
    type:"div",
    el:"DOM 援用",
    children:[{type:"p",children:"a"},
        {type:"p",children:"b"},
        {type:"p",children:"c"},
    ]
}
const news = {
    type:"div",
    el:"DOM 援用",
    children:[{type:"p",children:"d"},
        {type:"p",children:"e"},
        {type:"p",children:"f"},
    ]
}

no diff

在无 diff 的状况下，因为框架只能追溯到文件级别，咱们不得不卸载全副的旧节点，而后后从新去挂载全副的新节点，伪代码如下

function patchChildren(n1,n2){if(n1 && Array.isArray(n1.children)){for(let i=0;i<n1.children.length;i++){n1.el.removeChild(n1.children[i])
        }
    }
    if(n2 && Array.isArray(n2.children)){for(let i=0;i<n2.children.length;i++){n2.el.removeChild(n2.children[i])
        }
    }
}

能够看到，咱们遍历新旧节点别离进行 for 循环，一共进行了 3 次卸载操作和三次增加操作，3+ 3 实践上就是 6 次

diff

先别急，咱们先剖析下示例节点的特点：

1- 更新前后的标签元素不变，都是 p 标签

2- 只有 p 标签的子节点在发生变化

能够看出，只有 p 标签的子节点不诚实，始终在变，所以咱们要做的是找到哪些不安分的点替换掉，老实人自当留下来好好为公司发明价值才对，为此，只须要进行三次 dom 操作就够了，我掐指一算，6 除以 3，好家伙，性能间接翻倍

伪代码如下，咱们新增了 patch 函数来对新旧子节点进行比对，该函数会仅在发现不同节点时才会执行 dom 操作

function patchChildren(n1, n2) {if (n2 && Array.isArray(n2.children)) {const oChildrens = n1.children || [];
    const nChildrens = n2.children;
    for (let i = 0; i < nChildrens.length; i++) {patch(oChildrens[i], nChildrens[i]);
    }
  }
}

在比照章节中，咱们通过一个可能算得上比拟糟粕的例子阐明了 diff 能够更快，但忘了规定一个前置条件了：新旧节点的数量变动雷同。

这这这 ……，有点粗率了

在理论状况中，新旧节点的数量变动好似脱缰的野马，数量难料：

1- 新节点的 children 数量 = 旧节点的 children 数量

2- 新节点的 children 数量 > 旧节点的 children 数量

3- 新节点的 children 数量 < 旧节点的 children 数量

咱们针对上述情况来进行探讨

当 = 的状况下，它总是能兼顾到新旧两组的每一个子节点，此时咱们抉择谁都无所谓
当 > 或 < 的状况下：

1- 如果抉择较小的节点汇合，则剩下的节点不是新增就是须要执行卸载的节点

function patchChildren(n1, n2) {
  const oLen = n1.children.length;
  const nLen = n2.children.length;
  const len = Math.min(oLen, nLen);
  for (let i = 0; i < len; i++) {
    // 执行比对更新
    path(n1.children[i],n2.children[i])
  }
  if(oLen < nLen){// 执行挂载} else if(oLen > nLen){// 执行卸载}
}

2- 如果抉择较大的节点汇合，则剩下的节点不是新增就是须要执行卸载的节点。看如下伪代码，咱们为了 patch 函数能失常工作，额定减少了守卫条件，同时为了防止不必要的 for 循环，又额定减少了 break 代码

function patchChildren(n1, n2) {
  const oLen = n1.children.length;
  const nLen = n2.children.length;
  const len = Math.max(oLen, nLen);
  for (let i = 0; i < len; i++) {if(n1.children[i] && n2.children[i]){
        // 执行比对更新
        path(n1.children[i],n2.children[i])
    }
    if(i >= Max.min(oLen,nLen)) break
  }
  if(oLen < nLen){// 执行挂载} else if(oLen > nLen){// 执行卸载}
}

咱们可是连正文都懒得写的程序员啊，当然要选具备更精炼代码实现的更小节点汇合咯

type 标记的局限性

那个 ……，先道个歉，因为我又又又遗记规定一个前提了，那就是咱们 patch 函数比对判断复用的前提是 type 字段雷同

好了，当初，咱们通过 type 字段来标记节点，它很好的帮忙咱们辨认了节点身份。但问题又来了，我要是不给你玩 36 变，我就是天生活跃好动，没事爱到处逛逛呢？

// 旧节点列表
[{type:"p",children:"a"},
 {type:"div",children:"b"},
 {type:"span",children:"c"},
]
// 新节点列表
[{type:"span",children:"2"},
 {type:"p",children:"1"},
 {type:"div",children:"3"},
]

好了，鉴于你这个人技术真的很强，又无可替代的，我苏某人忍了！！！

可是因为每次比对更新传入的是同一地位的节点，并且判断复用的条件是 n1.type === n2.type，因而，每次都会被判断为不同节点从而从新创建，那应该怎么防止误判呢？

key 的作用

为了防止误判，我想到了身份证，它让咱们在整个中国都是最不同凡响举世无双的存在（ps：实际上平庸的一 p），于是咱们为每一个节点减少具备唯一性的 key 值

// 旧节点列表
[{type:"p",children:"a",key:"1"},
 {type:"div",children:"b",key:"2"},
 {type:"span",children:"c",key:"3"},
]
// 新节点列表
[{type:"span",children:"2",key:"3"},
 {type:"p",children:"1",key:"1"},
 {type:"div",children:"3",key:"2"},
]

于是加钱哥他来了

我管你是谁，只有在每次比对时在长列表中能找到 key 值，我就认为你是可复用的节点（那个活跃好动，没事瞎逛的人），伪代码如下

function patchChildren(n1, n2) {
  let runArr = n1.children
  let restArr = n2.children
  const len = Math.min(runArr.length, restArr.length);
  if(restArr.length === len){
      const temp = runArr
      runArr = restArr
      restArr = runArr
  }
  for (let i = 0; i < len; i++) {const exist = restArr.find(v=>v.key === runArr[i].key)
     if(exist){
         // 执行比对更新
         path(runArr[i],exist)
     }  
  }
  if(runArr.length < nLen){// 执行挂载} else if(restArr > nLen){// 执行卸载}
}

通过身份标记 key，咱们胜利找到了可复用的节点并如愿通过 patch 函数对其子节点进行了更新，譬如：将元素标签为 p 的子节点由 a 更新为 3

但问题又又又来了

因为咱们间接复用了节点，只更新了它的子节点，页面中的 dom 的程序还是旧的，即 p 标签依然在子元素列表的第一个地位

<p>3</p>
...div...
...span...

咱们心愿将它扭转到第二个地位上

...div...
<p>3</p>
...span...

如何断定节点产生挪动

咱们先逆向思考一波来寻找法则，如果节点地位不变则可复用的节点肯定在新旧节点列表中的地位是一一对应的

那反过来说，是不是当节点地位发生变化时，可复用的节点肯定在新旧节点列表中的地位对不上了呢：

以前文的 p 标签为例，产生扭转前，其地位索引为 0，产生扭转后，其地位索引为 1，0!==1

以如下的 p 标签为例，产生扭转前，其地位索引为 2，产生扭转后，其地位索引为 0，2!==0

// 旧的
...div...
...span...
<p>3</p>
// 新的
<p>3</p>
...div...
...span...

代码示意

咱们在明确节点可复用后，即 news[i].key === olds[j].key 后，再通过比对索引地位的大小关系来判断是否产生了地位迁徙，这里 lastIndex 是一个动静更新的值，咱们用它来记录以后遇到的最大索引地位

function checkPosChanged(news,olds){
    let lastIndex = 0
    for(let i=0;i<news.length;i++){for(let j=0;j<olds.length;j++){if(news[i].key === olds[j].key){if(j < lastIndex){// 节点产生了挪动}else{lastIndex = j}
            }
        }
    }
}

而后咱们用如下示例再手动演示一遍 checkPosChanged 的执行流程：

// 旧
<p></p>
<span></span>
<div></div>
// 新
<div></div>
<span></span>
<p></p>

第一次，咱们取一个参照物，后边都基于此做绝对地位计算，因而把初始的 lastIndex 设置为 0，从而在运行时进入 else 分支获取参照地位；

第二次，已知条件：1-span 节点在新列表中的索引地位 > div 节点在新列表中的索引地位；2-div 节点的在旧列表中的索引地位为 2 。仍是取新列表的 span 节点，并在旧列表中找到的索引地位为 1\
此时 1 <2，即span 节点在旧列表中的索引地位 < div 节点在旧列表中的索引地位，此时地位关系对不上，阐明地位产生变动；

第三次，已知条件：1- p 节点在新列表中的索引地位 > span 节点在新列表中的索引地位；2-span 节点的在旧列表中的索引地位为 1 。仍是取新列表的 p 节点，并在旧列表中找到的索引地位为 0\
此时 0 <1，即 p 节点在旧列表中的索引地位 < p 节点在旧列表中的索引地位，此时地位关系对不上，阐明地位产生变动；

当初，咱们曾经把握了更新节点的外围条件，接下来就是当条件满足时去执行更新逻辑，不过在此之前，我想先把一些公共的辅助函数定义一下，目前它大略长这样:

const helpers = {insert(){}}

如上，我用一个对象来承载更新操作，但目前它什么都做不了。那该如何去实现它，且容我想一哈 ……

因为操作的是实在的 DOM，所以必然绕不开 insertBefore，既然是 insertBefore，那参数就明了了

const helpers = {insert(parent,el,sibling=null){parent.insertBefore(el,sibling)
    }
}

所以，就只须要在断定到须要挪动时喊它来解决一下就 ok 了

function patchChildren(n1,n2,continer){
    const oldChildren = n1.children
    const newChildren = n2.children
    let lastIndex = 0
    for(let i=0;i<newChildren.length;i++){const v = newChildren[i]
        let j = 0
        for(j;j<oldChildren.length;j++){const k = oldChildren[j]
            if(v.key === k.key){
                // 对以后节点进行比对更新
                ...
                // 判断节点变动
                if(j<lastIndex){const pre = v[i-1]
                    if(pre){
                        const anchor = pre.el.nextSibling
                        helpers.insert(k.el,continer,anchor)
                    }
                }else{lastIndex = j}
            }
        }
    }
}

因为 for 循环的遍历程序正好代表着新节点在 DOM 中的程序，即 v[i-1]标识以后节点的前一个兄弟节点。而 lastIndex = j 恰好就是前一个兄弟节点在旧列表中的地位，因而，咱们曾经确定了以后节点和前一个兄弟节点在新列表中的对应地位

此时只须要推断出以后节点和前一个兄弟节点在旧列表中的地位关系与新列表不等即可证实挪动，联合前文的剖析，即 j < lastIndex 时

要想解决新增，有两个迫切需要解决的点：

1- 如何判断是新增节点

2- 如何挂载到正确的地位

为了避免你懒得向上翻，我把前一大节的代码拷贝一份

function patchChildren(n1,n2,continer){
    const oldChildren = n1.children
    const newChildren = n2.children
    let lastIndex = 0
    for(let i=0;i<newChildren.length;i++){const v = newChildren[i]
        let j = 0
        for(j;j<oldChildren.length;j++){const k = oldChildren[j]
            if(v.key === k.key){...}
        }
    }
}

如上，咱们从新节点中顺次取值并判断 v.key === k.key 时进行复用，那反过来说，v.key !== k.key 时，不就阐明是新增嘛！！！

好！当初咱们来剖析第二个点，即如何挂载到正确的地位？这也不难，咱们在前文中其实始终在强调一个概念，即：绝对地位，所以，咱们只须要将其挂载到前一个节点的后边就 ok 啦

解决了以上两个关键点，代码就好写了

function patchChildren(n1,n2,continer){
    const oldChildren = n1.children
    const newChildren = n2.children
    let lastIndex = 0
    for(let i=0;i<newChildren.length;i++){const v = newChildren[i]
        let j = 0
        let isHave = false
        for(j;j<oldChildren.length;j++){const k = oldChildren[j]
            if(v.key === k.key){
                isHave = true
                ...
                break
            }
        }
        if(!isHave){const pre = v[i-1]
            let anchor = null
            if(pre){anchor = pre.nextSibling}else{anchor = continer.firstChild}
        }
        // 执行 path 进行挂载
    }
}

如上，咱们减少了变量 isHave 来标记是否找到了可复用的节点，为 false 时执行新增，默认咱们把容器（列表的父节点）中的第一个 DOM 节点作为参考地位

终于要翻过 diff 算法这座大山啦，不过人生嘛，哪有一帆风顺的，所以我打算先为本人打个 call

我目前正在开发一个名为 unplugin-router 的我的项目, 它是一个约定式路由生成的库，目前已反对在 webpack 和 vite 中应用，也已实现对 vue-router3.x 和 vue-router4.x 的反对，且曾经接入到公司的一个 vite3+vue3 的我的项目中

不过受限于工作工夫进度比较慢，在此寻找气味相投的敌人一起来实现这件事，后续打算对性能做进一步的欠缺，比方反对 @hmr 注解、反对权限路由等，也有对 react 路由和 svelte 路由的反对打算，以及除了 webpack 和 vite 这两个之外的构建工具的反对，还有单元测试的编写 …..

好了，咱们书接上文！！！

要想搞清楚删除，其实咱们只须要明确以后曾经做好的性能是什么样的就能够了。在现有逻辑中，如果不出意外，代码执行完结后，除了须要删除的，新旧节点肯定是雷同的，如果想明确了这一点，那代码应该就信手拈来了吧

function patchChildren(n1,n2,continer){
    const oldChildren = n1.children
    const newChildren = n2.children
    let lastIndex = 0
    for(let i=0;i<newChildren.length;i++){...}
    for(let i=0;i<oldChildren.length;i++){const v = oldChildren[i]
        const has = newChildren.find(c=>v.key === v.key)
        if(!has){// 执行卸载}
    }
}

如上，咱们新增了 for 循环拿旧列表的节点到新列表中匹配，匹配不到就阐明是须要进行删除的节点

关于vue.js:diff算法核心原理精讲

github 与好文

前言

为什么要有 diff

什么是 diff

比照

外围原理解说

确认遍历主体

用于身份标记的 key 值

解决挪动节点

断定节点产生挪动

更新虚构节点到理论的 dom 节点

解决新增节点

解决删除节点