# React Diff 算法

一个 React 组件的渲染主要经历两个阶段，diff 算法发生在调度阶段。

调度阶段（Reconciler）：用新的数据生成一棵新的树，然后通过 Diff 算法，遍历旧的树，快速找出需要更新的元素，放到更新队列中去，得到新的更新队列。
渲染阶段（Renderer）：遍历更新队列，通过调用宿主环境的 API，实际更新渲染对应的元素。宿主环境如 DOM，Native 等。

第一次渲染不需要 diff，直接 vdom 转 fiber。再次渲染的时候，会产生新的 vdom，这时候要和之前的 fiber 做下对比，决定怎么产生新的 fiber。

# Diff 算法的特点

Diff 算法具有以下特点：

分层，同级比较：React 将整个 DOM 树分为多个层级，然后逐层比较，只比较同一层级的节点，从而减少比较的复杂度。同级比较时按照从左到右的顺序进行比较。
key 属性：React 使用 key 属性来标识节点的唯一性，从而在比较时能够快速定位到需要更新的节点。

# key

key 是 React 中用于标识节点的唯一性的一种机制。在 Diff 算法中，React 使用 key属性来快速定位到需要更新的节点，从而提高 Diff 算法的性能。

我们经常强调在列表渲染中要使用 key 来提高性能，那么 key 到底是怎么帮助我们识别的呢？看一个简单的例子：

<div>
	<p key="a">a</p>
	<span key="b">b</span>
</div>

<div>
	<span key="b">b</span>
	<p key="a">a</p>
</div>

在上面的例子中，React 在比较两个 JSX 对象时，会按照从左到右的顺序进行比较。那么两个 JSX 在比较第一个子节点时，发现 p 和 span 的元素类型不同，因此会销毁旧树并创建新树。

但是由于他们有 key，React 会认为他们只是位置发生了变化，而不是元素类型发生了变化，因此会复用旧树中的节点，只是改变他们的位置。

# Diff 流程两轮遍历

第一轮遍历，处理可复用的节点。
第二轮遍历，遍历第一轮剩下的 fiber。

# 第一轮遍历

对比新旧节点，如果可以复用就处理下一个节点，否则就结束遍历。结束遍历时如果还有旧的节点没处理完，那就进行第二次遍历。

# 第二轮遍历

把第一轮剩下的老 fiber 节点放到 map 里，然后遍历新的 vdom 节点，从 map 中能找到的话，就是可复用，移动过来打上更新的标记。遍历完之后，剩下的老 fiber 节点删掉，剩下的新 vdom 新增。

# 举例

<!-- 更新前 -->
<ul>
	<li key="a">a</li>
	<li key="b">b</li>
	<li key="c">c</li>
	<li key="d">d</li>
</ul>
<!-- 更新后 -->
<ul>
	<li key="a">a</li>
	<li key="c">c</li>
	<li key="b">b</li>
	<li key="e">e</li>
</ul>

对比新的 vdom 和老的 fiber，发现 A 是可以复用的。继续向后遍历发现 C 不可复用，所以结束第一轮遍历，进入第二轮遍历。把剩下的老 fiber 节点 b, c, d 放到 map 里，然后遍历新的 vdom 节点，从 map 中能找到 b 和 c，则代表可复用，移动过来打上更新的标记。剩下的 d 删除，e 为新增。

← React 版本