diff 算法

概念

前端框架中的 diff 算法主要用于高效地更新和渲染用户界面（UI）。React、Vue 这些框架中，diff 算法的核心目标就是比较虚拟 DOM（Virtual DOM）树的变化，并最小化实际 DOM 操作，从而提高性能。

虚拟 DOM (Virtual DOM)：前端框架常用一个轻量级的 JavaScript 对象来表示真实的 DOM 结构，这个对象称为虚拟 DOM。当状态或数据变化时，框架会创建一个新的虚拟 DOM 树。
比较（Diffing）：将新的虚拟 DOM 树与旧的虚拟 DOM 树进行比较，找出差异。
补丁（Patching）：根据差异生成最小的 DOM 操作集合，并应用到真实 DOM 上。

React 的 diff 算法采用了深度优先遍历算法。因为广度优先遍历可能会导致组件的生命周期时序错乱，而深度优先遍历算法就可以解决这个问题。

深度优先遍历一棵树时间复杂度是 O(n^3)，React 通过一些优化，将时间复杂度降低到了 O(n)。

优化手段：

对于单节点而言：判断 key 和 type 相同时，复用节点，否则销毁旧节点并创建新节点。

对于多节点而言：

第一轮遍历 对比新旧节点，找到节点是否可以复用，如果可以复用就继续遍历。

不可复用的情况：key 值不同，立即跳出循环；key 相同但 type 不同，会标记为 DELETION，继续遍历。

第二轮遍历

新节点没遍历完，旧节点遍历完

说明已有的 DOM 节点都复用了，这时还有新加入的节点，我们只需要遍历剩下的新节点为生成的 workInProgress fiber 依次标记 Placement 即可。
新节点遍历完，旧节点没遍历完

说明节点数量少了，有节点被删除了。所以遍历旧节点，依次标记 Deletion。
新旧节点都没遍历完

说明节点发生了位置变化。下面详细介绍。

处理移动的节点

未处理的 oldFiber 存入以 key 为 key，oldFiber 为 value 的 Map 中。

用变量 oldIndex 表示遍历到的可复用节点在 oldFiber 中的位置索引，maxIndex 访问过的新节点在老集合的最大下标。

比较 oldIndex 和 maxIndex，规则如下：

第一轮比较

【头比较】从左到右比对，如果是相同的就进行更新比对，如果不相同则停止比对，并且记录停止的下标。
【尾比较】从右到左比对，如果是相同的就进行更新比对，如果不相同也停止比对，也进行记录停止的下标。
【创建/删除】左右比对完之后，如果新节点已经比对完了，老节点列表还存在节点未比对，则删除老节点列表上的未比对的节点，如果老节点已经比对完了，新节点列表还存在未比对的节点则进行创建。

第二轮比较

说明新旧节点未比对完

先把剩下的新节点处理成节点的 key 为 key, 节点下标为 value 的 Map；
初始化数组 newIndexToOldIndexMap，长度为未比对的新节点的长度，默认值都为 0。
循环剩下的旧节点，通过旧节点的 key 去 Map 中查找。如果旧节点没有 key 则需要通过循环剩下的新节点进行查找。
如果旧节点在新节点中没找到，则说明该旧节点需要进行删除。
如果找到了，则把找到的新节点的下标对应存储到上述的数组 newIndexToOldIndexMap 中，然后更新比对匹配到的新老节点。
把所有的旧节点比对完成后，就会得到一个刚刚收集的新节点的下标数组，然后对这个新节点的下标数组进行进行最长递增子序列查找。
再后序遍历对比完之后剩余新节点的下标，判断循环的下标是否被上述的数组 newIndexToOldIndexMap 进行收集了，如果没被收集到则说明这个新节点需要进行创建，如果已经被收集了则判断该循环的下标是否在上面计算得到的最长递增子序列中，如果不在则需要对该循环节点进行移动操作。

需要最长递增子序列是因为需要尽可能多的找到不需要移动的节点，所以总长度减去最长递增子序列就是要移动的节点个数