导语 | 开发者工作中,钻研代码逻辑常须要思考这个问题:数组变更后,具体变更了哪一些元素?变更的地位如何?本文作者陈碧松解析并覆写了针对数组变动的 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 与算法| 运维 | 工程师文化