vue源码：diff算法

password

URL

type

status

date

slug

summary

什么时候开始 diff 算法

当触发 render 时，如果有新旧节点，则进入 patch 方法进行对比。

在 patch 里，首先根据新旧虚拟节点的 type 和 key 的对比结果，判断两个元素是否相同，如果不同则卸载老的，添加新的。如果相同，再根据 type 类型的不同，进入不同的 process 逻辑。

若虚拟节点的类型为是 element ，则开始对比元素。对元素本身和 props 更新后，就开始对比两个元素的 children。

此时的 children 有三种情况，分别为 null，字符串和数组，此时分情况讨论。

新children	老children	处理
null	null	不做处理
null	字符串	卸载老的
null	数组	卸载老的
字符串	null	添加新的
字符串	字符串	卸载老的，添加新的
字符串	数组	卸载老的，添加新的
数组	null	添加新的
数组	字符串	卸载老的，添加新的
数组	数组	diff算法

只在两个元素的孩子都为数组的时候，才会走到diff算法的逻辑

diff 算法步骤

其实diff算法并不复杂，反而显得非常的暴力。

对比两个数组，首先想到的是看看头尾有没有一样的元素，所以先分别从头尾遍历。

指针分别指向两个数组的开头和结尾，i 指向两个数组的开头，e1 指向数组1 的末尾，e2 指向数组2 的末尾。

从头遍历

如果两个数组开头相同的元素比较多，则先处理。如下面两个例子，i 指向的元素相同，则向后遍历

左边为新孩子数组个数比老的多的情况，右边为新孩子数组个数比老的少。

从尾遍历

如果两个数组结尾相同的元素比较多，则先处理。如下面两个例子，如果 e1 和 e2 所指向的元素相同，则向前遍历，得到如下结果：

左边为新孩子数组个数比老的多的情况，右边为新孩子数组个数比老的少。

挂载新节点

观察上述两种遍历方式的结果，发现 i 比 e1 大，说明老的比新的少，需要挂载新的，i 和 e2 之间的就是新增部分，直接使用 patch 挂载新元素

卸载老节点

i 比 e2 大，说明新的比老的少，需要卸载老的，i 和 e1 之间的就是需要卸载的，直接使用 patch 卸载老元素

乱序对比

通过上述的处理，如果两个数组如下图所示，那么剩下的就只有绿色框线的部分。

遍历新孩子数组，将节点的 key 与 index 做一个映射；随后遍历老孩子数组，如果根据对应的key 在这个映射中找到，则说明这个元素在新数组中也存在，调用 patch 更新，并标记被更新的元素；如果没有找到，直接卸载老的元素。在上图中，就会更新 c ，d ，e 元素。

此时要引入一个新的概念”最长递增子序列“，即，在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值依次递增，并且这个子序列的长度尽可能地大。

观察发现，在老孩子数组中的最长递增子序列，在新数组中依旧保持对应的顺序，也就是说，最长递增子序列里的元素位置不用变化；并且在上一步已经更新过元素的内容，这就导致这些元素在后续不需要操作了。通过算法算出老数组内的最长递增子序列，就是绿框中的 ce 。

随后，倒序遍历新节点刷要乱序对比的部分，就是图片里第二行绿框里的部分。如果是新增的元素，就直接插入，如果元素存在与最长递增子序列内就不做任何操作，否则就移动元素。

总结

这块代码逻辑倒不是特别难，有点兵来将挡的意思，遇到什么问题直接处理即可。整个算法的时间复杂度一直保持在 O(n) ，还使用的各种技巧优化对比速度，主要是最长递增子序列的应用，目的就是为了减少对 DOM 的操作。