精读

 

Dom diff 是所有现在框架必须做的事情，这背后的原因是，由 Jquery 时代的面向操作过程转变为数据驱动视图导致的。

 

为什么 Jquery 时代不需要 Dom diff？因为 Dom diff 交给业务处理了，我们调用 .append 或者 .move 之类 Dom 操作函数，就是显式申明了如何做 Dom diff，这种方案是最高效的，因为怎么移动 Dom 只有业务最清楚。

 

但这样的问题也很明显，就是业务心智负担太重，对于复杂系统，需要做 Dom diff 的地方太多，不仅写起来繁琐，当状态存在交错时，面向过程的手动 Dom diff 容易出现状态遗漏，导致边界错误，就算你没有写出 bug，代码的可维护性也绝对算不上好。

 

解决方案就是数据驱动，我们只需要关注数据如何映射到 UI，这样无论业务逻辑再复杂，我们永远只需要解决局部状态的映射，这极大降低了复杂系统的维护复杂度，以前需要一个老手写的逻辑，现在新手就能做了，这是非常了不起的变化。

 

但有利也有弊，这背后 Dom diff 就要交给框架来做了，所以是否能高效的做 Dom diff，是一个数据驱动框架能否应用于生产环境的重要指标，接下来，我们来看看 Dom diff 是如何做的吧。

 

理想的 Dom diff

 

如图所示，理想的 Dom diff 自然是滴水不漏的复用所有能复用的，实在遇到新增或删除时，才执行插入或删除。这样的操作最贴近 Jquery 时代我们手写的 Dom diff 性能。

 

可惜程序无法猜到你的想法，想要精确复用就必须付出高昂的代价：时间复杂度 O(n³) 的 diff 算法，这显然是无法接受的，因此理想的 Dom diff 算法无法被使用。

 

关于 O(n³) 的由来。由于左树中任意节点都可能出现在右树，所以必须在对左树深度遍历的同时，对右树进行深度遍历，找到每个节点的对应关系，这里的时间复杂度是 O(n²)，之后需要对树的各节点进行增删移的操作，这个过程简单可以理解为加了一层遍历循环，因此再乘一个 n。

 

简化的 Dom diff

 

如图所示，只按层比较，就可以将时间复杂度降低为 O(n)。按层比较也不是广度遍历，其实就是判断某个节点的子元素间 diff，跨父节点的兄弟节点也不必比较。

 

这样做确实非常高效，但代价就是，判断的有点傻，比如 ac 明明是一个移动操作，却被误识别为删除 + 新增。

 

好在跨 DOM 复用在实际业务场景中很少出现，因此这种笨拙出现的频率实际上非常低，这时候我们就不要太追求学术思维上的严谨了，毕竟框架是给实际项目用的，实际项目中很少出现的场景，算法是可以不考虑的。

 

下面是同层 diff 可能出现的三种情况，非常简单，看图即可：

 

那么同层比较是怎么达到 O(n) 时间复杂度的呢？我们来看具体框架的思路。

 

Vue 的 Dom diff

 

Vue 的 Dom diff 一共 5 步，我们结合下图先看前三步：

 

如图所示，第一和第二步分别从首尾两头向中间逼近，尽可能跳过首位相同的元素，因为我们的目的是 尽量保证不要发生 dom 位移。

 

这种算法一般采用双指针。如果前两步做完后，发现旧树指针重合了，新树还未重合，说明什么？说明新树剩下来的都是要新增的节点，批量插入即可。很简单吧？那如果反过来呢？如下图所示：

 

第一和第二步完成后，发现新树指针重合了，但旧树还未重合，说明什么？说明旧树剩下来的在新树都不存在了，批量删除即可。

 

当然，如果 1、2、3、4 步走完之后，指针还未处理完，那么就进入一个小小算法时间了，我们需要在 O(n) 时间复杂度内把剩下节点处理完。熟悉算法的同学应该很快能反映出，一个数组做一些检测操作，还得把时间复杂度控制在 O(n)，得用一个 Map 空间换一下时间，实际上也是如此，我们看下图具体做法：

 

如图所示，1、2、3、4 步走完后，Old 和 New 都有剩余，因此走到第五步，第五步分为三小步：

 

遍历 Old 创建一个 Map，这个就是那个换时间的空间消耗，它记录了每个旧节点的 index 下标，一会好在 New 里查出来。

 

遍历 New，顺便利用上面的 Map 记录下下标，同时 Old 里不存在的说明被删除了，直接删除。

 

不存在的位置补 0，我们拿到 e:4 d:3 c:2 h:0 这样一个数组，下标 0 是新增，非 0 就是移过来的，批量转化为插入操作即可。

 

最后一步的优化也很关键，我们不要看见不同就随便移动，为了性能最优，要保证移动次数尽可能的少，那么怎么才能尽可能的少移动呢？假设我们随意移动，如下图所示：

 

但其实最优的移动方式是下面这样：

 

为什么呢？因为移动的时候，其他元素的位置也在相对变化，可能做了 A 效果同时，也把 B 效果给满足了，也就是说，找到那些相对位置有序的元素保持不变，让那些位置明显错误的元素挪动即是最优的。

 

什么是相对有序？a c e 这三个字母在 Old 原始顺序 a b c d e 中是相对有序的，我们只要把 b d 移走，这三个字母的位置自然就正确了。因此我们只需要找到 New 数组中的 最长子序列。具体的找法可以当作一个小算法题了，由于知道每个元素的实际下标，比如这个例子中，下标是这样的：

 

[b:1, d:3, a:0, c:2, e:4]

 

肉眼看上去，连续自增的子串有 b d 和 a c e，由于 a c e 更长，所以选择后者。

 

换成程序去做，可以采用贪心 + 二分法进行查找，详细可以看这道题 最长递增子序列，时间复杂度 O(nlogn)。由于该算法得出的结果顺序是乱的，Vue 采用提前复制数组的方式辅助找到了正确序列。