React虚拟DOM的 Diff原理全解析

Diff算法思维图

设计思想概述

对一颗树进行更新，如果利用循环递归的方法对每一个节点进行比较，那算法的复杂度可以达到 O(n^3) 简单来说就是一颗有 1000 节点的树，要对比 10亿 次，还不包括比对类型、属性等节点的细节，再好的 CPU 也难以迅速的算出结果

但 React 说它的 Diff 算法能够达到 O(n)

其实它就是偷工减料没有老老实实的对比每一个节点，有一套自己的方法论：

• 永远只比较同层节点，不会跨层级比较节点

• 不同的两个节点产生不同的树，把原来的节点以及它的后代全部干掉，换成新的

• 通过 key 值指定哪些元素是相同的

执行规则 流程

• 元素类型不相同时

  • 直接将原 VDOM 树上该节点以及该节点下所有的后代节点全部删除，然后替换为新 VDOM 树上同一位置的节点，当然这个节点的后代节点也全都跟着过来了

• 元素类型相同时

  • 都是 DOM 节点：

    • 通过对比两个元素，React 知道需要修改 DOM 元素上的哪些属性

    • 处理完该节点之后，继续对子节点进行递归

  • 都是组件元素：

    • 组件实例保持不变，更新 props

    • 调用 componentWillReceiveProps() 方法，然后通过 shouldComponentUpdate 返回值决定是否调用 render 方法

    • 处理完该节点之后，继续对子节点进行递归

  • 特殊情况：遍历子元素列表

    • 引入 key 值：

<ul>
  <li>1</li>
  <li>2</li>
</ul>

在列表末尾插入一个元素

<ul>
  <li>1</li>
  <li>2</li>
  <li>3</li>
</ul>

这样 React 会先匹配两个对应的树，最后插入第三个元素，没有任何问题

但是 如果在头部插入呢 ？

<ul>
  <li>3</li>
  <li>1</li>
  <li>2</li>
</ul>

此时前两个元素和原来都不一样，第三个元素被当作新增的节点，明明只需要更新一个节点，现在需要更新三个，这样的情况效率是非常低的

所以，React 引入了 key 值的概念

<ul>
  <li key="first">1</li>
  <li key="second">2</li>
</ul>

插入数据之后变成：

<ul>
  <li key="third">3</li>
  <li key="first">1</li>
  <li key="second">2</li>
</ul>

现在 React 通过 key 得知 1 和 2 原来是存在的，现在只是换了位置，因此就不需要更新整个节点了，只需要移动位置即可，大大提高效率

选取 key 值的问题

key 选取的原则：不需要全局唯一，但是必须列表中保持唯一

如果使用 数组元素的下标 作为 key 值，在元素顺序不改变的情况下是没有问题的，但一旦顺序发生改变，diff 效率就可能骤然下降 因为在数组中间插入一条数据，那么插入数组之后的数组元素下标都会发生改变，即 key 值改变，那么后面的节点都得更新

不要使用数组下标做 key 值的根本原因在于：数组下标值不稳定，修改顺序就会修改当前 key