关于react.js:React面试谈谈虚拟DOMDiff算法与Key机制

原生的 JS DOM 操作十分耗费性能，而 React 把实在原生 JS DOM 转换成了 JavaScript 对象。这就是虚构 Dom（Virtual Dom）

每次数据更新后，从新计算虚构 Dom，并和上一次生成的虚构 dom 进行比照，对发生变化的局部作批量更新。在此其中，React 提供了 componentShouldUpdate 生命周期来让开发者手动管制缩小数据变动后不必要的虚构 dom 比照，晋升性能和渲染效率。

原生 html 元素代码：

<div class="title">
      <span>Hello ConardLi</span>
      <ul>
        <li> 苹果 </li>
        <li> 橘子 </li>
      </ul>
</div>

在 React 可能存储为这样的 JS 代码：

const VitrualDom = {
  type: 'div',
  props: {class: 'title'},
  children: [
    {
      type: 'span',
      children: 'Hello ConardLi'
    },
    {
      type: 'ul',
      children: [{ type: 'li', children: '苹果'},
        {type: 'li', children: '橘子'}
      ]
    }
  ]
}

当咱们须要创立或更新元素时，React 首先会让这个 VitrualDom 对象进行创立和更改，而后再将 VitrualDom 对象渲染成实在 DOM；

当咱们须要对 DOM 进行事件监听时，首先对 VitrualDom 进行事件监听，VitrualDom 会代理原生的 DOM 事件从而做出响应。

虚构 DOM 的组成：

通过 JSX 或 React.createElement，React.createClass 等形式创立虚构元素和组件。即 ReactElementelement 对象，咱们的组件最终会被渲染成上面的构造：

type：元素的类型，能够是原生 html 类型（字符串），或者自定义组件（函数或 class）
key：组件的惟一标识，用于 Diff 算法，上面会具体介绍
ref：用于拜访原生 dom 节点
props：传入组件的 props，chidren 是 props 中的一个属性，它存储了以后组件的孩子节点，能够是数组（多个孩子节点）或对象（只有一个孩子节点）
owner：以后正在构建的 Component 所属的 Component
self：（非生产环境）指定以后位于哪个组件实例
_source：（非生产环境）指定调试代码来自的文件 (fileName) 和代码行数(lineNumber)

<div className="title">
      <span>Hello ConardLi</span>
      <ul>
        <li> 苹果 </li>
        <li> 橘子 </li>
      </ul>
</div>

将此 JSX 元素打印进去，证实虚构 DOM 实质就是 js 对象：

其中，在 jsx 中应用的原生元素标签，其 type 为标签名。而如果是函数组件或 class 组件，其 type 就是对应的 class 或 function 对象

React 须要同时保护两棵虚构 DOM 树：一棵示意以后的 DOM 构造，另一棵在 React 状态变更将要从新渲染时生成。React 通过比拟这两棵树的差别，决定是否须要批改 DOM 构造，以及如何批改。这种算法称作 Diff 算法。

这个算法问题有一些通用的解决方案，即生成将一棵树转换成另一棵树的最小操作数。然而，即便在最前沿的算法中，该算法的复杂程度为 O(n 3)，其中 n 是树中元素的数量。

如果在 React 中应用了该算法，那么展现 1000 个元素所须要执行的计算量将在十亿的量级范畴。这个开销切实是太过昂扬。于是 React 在以下两个假如的根底之上提出了一套 O(n) 的启发式算法：参考：前端 react 面试题具体解答

1：两个不同类型的元素会产生出不同的树；

2：开发者能够通过 key prop 来暗示哪些子元素在不同的渲染下能保持稳定；

React diff 算法大抵执行过程：

Diff 算法会对新旧两棵树做深度优先遍历，防止对两棵树做齐全比拟，因而算法复杂度能够达到 O(n)。而后给每个节点生成一个惟一的标记：

在遍历的过程中，每遍历到一个节点，就将新旧两棵树作比拟，并且 只对同一级别的元素进行比拟：

也就是只比拟图中用虚线连接起来的局部，把前后差别记录下来。

React diff 算法具体策略：

（1）tree diff

tree diff 次要针对的是 React dom 节点跨层级的操作。因为跨层级的 DOM 挪动操作较少，所以 React diff 算法的 tree diff 没有针对此种操作进行深刻比拟，只是简略进行了删除和创立操作

如图所示，A 节点（包含其子节点）整个被挪动到 D 节点下，因为 React 只会简略地思考同层级节点的地位变换，而对于不同层级的节点，只有创立和删除操作。

当根节点发现子节点中 A 隐没了，就会间接销毁 A；当 D 发现多了一个子节点 A，则会创立新的 A（包含子节点）作为其子节点。此时，diff 的执行状况：create A → create B → create C → delete A

