跳到主要内容

认识

2024年03月13日
柏拉文
越努力，越幸运

一、认识​

在 BeginWork 递阶段 从根 Fiber 开始, 对每个 Fiber 节点，调用对应的处理函数。拿到最新的 ReactElement 之后, 首先判断是否命中 bailOut 优化策略, bailout 性能优化策略, 如果未命中, 调用 reconcileChildren, 通过 Diff 算法来对比 当前的旧 Fiber 和最新的 ReactElement。根据新旧差异决定是复用已有的 Fiber 还是创建新的 Fiber 节点, 在对比过程中，为需要更新的节点打上相应的 flag（如 Placement、Update 或 Deletion）。同时创建或更新当前节点的子 Fiber 链，为后续 CompleteWork 阶段做准备。React Diff 算法的目标是最小化真实 DOM 更新的代价。它通过在内存中（虚拟 DOM 层面）构造新旧 Fiber 树，然后计算出二者之间的最小差异，再把这些差异反映到真实 DOM 上。Diff 策略如下:

一、单节点 Diff, newChild 为对象, 说明子节点为单节点, 进行单节点 Diff。根据 key 和 type 判断复用、替换或删除。

二、多节点 Diff, newChild 为数组, 说明子节点为多节点, 进行多节点 Diff。在处理多个节点的情况时，React 发现日常开发中更新操作（即节点属性、子节点内容等变化）远比新增和删除更为常见，因此 Diff 算法设计了两轮遍历策略，优先处理可以复用的 更新节点, 再针对剩余节点做增删和移动处理。

  • 第一轮遍历, 从头到尾逐一对比新旧节点,优先处理更新、复用节点,并记录最后一个成功复用节点的位置。遇到 key 不同时立即终止第一轮遍历,这是为了后续更高效地处理剩余节点（新增、删除和移动）: 从 newChildren 数组中依次取出新节点，从 newIdx = 0 开始，与旧 Fiber 链表中的第一个节点开始对比, 比较 newChildren[newIdx] 与当前 oldFiber, 如果可以复用（即满足 key 和 type 判断复用的条件）, 则不会创建新的 Fiber, 并继续比较下一个新节点与 oldFiber.sibling。如果遇到不可以复用的情况, 则有两种: key 不同, 立刻跳出第一轮遍历，此时新旧节点都还未全部遍历完; key 相同但 type 不同, 标记当前旧 Fiber 为 Deletion, 但仍继续遍历后续旧 Fiber 看是否能找到复用机会。当新节点遍历完（newIdx === newChildren.length）, 或旧 Fiber 链表遍历完（oldFiber.sibling === null）时, 第一轮遍历结束。第一轮结束后，记录最后一个成功复用的旧 Fiber 在链表中的位置索引, 记为 lastPlacedIndex。这一索引将在后续判断节点是否需要移动时起到关键作用。

  • 第二轮遍历, 根据第一轮遍历的结果, 对剩余的新节点或旧节点分别标记为 Placement（新增）、Deletion（删除）或处理移动。对于移动检测, 通过将剩余旧节点存入 Map, 再对新节点进行查找, 比对旧节点在列表中的位置与 lastPlacedIndex 来决定是否需要移动, 这是算法的核心优化之一: 根据第一轮结束时的状态, 存在以下几种情况: 1. 新旧同时遍历完, 表示所有节点都已处理完，仅需完成更新操作, Diff 算法结束; 2. 新节点未遍历完，旧 Fiber 遍历完, 说明在更新中存在新增节点, 遍历剩余的新节点, 为每个生成新的 Fiber, 并标记为 Placement（插入）。3. 新节点遍历完，旧 Fiber 未遍历完, 表示更新后节点数量减少, 需要删除多余的旧节点, 遍历剩余的旧 Fiber, 标记为 Deletion。4. 新旧都未遍历完：处理移动节点, 这部分是 Diff 算法最精髓也是最复杂的部分，主要逻辑如下:

    • 构建 Map: 为剩余的旧 Fiber构建 old Fiber Key - to - Old Fiber 映射 Map（例如 existingChildren）, 以便快速查找。

    • 遍历剩余的新节点: 对于每个新节点, 通过其 key 快速在 existingChildren 中查找是否存在对应的旧 Fiber。

    • 判断是否需要移动: 通过从 Map 中拿到旧节点的 index（称为 oldIndex）, 与记录的 lastPlacedIndex 进行比较。如果 oldIndex >= lastPlacedIndex, 说明该节点在旧列表中的顺序未发生逆转, 因此不需要移动，同时更新 lastPlacedIndex。如果 oldIndex < lastPlacedIndex, 说明该节点在旧列表中的位置早于之前的复用节点, 表示它需要移动, 新生成的 Fiber 将被打上 Placement 标记，表示后续需要进行真实 DOM 的移动操作。

