diffing algorithm
The rules React uses to compare an old element tree with a new one and find what changed.
In more detail
A general algorithm for comparing two trees takes cubic time in the number of nodes. React instead assumes that elements of different types produce different trees and that keys mark the same child across renders, which brings the cost down to linear time.
Related terms
- reconciliation — The process where React compares the new tree of elements with the previous one and works out the smallest set of changes to the page.
- heuristic — A practical rule of thumb that gives a good answer quickly in normal cases, without guaranteeing the best answer every time.
- Big O notation — A way of writing an upper bound on growth: O(f(n)) means the cost grows no faster than a constant times f(n) for large n.
- key (React) — A special string or number you give to elements in a list so React can tell which item is which between renders.
Taught in
- Virtual DOM vs Real DOM: The Reconciliation Cost Model — React 19 & Modern Component Architecture
- React Fiber Architecture: Work Units, Priority And Commits — React 19 & Modern Component Architecture
- Keys In Depth: Identity Preservation And Identity Resetting — React 19 & Modern Component Architecture
- Diffing Algorithm: Element Type Shifts And Subtree Tear Down — React 19 & Modern Component Architecture
- Concurrent Mode: Interruptible Work And Lane Priority — React 19 & Modern Component Architecture
- React.memo, useMemo, And useCallback: Optimization Costs — React 19 & Modern Component Architecture