react 中的 diff 算法，通俗易懂的解读

2022 年 9 月 25 日
浙江
本文字数：3841 字
阅读完需：约 13 分钟

react 中的 diff 算法，通俗易懂的解读

diff 算法在前端面试中也算是一个高频考题了，那怎么给面试官一个满分解答呢？难道还是简单的说个“深度优先，同层级比较”吗？这太短小精悍了......!

好了，下面开始进入正题

单节点 diff

单节点 diff 就比较简单了，从同层级的老fiber节点中找出key值和type都相等的老节点，如果该老 fiber 节点存在，则复用他，然后删除剩余的节点，否则重新生成一个新的fiber节点（这也就意味着以这个节点为根的子树需要重新生成）。

下面我们来看看单节点diff的核心源码

function reconcileSingleElement(  returnFiber: Fiber,  currentFirstChild: Fiber | null,  element: ReactElement,  lanes: Lanes): Fiber {  const key = element.key;  let child = currentFirstChild;  // 遍历同层级的老fiber节点  while (child !== null) {    if (child.key === key) {      const elementType = element.type;      // 从老fiber节点中找出key和type都相同的节点，如果找到则将该节点复用，并删除多余的节点，退出循环      if (child.elementType === elementType) {        deleteRemainingChildren(returnFiber, child.sibling);        const existing = useFiber(child, element.props);        existing.ref = coerceRef(returnFiber, child, element);        existing.return = returnFiber;        return existing;      }      deleteRemainingChildren(returnFiber, child);      break;    } else {      // 如果该fiber节点没匹配上，则删除      deleteChild(returnFiber, child);    }    child = child.sibling;  }
  // 能走到这里就意味着无法从老fiber中匹配到key和type都相同的节点，无法复用，需要重新生成  const created = createFiberFromElement(element, returnFiber.mode, lanes);  created.return = returnFiber;  return created;}

复制代码

多节点 diff

重点来了，注意了啊，多节点才是精髓

多节点 diff 主要可以分为两轮循环，第一轮循环主要是新旧节点同位置对比，找到第一个无法复用的节点位置后，以最后一个可复用旧节点的位置作为后续作为判断节点是否需要重新插入的基准位置值（该值后续可能会变），然后跳出循环。

如果经历了第一轮循环后，会存在三种情况：

新节点已经遍历完成：删除剩余的老节点，结束多节点 diff
老节点遍历完成，新节点还为遍历完，将剩余的新节点逐一创建fiber节点，并标记为重新插入，然后结束 diff
老节点、新节点都没遍历完，这种情况就比较复杂，需要将剩余的老节点放入一个 map 中，然后开启第二轮循环；

第二轮循环：

本轮循环是遍历剩余的新节点，遍历时，新节点都从 map 中寻找有没有自己能复用的老节点（key 和 type 相同即可复用），如果 map 中存在就复用，然后将该老节点从 map 中移除，否则就重新生成。如果老节点被复用了，就会将该老节点原来所在的位置和第一轮循环确定的基准位置值比较，老节点的位置在基准位置值的左边时，说明复用该老节点的新节点需要重新插入，基准位置值不变；老节点的位置在基准位置值的右边时，说明复用该老节点的新节点无须移动，但是基准位置值需要更新为老节点的位置。

第二轮循环结束了，只需要将 map 中剩余的老节点标记为删除即可。

举个例子：（第三种情况）

目前页面上有 3 个 li，内容和 key 分别为 1、2、3（fiber树如下图所示）

现在我要让页面变成 3 个 li，内容和 key 分别是 1、3、2，其所对应的ReactElement结构为

[    {$$typeof: REACT_ELEMENT_TYPE, type: 'li', props: {children: 1}, key: 1, ...},    {$$typeof: REACT_ELEMENT_TYPE, type: 'li', props: {children: 3}, key: 3, ...},    {$$typeof: REACT_ELEMENT_TYPE, type: 'li', props: {children: 2}, key: 2, ...},]

复制代码

那么我们需要怎么做呢？

注意：diff 比较是老fiber与newChild（在这我就先把它叫新节点吧）的比较

首先定义一个lastPlacedIndex用来作为基准位置来判断旧节点是否需要移动，初始为 0，newIndex 代码新节点的索引
此时第一轮循环开始了，oldFiber 跟 newChild 进行比较，发现它们的 key 和 type 都相等，该节点可复用，而且 oldFiber 的位置并不在 lastPlaceIndex 的左边，无需重新插入，继续往下遍历
这个时候发现 oldFiber 的 key 值和 newChild 的 key 不想等，这意味着无法复用，第一轮循环结束。老节点和新节点都未遍历完成，需要开启第二轮循环了。
将剩余的老节点存入一个 map 中，如果老节点中存在 key 值，则将该 key 值作为 map 中的 key，没有就以老节点所在的位置作为 map 中的 key，该节点作为 map 中的值
第二轮循环开始，新节点存在 key 值，为 3，从 map 中寻在以 key 为 3 的值，发现 map 中存在该值，且该老节点的 key 和 type 都 newChild 相同，可以复用，然后将该老节点的位置(2)与基准位置值(0)对比，发现该老节点位置在基准位置的右边，复用该老节点的新节点无须移动，基准位置值更新为 2，最后从 map 中删除 key 为 3 的值
新节点存在 key 值，为 3，从 map 中寻在以 key 为 2 的值，发现 map 中存在该值，且该老节点的 key 和 type 都 newChild 相同，可以复用，然后将该老节点的位置(1)与基准位置值(2)对比，发现该老节点位置在基准位置的左边，复用该老节点的新节点需要重新插入，标记为 Placement，基准位置值不变，最后从 map 中删除 key 为 2 的值
此时新节点也已经遍历完成了，第二轮循环结束，将 map 中剩余的老节点标记为删除

下面来看下 react diff 代码片段的实现

function reconcileChildrenArray(  returnFiber: Fiber,  currentFirstChild: Fiber | null,  newChildren: Array<*>,  lanes: Lanes): Fiber | null {
  let resultingFirstChild: Fiber | null = null;  let previousNewFiber: Fiber | null = null;
  let oldFiber = currentFirstChild;  let lastPlacedIndex = 0;  let newIdx = 0;  let nextOldFiber = null;  // 第一轮遍历  for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {    // ...    nextOldFiber = oldFiber.sibling;    // 如果type和key相同则复用该fiber节点返回一个newFiber，否则返回null，然后跳出第一轮循环    const newFiber = updateSlot(      returnFiber,      oldFiber,      newChildren[newIdx],      lanes    );    if (newFiber === null) {      // ...      break;    }    if (oldFiber && newFiber.alternate === null) {      // 兜底操作，如果该newFiber不是复用来的，就将oldFiber标记为删除      deleteChild(returnFiber, oldFiber);    }    // 标记该newFiber是否需要重新插入    lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);    if (previousNewFiber === null) {      resultingFirstChild = newFiber;    } else {      previousNewFiber.sibling = newFiber;    }    previousNewFiber = newFiber;    oldFiber = nextOldFiber;  }
  // 第一轮循环结束，newChildren遍历完成，删除多余的oldFiber  if (newIdx === newChildren.length) {    // We've reached the end of the new children. We can delete the rest.    deleteRemainingChildren(returnFiber, oldFiber);    return resultingFirstChild;  }
  if (oldFiber === null) {    // 老fiber被遍历完了，但是newChildren还未遍历完，则需要生成fiber并标记为需要插入    for (; newIdx < newChildren.length; newIdx++) {      const newFiber = createChild(returnFiber, newChildren[newIdx], lanes);      if (newFiber === null) {        continue;      }      lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);      if (previousNewFiber === null) {        resultingFirstChild = newFiber;      } else {        previousNewFiber.sibling = newFiber;      }      previousNewFiber = newFiber;    }    return resultingFirstChild;  }
  // 将剩余的oldFiber存入map中，key=oldFiber.key||oldFiber.index  const existingChildren = mapRemainingChildren(returnFiber, oldFiber);
  // 遍历剩余的newChildren  for (; newIdx < newChildren.length; newIdx++) {    // 从map中查询是否有oldFiber可以复用，根据newChild.key||newIndex来查询，有则复用，没有则重新生成    const newFiber = updateFromMap(      existingChildren,      returnFiber,      newIdx,      newChildren[newIdx],      lanes    );    if (newFiber !== null) {      // 走到这里说明newFiber是生成而来的      if (newFiber.alternate !== null) {        // 从map中移除已经被复用的oldFiber        existingChildren.delete(newFiber.key === null ? newIdx : newFiber.key);      }      // 判断该节点是否需要移动      lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);      if (previousNewFiber === null) {        resultingFirstChild = newFiber;      } else {        previousNewFiber.sibling = newFiber;      }      previousNewFiber = newFiber;    }  }
  // 删除map中剩余的oldFiber  existingChildren.forEach((child) => deleteChild(returnFiber, child));
  return resultingFirstChild;}

复制代码

留个思考题？如果 diff 过程中，oldFibers 中有部分节点的 key 值相同，会造成什么问题呢？

发布于: 刚刚阅读数: 4

flyzz177

关注

还未添加个人签名 2021.12.07 加入

还未添加个人简介

发布

暂无评论

创作场景

react 中的 diff 算法，通俗易懂的解读

react 中的 diff 算法，通俗易懂的解读

单节点 diff

相关参考视频讲解：进入学习

多节点 diff

flyzz177

评论