三、Key 的重要性, 在 Diff 算法中, React 通过 key 来快速匹配新旧节点, 可以让 React 避免逐一比较所有节点, 大大提升 Diff 算法的效率。如果每个节点都有唯一的 key, React 就可以准确地找到它在上一次渲染中的对应项，进而判断出哪些节点是复用、哪些需要更新、删除或移动。对于列表中的组件来说, key 还能帮助 React 保持组件的内部状态。当列表发生增删或重新排序时, 带有稳定 key 的组件能够正确保留它们的状态。如果不加 Key, 会发生什么？: 默认使用索引匹配, 如果没有提供 key, React 会退而求其次, 使用节点在数组中的索引来作为默认 key。这种方式在静态列表中可能没问题，但在列表项频繁增删、排序或动态变化的场景下, 会带来一些问题: 1. 匹配不准确, 当数据项的顺序发生变化或插入新的数据时, 使用索引可能会导致 React 错误地匹配节点, 从而将错误的状态应用到错误的组件上; 2. 性能下降, 缺少稳定的 key, 使得 Diff 算法需要更复杂的判断，可能导致更多的节点被重新渲染，影响性能。3. 状态丢失, 在组件内有状态（例如输入框的内容、动画状态等）的情况下，如果使用索引匹配，列表重新排序或数据变化时可能导致状态错误地复用或丢失。

四、Fiber 链表的优势与限制, React 在运行前, 将 JSX 全部转换为 ReactElement 虚拟 DOM, 随后在 Render BeginWork 递阶段 会生成 Fiber 树, 具有两种数据结构。由于 React 具有两种结构, 在进行 Diff 对比时, 通过对比 ReactElement 数组 与 Fiber 单链表, Fiber 结构方便快速访问父、子和兄弟节点, 但因为没有直接引用前一个节点, 只能从左到右依次比对, 无法实现双端对比。 因此, Diff 算法在处理移动操作时必须依赖额外的 Map 进行优化查找，这也是算法中最复杂的部分。

五、多节点 Diff 利用 Map 优化移动检测, 在多节点 Diff 中, 遇到节点顺序发生变化时, React 为了高效判断哪些节点需要移动，会利用一个 Map 来加速查找和比较。在第一轮遍历中, React 会依次比较新旧节点, 优先处理可以直接复用的部分, 并记录最后一个复用成功的旧节点的位置索引（lastPlacedIndex）。为了快速查找这些剩余旧节点, React 将它们存储在一个 Map 中, Map 的键为节点的 key, 值为对应的旧 Fiber （Fiber 中包含它在原列表中的索引）。通过新节点的 key 在 Map 中查找是否存在对应的旧 Fiber。如果找到, 就说明这个节点理论上可以复用。每个旧节点都有一个原始位置索引（oldIndex）, React 会将这个 oldIndex 与之前记录的 lastPlacedIndex 进行比较, 如果 oldIndex >= lastPlacedIndex, 说明这个节点在旧列表中的顺序保持相对正确, 不需要移动。然后更新 lastPlacedIndex 为当前 oldIndex。如果 oldIndex < lastPlacedIndex, 则说明该节点在旧列表中的位置比前面复用的节点要早, 意味着新节点在当前的位置上与旧节点的顺序已经发生逆转, 即需要进行移动操作。此时, 新生成的 Fiber 会被打上 Placement 标记, 指示后续需要在真实 DOM 中重新调整位置。利用 Map 的常数时间查找, 可以大大加快从剩余旧节点中找到匹配项的速度, 而不需要遍历整个链表。通过比较旧节点的位置索引与 lastPlacedIndex, React 能准确地识别出哪些节点需要移动，确保最终的节点顺序与新的数据一致。

