Reconciliationの内部
なぜReactのdiffはO(n)で済むのか。keyがアルゴリズムにどう影響するか。疑似コードで内部実装を読み解きます。
Reconciliationとは何か
stateが変化するたびにReactは新しいVirtual DOMツリーを生成します。しかし、新しいツリーをそのままDOMに反映するのは非効率です。 そこでReactは前回のツリーと新しいツリーを比較（diff）し、変化した最小限の箇所だけをDOMに反映します。 このプロセスを Reconciliation（リコンシリエーション） と呼びます。
一般的なツリーのdiffアルゴリズムはO(n³)かかります。しかしReactのdiffはO(n)です。 どうやってそれを実現しているのでしょうか？
Reactが採用する2つの仮定
- 異なる型の要素は、異なるツリーを生成する（型が変わったら再構築）
- keyによって、リスト内の要素を安定的に識別できる
この2つの仮定によって、ReactはO(n³)の問題をO(n)に落とし込んでいます。
O(n³) → O(n)：なぜ可能なのか
2つの任意のツリー間の最小編集距離を求める最良の既存アルゴリズムはO(n³)の複雑度を持ちます。 1000要素のReactアプリでは10億回の計算が必要になり、実用的ではありません。
Reactは2つのヒューリスティック仮定を用いてこれをO(n)に落とし込みます。
仮定1: 異なる型 → 完全な再構築
ReactはコンポーネントA（例: <div>）が
<span>に変わった場合、
サブツリー全体を破棄して再構築します。diffを計算しません。
仮定2: keyによる同一性識別
同じ型の子要素リストに対し、Reactは上から順番に比較します（インデックスベース）。
しかしkeyがある場合、
Reactはkeyで要素を識別し、移動・追加・削除を正確に追跡します。
疑似コードで読むReconciliation
実際のReactソースコードを簡略化した疑似コードでReconciliationのコアロジックを理解します。
function reconcileChildren(current, workInProgress, newChildren) {
// keyがある場合は Map で O(1) ルックアップ
const existingChildren = mapRemainingChildren(current);
for (let i = 0; i < newChildren.length; i++) {
const newChild = newChildren[i];
const key = newChild.key ?? i; // keyなしはindexを使用
const existing = existingChildren.get(key);
if (existing && existing.type === newChild.type) {
// 同じ型 → 再利用してpropsだけ更新
updateFiber(existing, newChild.props);
existingChildren.delete(key); // 使用済みマーク
} else {
// 型が違うか新規 → 新しいFiberを作成
createFiber(newChild);
}
}
// 残った既存要素は削除
existingChildren.forEach(child => deleteChild(child));
} この処理はMapを使っているため、各要素の検索がO(1)です。 n個の要素を処理するので全体でO(n)になります。
FiberとReconcilerの分離
React 16以降、ReconciliationはFiberアーキテクチャの上で動きます。 Fiberとは何か、なぜ中断可能なのかはFiberとは何か？で詳しく解説します。
重要な分離: ReactのコアはReconciler（何をするか決める）とRenderer（実際にDOMを操作する）に分かれています。 これがReact Native・React Three Fiberなどが存在できる理由です。