导语 | 开发者工作中，钻研代码逻辑常须要思考这个问题：数组变更后，具体变更了哪一些元素？变更的地位如何？本文作者陈碧松解析并覆写了针对数组变动的diff算法逻辑。心愿本文对你有帮忙。

diff办法的运行规定和前提办法

为了理解diff办法的运行规定和前提办法，首先咱们通过几个图疾速区别虚构node进行深度优先和同级比照。

深度优先:

同级比照：

如下面图所示，每次vnode都是执行同级比照。（对应dom同一个父元素）

代码逻辑如下图：

第二，简略判断：sameVnode函数用来进行判断是否是同一个vnode元素。源代码如下：

如图所示：

这里有两个重要元素：key : 开发者定义的“:key”；sel :  元素tagName+元素id+元素class。

sel的定义源码如下：

vNode构建函数：

第三是构建索引。

逻辑如图：

如何解决元素

尽量不新增/删除dom。如图下所示:

如果是雷同vnode，源码如下：

开始比拟

首先会进行工夫复杂度O(n)的while循环，循环条件为“遍历旧节点数组&&遍历新节点数组，谁先遍历完循环就完结”。源码如下图:

在每次的循环过程中，会有两大类判断办法：

1）首尾比拟&首尾序号

逻辑：如图上所示。首先在循环遍历前标记好新，旧节点数组的开始地位和完结地位的序号：oldStartIdx、oldEndIdx、newStartIdx、newEndIdx；其次在循环遍历的过程中采纳“首首比拟，尾尾比拟，首尾比拟"。

源码如下：

如果数据为图上所示，那么依据首尾比拟办法会有如下图所示后果，最终全副执行了更新操作：

2）索引比拟

最坏状况,这里的工夫复杂度也是O(n)，即整个算法复杂度O(n)+O(n)。每次遍历的过程中可能存在"新数组节点新增/旧数组节点删除"，那么前后比照就满足不了条件。这里逻辑会进入索引比拟：比方这种状况：

那么循环中会执行一遍，创立旧数组的索引对象。从创立到比拟的整个逻辑图如下：

这里的源码如下:

  • 当旧节点不存在新增的节点时,进行以后oldStartIdx地位的增加

源码如下:

  • 当旧数组存在节点，那么进行地位挪动

源码：

3）当节点遍历完之后

会存在两种状况：新数组曾经遍历完，但旧数组没有遍历实现；旧数组遍历实现，但新数组没有遍历实现。故源代码的判断如下:

  • 旧数组没有循环实现

旧数组没有循环实现的成果如下图所示：

这里留神一个点，咱们每次的节点更新会挪动序号，即便被删除的节点不在一块最终也会被首尾比拟算法“摞在一块”（oldStartIdx~oldEndIdx）。上图所示更加显著。源码在这里就进行批量删除：

  • 新数组没有循环实现

成果如下图所示:

整体来说，有几个关键点：简略比照；创立旧数组的索引表；首位比照&首尾索引&vnode地位挪动；索引增加/位移；残余局部批量解决增加/删除。

通过前后比照&索引的过滤后，只会存在新.开端节点!==旧节点及之前的间断的新节点(!==旧节点)，所以这里也被“摞在一块”，即 （newStartIdx~newEndIdx）。源码如下。这样，整个diff的比照算法就曾经走完了。外围就是：前后比照+索引。

vue3.0对于diff比拟前的优化

vue3.0针对“无脑”patchVnode进行了过滤--动态类型Vnode老版的源码:

这里，咱们再反复下vue2.x系列的比照更新逻辑:

新版的vue3.0减少了动态类型Vnode。如果是动态类型的vnode，间接跳过更新，批改新节点援用即可。

comment类型目前翻到它的源码也只是更改援用，源码作者加上了一行正文。

补充一下，flagment碎片类型为新增的vnode类型，即：

vue3.0的过滤判断源码如下:

数组比拟的利用

因为咱们想监听数组的变动，参考了diff算法覆写相似的逻辑，用来在update,add,dels时，代码层面获取操作的具体节点明细（新旧节点的地位，内容）。心愿本文对你有帮忙。

你可能感兴趣的腾讯工程师作品

| 优雅应答故障：QQ音乐怎么做高可用架构体系？

| 最全Go select底层原理，一文学透高频用法

| 十亿人都在用的衰弱码，运维体系是怎么设计的

|详解全网最快Go泛型跳表【内附源码】

技术盲盒：前端｜后端｜AI与算法｜运维｜工程师文化