# DOM Diff 算法

# 解释1

# 设计思考

在某一时间节点调用React的 render()方法，会创建一棵由 react元素组成的树。在下一次state或props 更新时，相同的render()方法会返回一棵不同的树。React需要基于这两棵树之间的差别来判断如何有效率的更新UI以保证当前UI与最新的树保持同步。

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

如果在 React 中使用了该算法，那么展示 1000 个元素所需要执行的计算量将在十亿的量级范围。这个开销实在是太过高昂。于是 React 在以下两个假设的基础之上提出了一套 O(n) 的启发式算法：

两个不同类型的元素会产生出不同的树；
可以通过 key prop 来暗示哪些子元素在不同的渲染下能保持稳定；

# 原理

diff算法可以简单都划分为三类：

对比不同类型的元素
对比相同类型的元素
对比同类型的组件元素

# 对比不同类型的元素

当根节点为不同类型的元素时，React 会拆卸原有的树并且建立起新的树

<div>
  <Counter />
</div>

<span>
  <Counter />
</span>

# 对比相同类型的元素

当比对两个相同类型的 React 元素时，React 会保留 DOM 节点，仅比对及更新有改变的属性

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

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

# 对比同类型的组件元素

当一个组件更新时，组件实例保持不变，这样state在跨越不同的渲染时保持一致。React 将更新该组件实例的 props 以跟最新的元素保持一致，并且调用该实例的 componentWillReceiveProps() 和 componentWillUpdate() 方法。之后会调用render方法，diff算法将在之前的结果和新的结果中进行递归。

# 优化

保证稳定dom结构有利于提升性能，不建议频繁真正的移除或者添加节点
对于同一类型组件合理使用shouldComponentUpdate()，应该避免结构相同类型不同的组件
在开发过程中，同层级的节点添加唯一key值可以极大提升性能，尽量减少将最后一个节点移动到列表首部的操作，当节点达到一定的数量以后或者操作过于频繁，在一定程度上会影响React的渲染性能。比如大量节点拖拽排序的问题。

# 解释2

# 策略

策略一：忽略Web UI中DOM节点跨层级移动；
策略二：拥有相同类型的两个组件产生的DOM结构也是相似的，不同类型的两个组件产生的DOM结构则不近相同
策略三：对于同一层级的一组子节点，通过分配唯一唯一id进行区分（key值）

在Web UI的场景下，基于以上三个点，React对tree diff、component diff、element diff进行优化，将普适diff的复杂度降低到一个数量级，保证了整体UI界面的构建性能！

# tree diff

基于策略一，React的做法是把DOM tree分层级，对于两个DOM tree只比较同一层次的节点，忽略DOM中节点跨层级移动操作，只对同一个父节点下的所有的子节点进行比较。如果对比发现该父节点不存在则直接删除该节点下所有子节点，不会做进一步比较，这样只需要对DOM tree进行一次遍历就完成了两个tree的比较。

# component diff

React应用是基于组件构建的，对于组件的比较优化侧重于以下几点：

同一类型组件遵从tree diff比较v-DOM树
不通类型组件，先将该组件归类为dirty component，替换下整个组件下的所有子节点
同一类型组件Virtual DOM没有变化，React允许开发者使用shouldComponentUpdate()来判断该组件是否进行diff，运用得当可以节省diff计算时间，提升性能

# element diff

对于同一层级的element节点，diff提供了以下3种节点操作

INSERT_MARKUP 插入节点：对全新节点执行节点插入操作
MOVE_EXISTING 移动节点：组件新集合中有组件旧集合中的类型，且element可更新，即组件调用了receiveComponent，这时可以复用之前的DOM，执行DOM移动操作
REMOVE_NODE 移除节点：此时有两种情况：组件新集合中有组件旧集合中的类型，但对应的element不可更新、旧组件不在新集合里面，这两种情况需要执行节点删除操作

# DOM Diff中的key有什么用

总结：是一种用空间换时间的方式，使用key能够对同一层级的同组子节点进行区分和标识，避免对比的时候频繁的创建新的元素

bad:

不使用key

old: A B C D
new: B A D C

结果：虽然仅仅只是元素的位置发生改变了，但是按照diff的规则(不使用key)，那么B A D C都会是重新创建的新的元素

使用key

old: A B C D
new: B A D C

结果：使用key后，diff算法会对元素和位置进行比较，仅移动小范围的元素即可达到高效的结果

# 使用局限

React的diff也有自己的不足之处，比如新旧集合元素全部可以复用，只是新集合中将旧集合最后一个元素放到了第一个位置，短板就会出现

ABCD -> DABC
A B C D
D A B C

比如按照React的diff算法，不是D移动一次，而是需要将A，B，C移动三次到最后

# 参考

← React 虚拟DOM React Event 事件 →