diff算法

diff 算法是一种通过同层的树节点进行比较的高效算法。

其有两个特点：

比较只会在同层级进行, 不会跨层级比较
在diff比较的过程中，循环从两边向中间比较

diff 算法在很多场景下都有应用，在 vue 中，作用于虚拟 dom 渲染成真实 dom 的新旧 VNode 节点比较。

比较方式

传统diff算法

处理方案: 循环递归每一个节点

算法复杂度能达到O(n^2) ，查找完差异后还需计算最小转换方式，最终达到的算法复杂度是O(n^3)。

将两颗树中所有的节点一一对比需要O(n²)的复杂度，在对比过程中发现旧节点在新的树中未找到，那么就需要把旧节点删除，删除一棵树的一个节点(找到一个合适的节点放到被删除的位置)的时间复杂度为O(n),同理添加新节点的复杂度也是O(n),合起来diff两个树的复杂度就是O(n³)

优化的diff算法

diff整体策略为：深度优先，同层比较

比较只会在同层级进行, 不会跨层级比较
比较的过程中，循环从两边向中间收拢

时间复杂度为O(n)

原理

当数据发生改变时，set方法会调用Dep.notify通知所有订阅者Watcher，订阅者就会调用patch给真实的DOM打补丁，更新相应的视图。

patch

patch函数前两个参数位为oldVnode 和 Vnode ，分别代表新的节点和之前的旧节点，主要做了四个判断：

没有新节点，直接触发旧节点的destory钩子
没有旧节点，说明是页面刚开始初始化的时候，此时，根本不需要比较了，直接全是新建，所以只调用 createElm
旧节点和新节点自身一样，通过 sameVnode 判断节点是否一样，一样时，直接调用 patchVnode去处理这两个节点
旧节点和新节点自身不一样，当两个节点不一样的时候，直接创建新节点，删除旧节点

patchVnode

patchVnode用来比较两个虚拟节点的子节点并更新其子节点对应的真实Dom节点。

patchVnode主要做了几个判断：

新节点是否是文本节点，如果是，则直接更新dom的文本内容为新节点的文本内容
新节点和旧节点如果都有子节点，则处理比较更新子节点
只有新节点有子节点，旧节点没有，那么不用比较了，所有节点都是全新的，所以直接全部新建就好了，新建是指创建出所有新DOM，并且添加进父节点
只有旧节点有子节点而新节点没有，说明更新后的页面，旧节点全部都不见了，那么要做的，就是把所有的旧节点删除，也就是直接把DOM 删除

子节点不完全一致，则调用updateChildren

updateChildren

updateChildren是vue diff的核心。

updateChildren主要做了以下操作：

设置新旧VNode的头尾指针
新旧头尾指针进行比较，循环向中间靠拢，根据情况调用patchVnode进行patch重复流程、调用createElem创建一个新节点，从哈希表寻找 key一致的VNode 节点再分情况操作

过程可以概括为：oldCh和newCh各有两个头尾的变量StartIdx和EndIdx，它们的2个变量相互比较，一共有4种比较方式。如果4种比较都没匹配，如果设置了key，就会用key进行比较，在比较的过程中，变量会往中间靠，一旦StartIdx>EndIdx表明oldCh和newCh至少有一个已经遍历完了，就会结束比较。

key

当我们在使用v-for时，需要给单元加上key

1
2
3

<ul>
    <li v-for="item in items" :key="item.id">...</li>
</ul>

用+new Date()生成的时间戳作为key，手动强制触发重新渲染

1	<Comp :key="+new Date()" />

key是给每一个vnode的唯一id，也是diff的一种优化策略，可以根据key，更准确，更快的找到对应的vnode节点。

vue3的diff算法

Vue3.x借鉴了 ivi算法和 inferno算法。在创建VNode时就确定其类型，以及在mount/patch的过程中采用位运算来判断一个VNode的类型，在这个基础之上再配合核心的Diff算法，使得性能上较Vue2.x有了提升。

该算法中还运用了动态规划的思想求解最长递归子序列。

总结

由于diff算法对比的是虚拟Dom，而虚拟Dom是呈树状的，所以我们可以发现，diff算法中充满了递归。总结起来，其实diff算法就是一个 patch —> patchVnode —> updateChildren —> patchVnode —> updateChildren —> patchVnode这样的一个循环递归的过程。