一文讲清楚React的diff算法

一文讲清楚React的diff算法

1. 为什么需要diff

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

2. diff的具体策略和实现

• React将传统的时间复杂度为O(n^{3)循环递归遍历VDOM优化为时间复杂度为O(n}1)的diff算法，主要通过一下三个策略
• 1. 节点的跨层级移动忽略不计，针对TreeDiff优化
• 2. 相同类的两个组件会生成相似的树状结构，不同类的两个组件将会生成不同的树状结构，针对Component Diff进行优化
• 3. 同一层的节点，通过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：新的组件类型不在旧集合中，即全新的节点，需要对新节点进行插入操作。
• 2. MOVE_EXISTING：旧集合中有新组件类型，且 element 是可更新的类型，generateComponent 已调用 recevieComponent，这种情况下 prevChild = nextChild，这时候就需要做移动操作，可以复用以前的 DOM 节点。
• 3. 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])
      );
    }
  }
}