reconciliation 和解，diff 算法

[shoutingwei]

Motivation When you use React, at a single point in time you can think of the render() function as creating a tree of React elements. On the next state or props update, that render() function will return a different tree of React elements. React then needs to figure out how to efficiently update the UI to match the most recent tree.

There are some generic solutions to this algorithmic problem of generating the minimum number of operations to transform one tree into another. However, the state of the art algorithms have a complexity in the order of O(n3) where n is the number of elements in the tree.

If we used this in React, displaying 1000 elements would require in the order of one billion comparisons. This is far too expensive. Instead, React implements a heuristic O(n) algorithm based on two assumptions:

Two elements of different types will produce different trees.

The developer can hint at which child elements may be stable across different renders with a key prop.

In practice, these assumptions are valid for almost all practical use cases.

动机 在你使用react时，你可以认为render创建了一棵React元素树。在下一次state和props更新时，render方法会返回一个不同的React元素树。React就需要搞清楚如何能高效地更新UI来匹配最近的树。 关于用最少的步骤将一棵树转换成另一棵树会有一些普遍的方法。然而，算法复杂度达到O(n3)。 如果我们使用React，展示了1000个元素，就需要十亿次的比较。这样的消耗太昂贵。React使用了一种启发式的算法。这个算法建立在两个假设之上： 首先，两个元素如果是不同类型的，就会产生不同的树。 其次，开发者可以从唯一的key属性上推测出子元素是否相同。

这两个假设在实践中基本都能适用。

The Diffing Algorithm When diffing two trees, React first compares the two root elements. The behavior is different depending on the types of the root elements.

Diffing算法

Elements Of Different Types Whenever the root elements have different types, React will tear down the old tree and build the new tree from scratch. Going from to , or from

to , or from to

- any of those will lead to a full rebuild.

不同类型的元素 不论什么时候根元素下会有不同的类型，react都会把旧的树去除并从头开始创建一棵新的树。从到,又或者从

到,或从

到

,这些都会使得彻底的重构。

When tearing down a tree, old DOM nodes are destroyed. Component instances receive componentWillUnmount(). When building up a new tree, new DOM nodes are inserted into the DOM. Component instances receive componentWillMount() and then componentDidMount(). Any state associated with the old tree is lost.

当把一棵树除去时，旧的DOM元素会被销毁。组件的实例会进行componentWillUnmount()。在创建一棵新树的时候，新的DOM节点会被插入DOM。组件实例会进行componentWillMount() 之后进行 componentDidMount()。任何在旧树上的state都会被清空。

Any components below the root will also get unmounted and have their state destroyed. For example, when diffing:

任何根结点下的组件会被unmounted并且state会被销毁。比如在进行diffing时。

<div>
  <Counter />
</div>

<span>
  <Counter />
</span>

This will destroy the old Counter and remount a new one.

这样改写代码会重新加载一个新组件。

DOM Elements Of The Same Type When comparing two React DOM elements of the same type, React looks at the attributes of both, keeps the same underlying DOM node, and only updates the changed attributes. For example:

DOM元素如果相同

在比较了两个React DOM元素是相同的时候， React会检查两边的attributes。保持相同的不变只改变变化的attributes。比如：

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

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

By comparing these two elements, React knows to only modify the className on the underlying DOM node.

When updating style, React also knows to update only the properties that changed. For example:

比较了这俩个元素，React知道下面的元素只有className改变了。 在更新style时，React也知道只去更新改变了的properties。比如：

<div style={{color: 'red', fontWeight: 'bold'}} />

<div style={{color: 'green', fontWeight: 'bold'}} />

When converting between these two elements, React knows to only modify the color style, not the fontWeight.

After handling the DOM node, React then recurses on the children.

Component Elements Of The Same Type When a component updates, the instance stays the same, so that state is maintained across renders. React updates the props of the underlying component instance to match the new element, and calls componentWillReceiveProps() and componentWillUpdate() on the underlying instance.

Next, the render() method is called and the diff algorithm recurses on the previous result and the new result.

在转换两个元素时，React知道只更新color属性的style，不是字体的粗细。 在处理了DOM的节点，React对子元素进行递归。

组件是同一类型 在一个组件更新时，实例不变，所以state才能在变化的render中维护下来，React更新了下面组件实例的属性，来匹配新的元素，调用下面那些实例的componentWillReceiveProps和componentWillUpdate。

接下来，render会被调用。diff算法会在之前的结果和新的结果上递归调用。

Recursing On Children By default, when recursing on the children of a DOM node, React just iterates over both lists of children at the same time and generates a mutation whenever there’s a difference.

For example, when adding an element at the end of the children, converting between these two trees works well:

在子元素上递归 一般，当在一个DOM节点的子元素上进行递归时，React会同时在新旧两个子元素列表里迭代，并在发生不同时进行改变。

比如，在添加子元素们的结尾添加新的元素，两棵树之间能很好的转换。

<ul>
  <li>first</li>
  <li>second</li>
</ul>

<ul>
  <li>first</li>
  <li>second</li>
  <li>third</li>
</ul>

React will match the two

first

trees, match the two

