Vue-深入浅出Vue Diff 算法

前言

在 Vue 的响应式系统中，当数据发生变化时，Vue 会生成一颗新的虚拟 DOM 树（VNode Tree）。Diff 算法的核心任务就是通过对比新旧两棵树，以最小的性能代价完成真实 DOM 的更新。本文将带你深度拆解 Vue Diff 的核心机制。

一、 Diff 算法的核心策略

Vue 的 Diff算法就是比较dom树的新旧节点，一边比较一边给真实dom移动、插入或者删除节点。Diff 算法基于两个基本假设，从而将时间复杂度从 $O(n^3)$ 降低到了 $O(n)$：

1. 同层比较：算法只会对同一层级的节点进行比较，不会跨层级操作。

2. 深度优先：通过递归的方式，先处理子节点，再处理父节点。

二、 三大核心函数解析

Diff 的过程主要由 patch、patchVnode 和 updateChildren 三个函数协同完成。

1. patch 函数：同层比对的入口

这是 Diff 的起点，它负责决定是直接替换整个节点，还是深入比对，比较策略如下:

• 如果新节点不存在：直接删除旧节点。
• 如果新节点存在，旧节点不存在：直接新建并插入节点。
• 如果两个节点都存在，但节点类型不同：认为节点已改变，销毁旧的，创建新的。
• 如果两个节点都存在，且节点类型相同：则调用 patchVnode 继续比对
• 。

2. patchVnode 函数：属性与文本的更新

当确定两个节点“值得比较”时，执行以下逻辑：

• 首先判断新节点是否为文本节点（为文本节点就说明没有子节点了），如果是的话，则直接更新dom的文本内容为新节点的文本内容。

• 如果新节点不是文本节点，而旧节点是文本节点的话，说明节都是全新的，所以直接将新节点添加到父节点中

• 如果新旧节点都不是文本节点，则说明两者都有子节点，接下来就进updateChildren()函数进行下一步比较并更新子节点

3. updateChildren 函数：双端比较算法

这是 Vue Diff 的灵魂。它通过 “双端指针” （新头、新尾、旧头、旧尾）向中间靠拢，寻找可复用的节点。updateChildren函数对会新旧两个节点设置4个指针，分别指向新头、旧头、新尾、旧尾，它主要对5种情况进行比较：

比较的五种优先级：

1. 首先是旧头新头进行比较：如果二者相同，就对二者执行patchVnode()，并将旧头新头两个指针向中间移动。

2. 如果旧头新头不相同，就进行旧尾新尾的比较：如果旧尾新尾相同的话，则将旧尾新尾两指针向中间移动。

3. 如果旧头与新头，旧尾与新尾都不相同：那就进行交叉比较，比较方式如下：

   • 首先是旧头新尾比较，如果二者相同，那么就执行patchVnode()，并将旧头指针向后移一位，新尾指针前移一位
   • 如果旧头新尾不相同，那就比较新头旧尾，如果二者相同，那么就执行patchVnode()，并将新头指针后移一位，旧尾指针前移一位

4. 如果以上四种情形都不满足的话，那说明没有相同的节点可以复用，则将在旧节点中遍历寻找与新头节点key值相同的节点。

   • 如果没有在旧节点中找到key值相同的节点，则说明新头节点是一个新的节点，那么就直接新建，并将新头指针后移
   • 如果在旧节点中找到了key值相同的节点，则执行patchVnode()函数继续比较对应key值相同的节点是否为同一节点，并将新头指针后移

三、 案例实战：双端比对全过程

第一次循环后，发现旧头新尾、旧头新头不相同，但旧尾新头相同，直接复用旧节点D作为diff后的第一个真实节点，同时旧节点endIndex移动到C，新节点的 startIndex 移动到了 C。

二次循环后，同样是旧尾新头相同，这时就将diff 后创建的真实节点 C 插入到第一次创建的 D 节点后面。同时旧节点的 endIndex 移动到了 B，新节点的 startIndex 移动到了 E。

第三次循环中，发现在旧节点中没有找到E节点，这时候直接创建新的真实节点 E，插入到第二次创建的 C 节点之后。同时新节点的 startIndex 移动到了 A。旧节点startIndex 和 endIndex 都保持不动。

四次循环中，发现了新头旧头相同，于是 diff 后创建了 A 的真实节点，插入到前一次创建的 E 节点后面。同时旧节点的 startIndex 移动到了 B，新节点的startIndex 移动到了 B

第五次循环中，发现了新头旧头相同，因此 diff 后创建了 B 真实节点 插入到前一次创建的 A 节点后面。同时旧节点的 startIndex移动到了 C，新节点的startIndex移动到了 F。

最后一次循环中，发现在旧节点中没有找到F节点，这时直接创建 F 对应的真实节点，直接将其插入到 B 节点后面，并将新头指针向后移动一位，发现startIndex大于endIndex ，这时循环结束。

四、 总结

• Diff 的本质：是虚拟 DOM 周期的终点，也是真实 DOM 更新的起点。
• Key 的重要性：没有 key 会导致 Diff 算法回退到性能极差的逐个更新模式。务必在 v-for 中提供稳定、唯一的 key。