二、节点结构​

2.1 旧节点​

const oldFiber: ReactFiber = {
    return: 父节点,
    sibling: 兄弟节点,
    child: 第一个孩子节点,
}

2.2 新节点​

const newFiber: ReactElement = [
    fiber1,
    fiber2,
    ……
]

2.3 新旧对比​

React Diff 目前的对比方式是:

  • newChildren[i] 与 oldFiber 对比

  • newChildren[i++] 与 oldFiber.sibling 对比

从已上可以得知: Fiber 链表的数据结构的特点: 就是任何一个位置的 Fiber 节点，都可以非常容易知道它的父 Fiber, 第一个子元素的 Fiber,和它的兄弟节点 Fiber。却不容易知道它前一个 Fiber 节点是谁，这就是 React 中单向链表 Fiber 节点的特点。

三、单节点细节​

3.1 key 相同 type 相同​

key 相同 type 相同, 复用当前旧节点

3.2 key 相同 type 不同​

key 相同 type 不同, 不存在任何复用的可能性, 标记所有旧节点为 ChildDeletion

3.3 key 不同 type 相同​

key 不同 type 相同, 当前节点不可复用, 标记当前旧节点为 ChildDeletion, 继续遍历

3.4 key 不同 type 不同​

key 不同 type 不同, 不存在任何复用的可能性, 标记所有旧节点为 ChildDeletion

四、多节点细节​

多节点 Diff 优先级: React团队发现，在日常开发中，相较于新增和删除，更新组件发生的频率更高。所以Diff会优先判断当前节点是否属于更新。因此, Diff 算法的整体逻辑会经历两轮遍历:

  • 第一轮遍历: 处理更新的节点。

  • 第二轮遍历: 处理剩下的不属于更新的节点。

4.1 一轮遍历​

  1. newIdx = 0 遍历 newChildren, 比较 newChildren[newIndex] 和 oldFiber, 判断 DOM 节点是否可以复用

  2. 如果可以复用, 继续循环遍历比较 newChildren[newIndex++] 和 oldFiber.sibling

  3. 如果不可以复用, 分两种情况:

    • key 不同导致不可复用, 立即跳出整个遍历, 第一轮遍历结束

    • key 相同 type 不同导致不可复用, 会将oldFiber标记为DELETION，并继续遍历

  4. 如果newChildren遍历完（即i === newChildren.length - 1）或者oldFiber遍历完（即oldFiber.sibling === null），跳出遍历，第一轮遍历结束。

  5. 第一轮遍历结束, 会有两种结果:

    • 因为不可以复用, 结束的循环遍历, 此时, newChildren没有遍历完，oldFiber也没有遍历完。

    • 因为 newChildren 遍历完或者 oldFiber 遍历完 或者它们同时遍历完成

  6. 第一轮循环遍历结束, 记录最后一个可复用的节点在 oldFiber 中的位置索引 lastPlacedIndex