由此能够发现，当呈现节点跨层级挪动时，并不会呈现设想中的挪动操作，而是以 A 为根节点的整个树被从新创立。这是一种影响 React 性能的操作，因而官网倡议不要进行 DOM 节点跨层级的操作。

基于上述起因，在开发组件时，保持稳定的 DOM 构造会有助于性能的晋升。例如，能够通过 CSS 暗藏或显示节点，而不是真正地移除或增加 DOM 节点

（2）component diff：

component diff 是专门针对更新前后的同一层级间的 React 组件比拟的 diff 算法：

如果是同一类型的组件，依照原策略持续比拟 Virtual DOM 树（例如持续比拟组件 props 和组件里的子节点及其属性）即可。
如果不是，则将该组件判断为 dirty component，从而替换整个组件下的所有子节点，即销毁原组件，创立新组件。
对于同一类型的组件，有可能其 Virtual DOM 没有任何变动，如果可能确切晓得这点，那么就能够节俭大量的 diff 运算工夫。因而，React 容许用户通过 shouldComponentUpdate()来判断该组件是否须要进行 diff 算法剖析

如图所示，当组件 D 变为组件 G 时，即便这两个组件构造类似，一旦 React 判断 D 和 G 是不同类型的组件，就不会比拟二者的构造，而是间接删除组件 D，从新创立组件 G 及其子节点。

尽管当两个组件是不同类型但构造类似时，diff 会影响性能，但正如 React 官网博客所言：不同类型的组件很少存在类似 DOM 树的状况，因而这种极其因素很难在理论开发过程中造成重大的影响

（3）element diff

element diff 是专门针对同一层级的所有节点（包含元素节点和组件节点）的 diff 算法。当节点处于同一层级时，diff 提供了 3 种节点操作，别离为 INSERT_MARKUP（插入）、MOVE_EXISTING（挪动）和 REMOVE_NODE（删除）。

咱们将虚构 dom 树中欲比拟的某同一层级的所有节点的汇合别离称为新汇合和旧汇合，则有以下策略：

INSERT_MARKUP：新汇合的某个类型组件或元素节点不存在旧汇合里，即全新的节点，须要对新节点执行插入操作。
MOVE_EXISTING：新汇合的某个类型组件或元素节点存在旧汇合里，且 element 是可更新的类型，generateComponent-Children 已调用 receiveComponent，这种状况下 prevChild=nextChild，就须要做挪动操作，能够复用以前的 DOM 节点。
REMOVE_NODE：旧汇合的某个组件或节点类型，在新汇合里也有，但对应的 element 不同则不能间接复用和更新，须要执行删除操作，或者旧组件或节点不在新汇合里的，也须要执行删除操作。

如图所示，旧汇合中蕴含节点 A、B、C 和 D，更新后的新汇合中蕴含节点 B、A、D 和 C（只是产生了地位变动，各自节点以及外部数据没有变动），此时 新旧汇合按程序进行逐个的 diff 差异化比照，发现 B != A，则创立并插入 B 至新汇合，删除旧汇合 A；以此类推，创立并插入 A、D 和 C，删除 B、C 和 D。

React 发现这类操作繁缛冗余，因为这些都是雷同的节点，但因为地位程序发生变化，导致须要进行繁冗低效的删除、创立操作，其实只有对这些节点进行地位挪动即可。

针对这一景象，React 提出优化策略：容许开发者对同一层级的同组子节点，增加惟一 key 进行辨别，。见上面 key 机制

（1）key 的作用

当同一层级的某个节点增加了对于其余同级节点惟一的 key 属性，当它在以后层级的地位产生了变动后。react diff 算法通过新旧节点比拟后，如果发现了 key 值雷同的新旧节点，就会执行挪动操作（而后仍然按原策略深刻节点外部的差别比照更新），而不会执行原策略的删除旧节点，创立新节点的操作。这无疑大大提高了 React 性能和渲染效率

（2）key 的具体执行过程

首先，对新汇合中的节点进行循环遍历 for (name in nextChildren)，通过惟一的 key 判断新旧汇合中是否存在雷同的节点 if (prevChild === nextChild)，如果存在雷同节点，则进行挪动操作，但在挪动前须要将以后节点在旧汇合中的地位与 lastIndex 进行比拟 if (child._mountIndex < lastIndex)，否则不执行该操作。

例子 1：同一层级的所有节点只产生了地位变动：

按新汇合中程序开始遍历

B 在新汇合中 lastIndex(相似浮标) = 0, 在旧汇合中 index = 1，index > lastIndex 就认为 B 对于汇合中其余元素地位无影响，不进行挪动，之后 lastIndex = max(index, lastIndex) = 1
A 在旧汇合中 index = 0，此时 lastIndex = 1, 满足 index < lastIndex, 则对 A 进行挪动操作，此时 lastIndex = max(Index, lastIndex) = 1
D 和 B 操作雷同，同(1)，不进行挪动，此时 lastIndex=max(index, lastIndex) = 3
C 和 A 操作雷同，同(2)，进行挪动，此时 lastIndex = max(index, lastIndex) = 3

