聊聊 Vue 的双端 Diff 算法

Vue 和 React 都是基于 vdom 的前端框架，组件渲染会返回 vdom，渲染器再把 vdom 通过增删改的 api 同步到 dom。

当再次渲染时，会产生新的 vdom，渲染器会对比两棵 vdom 树，对有差异的部分通过增删改的 api 更新到 dom。

这里对比两棵 vdom 树，找到有差异的部分的算法，就叫做 diff 算法。

diff 算法是渲染器中最复杂的部分，也是面试的热点问题。今天我们就通过 Vue 的 diff 算法来探究下 diff 算法吧。

diff 算法

我们知道，两棵树做 diff，复杂度是 O(n^3) 的，因为每个节点都要去和另一棵树的全部节点对比一次，这就是 n 了，如果找到有变化的节点，执行插入、删除、修改也是 n 的复杂度。所有的节点都是这样，再乘以 n，所以是 O(n * n * n) 的复杂度。

这样的复杂度对于前端框架来说是不可接受的，这意味着 1000 个节点，渲染一次就要处理 1000 * 1000 * 1000，一共 10 亿次。

所以前端框架的 diff 约定了两种处理原则：只做同层的对比，type 变了就不再对比子节点。

因为 dom 节点做跨层级移动的情况还是比较少的，一般情况下都是同一层级的 dom 的增删改。

这样只要遍历一遍，对比一下 type 就行了，是 O(n) 的复杂度，而且 type 变了就不再对比子节点，能省下一大片节点的遍历。另外，因为 vdom 中记录了关联的 dom 节点，执行 dom 的增删改也不需要遍历，是 O(1)的，整体的 diff 算法复杂度就是 O(n) 的复杂度。

1000 个节点渲染一次最多对比 1000 次，这样的复杂度就是可接受的范围了。

但是这样的算法虽然复杂度低了，却还是存在问题的。

比如一组节点，假设有 5 个，类型是 ABCDE，下次渲染出来的是 EABCD，这时候逐一对比，发现 type