React provides a declarative API so that you don’t have to worry about exactly what changes on every update. This makes writing applications a lot easier, but it might not be obvious how this is implemented within React. This article explains the choices we made in React’s “diffing” algorithm so that component updates are predictable while being fast enough for high-performance apps.
React 提供了声明式 API，所以，你不用考虑每次更新都更改了哪些内容。这让你开发应用更加容易，但会使你并不了解 React 内部是如何实现它的。本文解释了我们在 React 的“差异化”算法中做出的选择，以便组件的更新可预测，同时让高性能应用程序也足够快。
动机(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.
当你使用 React 时，你可以认为 render() 函数创建了一个 React 元素的树。在下一次状态或属性更新的时候， render() 函数将返回一个不同的 React 元素树。然后 React 需要解决如何有效地更新 UI 以使其匹配最新的元素树。
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.
目前有一些通用的方案，可以解决用最少的操作步骤将一棵元素树转换为另一棵元素树的这样的算法问题。然而，最先进的算法 也具有O(n3)的复杂度，其中 n 是树中元素的数量。
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:
1.Two elements of different types will produce different trees.
2.The developer can hint at which child elements may be stable across different renders with a key prop.
如果我们在 React 中使用它，则显示 1000 个元素将需要进行 10 亿次比较，这个代价太贵了。相反，基于以下两个假设，实现了启发式的复杂度为 O(n) 的算法：
1.两种不同类型的元素会产生不同的树。
2.开发人员可以通过关键属性 key 暗示哪些子元素可以在不同的渲染中保持稳定。
In practice, these assumptions are valid for almost all practical use cases.
实际上，这两个假设对于几乎所有的实践中都是有效的。
Diffing算法(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.
在比较两棵树时，React 首先比较它们两个的根元素。根据根元素的类型而有不同行为。
不同类型的元素(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 <a></a> to <img>, or from <Article> to <Comment>, or from <Button> to <div> - any of those will lead to a full rebuild.
每当根元素具有不同的类型时，React 将会销毁旧树并从头开始构建新的树。从 <a> 到 <img>，或从 <Article> 到 <Comment>，或从 <Button> 到 <div> —— 这些都将导致元素完全重建。
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()。任何与旧树相关的状态都将丢失。
Any components below the root will also get unmounted and have their state destroyed. For example, when diffing:
根节点下的任何组件也将被卸载，并将其状态（state）销毁。例如，当比较：
<div> |
This will destroy the old Counter and remount a new one.
这将会销毁旧的 Counter 组件，并重新挂载一个新的 Counter 组件。
相同类型的DOM元素(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:
当比较类型相同的两个 React DOM 元素时，React 会查看两者的属性，保持相同的底层 DOM 节点，并只更新已修改的属性。例如：
<div className="before" title="stuff" /> |
By comparing these two elements, React knows to only modify the className on the underlying DOM node.
通过比较这两个元素， React 知道仅修改底层 DOM 节点的 className 属性。
When updating style, React also knows to update only the properties that changed. For example:
当更新 style 属性时，React 也知道仅更新发生改变的属性，例如：
<div style={ {color: 'red', fontWeight: 'bold'} } /> |
When converting between these two elements, React knows to only modify the color style, not the fontWeight.
在对这两个元素进行转化时，React 知道只修改 color 样式，而不修改 fontWeight。
After handling the DOM node, React then recurses on the children.
当处理完 DOM 节点后，React 会递归处理其子节点。
相同类型的组件元素(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.
当一个组件更新时，这个实例保持不变，所以状态在整个渲染过程中保持不变。React更新底层组件实例的属性（props）以匹配新元素，并在底层实例上调用 componentWillReceiveProps() 和 componentWillUpdate() 。
Next, the render() method is called and the diff algorithm recurses on the previous result and the new result.
接下来， render() 方法被调用，并且 diff 算法对 render() 方法返回的前一个结果和新结果开始递归执行。
对子元素递归(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.
默认情况下，在递归 DOM 节点的子元素时，React 只是同时迭代两个树的子节点列表，并且每当子节点出现差异时对其改变。
For example, when adding an element at the end of the children, converting between these two trees works well:
例如，当在子元素的末尾添加一个元素时，在这新旧两棵元素树之间的转化效率很高：
<ul> |
React will match the two <li>first</li> trees, match the two <li>second</li> trees, and then insert the <li>third</li> tree.
React 将比较 <li>first</li> 和 <li>second</li> 两个树，然后插入 <li>third</li> 树。
If you implement it naively, inserting an element at the beginning has worse performance. For example, converting between these two trees works poorly:
如果你在最前面插入元素的时候也这么简单的实现它，性能将变得很差。例如，这下面这两棵树之间的转换效果就很差：
<ul> |
React will mutate every child instead of realizing it can keep the <li>Duke</li> and <li>Villanova</li> subtrees intact. This inefficiency can be a problem.
React 会改变每个子元素，而不是意识到它可以保持 <li>Duke</li> 和 <li>Villanova</li> 两个子树不变，这种低效率的操作方式是一个问题。
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 支持一个 key 属性。当子元素包含有 key 属性的时候，React 使用 key 属性值来匹配原始树中的子元素和新树中的子元素。例如，为我们上面的低效率示例添加一个 key 可以使树的转换变得高效：
<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.
现在React知道 key 为 '2014' 的元素是新元素， key 为 '2015' 和 '2016' 的元素只需要移动即可。
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:
在实践中，找到一个 key 通常不难。你要显示的元素一般有一个唯一的 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.
如果并非如此，你可以将新的 ID 属性添加到模型中，或者对内容的某些部分进行哈希以生成它。关键只在于它在它的兄弟姐妹是独一无二的，而不需要在全局中唯一。
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.
作为最后的手段，你可以传递数组中的元素索引作为 key。如果列表从未重新排序，这可以很好地工作。但重新排序将会变慢。
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 controlled inputs can get mixed up and updated in unexpected ways.
但当使用索引用作 key 时，重新排序也会导致组件状态的问题。组件实例基于它的 key 进行更新和重用。如果 key 是索引，则移动项目会改变它的 key。因此，像受控输入之类的组件状态可能会以意想不到的方式发生混淆和被更新。
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.
这里是 CodePen 上使用索引作为 key 可能导致的问题的一个例子，这里 是同一个例子的更新版本，展示了不使用索引作为 key 将解决这些排序、重新排序和潜在的问题。
权衡(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 的一个实现细节。 React 可以在每个操作上重新渲染整个应用程序，而最终的结果将是一样的。你需要了解，在这种情况下重新渲染意味着为所有组件调用渲染，并不意味着 React 将卸载并重新加载这些，它只会按照前面章节所述的规则进行工作。
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.
为了更快地创建通用用例，我们定期改进我们的启发式算法。在目前的实现中，你可以知道的是，子树已经在其兄弟姐妹之间移动，但是你不必了解它被移动到哪里。该算法将重新渲染完整的子树。
Because React relies on heuristics, if the assumptions behind them are not met, performance will suffer.
因为 React 依赖这个启发式，如果不满足它们背后的假设，性能将受到影响。
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.该算法不会尝试匹配不同组件类型的子树。如果你发现自己在输出非常相似的两种组件之间交替转换，则应该使它们的类型相同。实际上，我们并没有发现这样的问题。
Keys应该是稳定的，可预测的和唯一的。不稳定的keys（如
Math.random()生成的）将导致许多组件实例和 DOM 节点被不必要地重新创建，这可能会导致子组件中的性能下降和状态丢失。