4.2 二轮遍历​

  1. newChildren与oldFiber同时遍历完: 只需在第一轮遍历进行组件更新。此时Diff结束。

  2. newChildren没遍历完，oldFiber遍历完: 已有的DOM节点都复用了，这时还有新加入的节点，意味着本次更新有新节点插入，我们只需要遍历剩下的newChildren为生成的workInProgress fiber依次标记Placement。

  3. newChildren遍历完，oldFiber没遍历完: 意味着本次更新比之前的节点数量少，有节点被删除了。所以需要遍历剩下的oldFiber，依次标记Deletion。

  4. newChildren与oldFiber都没遍历完: 这意味着有节点在这次更新中改变了位置, 这是Diff算法最精髓也是最难懂的部分。处理移动节点 逻辑如下:

    • 将所有还未处理的oldFiber存入以key为key，oldFiber为value的Map中: 这样可以快速的找到 key 对应的 oldFiber

      // Add all children to a key map for quick lookups.
      const existingChildren = mapRemainingChildren(returnFiber, oldFiber);

    • 接下来遍历剩余的newChildren，通过newChildren[i].key就能在existingChildren中找到key相同的oldFiber。

    • 此时 lastPlacedIndex 变量记录着最后一个可复用的节点在oldFiber中的位置索引, 通过 newChildren[i].key 从 existingChildren Map 中拿到 oldFiber 中的 index 并取名为 oldIndex

    • 比较 oldIndex 与 lastPlacedIndex

      • 如果 oldIndex >= lastPlacedIndex: 代表该可复用节点不需要移动, 并将 lastPlacedIndex = oldIndex, 返回老 Fiber 的位置即

      • 如果 oldIndex < lastPlacedIndex: 该可复用节点之前插入的位置索引小于这次更新需要插入的位置索引，代表该节点需要移动, 给新 Fiber 节点打上一个 Placement 的标记，并继续返回上一次协调返回的位置

五、思考​

5.1 React Diff 中 key 的作用?​

React Diff Key 作为新旧元素的唯一标识, 当对比新旧元素时, 首先要对比的就是 key 是否相同。如果 key 不相同或者 key 不存在, 那么认为此时的旧元素不可复用, 直接将旧元素删除, 随后重新创建 Fiber 节点。

在 Diff 算法中, React 通过 key 来快速匹配新旧节点, 可以让 React 避免逐一比较所有节点, 大大提升 Diff 算法的效率。如果每个节点都有唯一的 key, React 就可以准确地找到它在上一次渲染中的对应项，进而判断出哪些节点是复用、哪些需要更新、删除或移动。对于列表中的组件来说, key 还能帮助 React 保持组件的内部状态。当列表发生增删或重新排序时, 带有稳定 key 的组件能够正确保留它们的状态。如果不加 Key, 会发生什么？: 默认使用索引匹配, 如果没有提供 key, React 会退而求其次, 使用节点在数组中的索引来作为默认 key。这种方式在静态列表中可能没问题，但在列表项频繁增删、排序或动态变化的场景下, 会带来一些问题: 1. 匹配不准确, 当数据项的顺序发生变化或插入新的数据时, 使用索引可能会导致 React 错误地匹配节点, 从而将错误的状态应用到错误的组件上; 2. 性能下降, 缺少稳定的 key, 使得 Diff 算法需要更复杂的判断，可能导致更多的节点被重新渲染，影响性能。3. 状态丢失, 在组件内有状态（例如输入框的内容、动画状态等）的情况下，如果使用索引匹配，列表重新排序或数据变化时可能导致状态错误地复用或丢失。

5.2 React Diff 为什么不能用随机数做 key？​

随机数 Key 意味着它是一个不稳定的 Key, 会产生无序性，可能会导致所有的 key 都匹配不上, 然后舍弃掉之前所有构建出来的 fiber 节点, 再重新创建新的节点。

5.3 React Diff 最好不要使用数组的下标做为 key ?​

如果使用数组的下标作为 key, 默认使用索引匹配, 如果没有提供 key, React 会退而求其次, 使用节点在数组中的索引来作为默认 key。这种方式在静态列表中可能没问题，但在列表项频繁增删、排序或动态变化的场景下, 会带来一些问题: 1. 匹配不准确, 当数据项的顺序发生变化或插入新的数据时, 使用索引可能会导致 React 错误地匹配节点, 从而将错误的状态应用到错误的组件上; 2. 性能下降, 缺少稳定的 key, 使得 Diff 算法需要更复杂的判断，可能导致更多的节点被重新渲染，影响性能。3. 状态丢失, 在组件内有状态（例如输入框的内容、动画状态等）的情况下，如果使用索引匹配，列表重新排序或数据变化时可能导致状态错误地复用或丢失。