上述论断中的挪动操作即对节点进行更新渲染，而不进行挪动则示意无需更新渲染

例子 2：同一层级的所有节点产生了节点增删和节点地位变动：

同下面那种情景，B 不进行挪动，lastIndex=1
新汇合中获得 E, 发现旧中不存在 E，在 lastIndex 处创立 E，lastIndex++
在旧汇合中取到 C，C 不挪动，lastIndex=2
在旧汇合中取到 A，A 挪动到新汇合中的地位，lastIndex=2
实现新汇合中所有节点 diff 后，对旧汇合进行循环遍历，寻找新汇合中不存在但就汇合中的节点(此例中为 D)，删除 D 节点。

（3）index 作为 key

react 中经常会用到通过遍历（如 Array.map）来在以后层级动静生成多个子节点的操作。这是常见的列表数据渲染场景。

React 官网倡议不要用遍历的 index 作为这种场景下的节点的 key 属性值。比方以后遍历的所有节点类型都雷同，其外部文本不同，在用 index 作 key 的状况下，当咱们对原始的数据 list 进行了某些元素的程序扭转操作，导致了新旧汇合中在进行 diff 比拟时，雷同 index 所对应的新旧的节点其文本不统一了，就会呈现一些节点须要更新渲染文本，而如果用了其余稳固的惟一标识符作为 key，则只会产生地位程序变动，无需更新渲染文本，晋升了性能。

此外应用 index 作为 key 很可能会存在一些出乎意料的显示谬误的问题：

{this.state.data.map((v,index) => <Item key={index} v={v} />)}
// 开始时：['a','b','c']=>
<ul>
    <li key="0">a <input type="text"/></li>
    <li key="1">b <input type="text"/></li>
    <li key="2">c <input type="text"/></li>
</ul>

// 数组重排 -> ['c','b','a'] =>
<ul>
    <li key="0">c <input type="text"/></li>
    <li key="1">b <input type="text"/></li>
    <li key="2">a <input type="text"/></li>
</ul>

下面实例中在数组从新排序后，key 对应的实例都没有销毁，而是从新更新。具体更新过程咱们拿 key= 0 的元素来阐明，数组从新排序后：

组件从新 render 失去新的虚构 dom；
新老两个虚构 dom 进行 diff，新老版的都有 key= 0 的组件，react 认为同一个组件，则只可能更新组件；
而后比拟其 children，发现内容的文本内容不同（由 a —>c)，而 input 组件并没有变动，这时触发组件的 componentWillReceiveProps 办法，从而更新其子组件文本内容;
因为组件的 children 中 input 组件没有变动，其又与父组件传入的任 props 没有关联，所以 input 组件不会更新(即其 componentWillReceiveProps 办法不会被执行)，导致用户输出的值不会变动。

（4）key 机制的毛病

如图所示，若新汇合的节点更新为 D、A、
B、C，与旧汇合相比只有 D 节点挪动，而 A、B、C 依然放弃原有的程序，实践上 diff 应该只需对 D 执行挪动操作，然而因为 D 在旧汇合中的地位是最大的，导致其余节点的 _mountIndex <lastIndex，造成 D 没有执行挪动操作，而是 A、B、C 全副挪动到 D 节点前面的景象.

在开发过程中，尽量减少相似将最初一个节点挪动到列表首部的操作。当节点数量过大或更新操作过于频繁时，这在肯定水平上会影响 React 的渲染性能。。

（5）key 应用注意事项：

如果遍历的列表子节是作为纯展现，而不波及到列表元素程序的动静变更，那应用 index 作为 key 还是没有问题的。
key 只是针对同一层级的节点进行了 diff 比拟优化，而跨层级的节点相互之间的 key 值没有影响
大部分状况下，通过遍历的同一层级的应用了 key 属性的元素节点其节点类型是雷同的（比方都是 span 元素或者同一个组件）。如果存在新旧汇合中，雷同的 key 值所对应的节点类型不同（比方从 span 变成 div），这相当于齐全替换了旧节点，删除了旧节点，创立了新节点。
如果新汇合中，呈现了旧汇合没有存在过的 key 值。例如某个节点的 key 之前为 1，当初为 100，但旧汇合中其余节点也没有应用 100 这个 key 值。阐明没产生过挪动操作，此时 diff 算法会对对应的节点进行销毁并从新创立。这在一些场景中会比拟有用（比方重置某个组件的状态）
key 值在比拟之前都会被执行 toString()操作，所以尽量不要应用 object 类型的值作为 key，会导致同一层级呈现 key 值雷同的节点。key 值反复的同一类型的节点或组件很可能呈现拷贝反复外部子元素的问题

关于react.js:React面试谈谈虚拟DOMDiff算法与Key机制

1. 虚构 dom

2.diff 算法

3. key 机制