1. 为什么要用Diff算法

由于在浏览器中操作DOM的代价是非常“昂贵”的，所以才在Vue引入了Virtual DOM，Virtual DOM是对真实DOM的一种抽象描述，不懂的朋友可以自行查阅相关资料。

1.1为什么需要VD

VD 最大的特点是将页面的状态抽象为 JS 对象的形式，配合不同的渲染工具，使跨平台渲染成为可能。如 React 就借助 VD 实现了服务端渲染、浏览器渲染和移动端渲染等功能。

此外，在进行页面更新的时候，借助VD，DOM 元素的改变可以在内存中进行比较，再结合框架的事务机制将多次比较的结果合并后一次性更新到页面，从而有效地减少页面渲染的次数，提高渲染效率。我们先来看下页面的更新一般会经过几个阶段。

从上面的例子中，可以看出页面的呈现会分以下3个阶段：

JS计算

生成渲染树

绘制页面

这个例子里面，JS计算用了691毫秒，生成渲染树578毫秒，绘制73毫秒。如果能有效的减少生成渲染树和绘制所花的时间，更新页面的效率也会随之提高。

通过VD的比较，我们可以将多个操作合并成一个批量的操作，从而减少dom重排的次数，进而缩短了生成渲染树和绘制所花的时间。至于如何基于VD更有效率的更新dom，是一个很有趣的话题，日后有机会将另写一篇文章介绍。

即使使用了Virtual DOM来进行真实DOM的渲染，在页面更新的时候，也不能全量地将整颗Virtual DOM进行渲染，而是去渲染改变的部分，这时候就需要一个计算Virtual DOM树改变部分的算法了，这个算法就是Diff算法。

2. 传统的Diff算法

传统的Diff算法通过循环递归对节点进行比较，然后判断每个节点的状态以及要做的操作（add，remove，change），最后 根据Virtual DOM进行DOM的渲染。大体流程如下图（图来源）：

传统Diff算法的复杂度为O(n^3)，这个复杂度相对来说还是较高的。后来React开发者提供了一种复杂度仅为O(n) 的Diff算法。下面就来看一下O(n)复杂度的Diff算法是如何实现的。

3. 更高效的Diff算法

React的开发者结合Web界面的特点做出了两个大胆的假设，使得Diff算法复杂度直接从O(n^3)降低到O(n)，假设如下：

两个相同组件产生类似的DOM结构，不同的组件产生不同的DOM结构；

对于同一层次的一组子节点，它们可以通过唯一的id进行区分。

通过这两个假设，他们提供了下面的Diff算法思路。

同层比较

新的Diff算法是逐层进行比较，只比较同一层次的节点，大大降低了复杂度，具体如下图。在后面的内容中也会介绍Vue中同层节点比较的具体实现。

不同类型节点的比较

如果发现新旧两个节点类型不同时，Diff算法会直接删除旧的节点及其子节点并插入新的节点，这是由于前面提出的不同组件产生的DOM结构一般是不同的，所以可以不用浪费时间去比较。注意的是，删除节点意味着彻底销毁该节点，并不会将该节点去与后面的节点相比较。

相同类型节点的比较

若是两个节点类型相同时，Diff算法会更新节点的属性实现转换。

列表节点的比较

列表节点的操作一般包括添加、删除和排序，列表节点需要我们给它一个key才能进行高效的比较。

4.Vue Diff算法的实现

了解了Diff算法的大体思路后，我们回过头来看下Vue中的Diff算法是如何实现的。

Vue的Diff算法与上面的思路大体相似，只比较同级的节点，若找不到与新节点类型相同的节点，则插入一个新节点，若有相同类型的节点则进行节点属性的更新，最后删除新节点列表中不包含的旧节点。具体的实现在vue源码的src/core/vdom/patch.js中的updateChildren方法中，由于代码较长，下面简单说一下整个的比较流程。

如上图，有一组新旧节点数组before：[A, B, C, D]、after：[E, C, F, G]，我们设置了四个哨兵节点，oldStartIdx、newStartIdx、oldEndIdx、newEndIdx分别指向新旧节点数组的起始下标和开始下标，值为0,0,3,3；oldStartVnode，newStartVnode，oldEndVnode，newEndVnode则分别指向了before和after节点列表中对应哨兵节点下标的值，值为before[oldStartVnode],after[newStartIdx],before[oldEndIdx],after[newEndIdx]。

总结

Vue中的Diff算法采用了React相似的思路，都是同层节点进行比较，在比较的过程中，使用了一些优先判断和就地复用策略，提高了Diff算法的效率。