一文讲清楚React的diff算法

发布于:2025-07-10 ⋅ 阅读:(16) ⋅ 点赞:(0)

一文讲清楚React的diff算法

1. 为什么需要diff

  • 首先,diff只有在更新的时候才会有,首次渲染是全量渲染,不存在对比一说
  • 那为什么更新的时候需要diff呢,我们知道React通过VDOM减少对DOM的操作,但是当我们state或者props变化的时候,不能只要有变化就重新生成整个DOM吧,我们最好是知道哪变了,变啥了,影不影响目前的渲染,要不要全部重新渲染还是是渲染部分就可以
  • diff算法就是干这个事

2. diff的具体策略和实现

  • React将传统的时间复杂度为O(n3)循环递归遍历VDOM优化为时间复杂度为O(n1)的diff算法,主要通过一下三个策略
    1. 节点的跨层级移动忽略不计,针对TreeDiff优化
    1. 相同类的两个组件会生成相似的树状结构,不同类的两个组件将会生成不同的树状结构,针对Component Diff进行优化
    1. 同一层的节点,通过key进行区分,针对Element Diff进行优化

2.1 Tree Diff

  • 只删除创建不移动
  • 简单点来说就是同一层级上,旧节点有子节点A,新节点没有,但是新节点的子节点B下面有A节点,这时候不会把旧的节点A移动到D节点下面,而是直接在B节点下面新建子节点A,并删除原来的子节点A
    在这里插入图片描述

2.2 Component Diff

  • 对比前后,如果组件的类型相同,则继续下走
  • 如果组件类型不同,删除旧组件,创建新组建
    在这里插入图片描述

2.3 Element Diff

  • Element Diff 对应三种节点操作,分别为 INSERT_MARKUP(插入)、MOVE_EXISTING(移动) 和 REMOVE_NODE(删除)。

    1. INSERT_MARKUP:新的组件类型不在旧集合中,即全新的节点,需要对新节点进行插入操作。
    1. MOVE_EXISTING:旧集合中有新组件类型,且 element 是可更新的类型,generateComponent 已调用 recevieComponent,这种情况下 prevChild = nextChild,这时候就需要做移动操作,可以复用以前的 DOM 节点。
    1. REMOVE_NODE:旧组件类型,在新集合里也有,但对应的 element 不同则不能直接复用和更新,需要执行删除操作,或者旧组件不在新集合里的,也需要执行删除操作。
      在这里插入图片描述
  • index: 新集合的遍历下标。

  • oldIndex:当前节点在⽼集合中的下标

  • maxIndex:在新集合访问过的节点中,其在⽼集合的最⼤下标

  • 如果当前节点在新集合中的位置⽐⽼集合中的位置靠前的话,是不会影响后续节点操作的,这⾥这时候
    被动字节不⽤动
    操作过程中只⽐较oldIndex和maxIndex,规则如下:

  • 当oldIndex>maxIndex时,将oldIndex的值赋值给maxIndex

  • 当oldIndex=maxIndex时,不操作

  • 当oldIndex<maxIndex时,将当前节点移动到index的位置
    diff 过程如下:

  • 节点B:此时 maxIndex=0,oldIndex=1;满⾜ maxIndex< oldIndex,因此B节点不动,此时
    maxIndex= Math.max(oldIndex, maxIndex),就是1

  • 节点A:此时maxIndex=1,oldIndex=0;不满⾜maxIndex< oldIndex,因此A节点进⾏移动操作,
    此时maxIndex= Math.max(oldIndex, maxIndex),还是1

  • 节点D:此时maxIndex=1, oldIndex=3;满⾜maxIndex< oldIndex,因此D节点不动,此时
    maxIndex= Math.max(oldIndex, maxIndex),就是3

  • 节点C:此时maxIndex=3,oldIndex=2;不满⾜maxIndex< oldIndex,因此C节点进⾏移动操作,
    当前已经⽐较完了
    当ABCD节点⽐较完成后, diff 过程还没完,还会整体遍历⽼集合中节点,看有没有没⽤到的节点,
    有的话,就删除

2.4 diff算法源码

_updateChildren: function(nextNestedChildrenElements, transaction, context) {
  // 存储之前渲染的子元素
  var prevChildren = this._renderedChildren;
  // 存储已经移除的子元素
  var removedNodes = {};
  // 存储将要挂载的子元素
  var mountImages = [];
 
  // 获取新的子元素数组,并执行子元素的更新
  var nextChildren = this._reconcilerUpdateChildren(
    prevChildren,
    nextNestedChildrenElements,
    mountImages,
    removedNodes,
    transaction,
    context
  );
 
  // 如果新旧子元素都不存在,直接返回
  if (!nextChildren && !prevChildren) {
    return;
  }
 
  var updates = null;
  var name;
  var nextIndex = 0;
  var lastIndex = 0;
  var nextMountIndex = 0;
  var lastPlacedNode = null;
 
  for (name in nextChildren) {
    if (!nextChildren.hasOwnProperty(name)) {
      continue;
    }
    var prevChild = prevChildren && prevChildren[name];
    var nextChild = nextChildren[name];
    if (prevChild === nextChild) {
      // 同一个引用,说明是使用的同一个component,需要进行移动操作
      // 移动已有的子节点
      // 注意:这里根据nextIndex, lastIndex决定是否移动
      updates = enqueue(
        updates,
        this.moveChild(prevChild, lastPlacedNode, nextIndex, lastIndex)
      );
 
      // 更新lastIndex
      lastIndex = Math.max(prevChild._mountIndex, lastIndex);
      // 更新component的.mountIndex属性
      prevChild._mountIndex = nextIndex;
 
    } else {
      if (prevChild) {
        // 更新lastIndex
        lastIndex = Math.max(prevChild._mountIndex, lastIndex);
      }
 
      // 添加新的子节点在指定的位置上
      updates = enqueue(
        updates,
        this._mountChildAtIndex(
          nextChild,
          mountImages[nextMountIndex],
          lastPlacedNode,
          nextIndex,
          transaction,
          context
        )
      );
 
      nextMountIndex++;
    }
 
    // 更新nextIndex
    nextIndex++;
    lastPlacedNode = ReactReconciler.getHostNode(nextChild);
  }
 
  // 移除掉不存在的旧子节点,和旧子节点和新子节点不同的旧子节点
  for (name in removedNodes) {
    if (removedNodes.hasOwnProperty(name)) {
      updates = enqueue(
        updates,
        this._unmountChild(prevChildren[name], removedNodes[name])
      );
    }
  }
}

网站公告

今日签到

点亮在社区的每一天
去签到