second

trees, and then insert the

third

tree.

If you implement it naively, inserting an element at the beginning has worse performance. For example, converting between these two trees works poorly:

React会匹配两个

first

和两个

second

，然后插入

third

。 若你想你想简单地实现，直接在开头插入元素，性能会很差。比如这样转换两棵树，就会表现很差。

<ul>
  <li>Duke</li>
  <li>Villanova</li>
</ul>

<ul>
  <li>Connecticut</li>
  <li>Duke</li>
  <li>Villanova</li>
</ul>

React will mutate every child instead of realizing it can keep the

Duke

and

Villanova

subtrees intact. This inefficiency can be a problem.

Keys In order to solve this issue, React supports a key attribute. When children have keys, React uses the key to match children in the original tree with children in the subsequent tree. For example, adding a key to our inefficient example above can make the tree conversion efficient:

React会把每个自元素更改了而不是保留

Duke

和

Villanova

两棵子树的完整。这种不足会是个问题。

Keys 为了解决这个问题。React支持key attribute。当自元素又key值时，React用key来匹配原树和后来的树的子元素。比如，添加一个key到我们上面不足的示例上，这会使得转换高效。

</ul>
  <li key="2015">Duke</li>
  <li key="2016">Villanova</li>
</ul>

<ul>
  <li key="2014">Connecticut</li>
  <li key="2015">Duke</li>
  <li key="2016">Villanova</li>
</ul>

Now React knows that the element with key '2014' is the new one, and the elements with the keys '2015' and '2016' have just moved.

In practice, finding a key is usually not hard. The element you are going to display may already have a unique ID, so the key can just come from your data:

目前React知道key2014是一个新的元素，并且这个2015和2016都被移动了。在实际中，找到一个key并不难。你要展示的element已经有一个独特的id，所以key就可以来自于你的数据。

<li key={item.id}>{item.name}</li>

When that’s not the case, you can add a new ID property to your model or hash some parts of the content to generate a key. The key only has to be unique among its siblings, not globally unique.

As a last resort, you can pass an item’s index in the array as a key. This can work well if the items are never reordered, but reorders will be slow.

Reorders can also cause issues with component state when indexes are used as keys. Component instances are updated and reused based on their key. If the key is an index, moving an item changes it. As a result, component state for things like uncontrolled inputs can get mixed up and updated in unexpected ways.

Here is an example of the issues that can be caused by using indexes as keys on CodePen, and here is a updated version of the same example showing how not using indexes as keys will fix these reordering, sorting, and prepending issues.

当情况不是这样时，你可以添加一个新的id属性到你的model里面或者将某些内容hash成为一个key。key只需要是同级元素中的唯一即可，不需要全局唯一。 作为最后的手段，你可以传递index作为key。如果不重新进行排序，那么index使用起来没有问题，但排序会比较慢。重新排序也会引起组件state问题，组件的实例会基于key进行更新和重用。如果key是index，移动一个项目时会改变他的index，像非受控的input组件的state会被搞乱并且以意料之外的方式更新。 见评论

这里是个例子，以及不使用index可以修复reordering, sorting, 和 prepending 问题。

Tradeoffs It is important to remember that the reconciliation algorithm is an implementation detail. React could rerender the whole app on every action; the end result would be the same. Just to be clear, rerender in this context means calling render for all components, it doesn’t mean React will unmount and remount them. It will only apply the differences following the rules stated in the previous sections.

折中 reconciliation算法是一种具体的实现。React 可以在每个action之后重新render整个app。最后结果是一样的，重新在context中render代表着调用每个组件的render方法，这不是说React就会unmount或者重新mount他们。他只会根据规则把不同点应用于上。

We are regularly refining the heuristics in order to make common use cases faster. In the current implementation, you can express the fact that a subtree has been moved amongst its siblings, but you cannot tell that it has moved somewhere else. The algorithm will rerender that full subtree.

为了让常见的case更快，我们一般都会重新定义启发式算法。在目前的实现中，你可以说一个子树已经被从同级元素中拿走，但你不能说他被移到了别的地方。算法会重新render整个子树。

Because React relies on heuristics, if the assumptions behind them are not met, performance will suffer.

The algorithm will not try to match subtrees of different component types. If you see yourself alternating between two component types with very similar output, you may want to make it the same type. In practice, we haven’t found this to be an issue.

Keys should be stable, predictable, and unique. Unstable keys (like those produced by Math.random()) will cause many component instances and DOM nodes to be unnecessarily recreated, which can cause performance degradation and lost state in child components.

因为React依赖于此“启发式”，如果之前提到的假设不满足的话，会影响性能。

算法不会尝试去匹配不同类型组件的子树。如果你看见你在两个不同组件类型有相同的输出，你应该把他们改成同一个类型。实际中，我们觉得这并没什么问题。

Key应该稳定，可以预知，并且唯一。不稳定的key比如Math.random回应起组件实例或者DOM节点不必要的重构，这就会引起性能退化并且使得子组件失去state。

所以如果用index作为key 到底是会出错还是会慢？

https://www.cnblogs.com/wonyun/p/6743988.html 会出错