5.4 React Diff 为什么不采用双端对比来优化呢?​

Fiber 链表的优势与限制, React 在运行前, 将 JSX 全部转换为 ReactElement 虚拟 DOM, 随后在 Render BeginWork 递阶段 会生成 Fiber 树, 具有两种数据结构。由于 React 具有两种结构, 在进行 Diff 对比时, 通过对比 ReactElement 数组 与 Fiber 单链表, Fiber 结构方便快速访问父、子和兄弟节点, 但因为没有直接引用前一个节点, 只能从左到右依次比对, 无法实现双端对比。 因此, Diff 算法在处理移动操作时必须依赖额外的 Map 进行优化查找，这也是算法中最复杂的部分。

5.5 React Diff Vs Vue2.0 Diff Vs Vue3.0 Diff​

React: 在进行 Diff 对比时, 通过对比 ReactElement 数组 与 Fiber 单链表, Fiber 结构方便快速访问父、子和兄弟节点, 但因为没有直接引用前一个节点, 只能从左到右依次比对, 无法实现双端对比。 从头到尾逐一对比新旧节点, 处理第一轮循环剩余的节点, React 需要把 Old Fiber 处理 old Fiber Key - to - Old Fiber 的 Map 数据结构。判断移动的逻辑为: 通过新节点的 key 在 Map 中查找是否存在对应的旧 Fiber。如果找到, 就说明这个节点理论上可以复用。每个旧节点都有一个原始位置索引（oldIndex）, React 会将这个 oldIndex 与之前记录的 lastPlacedIndex 进行比较, 如果 oldIndex >= lastPlacedIndex, 说明这个节点在旧列表中的顺序保持相对正确, 不需要移动。然后更新 lastPlacedIndex 为当前 oldIndex。如果 oldIndex < lastPlacedIndex, 则说明该节点在旧列表中的位置比前面复用的节点要早, 意味着新节点在当前的位置上与旧节点的顺序已经发生逆转, 即需要进行移动操作。React 因为是通过 JSX 进行编译的，是无法进行静态节点分析的，所以 React 在对静态节点处理这一块是要逊色的。

Vue2.0: 在进行 Diff 对比时, 通过对比新旧 VNode 数组。进行双端对比, 先进行首尾、首首、尾尾部分的处理，然后再进行中间复杂部分的处理。处理第一轮循环剩余的节点, 剩余旧节点构建 oldVNode.key - to - oldVNode.index 的 Map 映射结构。Vue 是通过 template 模版进行编译的，所以在编译的时候可以很好对静态节点进行分析然后进行打补丁标记，然后在 Diff 的时候，Vue2 是判断如果是静态节点则跳过过循环对比

Vue3.0: 在进行 Diff 对比时, 通过对比新旧 VNode 数组。进行双端对比, 先处理首尾部分，然后再处理中间复杂部分。处理第一轮循环剩余的节点, 构建 newVNode.key - to - newVNode.index 的剩余节点映射 Map。判断移动的逻辑为: 遍历旧节点, 尝试找到在新节点中的位置, 如果旧节点在新节点中找不到，则卸载它, 如果能找到，则记录其在新数组中的位置到一个数组中, 利用 最长递增子序列 算法从记录的索引数组中找出最长递增序列, 那些节点在新节点中的位置如果是递增的，则不需要移动, 其余需要移动。由于 Vue 是通过 template 模版进行编译的，所以在编译的时候可以很好对静态节点进行分析然后进行打补丁标记，然后在 Diff 的时候, Vue3 则是把整个静态节点进行提升处理，Diff 的时候是不过进入循环的，所以 Vue3 比 Vue2 的 Diff 性能更高效。

React、Vue2.0、Vue3.0 都采用了 Map 来优化移动检测, 计算查找和比较, 来高效判断哪些节点需要移动。

参考资料​

为什么 React 的 Diff 算法不采用 Vue 的双端对比算法？