How does React diffing algorithm work?

React's diffing algorithm is a fundamental part of its reconciliation process, which aims to efficiently update the UI to match the latest state. Instead of re-rendering the entire DOM tree on every change, React uses a set of heuristics to determine the minimal set of changes needed to update the actual DOM.

The Core Idea: Reconciliation and Virtual DOM

Reconciliation is the process by which React updates the browser's DOM. React maintains an in-memory representation of the UI called the Virtual DOM. When a component's state or props change, React creates a new Virtual DOM tree and compares it with the previous one. This comparison is where the diffing algorithm comes into play.

Key Principles of the Diffing Algorithm

The diffing algorithm operates on two main assumptions, which are highly efficient for typical web application UI patterns:

• 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.

Comparing Elements of Different Types

When React compares two root elements of different types (e.g., a <div> changing to a <span>), it will tear down the old tree and build the new tree from scratch. This means destroying all children, unmounting old components, and mounting new ones. Any state associated with the old components is lost.

Comparing Elements of the Same Type

When comparing two React elements of the same type, React looks at their attributes (props). It keeps the underlying DOM node and only updates the changed attributes. For example, if a <div>'s className changes, React only updates that specific attribute on the existing DOM div node.

After updating the element's attributes, React recursively continues to diff the children of the two elements.

Reconciling Children with the `key` Prop

When a component has multiple children, React iterates over both the old children and the new children lists simultaneously. By default, it simply compares the first child in the old list with the first child in the new list, the second with the second, and so on.

This naive approach becomes inefficient when items in a list are reordered, inserted, or deleted. For example, if an item is inserted in the middle of a list, React might unnecessarily re-render many subsequent children because it assumes they have changed.

To solve this, React supports a key prop. When children have keys, React uses them to match children in the original tree with children in the subsequent tree. Keys should be unique among siblings and stable (i.e., not generated randomly). They help React identify which items have changed, been added, or been removed, allowing for more efficient updates.

<ul>
  {items.map(item => (
    <li key={item.id}>{item.name}</li>
  ))}
</ul>

Summary of Diffing Rules

• Different Element Types: Old tree is unmounted, new tree is mounted. State is lost.
• Same Element Types: React keeps the DOM node and updates only the changed attributes (props). Recursive diffing occurs for children.
• List Children: The key prop is crucial for efficient reconciliation of lists, allowing React to identify item identities across renders.

By following these heuristics, React achieves near-optimal UI updates without the performance cost of full DOM manipulation, making it fast and efficient for most applications.