React diff

程序员文章站 2022-06-15 20:13:13

...

传统diff算法

传统diff算法通过循环递归对节点进行依次对比，效率低下，算法复杂度达到 O(n^3)，其中 n 是树中节点的总数

let result = [];
const diffLeafs = function (beforeLeaf, afterLeaf) {
    // 获取较大节点树的长度
    let count = Math.max(beforeLeaf.children.length, afterLeaf.children.length);
    // 循环遍历
    for (let i = 0; i < count; i++) {
        const beforeTag = beforeLeaf.children[i];
        const afterTag = afterLeaf.children[i];
        if (beforeTag === undefined) {
            result.push({ type: "add", element: afterTag });
        } else if (afterTag === undefined) {
            esult.push({ type: "remove", element: beforeTag });
        } else if (beforeTag.tagName !== afterTag.tagName) {
            result.push({ type: "remove", element: beforeTag });
            result.push({ type: "add", element: afterTag });
        } else if (beforeTag.innerHTML !== afterTag.innerHTML) {// 节点不变而内容改变时，改变节点
            if (beforeTag.children.length === 0) {
                result.push({
                    type: "changed",
                    beforeElement: beforeTag,
                    afterElement: afterTag,
                    html: afterTag.innerHTML
                });
            } else {
                diffLeafs(beforeTag, afterTag);
            }
        }
    }
    return result;
}

http://grfia.dlsi.ua.es/ml/algorithms/references/editsurvey_bille.pdf

若我们在React中使用，展示1000个元素则需要进行10亿次的比较。这操作太过昂贵，相反，React基于两点假设，实现了一个启发的O(n)算法：

两个不同类型的元素将产生不同的树。
通过渲染器附带key属性，开发者可以示意哪些子元素可能是稳定的。

React Reconciliation(一致性比较)

1. 元素类型不相同

无论什么时候，当根元素类型不同时，React 将会销毁原先的树并重写构建新的树。从 <a> 到 <img> ，或者从 <Article> 到 <Comment> ，从<Button> 到 <div> – 这些都将导致全部重新构建。

当销毁原先的树时，之前的 DOM 节点将销毁。实例组件执行 componentWillUnmount() 。当构建新的一个树，新的 DOM 节点将会插入 DOM 中。组件将会执行 componentWillMount() 以及 componentDidMount()。与之前旧的树相关的 state 都会丢失。

根节点以下的任何组件都会被卸载(unmounted)，其 state(状态)都会丢失。例如，当比较:

<div>
  <Counter />
</div>

<span>
  <Counter />
</span>

当一个节点从div变成span时，简单的直接删除div节点，并插入一个新的span节点。如果该删除的节点之下（<div>）有子节点(<Counter>)，那么这些子节点也会被完全删除，它们也不会用于后面的比较,这也是算法复杂能够降低到O（n）的原因。即：逐层进行节点比较

React diff

React只会对相同颜色方框内的DOM节点进行比较，即同一个父节点下的所有子节点。当发现节点已经不存在，则该节点及其子节点会被完全删除掉，不会用于进一步的比较。这样只需要对树进行一次遍历，便能完成整个DOM树的比较。

2.DOM元素类型相同

当比较两个相同类型的 React DOM 元素时，React 检查它们的属性（attributes），保留相同的底层 DOM 节点，只更新反生改变的属性（attributes）。例如：

<div className="before" title="stuff" />

<div className="after" title="stuff" />

通过比较两个元素，React 会仅修改底层 DOM 节点的 className 属性。

当更新 style属性，React 也会仅仅只更新已经改变的属性，例如:

<div style={{color: 'red', fontWeight: 'bold'}} />

<div style={{color: 'green', fontWeight: 'bold'}} />

当React对两个元素进行转化的时候，仅会修改color，而不会修改 fontWeight 。

在处理完当前 DOM 节点后，React 会递归处理子节点。

3. 相同类型的组件

