各位小伙伴新年好啊～新的一年又要开始了，继续努力加油…
～
求关注，求收藏，求点赞，如果发现博主有写的不合理的地方请及时告知，谢谢~
前言
最近在看Vue2.6.14版本的源码，本系列博文主要以记录个人源码学习相关心得，希望我个人的学习心得能对正在学习的你有一点点帮助；本文主要记录了关于Diff算法相关的学习，明白了Diff算法大致的运行逻辑以及Virtual-DOM的来龙去脉； 注意的是本文不涉及Diff算法的源码，源码的分析将放在下一篇博文仔细分解…
耐心看完，一定有所收获；
Virtual-dom
在开始学习Diff算法相关内容前，必须先了解为什么会有Diff算法，以及Diff算法的存在是为了解决什么问题，这一切得从盘古…不对，得从MVVM开始说起;
MVC和MVVM
当今的前端领域里MVVM模式大行其势，使得原来的MVC开发模式几近绝迹，而在MVVM的开发模式里最出名的框架就是：React，Vue，Angular，之前我有个小伙伴问我：MVVM模式相比MVC究竟优势在哪里，网上搜来搜去就是在解释什么是MVVM，什么是MVC，也没看出个所以然来；
放在前端领域，MVC的含义差不多就是：M（Model）数据，V（View）代表视图，C（Controller）业务逻辑，有点像是这样
比如MVC中的JQuery举例：
- M代表数据（可以是后来请求来的，也可以是用户输入的）；
- V就是HTML对应的页面，包括对DOM的操作逻辑等等；
- C就是业务逻辑、交互逻辑，比如当用户输入完数据后，如何将数据处理并填充渲染到页面上去的过程，反之亦然；
在这个模式中C也就是Controller这一层其实非常薄弱，职能不强，View这一层倒反正非常厚，所有对DOM处理的操作都在这一层，一旦数据变动了就要去重新操作DOM，用设计模式的话说就是 耦合度非常高，如果业务有变动往往代码就要重写，并且还写不好…所以也就有了MVVM这种模式，那么这两种模式最大的区别是什么？
在回答这个问题之前，我先问个问题，DOM渲染页面之后，什么操作会对浏览器的性能产生较大影响？在我看来GUI 渲染线程中的重绘（Repaint）和回流（reflow）会对浏览器的性能产生较大影响，可能会有小伙伴不大清楚什么是重绘、什么是回流，这里简单说一下吧
- 重绘： 当一些元素需要更新属性，而这些属性的更新仅仅影响元素的外观，风格，而不会影响布局的，比如background-color。则就叫称为重绘。
- 回流： 当页面布局发生变化，比如我们修改一个元素的宽高，这时候DOM树结构随之也会发生变化，而DOM树与渲染树是紧密相连的，DOM树构建完，渲染树也会随之对页面进行再次渲染，这个过程就叫回流。
了解重绘和回流之后，那么我们就可以来说说为什么会有MVVM这种模式了，先说我的个人结论，我认为MVC和MVVM这两者本质上其实没多大区别，MVVM是脱胎于MVC的一种开发模式，传统MVC设计模式中针对DOM的操作几乎都是手动的，也就是需要开发人员去手动开发相关的控制代码，比如我们更新数据需要先获取到DOM，然后对DOM中的值进行覆盖，这也就导致了开发人员会频繁的去操作DOM，页面会频繁的在重绘和回流，MVVM这种模式就优化了这一步，它将Controller的职能完全放大，并且数据与页面DOM之间原则上不再有直接关联，通通交给Controller，包括对DOM的操作也都是框架自动去渲染，如下示例：
这么改的好处就是，开发人员可以专注于数据与业务的处理，C这一层就进行了一次进化，将DOM操作这些全部归纳到VM（ViewModel）里，VM的本质也会去操作DOM，但框架有最优秀的一批开发大佬写算法计算如何最优的去动态处理DOM，什么样的操作DOM消耗的性能最小，体验最好，那么 VM里面是如何做优化的呢，那就要说到这一小节的主角了，Virtual-dom；
Virtual-dom
Virtual-dom，又叫虚拟DOM，本质上就是用JS对象在描述DOM结构， 为什么要这么干，因为操作DOM就会重绘与回流，就会增加浏览器压力，但是操作DOM却非常简单，举一个简单的例子
// html代码
<div><a href="oliver.blog.csdn.net"></a></div>
换成虚拟DOM后，差不多就是类似于这种
{
tagName:"div",
children:[
{
tagName:"a",
href:"oliver.blog.csdn.net"
}
]
}
每次如果要渲染页面，只需要根据虚拟DOM树就可以去渲染了，因此，在MVVM中每一次变更数据后，对应的虚拟DOM树节点上的属性也会跟着变，最后根据这个树再统一去渲染页面，这样就可以大幅提高性能，可能有小伙伴还是不大明白，使用虚拟DOM后怎么就提高性能了，再举一个实际一点例子吧：
比如在一次操作中，我门需要更新20个DOM节点，浏览器在收到第一个DOM更新的请求后并不知道还有19次更新的操作，因此浏览器会马上执行流程，最终执行20次。例如，第一次计算完，紧接着下一个DOM更新请求，而在第二次DOM更新中这个节点的值就变了，这也就导致了第一次计算结果白白浪费了。即使计算机硬件一直在迭代更新，操作DOM的代价仍旧是昂贵的，频繁操作还是会出现页面卡顿，影响用户体验；
使用虚拟DOM后就会变成这样：
在一次操作中有20次更新DOM的动作，虚拟DOM不会立即操作DOM，而是将这20次更新的diff内容保存到本地一个对象中，最终将这个JS对象一次性更新到DOM树上，再进行后续操作，避免大量无谓的计算量。所以，虚拟DOM节点的好处很明显，页面的更新可以先全部反映在JS对象(虚拟DOM)上，操作内存中的JS对象的速度显然要更快，等更新完成后，再将最终的JS对象映射成真实的DOM，交由浏览器去绘制。
（注意：这里强调了是一次操作）
到这里，相信小伙伴应该能明白Virtual-dom是什么以及它的优点了吧，在Virtual-dom中如何比对新节点和老节点的算法，就是我们的主角Diff算法；
其他优势
其实Virtual-dom的优势远远不止性能上的提升，甚至正因为它的存在，使得JavaScript的跨端再次提升了一个档次，因为通过虚拟DOM我们完全可以识别到页面元素的组成以及样式
通过将传统的HTML，CSS，JavaScript转成Virtual-dom，而Virtual-dom就像是一种规范、规则化的标准数据，这种数据描述了整个页面上所有的元素属性，之后在对应的端上反译，达到跨端的目的；
小结
在MVVM的开发模式中引入了Virtual-dom这个概念，它用JS对象描述了整个DOM树，在更新DOM之前先统一由Virtual-dom进行处理，最终一次性更新到DOM上，这样便极大的提升了浏览器性能，这Diff算法便是Virtual-dom中比对新老节点的算法；
Diff算法
简介
总算介绍到Diff算法了，上文我们说到，Diff算法其实是用在Virtual-dom里的，在MVVM的开发模式中新增了一层抽象层用来模拟DOM结构，而Diff算法就是用来比对计算，比对新旧两个Virtual-dom里哪些节点发生了变化，仅针对这些发生变化的DOM节点做出更新即可；
Diff的策略
按层级diff比对
先说说Diff算法在MVVM框架中的比对策略吧，毕竟新旧两个Virtual-dom的比对不是瞎比对，看个图
在Vue或者说是React中都是遵循的同层级比对的策略，也就是说，旧Virtual-dom第一层蓝色只与新Virtual-dom的第一层做比对，旧Virtual-dom第二层紫色只与新Virtual-dom的第二层做比对，通过统计发现只有很少一部分情况会出现因为操作整个DOM结构都发生了更新，绝大多数情况都是DOM的层级不会变更；
按类型diff比对
这个怎么理解呢，举个例子，在Vue或者React中都有组件，diff算法在比对的时候如果发现组件的类型不一样了，那么这个组件包括其子组件都会被销毁，替换成新组件，而不会费时费力的去继续比对其子组件是否发生变化
比如这个例子中第一层的组件类型是三角形，它引用了两个子组件，经过变化后第一层的组件类型变成了五边形，但是子组件没有变化，这是diff不会去说因为只要第一层变化了，子组件都没有变因此只改变第一层的组件，保留第二次的三角，它会销毁整个蓝色三角以及其所有子组件，整体替换成五边形，并且新建了两个子组件；
执行流程分析
现在还不看源码，还是先弄明白Diff算法的执行过程，源码可以放到下一篇博文进行逐行分析，先看一下图例吧，图例里就是假设需要比对的新旧节点
先说一下含义：上面一排，代表的是旧的节点，下面一排，代表的是新的节点，大圆圈代表的Virtual-dom也就是虚拟DOM，小圆圈代表的是虚拟DOM对应的真实DOM；
当比对开始后，Diff算法会分别给这两个节点序列标注oldStartIdx、oldEndIdx、newStartIdx、newEndIdx的指针，标记完大致如下：
换句话说就是分别标记了起始位置和结束位置，标记结束就是正式开始比对逻辑；
第一步：比对oldStartIdx和newStartIdx
比对是会比对旧Virtual-dom的oldStartIdx和新Virtual-dom的newStartIdx的节点是否是同一个**，也是如下图的比对
结果发现旧Virtual-dom的oldStartIdx和新Virtual-dom的newStartIdx的节点是同一个，那么oldStartIdx和newStartIdx会都向后移动一位，变成如下所示**
继续比对第二个节点，也就是节点B和节点E，这是Diff发现节点B和节点E并不是同一个节点，那么此时就会去比对endIdx
第二步：比对oldEndIdx和newEndIdx
和startIdx一样，比对是会比对旧Virtual-dom的oldEndIdx和新Virtual-dom的newEndIdx的节点是否是同一个** ，**也是如下图的比对
比对结果发现旧Virtual-dom的oldEndIdx和新Virtual-dom的newEndIdx的节点是同一个，那么此时endIdx也会有startIdx一样往前移动1位
此时会进入第三个循环，继续比对旧Virtual-dom的oldStartIdx和新Virtual-dom的newStartIdx的节点是否是同一个，此时oldStartIdx和newStartIdx不是同一个，那么就继续去比对旧Virtual-dom的oldEndIdx和新Virtual-dom的newEndIdx，发现也不是同一个，那么此时会进行第三种比对，比对oldSatrtIdx和newEndIdx
第三步：比对oldSatrtIdx和newEndIdx
这一步比对也就是会比对oldSatrtIdx和newEndIdx，如图
比对结果发现oldSatrtIdx和newEndIdx是同一个节点，但是位置变化了，那么此时diff就会将B的位置进行转移重新排序，调整位置如下
并且，在转移的同时oldSatrtIdx和newEndIdx的位置也会分别移动一位，变成如下所示
之后继续进行新的一轮比对：
- 比对oldSatrtIdx和newStartIdx是否是同一个节点，发现不是，继续比对；
- 比对oldEndIdx和newEndIdx是否是同一个节点，发现不是，继续比对；
- 比对oldStartIdx和newEndIdx是否是同一个节点，发现不是，继续比对；
- 此时会出现一种新的比对方式，比对oldEndIdx和newStartIdx是否是同一个节点
第四步：比对oldEndIdx和newStartIdx
这一步就是比对oldEndIdx和newStartIdx是否是同一个节点，发现还不是，如果啊，如果发现oldEndIdx和newStartIdx是同一个节点，那么Diff会将这个节点调整位置，移动到oldStartIdx这个节点的前面；但是如图所示的例子中oldEndIdx和newStartIdx并不是同一个节点，那么此时会进行遍历操作；
第五步：遍历oldStart到oldEndIdx
变了操作大致就是：Diff会将oldStart到oldEndIdx之间所有的节点与newStartIdx节点进行逐一比对，看看是否有相同的，如果有相同的，调整位置，位置在oldStart的前面；
第六步：新创建节点
这一步是存在于没有相同节点是的操作，如图所示，当比对结束后，发现E节点不存在旧Virtual-dom中，那怎么办，此时diff会创建一个节点，节点的位置在oldStartIdx的位置之前
在完成这一步之后，newEndIdx会往前移动一位，变成这样
这时候，发现newEndIdx已经小于newStartIdx了，这就代表旧Virtual-dom与新Virtual-dom之间的比对已经结束了；
第七步：清理旧节点
这一步当中会将oldStartIdx与oldEndIdx之间所有节点删除，并将老的虚拟节点删除，变成这样
这样，新的结果就出现，比对结束；
key的处理
可能有小伙伴知道，在Vue中还有一个东西是官方强调的，那就是key，先看看官方是怎么说的：
为了给 Vue 一个提示，以便它能跟踪每个节点的身份，从而重用和重新排序现有元素，你需要为每项提供一个唯一 key attribute：
<div v-for="item in items" v-bind:key="item.id">
<!-- 内容 -->
</div>
建议尽可能在使用 v-for 时提供 key attribute，除非遍历输出的 DOM 内容非常简单，或者是刻意依赖默认行为以获取性能上的提升。
原文差不多是这样，那么这个key在执行流程中的作用是什么呢？继续看图吧
假设节点C与节点D之间存在一个节点E，当我们四步比对都已经比对结束了之后，要进行遍历了，此时在遍历前，diff会先到节点的map中去查询，这个节点之前是否存在过，怎么说呢，就是Vue会给每一个存在的节点都做一个标记，换存起来，大概是这个样子的
var map = {
"key-A":0,
"key-E":3
}
在遍历前，去查询这个节点是否存在，如果发现存在，那么就可以直接获取到节点的位置，就不再需要对oldStartIdx与oldEndIdx进行遍历了，这一步的性能就大大提升，可以直接将E这个节点移动到oldStartIdx的前面去了
这下子明白了吧，如果不设置Key，那么算法的复杂度最坏的情况会直接比设置了Key的复杂度大上一倍，所以强烈建议，设置Key；
小结
本小节主要讲述了什么是Diff算法，并且Diff算法的流程到底是怎么一个流程，另外在Vue中key的作用是什么，设置了Key之后的优化到底有多大；