各位好，欢迎来到今天的“React 内部构造”深度研讨会。我是你们的老朋友，那个喜欢在代码里找 Bug、在 DOM 树里种树的资深工程师。
今天我们要聊的是一个有点“硬核”，但也是面试必问的题目：React 多节点 Diff 核心逻辑——两次遍历算法。
别被“两次遍历”这个词吓到了，它听起来像是什么高深的数学定理，其实说白了，就是 React 怎么像一个精明的搬家工一样，在虚拟 DOM 里把一堆 HTML 节点重新排列，既不重绘整个页面，又能用最少的力气把新布局搞定。
准备好了吗？把咖啡续上，我们开始干活。
第一部分：Diff 的哲学——为什么我们不搞“全盘重造”？
在讲具体算法之前，我们要先聊聊 React 做这个决定的哲学。
假设你的浏览器是一个装修队，React 是那个拿着图纸的工头。每次父组件更新，React 都会生成一份新的虚拟 DOM 树（新图纸），然后拿它和上一次的虚拟 DOM 树（旧图纸）做对比。
如果是傻瓜式装修（全量 Diff），那就是把旧房子拆了，按照新图纸重新盖一座。这叫“暴力破解”，性能极差，用户还没看到结果，页面可能已经白屏了。
React 聪明多了。它有一个核心原则：同层比较。就像你不能把二楼的床搬到地下室去一样，React 不会跨层级去比较节点。而且，如果类型变了（比如 <div> 变成了 <span>），React 会认为这是一个“新生命”，直接扔掉旧的，创建一个新的。
所以，Diff 算法的核心战场，就是同级列表。比如你有一个数组渲染列表，React 只会在这个数组里折腾，不会去管隔壁兄弟组件。
第二部分：双端 Diff 算法——一场四向出击的军棋
好，我们进入正题。React 15（以及早期的 React 16）使用的是一种叫双端 Diff 算法（Double-ended Diffing）的策略。这个名字听起来很霸气，其实就是 React 在每一轮遍历中，同时从旧列表的头部和尾部发起进攻。
我们定义四个指针（或者叫特工）：
oldStart：旧列表的第一个节点。oldEnd：旧列表的最后一个节点。newStart：新列表的第一个节点。newEnd：新列表的最后一个节点。
然后，React 会像玩俄罗斯方块一样，疯狂地尝试这四个特工能不能“认亲”。
场景一：同向匹配（最爽的场面）
情况 1：oldStart === newStart
这是最理想的情况。旧列表的头和新列表的头，居然长得一模一样！
React 的操作：
直接跳过。两个指针都往后挪一位。这就好比你们俩在电梯口碰面，互相点个头：“哟，你也在这儿？那咱俩不用动位置，继续走。”
情况 2：oldEnd === newEnd
这是另一种理想情况。旧列表的尾巴和新列表的尾巴是同一个节点。
React 的操作：
直接跳过。两个指针都往前挪一位。这就像是下班打卡，你们俩在门口碰面，互相挥挥手：“你也下班了？行，那我也不用挪窝了。”
场景三：交叉匹配（有点意思）
情况 3：oldStart === newEnd
旧列表的头，居然是 newEnd。这意味什么？意味着新列表把旧列表的开头“插”到了最后面。
React 的操作：
React 会把 oldStart 这个节点，移动到 newEnd 的位置。在 DOM 操作上，这通常意味着 appendChild。
情况 4：oldEnd === newStart
旧列表的尾巴，居然是 newStart。这意味着新列表把旧列表的尾巴“插”到了最前面。
React 的操作：
React 会把 oldEnd 这个节点，移动到 newStart 的位置。在 DOM 操作上，这通常意味着 insertBefore。
代码示例：
function reconcileChildren(oldFiber, newFiber) {
let oldStartIndex = 0;
let newStartIndex = 0;
let oldEndIndex = oldFiber.length - 1;
let newEndIndex = newFiber.length - 1;
let oldStartFiber = oldFiber[oldStartIndex];
let newStartFiber = newFiber[newStartIndex];
let oldEndFiber = oldFiber[oldEndIndex];
let newEndFiber = newFiber[newEndIndex];
while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
// 情况 1: 旧头 == 新头
if (oldStartFiber.key === newStartFiber.key) {
// 复用节点
updateNode(oldStartFiber, newStartFiber);
oldStartIndex++;
newStartIndex++;
oldStartFiber = oldFiber[oldStartIndex];
newStartFiber = newFiber[newStartIndex];
}
// 情况 2: 旧尾 == 新尾
else if (oldEndFiber.key === newEndFiber.key) {
updateNode(oldEndFiber, newEndFiber);
oldEndIndex--;
newEndIndex--;
oldEndFiber = oldFiber[oldEndIndex];
newEndFiber = newFiber[newEndIndex];
}
// ... 情况 3 和 4 稍后讲
else {
// 碰到硬骨头，暴力查找
}
}
}场景四：硬骨头（暴力查找）
如果上述四种情况都不满足，说明这四个特工“认亲”失败了。这时候怎么办？
React 会怎么做？它会把 newStartFiber（新列表的头）拿出来，在 oldFiber 数组里从左到右遍历一遍，看看有没有哪个节点长得像它。
这就是著名的“暴力查找”。
代码示例：
else {
// 暴力查找：在 oldFiber 中查找 newStartFiber
let indexToFind = oldStartIndex;
let found = false;
while (indexToFind <= oldEndIndex) {
if (oldFiber[indexToFind] && oldFiber[indexToFind].key === newStartFiber.key) {
// 找到了！
found = true;
// 这是一个移动操作
let currentFiber = oldFiber[indexToFind];
updateNode(currentFiber, newStartFiber);
// 关键点来了：要把这个节点从原来的位置拿走，放到 newStart 的位置
// 在 React 内部，这涉及到调整 Fiber 树的指针
let nextFiber = currentFiber.sibling;
// 把这个节点“跳”到 oldStart 的位置
oldFiber[indexToFind] = nextFiber;
// 然后把 oldStart 指针后移，相当于把这个复用过的节点“吃”掉了
oldStartFiber = oldFiber[oldStartIndex];
break;
}
indexToFind++;
}
if (!found) {
// 没找到，说明这是一个新节点，需要创建
// 创建并挂载到 newStart 的位置
let newFiber = createNewFiber(newStartFiber);
// 这里简化处理，实际逻辑更复杂
// ...
}
}第三部分：两次遍历——第一遍找亲戚，第二遍收烂摊子
刚才我们只讲了一半。React 的双端 Diff 算法，实际上包含了两次遍历。
第一次遍历：双端匹配
这就是我们刚才讲的那一套 while 循环。它的目的是尽可能多地复用节点，尽量不动 DOM，只做“移动”操作。
第二次遍历：处理剩余节点
当第一次遍历结束时，会有两种情况：
- 旧列表空了，新列表没空：说明新增了一些节点。
- 新列表空了，旧列表没空：说明删除了一些节点。
- 两边都没空：说明中间还有没匹配上的节点。
这时候，React 就要进行第二次遍历了。
场景 A：新列表还有节点（新增）
如果 newStartIndex <= newEndIndex，说明新列表里还有没处理的节点。React 会直接把它们挂载到当前 DOM 的末尾。
代码示例：
if (newStartIndex <= newEndIndex) {
// 新增节点
for (let i = newStartIndex; i <= newEndIndex; i++) {
let fiberToInsert = newFiber[i];
// 简单粗暴，直接插队
insertAtEnd(parentDom, fiberToInsert);
}
}场景 B：旧列表还有节点（删除）
如果 oldStartIndex <= oldEndIndex，说明旧列表里还有没处理的节点。React 会把它们全部卸载。
代码示例：
if (oldStartIndex <= oldEndIndex) {
// 删除节点
for (let i = oldStartIndex; i <= oldEndIndex; i++) {
let currentFiber = oldFiber[i];
// 移除 DOM
removeDom(currentFiber.dom);
}
}第四部分：性能代价——搬家的成本
好了，算法讲完了。现在我们来算算账。这“两次遍历”到底贵不贵？
时间复杂度：O(N)
这是 React Diff 的核心优势。最坏的情况下（比如列表完全反转），React 需要进行一次暴力查找（O(N)），然后处理剩余节点（O(N)）。总的时间复杂度依然是线性的。相比于 React 之前的 O(N^3) 或者 Vue 2 的 O(N^2)，React 15 的双端 Diff 已经非常优秀了。
空间复杂度：O(1)
React 15 的 Diff 是原地更新的。它不需要创建一个新的虚拟 DOM 树来保存结果，而是直接修改旧的 Fiber 节点。这意味着它不需要额外的内存空间来存储中间状态。内存占用非常低。
DOM 操作的代价（真正的性能杀手）
虽然算法是 O(N) 的，但DOM 操作本身是很慢的。
- 移动节点：即使 React 算出了最优的移动路径，它依然需要调用
insertBefore或appendChild。这是浏览器层面的开销。 - 暴力查找：这是性能的瓶颈。如果列表很长，比如 1000 个节点，每次双端不匹配都要遍历一次，虽然只有一次，但在极端情况下（比如列表完全乱序），这会增加计算量。
第五部分：为什么 React 后来改了？（React 16+ 的 Fiber）
讲了半天 React 15，你可能想问：“老师，React 18 不是 Fiber 架构吗？还有两次遍历吗？”
答案是：有的，但是变了。
React 16 引入了 Fiber 架构，改变了 Diff 的执行方式，而不是改变了 Diff 的算法逻辑。
- 时间切片：React 15 的 Diff 是同步的，如果列表有 5000 个节点，Diff 过程可能会阻塞主线程 100 毫秒，导致页面卡顿。React 16 把这个 Diff 过程切成了无数个小片段，每处理几个节点就让出主线程，保证页面不卡顿。
- 自动批处理：React 16+ 会自动合并多次 setState，让 Diff 只执行一次。这大大减少了“两次遍历”的触发频率。
第六部分：深度剖析——最长递增子序列（LIS）优化
其实，在 React 15 的内部源码中，还有一个鲜为人知的优化，那就是最长递增子序列。
为了减少 DOM 的移动次数，React 会尝试计算一个最长的、不需要移动的节点序列。比如：
- 旧列表：
[A, B, C, D] - 新列表：
[C, B, A, E]
React 的双端 Diff 算法可能会发现，B 是可以保留在原位的（B 在旧列表是索引1，在新列表也是索引1）。然后它会尝试找出 C 和 A 的移动路径。
虽然 React 15 主要依赖双端 Diff，但理解 LIS 逻辑有助于你理解为什么某些列表更新非常快（因为很多节点不动），而某些更新很慢（因为节点全部乱序）。
总结：如何写出高性能的 React 代码？
既然知道了 React 的脾气，我们该怎么写代码呢？
- 不要乱改 Key：这是最重要的！Key 必须是稳定的、唯一的。如果你用
index作为 Key，当列表插入或删除时，React 就会认为所有节点都变了，导致双端 Diff 失效，变成暴力查找，性能直接崩盘。 - 避免全量移动：尽量让你的更新逻辑符合 React 的 Diff 预期。比如，把新增节点放在列表末尾，而不是中间。
- 使用
useMemo缓存列表：如果列表数据不频繁变化，用useMemo缓存一下，避免每次渲染都重新生成新数组。
好了，今天的“两次遍历算法”讲座就到这里。希望你们以后再看到 ReactDom.render 的时候，脑海里不再是黑乎乎的一团代码，而是一群戴着墨镜的特工在旧列表和新列表之间玩“找不同”。
记住，Diff 不是魔法，它是数学和逻辑的艺术。代码写得好不好，看的就是对底层逻辑的掌控。
下课！