当一个组件更新的时候，组件实例保持不变，以便在渲染中保持state。React会更新组件实例的属性来匹配新的元素，并在元素实例上调用 componentWillReceiveProps() 和 componentWillUpdate()。

接下来， render() 方法会被调用并且diff算法对上一次的结果和新的结果进行递归。

子元素递归
默认情况下，当递归一个 DOM 节点的子节点时，React 只需同时遍历所有的孩子基点同时生成一个改变当它们不同时。

例如，当给子元素末尾添加一个元素，在两棵树之间转化中性能就不错:

<ul>
  <li>first</li>
  <li>second</li>
</ul>

<ul>
  <li>first</li>
  <li>second</li>
  <li>third</li>
</ul>

React 会比较两个 <li>first</li>树与两个 <li>second</li> 树，然后插入 <li>third</li>树。

如果在开始处插入一个节点也是这样简单地实现，那么性能将会很差。例如，在下面两棵树的转化中性能就不佳。

<ul>
  <li>Duke</li>
  <li>Villanova</li>
</ul>

<ul>
  <li>Connecticut</li>
  <li>Duke</li>
  <li>Villanova</li>
</ul>

React 将会改变每一个子节点而没有意识到需要保留 <li>Duke</li> 和 <li>Villanova</li> 两个子树。这种低效是一个问题。

Keys
为了解决这个问题，React 支持一个 key 属性（attributes）。当子节点有了 key ，React 使用这个 key 去比较原来的树的子节点和之后树的子节点。例如，添加一个 key 到我们上面那个低效的例子中可以使树的转换变高效：

<ul>
  <li key="2015">Duke</li>
  <li key="2016">Villanova</li>
</ul>

<ul>
  <li key="2014">Connecticut</li>
  <li key="2015">Duke</li>
  <li key="2016">Villanova</li>
</ul>

现在 React 知道有’2014’ key 的元素是新的， key为’2015’ 和’2016’的两个元素仅仅只是被移动而已。

实际上，找到一个 key 通常不难。你所将要展示的组件一般都有唯一的ID，因此你的数据可以作为key的来源：
<li key={item.id}>{item.name}</li>
当情况不同时，你可以添加一个新的ID 属性（property）到你的数据模型，或者是hash 一部分内容生成一个key。这个key 需要在它的兄弟节点中是唯一的就可以了，不需要是全局唯一。

React Diff

当节点处于同一层级时，React diff 提供了三种节点操作，分别为：INSERT_MARKUP（插入）、MOVE_EXISTING（移动）和 REMOVE_NODE（删除）。

INSERT_MARKUP，新的 component 类型不在老集合里，即是全新的节点，需要对新节点执行插入操作。
MOVE_EXISTING，在老集合有新 component 类型，且 element 是可更新的类型，generateComponentChildren 已调用 receiveComponent，这种情况下 prevChild=nextChild，就需要做移动操作，可以复用以前的 DOM 节点。
REMOVE_NODE，老 component 类型，在新集合里也有，但对应的 element 不同则不能直接复用和更新，需要执行删除操作，或者老 component 不在新集合里的，也需要执行删除操作。

