聊聊React中的diff算法

React作为一个MVVM框架，它相当于一个中间桥梁，帮开发者处理最繁琐的DOM相关的操作，开发者只需要定义业务逻辑和数据部分，当需要更新时，React 会帮开发者将最新的改变反应到DOM节点上。那React到底是如何判断哪些DOM需要被更新的呢？这涉及到其中的一个核心算法：diff算法。

什么是diff算法

diff，是指difference，顾名思义，它是一种比较算法。

在React中，每当 props 或 state 更改时，就会触发组件的 render 方法，render 方法会返回一颗元素树，React 会对这两颗元素树进行比较，来决定如何高效更新UI。

为了找出这两颗元素树之间的差异，React 借鉴了传统的diff 算法。然而，即使使用最优的算法，该算法的复杂程度仍为 O(n³)，其中 n 是树中元素的数量。

如果在React中使用该算法，那么展示100个元素则需要100万次的比较。这个开销实在是太过高昂。于是React在以下两个假设的基础之上提出了一套O(n)的启发式算法：

• 两个不同类型的元素会产生出不同的树；
• 开发者可以使用key属性标识哪些子元素在不同的渲染中可能是不变的。

根据这两个规律，React将算法从O(n³)优化成了O(n)。

和Virtual DOM的关系

Virtual DOM是一个JavaScript对象，比如，如下的一个对象:

const virtualBtn = {
    type: 'button',
    props: {
        className: 'btn btn-blue',
        children: [
            {
                type: 'em',
                props: {
                    children: 'Confirm'
                }
            }
        ]
    }
}

在通过React转换后，对应到页面中的真实DOM节点是：

<button class="btn btn-blue">
    <em>Confirm</em>
</button>

在React框架中，diff算法实际比较的是Virtual DOM，而不是真实的DOM节点，每当数据更新时，diff算法就对前后两次的Virtual DOM进行比较，对发生变化的部分做批量更新。

和key的关系

在React中展示数组等列表数据时，通常需要给每列数据指定一个唯一的key，那为啥要指定这个key属性呢？如果不指定的话，会有啥问题呢？这和diff算法有关系吗？

我们来看一个例子，在如下的列表中：

有ABCD四个节点，由于某种原因，需要重新对这些节点进行排序，最后，这些节点的顺序变成了BADC的顺序。如果指定了key的话，diff算法通过key来发现新旧集合中的节点都是相同的节点，因此无需进行节点的删除和创建，只需要将旧集合中的节点位置进行移动即可，所以，最后的操作是：B、D不做任何操作，A、C进行移动操作。

而如果没有指定key的话，那么diff算法就无法判断哪些节点是可以重复使用的，就会重新创建这些已有的节点，造成性能上的浪费。

因此，在我们实际开发过程中，对于需要循环展示列表的情况，请记得给每一项都指定一个唯一的key，这对列表的性能有着重大的意义。

参考

• Reconciliation