一、前言

你将从本文了解到：

Vue2/Vue3/React diff算法的差异，以及各自diff算法的核心思路。

---

二、Diff 算法前置基础

1. 什么是 Diff 算法

当数据发生变化时，同层级对比新旧Dom树，找出最小差异，只更新变化的 DOM，不整棵树重绘，这个对比过程就是Diff 算法。

2. Key 的作用

Key 是节点唯一标识，帮助框架识别新旧节点是否为同一个节点，实现节点复用，这也是为什么不推荐index作为key的原因。

---

三、Vue2 双端比较

1. 核心思路

维护四个指针：旧头、旧尾、新头、新尾从两头向中间同时比对，四种匹配逻辑：

old头new头  old尾new尾  old头new尾  old尾new头，

命中任意一种，直接移动指针或移动 DOM 节点。

2. 四种都不匹配如何处理

通过 key 生成映射表，用新头 key 去旧列表查找：

1. 如果找到可复用节点，移动到旧列表尾部复用，实现匹配。

2. 如果没找到，创建新 DOM 插入尾部。

3. Vue2 双端比较优势

• 首尾微调场景速度极快
• 简单乱序场景适配性好

4. 缺点

大规模乱序、随机打乱列表时，无法算出最优解，DOM 移动操作冗余较多。

---

四、Vue3 双端 + LIS 最长递增子序列

1. 整体执行流程

先双端快速匹配，后 LIS 优化乱序

1. 先进行首尾双端比对，把顺序没变的首尾节点快速过滤，收缩指针范围；
2. 剩下中间乱序节点，开启 LIS 最长递增子序列优化；
3. 生成新列表可复用节点对应的旧索引数组；
4. 求出最长递增子序列，序列内节点原地不动，只移动不在序列中的节点。

2. LIS 解释

即在乱序节点中，找到递增的队列：

old队列: 123456     new队列: 143625

其中new队列里找到146作为最长递增子序列，然后移动3 2 5。

3. Vue3 Diff 优势

• 继承双端快速匹配优点，常规场景开销极低
• 乱序重排场景通过 LIS 实现最少 DOM 移动

4. 缺点

极简顺序场景，比 Vue2 多一点 LIS 计算开销，但其实也还好。

---

五、React 仅右移

1. 核心策略

单向从左到右遍历 + lastIndex 标记。

2. 仅右移规则

React 只会把节点向右插入，不会主动把后面的节点向左挪动。lastIndex是一个比较依据，不属于新旧队列指针。

遍历过程是这样的：

• 如果之前没有找到过新节点对应的 oldIndex，则通过 Map 获取 oldIndex，进入比较阶段；
• 如果 Map 中不存在该新节点的 oldIndex，视为新增节点，创建并插入到已渲染队列末尾；
• 如果之前找到过新节点对应的 oldIndex，进入比较阶段；

比较阶段：

• oldIndex >= lastIndex ，顺序正常，更新 lastIndex，复用该节点，追加到已渲染队列末尾；
• 若 oldIndex < lastIndex ，判定为需要右移，不更新 lastIndex，复用该节点，追加到已渲染队列末尾；

3. React Diff + Fiber 架构

把递归 Diff 拆分为 Fiber 链表小任务，利用时间切片，空闲时执行 Diff。

高优先级交互任务可插队，不会阻塞主线程，适合大型复杂项目，保证页面流畅度。

4. React Diff 优势

• 算法较为简单，单向遍历逻辑清晰易维护
• 适配 Fiber 时间切片，可中断调度

5. 缺点

乱序、倒序、头部插入场景，DOM 冗余操作多，性能较差。

---

六、总结

Vue2 采用双端比较，靠四指针头尾匹配，匹配失败就把可复用节点挪到旧列表尾部复用，只玩头尾。

Vue3 先双端精简首尾，再对中间乱序节点用LIS 最长递增子序列，LIS 节点原地不动，只移动其余节点，实现最少 DOM 移动。

React 采用单向遍历 + lastIndex 仅右移策略，算法简单，乱序开销大；依靠 Fiber 可中断调度，不阻塞主线程，更适合大型项目。