_updateChildren: function(nextNestedChildrenElements, transaction, context) {
  var prevChildren = this._renderedChildren;
  var nextChildren = this._reconcilerUpdateChildren(
    prevChildren, nextNestedChildrenElements, transaction, context
  );
  if (!nextChildren && !prevChildren) {
    return;
  }
  var name;
  var lastIndex = 0;//访问过的节点在老集合中最大的位置
  var nextIndex = 0;//节点在新集合中的位置
  for (name in nextChildren) {
    if (!nextChildren.hasOwnProperty(name)) {
      continue;
    }
    var prevChild = prevChildren && prevChildren[name];
    var nextChild = nextChildren[name];
    //如果存在相同节点，则进行移动操作
    if (prevChild === nextChild) {
      this.moveChild(prevChild, nextIndex, lastIndex);
      // 更新老集合中访问的最大位置
      lastIndex = Math.max(prevChild._mountIndex, lastIndex);
      prevChild._mountIndex = nextIndex;
    } else {
      if (prevChild) {
        // 更新老集合中访问的最大位置
        lastIndex = Math.max(prevChild._mountIndex, lastIndex);
        // 删除节点
        this._unmountChild(prevChild);
      }
      // 初始化并创建节点
      this._mountChildAtIndex(
        nextChild, nextIndex, transaction, context
      );
    }
    nextIndex++;
  }
  for (name in prevChildren) {
    if (prevChildren.hasOwnProperty(name) &&
        !(nextChildren && nextChildren.hasOwnProperty(name))) {
      // 删除节点      
      this._unmountChild(prevChildren[name]);
    }
  }
  this._renderedChildren = nextChildren;
},
// 移动节点
moveChild: function(child, toIndex, lastIndex) {
  //如果新集合中当前访问的节点比 lastIndex 大，说明当前访问节点在老集合中就比上一个节点位置靠后，则该节点不会影响其他节点的位置，因此不用添加到差异队列中，即不执行移动操作，只有当访问的节点比 lastIndex 小时，才需要进行移动操作
  if (child._mountIndex < lastIndex) {
    this.prepareToManageChildren();
    enqueueMove(this, child._mountIndex, toIndex);
  }
},
// 创建节点
createChild: function(child, mountImage) {
  this.prepareToManageChildren();
  enqueueInsertMarkup(this, mountImage, child._mountIndex);
},
// 删除节点
removeChild: function(child) {
  this.prepareToManageChildren();
  enqueueRemove(this, child._mountIndex);
},

_unmountChild: function(child) {
  this.removeChild(child);
  child._mountIndex = null;
},

_mountChildAtIndex: function(
  child,
  index,
  transaction,
  context) {
  var mountImage = ReactReconciler.mountComponent(
    child,
    transaction,
    this,
    this._nativeContainerInfo,
    context
  );
  child._mountIndex = index;
  this.createChild(child, mountImage);
},

思考：diff对比过程是怎样的？

pre: A - B - C - D
next: B - E - C - A

lastIndex = 0,nextIndex = 0
next中B，判断得知pre中含有B
此时：pre.B._mountIndex = 1,lastIndex = 0, => 不对 B 进行移动操作
lastIndex = 1, pre.B._mountIndex = 0
lastIndex = 1, nextIndex = 1
next中E，判断得知pre中没有E
创建E
lastIndex = 1, E._mountIndex = 1
lastIndex = 1, nextIndex = 2
next中C，判断得知pre中含有C
此时： pre.C._mountIndex = 2, lastIndex = 1, => 不对 C 进行移动操作
lastIndex = 2, pre.C._mountIndex = 2
lastIndex = 2, nextIndex = 3
next中A，判断得知pre中含有A
此时： pre.A._mountIndex = 0, lastIndex = 2, => 对 A 进行移动操作
lastIndex = 2, pre.c._mountIndex = 3
对pre集合进行遍历
新集合中没有但老集合中仍存在的节点 D

上一篇： HashSet源码解析（基于JDK1.8）

下一篇： Android笔记-service启动过程分析：startService源码分析

React diff

传统diff算法

React Reconciliation(一致性比较)

1. 元素类型不相同

2.DOM元素类型相同

3. 相同类型的组件

React Diff

思考：diff对比过程是怎样的？

React diff算法的实现示例

详解开发react应用最好用的脚手架 create-react-app

react-navigation的超级大坑

基于React实现表单数据的添加和删除详解

浅谈React Native 传参的几种方式(小结)

前端笔记之React（八）上传&图片裁切

详解在React-Native中持久化redux数据

干货!教大家如何选择Vue和React

React-router中结合webpack实现按需加载实例

React简单介绍