[Vue 源码] Vue 3.2 - Diff | React 18 - Diff - 有图有真相

概述

Vue Diff ，React Diff 算法都是同级节点的递归比较, 核心就是复用。

为什么是同级比较，笔者认为用户在操作 Dom 节点的时候，很少有将儿子节点变为父亲的情况，多数都是 向后追加，向前插入，正序，反序，这是非常常见的。如果不同级比较，去比较两棵树，是非常耗费性能的。

旧节点：a b c d e q f g

新节点：a b e c d h f g

假设 key 都是自身的字母，同一字母的 type 不变。

vue diff 效果

react diff 效果

React Diff 流程

React Difff 算法

对于以上两个新旧节点虚拟列表（React 是新的虚拟 dom 和 旧的 fiber 列表进行比较生产新的 fiber 列表），React 的做法是：

• 遍历新节点，与旧节点进行对比
• a,b 发现 type 和 key 相同，复用老的 fiber 去创建新的 fiber 节点
• 发现 e 和 c 不相同，break 跳出循环
• 将 c 之后包括 c 的旧节点加入 map中，键：key 值：旧的 fiber 节点
• 继续遍历新节点，遍历到 e 从 map 当中找，发现有，设置 lastIndex 为 4，4为 e 在旧节点当中的索引
• c 从 map 中找有，index < lastIndex, 2 < 4, 新的 fiber 节点标记移动
• d 从 map 中找有，index < lastIndex, 3 < 3，新的 fiber 节点标记移动
• h 从 map 中找，没有，lastIndex = 5，标记新增
• f 从 map 中找，有 index > lastIndex 6 > 5, lastIndex = 6，复用呆在原地
• g 从 map 中找，有 index > lastIndex 7 > 6, lastIndex = 7，复用呆在原地
• 删除真实dom节点中要移动和删除的节点，展示变为 a b e f g
• 开始移动
• c 节点在 新结点中索引为 3， mountIndex 为 3，发现 3 在 a b e f g 有元素f。
• insertBefore 将 c 插入到 f 前，变为 a b e c f g
• d 节点在 新结点中索引为 4， mountIndex 为 3，发现 3 在 a b e c f g 有元素f。
• insertBefore 将 c 插入到 f 前，变为 a b e c d h f g。
• 完成。

Vue Diff 流程

对于以上两个新旧节点虚拟列表（Vue 是新的虚拟 dom 和 旧的虚拟 dom 列表进行比较生产新的 fiber 列表），Vue 的做法是：

• 遍历新节点，与旧节点进行对比
• async start，从前遍历，a, b 与旧节点相同，不动
• 发现一个不相同的节点,break
• async end, 再向后遍历，f, g 与旧节点相同，不动
• 发现一个不相同的节点,break
• unkoown sequence， 两边尽可能复用，然后从中间开始遍历
• 用新的元素做成一个映射表，遍历老链表去找新的
• 老 c 从 新的映射表去找，发现有，复用 patch 操作
• 老 d 从 新的映射表去找，发现有，复用 patch 操作
• 老 e 从 新的映射表去找，发现有，复用 patch 操作
• 老 q 从 新的映射表去找，发现没有，卸载 unMount 操作
• 寻找最长递增序列，后缀添加 -> 贪心，替换得到最长递增子序列的个数 -> 倒叙追溯拿到不会移动的节点列表，计算出不移动的节点的索引。在这里是 3，4 也就是 c d节点
• 继续从中间遍历的最后一个节点 h 开始遍历,索引不是 3，4 以下一个 f 为achor插入。
• 继续遍历到 d，索引是4，则跳过不动。
• 继续遍历到 c，索引是3，则跳过不动。
• 继续遍历到 e ,索引不是 3，4 以下一个 d 为achor插入。
• 完成。