快人一步掌握vue源码解读，搞定diff算法！（超详细）
导语 | 最近碰到部分业务场景，代码逻辑需要了解“数组变更后，具体变更了哪一些元素，以及变更的位置…”。于是仔细研究并覆写了一遍针对数组变化的diff算法，在这里做下diff算法的逻辑分享&&源码解读。
一、介绍前的准备工作
我们先了解diff方法的运行规则和前提方法。
（一）虚拟node进行深度优先&&同级对比
深度优先:
同级对比:
如上图所示：
每次vnode都是执行同级对比（对应dom同一个父元素）
代码逻辑如下图：
（二）简单判断
`sameVnode`函数用来进行判断是否是同一个vnode元素。
源代码：
如图所示：
这里有两个重要元素：
`key` : 开发者定义的:“key”；
`sel `: 元素tagName+元素id+元素class。
sel的定义源码如下：
vNode构建函数：
（三）构建索引
逻辑如图：
二、如何处理元素
尽量不新增/删除dom，如下图所示:
如果是相同vnode，源码如下：
三、开始比较
首先会进行时间复杂度O(n)的while循环，循环条件为“遍历旧节点数组&&遍历新节点数组，谁先遍历完循环就结束”。
源码如下图:
在每次的循环过程中，会有两大类判断方法：
首尾比较&&首尾序号
逻辑：如图上所示，首先在循环遍历前标记好新，旧节点数组的开始位置和结束位置的序：oldStartIdx、oldEndIdx、newStartIdx、newEndIdx；其次在循环遍历的过程中采用“首首比较，尾尾比较，首尾比较”。
源码如下：
如果数据为图上所示，那么根据首尾比较方法会有如下图所示结果，最终全部执行了更新操作：
索引比较--最坏情况，这里的时间复杂度也是O(n)，即整个算法复杂度O(n)+O(n)
每次遍历的过程中可能存在“新数组节点新增/旧数组节点删除”，那么前后对比就满足不了条件。这里逻辑会进入索引比较；
比如这种情况：
那么，循环中会执行一遍创建旧数组的索引对象。
那么从创建到比较的整个逻辑图如下：
这里的源码如下:
当旧节点不存在新增的节点时，进行当前oldStartIdx位置的添加:
源码如下:
当旧数组存在节点，那么进行位置移动:
源码：
当节点遍历完之后
会存在两种情况，“新数组已经遍历完，但旧数组没有遍历完成” 和 “旧数组遍历完成，但新数组没有遍历完成”。
故源代码的判断如下:
旧数组没有循环完成：
效果如下图所示：
这里注意一个点，我们每次的节点更新会移动序号，即使被删除的节点不在一块最终也会被首尾比较算法 “摞在一块”，即（oldStartIdx~oldEndIdx）。上图所示更加明显一些。
源码在这里就进行批量删除：
新数组没有循环完成:
效果如下图所示:
经过前后对比&&索引的过滤后，只会存在新末尾节点!==旧节点及之前的连续的新节点(!==旧节点)；所以这里也“摞在一块”，即（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时代码层面获取操作的具体节点明细（新旧节点的位置，内容）。
git地址：http://git.code.oa.com/winkchen/diffArr.git
同时tnpm包：tnpmi@tencent/arraydiff
tnpm地址：
http://mirrors.tencent.com/#/private/npm/detail?repo_id=537&project_name=%40tencent%2Farraydiff
作者简介
陈碧松（winkchen）
腾讯web前端开发工程师
腾讯web前端开发工程师。目前负责腾讯IEG智慧发行的前端开发工作，有丰富的游戏内活动开发，游戏内视频直播开发经验。
推荐阅读
事务消息大揭秘！RocketMQ、Kafka、Pulsar全方位对比
“Docker VS Kubernetes”是共生还是相爱相杀？
