面接で「Vue の diff アルゴリズムはどう動くのか」をよく聞かれるが、ネットの記事は抽象的なものが多い。具体的な例を使って説明しよう。
なぜ仮想 DOM が必要か
本物の DOM を操作するのは遅い。操作のたびにブラウザのリフロー（レイアウト）とリペイント（描画）が発生する可能性があるからだ。
javascript
// リストを更新する一番乱暴な方法：
container.innerHTML = items.map((item) => `<li>${item.name}</li>`).join("");
// 問題：すべての DOM ノードを破棄して作り直す。
// フォーカスやスクロール位置などの DOM 状態が失われる。
// 理想の方法：変化した部分だけを更新する。
// 仮想 DOM は JS オブジェクトで DOM をモデル化し、
// 新旧の仮想ツリーを比較して最小差分を求める。
仮想 DOM の構造
javascript
// 実際の DOM
// <div class="container">
// <ul>
// <li>Item 1</li>
// </ul>
// </div>
// 対応する仮想 DOM（簡略版）
const vnode = {
tag: "div",
data: { class: "container" },
children: [
{
tag: "ul",
children: [{ tag: "li", children: [{ text: "Item 1" }] }],
},
],
};
diff アルゴリズムの基本方針
Vue の diff アルゴリズムはいくつかの重要な前提を設けている（React の diff から引用）：
1. 同一レベルのノードのみ比較（レベルをまたいだ比較はしない）
→ div A から div B にノードが移動した場合は削除＋追加として扱う
→ 現実には DOM のクロスレベル移動はほぼ発生しない
2. 型が異なるノードは直接置き換える（深い比較はしない）
→ <div> が <p> になった場合→サブツリー全体を置き換える
3. 同じ型のノードは key を使って同一性を判断する
→ key なし：位置で比較
→ key あり：同じ key のノードをマッチさせて並び替えを実現
リスト diff：ダブルエンド比較
Vue 2 のリスト diff はダブルエンド比較を使用する。新旧リストの両端から同時に比較する：
javascript
// 旧リスト: [A, B, C, D]
// 新リスト: [D, A, B, C]
// Step 1: 旧先頭(A) と 新先頭(D) → 不一致
// Step 2: 旧末尾(D) と 新末尾(C) → 不一致
// Step 3: 旧先頭(A) と 新末尾(C) → 不一致
// Step 4: 旧末尾(D) と 新先頭(D) → 一致！
// D を末尾から先頭に移動
// 結果：D を先頭に移動するだけ — 4回ではなく1回の DOM 移動
key の役割
vue
<!-- key なし：Vue は位置でノードを再利用。並び替えで input 値が失われる -->
<li v-for="item in items">{{ item.name }}</li>
<!-- key あり：Vue は同一性でノードをマッチ。並び替えでも状態が保持される -->
<li v-for="item in items" :key="item.id">{{ item.name }}</li>
まとめ
- 仮想 DOM は最小パッチを計算することで不要な全再描画を回避する
- 同一レベルのみの比較でアルゴリズムを O(n³) ではなく O(n) に保つ
key属性はリストの正しい並び替えに不可欠 — 常に指定すること- Vue 3 は LIS ベースの diff でさらに DOM 移動回数を削減している