一、Diff 概念
Vue 基于虚拟 DOM 做更新。diff 算法的核心就是比较两个虚拟节点的差异，返回一个 patch 对象，这个对象的作用就是存储两个节点不同的地方，最后用 patch 里记录的信息进行更新真实DOM。
diff 算法的在很多场景下都有应用，在Vue中作用于虚拟 DOM 渲染成真实 DOM 的新旧 VNode 节点比较。
1、diff 算法的特点：
① 比较只会在同层级进行, 不会跨层级比较；
采用的是同级比较的方式。如图，父级和父级比较，儿子和儿子比较，孙子和孙子比较，不考虑跨级比较的情况（因为在实际场景上极少用到，且可以减少比对次数，最大化的提高比对性能，所以不考虑跨级比较的情况）。
② 在 diff 比较的过程中，循环从两边向中间比较；
内部采用深度递归的方式 + 双指针的方式进行比较，不管新旧节点都有首尾两个元素。
二、Diff 比较总结
如果两个节点不相同的话，那么直接删除老节点，然后创建新节点。
如果是相同节点，那么会比较两个节点的差异，包括节点的 key 属性、tag 标签、事件等等；
如果两个父节点相同的话，那么就比较儿子节点。
比较子节点有以下4种情况：
- 如果都是文本节点且不相等，直接将
el文本节点更新为新节点的文本内容即可；- 如果老的有儿子，新的没儿子，直接删除老的儿子节点；
- 如果老的没儿子，新的有儿子，那么就创造新的儿子节点，直接插入父节点中；
- 如果两者都有子节点，则执行
updateChildren函数比较子节点。
其中，diff 算法的核心是两个都有儿子的情况，这里采用的是双指针和优化比较的策略，优先头头、尾尾、头尾、尾头比较，优化了我们经常使用的 DOM 操作。那若是乱序的情况下，这里的逻辑就是使用节点 key 创建了映射表，然后使用对比查找的方式，根据不同情况执行复用、删除、新增等操作。
在这期间循环向中间靠拢，根据情况调用
patchVnode进行patch重复流程、调用createElem创建一个新节点，从哈希表寻找key一致的VNode节点再分情况操作。
三、Diff 比较流程
1、父节点的比较
① 先比较两个虚拟节点是否是相同节点【key、tag】
主要是比较两个节点的 key 属性和 tag 标签，有任何一个不一样就说明这两个元素不是相同元素
② 如果是相同节点，下一步是比较属性并复用老节点 (将老的虚拟 DOM 复用给新的虚拟节点 DOM)
如果不一样，就会删除老节点，创建新节点
③ 如果两个父节点相同的话，那么就比较儿子节点，需要以下几种情况：
- 老的没儿子，新的有儿子。
那么就创造新的儿子节点，直接插入元素中
- 老的有儿子，新的没儿子。
直接删除老的儿子节点
- 老的儿子是文本，新的儿子也是文本。
如果不一致，直接更新文本节点即可
- 老的儿子是一个列表，新的儿子也是一个列表， updateChildren方法
两个列表的比较，也是diff算法的核心所在。一个数组跟另一个数组的比对，有差异就更新。
2、两个列表的比较：优化比较
常见DOM操作：追加、删除、倒序、反序
对应的优化比较策略：头头、尾尾、头尾、尾头
优化方案：
整个优化采用双指针的方式，也就是在新老节点的头部和尾部分别插入2个指针，在头部和尾部都有一个指针。在比对的过程中，采用的是有一方头尾指针重合的话，就意味着节点遍历结束。这个时候就会终止 diff 算法。
① 头和头节点比较【头头】
首先，比较A和A是否相同，相同则指针向后移动。 B和B，C和C，这时候指针已经越界，diff 算法结束。将 D 直接插入到节点中就可以了。
向尾部插入新节点：
替换尾部不相同的节点：
② 尾和尾节点比较【尾尾】
指针从尾部开始比较新老节点。
向头部插入新节点：
替换头部不相同的节点：
③ 头和尾节点比较【头尾】
先比较头和头是否相同，再比较尾和尾是否相同。都不相同的时候，那就是用头部比较。
将老节点的头部跟新节点的尾部比较，相同则将老节点移动到后面去。
后面就是按照头头比较、尾尾比较、头尾比较这种顺序走。
④ 尾和头节点比较【尾头】
先比较头和头是否相同，再比较尾和尾是否相同。都不相同的时候，那就是用头尾比较，再不相同就是尾头比较。
将老节点的尾部跟新节点的头部比较，相同则将老节点移动到前面去。
头指针比对成功，头指针需要往后移动一格。尾指针比对成功，尾指针需要往前移动一格。
⑤ 倒序
老规矩，递归的使用以下比对策略：先比较头头、尾尾，再比较头尾、尾头
固定一个节点，最后把每个节点进行移动来进行复用。并没有进行重新创建操作
3、无法优化比较的情况下，采用对比查找复用的方式：
比对查找进行复用：拿老的节点根据 key 做映射表，然后拿新的节点 key 去映射表中查找。若匹配则比较差异、复用并将其移动到前面去，移走的位置赋值为undefined，不匹配则创建元素并插入。老的节点为空的话，那就自动找下一个节点元素。
乱序的情况下： 通过 key 进行复用，能复用就复用，否则就删除或者创建
先看下是否符合头头、尾尾、头尾、尾头原则。
都不符合的话，那就采用比对查找的方式，那新节点去老节点中查找看是否存在，存在则将节点插到前面去，原来位置置空（位置保留是为了不改变索引位置）；不存在则创建，最后把前后指针指向的位置（也就是多余的老节点）删除就行了。
四、Vue3 中采用最长递增子序列来实现 diff 优化
例如这个例子中，A和Q不需要移动，直接将E插入中间即可。
