11.10 手写简易 diff

一句话：手写简易 diff 的目标是「理解 React 如何把两棵 vnode 树变成最小的 DOM 操作」——核心是「同层比较 + type 不同直接重建 + 用 key 匹配同一层数组」，把 O(n³) 降到 O(n)。

一、目标与复杂度

目标：给定「旧的 vnode 树」与「新的 vnode 树」，输出「需要做哪些 DOM 操作」。

理论最优（树的编辑距离）是 O(n³)：
  n 个节点 × 两两比较（O(n²)）× 每次比较递归子树（O(n)）
  对 1000 个节点 = 10⁹ 次操作 → 完全不可行

React 用三个【假设】把复杂度降到 O(n)：
  ① 同层比较（不跨层移动）
  ② type 不同 → 直接卸载重建
  ③ 同层数组用 key 匹配

⭐ 我们要手写的简化版只实现：
① vnode 结构（type / props / key / children）
② createElement（生成 vnode）
③ render/patch（把 vnode 变成 DOM，并做 diff）
④ patchChildren（同层数组的 key 匹配）
⑤ 事件与属性的更新

不实现：fiber、优先级、可中断、Suspense、类组件、Fragment…（那是完整 React）

二、vnode 结构

/**
 * @typedef {Object} VNode
 * @property {string | Function} type     'div' / 'span' / 函数组件
 * @property {Object} props               属性（含 children）
 * @property {string | number | null} key 同一层里的身份标识
 * @property {Node | null} el             对应的真实 DOM（渲染后挂上）
 */

function createElement(type, props, ...children) {
  const normalizedProps = { ...(props ?? {}) };

  // 把 children 统一成数组（并拍平、过滤空值）
  const flat = children.flat(Infinity).filter((c) => c !== null && c !== undefined && c !== false);

  if (flat.length > 0) normalizedProps.children = flat;
  else delete normalizedProps.children;

  return {
    type,
    props: normalizedProps,
    key: normalizedProps.key ?? null,
    el: null,
  };
}

// 便于写：h('div', { id: 'a' }, h('span', null, 'hi'))
const h = createElement;

三、首次渲染（把 vnode 变成 DOM）

function createDom(vnode) {
  // ① 文本节点
  if (typeof vnode === 'string' || typeof vnode === 'number') {
    const textEl = document.createTextNode(String(vnode));
    return textEl;
  }

  // ② 函数组件（简化：直接调用，取其返回的 vnode）
  if (typeof vnode.type === 'function') {
    const rendered = vnode.type(vnode.props);
    const el = createDom(rendered);
    vnode.el = el;                       // 让「组件 vnode」也能指向真实 DOM
    return el;
  }

  // ③ 宿主元素
  const el = document.createElement(vnode.type);
  vnode.el = el;

  // 设置属性
  updateProps(el, {}, vnode.props);

  // 递归子节点
  getChildren(vnode).forEach((child) => {
    el.appendChild(createDom(child));
  });

  return el;
}

function getChildren(vnode) {
  const children = vnode?.props?.children;
  if (children === undefined || children === null) return [];
  return Array.isArray(children) ? children : [children];
}

// 属性设置（含事件）
function updateProps(el, prevProps = {}, nextProps = {}) {
  // ① 移除「不再存在」的属性
  Object.keys(prevProps).forEach((name) => {
    if (name === 'children' || name === 'key') return;
    if (name in nextProps) return;

    if (name.startsWith('on') && typeof prevProps[name] === 'function') {
      el.removeEventListener(name.slice(2).toLowerCase(), prevProps[name]);
    } else {
      el.removeAttribute(name);
    }
  });

  // ② 设置「新增/变化」的属性
  Object.entries(nextProps).forEach(([name, value]) => {
    if (name === 'children' || name === 'key') return;
    if (Object.is(prevProps[name], value)) return;      // ⭐ 值没变就跳过

    if (name.startsWith('on') && typeof value === 'function') {
      // ⭐ 事件：先移除旧的（因为「函数引用」通常会变）
      if (typeof prevProps[name] === 'function') {
        el.removeEventListener(name.slice(2).toLowerCase(), prevProps[name]);
      }
      el.addEventListener(name.slice(2).toLowerCase(), value);
      return;
    }

    if (name === 'style' && typeof value === 'object') {
      Object.assign(el.style, value);
      return;
    }

    if (value === false || value === null || value === undefined) {
      el.removeAttribute(name);
    } else if (value === true) {
      el.setAttribute(name, '');
    } else {
      el.setAttribute(name, String(value));
    }
  });
}

四、diff（核心：同层比较）

/**
 * 把 oldVNode 更新为 newVNode（并返回 newVNode）
 * 核心逻辑：同层比较 + type 比较 + key 比较
 */
function patch(parent, oldVNode, newVNode, index = 0) {
  // ① 新节点不存在 → 删除旧节点
  if (newVNode === null || newVNode === undefined || newVNode === false) {
    if (oldVNode) removeNode(oldVNode);
    return null;
  }

  // ② 旧节点不存在 → 创建新节点
  if (oldVNode === null || oldVNode === undefined || oldVNode === false) {
    const el = createDom(newVNode);
    insertAt(parent, el, index);
    return newVNode;
  }

  // ③ 类型不同（或 key 不同）→ 卸载重建
  //    ⚠️ 这是「同层比较」的代价：跨层移动会被视为「删除 + 新建」
  if (oldVNode.type !== newVNode.type || oldVNode.key !== newVNode.key) {
    const el = createDom(newVNode);
    replaceNode(oldVNode, el);
    return newVNode;
  }

  // ④ 文本节点 → 直接更新文本
  if (typeof newVNode === 'string' || typeof newVNode === 'number') {
    if (oldVNode !== newVNode) {
      oldVNode.el.nodeValue = String(newVNode);
    }
    newVNode.el = oldVNode.el;                 // 复用同一个文本节点
    return newVNode;
  }

  // ⑤ 复用同一个 DOM 元素（type 与 key 都相同）
  const el = (newVNode.el = oldVNode.el);

  // 更新属性
  updateProps(el, oldVNode.props, newVNode.props);

  // ⑥ diff 子节点
  patchChildren(el, oldVNode, newVNode);

  return newVNode;
}

五、patchChildren（同层数组的 key 匹配）

function patchChildren(parentEl, oldVNode, newVNode) {
  const oldChildren = getChildren(oldVNode);
  const newChildren = getChildren(newVNode);

  // ===== 情况一：新的「没有 children」→ 清空 =====
  if (newChildren.length === 0) {
    oldChildren.forEach(removeNode);
    return;
  }

  // ===== 情况二：旧的「没有 children」→ 全部新建 =====
  if (oldChildren.length === 0) {
    newChildren.forEach((child) => parentEl.appendChild(createDom(child)));
    return;
  }

  // ===== 情况三：新旧都是「单个文本」→ 直接改文本 =====
  const isText = (v) => typeof v === 'string' || typeof v === 'number';
  if (oldChildren.length === 1 && newChildren.length === 1 && isText(oldChildren[0]) && isText(newChildren[0])) {
    if (oldChildren[0] !== newChildren[0]) {
      parentEl.textContent = String(newChildren[0]);
    }
    return;
  }

  // ===== 情况四：多节点 diff（用 key 匹配）=====
  diffKeyedChildren(parentEl, oldChildren, newChildren);
}

/**
 * 多节点 diff（简化版）：
 * ① 给「旧 children」建 Map：key → { vnode, index }
 * ② 遍历「新 children」：
 *    · Map 里有同 key → 复用（patch）
 *    · 没有 → 新建
 *    · 记录「已复用的旧索引」的最大值（lastPlacedIndex）
 * ③ 移动判定：如果「旧索引 < lastPlacedIndex」→ 需要移动
 * ④ 最后：把「没被复用」的旧节点删掉
 */
function diffKeyedChildren(parentEl, oldChildren, newChildren) {
  const oldMap = new Map();
  oldChildren.forEach((child, i) => {
    const key = getKey(child, i);
    oldMap.set(key, { vnode: child, index: i });
  });

  let lastPlacedIndex = 0;                        // ⭐ 已复用节点的「最大旧索引」
  const usedKeys = new Set();

  newChildren.forEach((newChild, newIdx) => {
    const key = getKey(newChild, newIdx);
    const matched = oldMap.get(key);

    if (matched && matched.vnode.type === newChild.type) {
      // ① 类型 + key 都相同 → 复用（递归 patch）
      usedKeys.add(key);

      const patched = patch(parentEl, matched.vnode, newChild, newIdx);

      // ② 移动判定（与 React 的 lastPlacedIndex 思路一致）
      if (matched.index < lastPlacedIndex) {
        // ⭐ 旧位置在「已复用节点的最右位置」之左 → 需要移动
        insertBefore(parentEl, patched.el, parentEl.childNodes[newIdx] ?? null);
      } else {
        lastPlacedIndex = matched.index;
      }
    } else {
      // ③ 没有匹配（或 type 变了）→ 新建
      const el = createDom(newChild);
      insertBefore(parentEl, el, parentEl.childNodes[newIdx] ?? null);
    }
  });

  // ④ 删除「没被复用」的旧节点
  oldChildren.forEach((child, i) => {
    const key = getKey(child, i);
    if (!usedKeys.has(key)) removeNode(child);
  });
}

/** 取 key：优先用 vnode.key，否则退化用 index（⚠️ 这就是「可以用 index」的场合） */
function getKey(vnode, index) {
  if (vnode === null || typeof vnode === 'string' || typeof vnode === 'number') return `text-${index}`;
  return vnode.key ?? `index-${index}`;
}

⭐ 「lastPlacedIndex」的作用（与 React 一致）：
  它记录「已经复用的旧节点里最大的 index」。
  对新复用的节点：如果它的「旧 index < lastPlacedIndex」，
  说明「它在旧数组里的位置在某个已复用节点的左边」，而现在要放到右边
  → 必须移动（否则顺序不对）。
  ⚠️ 这是「单指针贪心」，不保证「移动次数最少」（Vue 用双端 + LIS 更优）。

六、DOM 操作的辅助函数

function removeNode(vnode) {
  const el = vnode?.el;
  if (!el || !el.parentNode) return;
  el.parentNode.removeChild(el);
}

function insertAt(parent, el, index) {
  const ref = parent.childNodes[index] ?? null;
  parent.insertBefore(el, ref);
}

function insertBefore(parent, el, ref) {
  if (el === ref) return;                       // 已经在正确位置
  parent.insertBefore(el, ref);
}

function replaceNode(oldVNode, newEl) {
  const oldEl = oldVNode?.el;
  if (oldEl?.parentNode) {
    oldEl.parentNode.replaceChild(newEl, oldEl);
  }
}

七、完整可运行示例

<!doctype html>
<html>
  <body>
    <div id="app"></div>
    <button id="shuffle">乱序</button>
    <button id="insert">头部插入</button>
    <button id="add">追加</button>

    <script>
      // ================= vnode =================
      function h(type, props, ...children) {
        const p = { ...(props ?? {}) };
        const flat = children.flat(Infinity).filter((c) => c !== null && c !== undefined && c !== false);
        if (flat.length) p.children = flat;
        return { type, props: p, key: p.key ?? null, el: null };
      }

      const getChildren = (v) => {
        const c = v?.props?.children;
        return c == null ? [] : Array.isArray(c) ? c : [c];
      };

      // ================= 创建 =================
      function createDom(vnode) {
        if (typeof vnode === 'string' || typeof vnode === 'number') {
          return document.createTextNode(String(vnode));
        }
        if (typeof vnode.type === 'function') {
          const el = createDom(vnode.type(vnode.props));
          vnode.el = el;
          return el;
        }
        const el = document.createElement(vnode.type);
        vnode.el = el;
        updateProps(el, {}, vnode.props);
        getChildren(vnode).forEach((c) => el.appendChild(createDom(c)));
        return el;
      }

      // ================= 属性 =================
      function updateProps(el, prev = {}, next = {}) {
        for (const name of Object.keys(prev)) {
          if (name === 'children' || name === 'key' || name in next) continue;
          if (name.startsWith('on')) el.removeEventListener(name.slice(2).toLowerCase(), prev[name]);
          else el.removeAttribute(name);
        }
        for (const [name, value] of Object.entries(next)) {
          if (name === 'children' || name === 'key' || Object.is(prev[name], value)) continue;
          if (name.startsWith('on') && typeof value === 'function') {
            if (typeof prev[name] === 'function') el.removeEventListener(name.slice(2).toLowerCase(), prev[name]);
            el.addEventListener(name.slice(2).toLowerCase(), value);
          } else if (value === false || value == null) {
            el.removeAttribute(name);
          } else if (value === true) {
            el.setAttribute(name, '');
          } else {
            el.setAttribute(name, String(value));
          }
        }
      }

      // ================= diff =================
      function patch(parent, oldV, newV, index = 0) {
        if (newV == null || newV === false) { removeNode(oldV); return null; }
        if (oldV == null || oldV === false) {
          const el = createDom(newV);
          parent.insertBefore(el, parent.childNodes[index] ?? null);
          return newV;
        }

        // type 或 key 不同 → 重建
        if (oldV.type !== newV.type || oldV.key !== newV.key) {
          const el = createDom(newV);
          const oldEl = oldV.el;
          if (oldEl?.parentNode) oldEl.parentNode.replaceChild(el, oldEl);
          return newV;
        }

        if (typeof newV === 'string' || typeof newV === 'number') {
          if (oldV !== newV) oldV.el.nodeValue = String(newV);
          newV.el = oldV.el;
          return newV;
        }

        newV.el = oldV.el;
        updateProps(newV.el, oldV.props, newV.props);
        patchChildren(newV.el, oldV, newV);
        return newV;
      }

      function patchChildren(parentEl, oldV, newV) {
        const oldC = getChildren(oldV);
        const newC = getChildren(newV);
        const isText = (v) => typeof v === 'string' || typeof v === 'number';

        if (newC.length === 0) { oldC.forEach(removeNode); return; }
        if (oldC.length === 0) { newC.forEach((c) => parentEl.appendChild(createDom(c))); return; }
        if (oldC.length === 1 && newC.length === 1 && isText(oldC[0]) && isText(newC[0])) {
          if (oldC[0] !== newC[0]) parentEl.textContent = String(newC[0]);
          return;
        }

        diffKeyed(parentEl, oldC, newC);
      }

      function diffKeyed(parentEl, oldC, newC) {
        const keyOf = (v, i) => (typeof v === 'object' && v ? (v.key ?? `i-${i}`) : `t-${i}`);
        const oldMap = new Map(oldC.map((c, i) => [keyOf(c, i), { vnode: c, index: i }]));
        const used = new Set();
        let lastPlaced = 0;

        newC.forEach((newChild, newIdx) => {
          const key = keyOf(newChild, newIdx);
          const matched = oldMap.get(key);

          if (matched && matched.vnode.type === newChild.type) {
            used.add(key);
            const patched = patch(parentEl, matched.vnode, newChild, newIdx);
            if (matched.index < lastPlaced) {
              parentEl.insertBefore(patched.el, parentEl.childNodes[newIdx] ?? null);   // ⭐ 移动
            } else {
              lastPlaced = matched.index;
            }
          } else {
            const el = createDom(newChild);
            parentEl.insertBefore(el, parentEl.childNodes[newIdx] ?? null);
          }
        });

        oldC.forEach((c, i) => {
          if (!used.has(keyOf(c, i))) removeNode(c);
        });
      }

      function removeNode(v) {
        const el = v?.el;
        if (el?.parentNode) el.parentNode.removeChild(el);
      }

      // ================= 应用 =================
      const root = document.getElementById('app');
      let items = [
        { id: 'a', text: 'A' },
        { id: 'b', text: 'B' },
        { id: 'c', text: 'C' },
      ];
      let vnode = null;

      function render() {
        const next = h('ul', null,
          ...items.map((it) => h('li', { key: it.id }, `${it.text}-${it.id}`))
        );

        if (!vnode) {
          root.innerHTML = '';
          root.appendChild(createDom(next));
        } else {
          patch(root, vnode, next);
        }
        vnode = next;
      }

      document.getElementById('shuffle').onclick = () => {
        items = [items[2], items[0], items[1]];     // ⭐ 乱序 → 观察「移动」而不是「重建」
        render();
      };
      document.getElementById('insert').onclick = () => {
        items = [{ id: `x${Date.now()}`, text: '新' }, ...items];
        render();
      };
      document.getElementById('add').onclick = () => {
        items = [...items, { id: `y${Date.now()}`, text: '尾' }];
        render();
      };

      render();
    </script>
  </body>
</html>

⭐ 跑起来观察（用 DevTools 的 Elements 面板）：
① 点「乱序」→ 只有 li 的**顺序**变了，DOM 节点**没有被重建**（节点身份不变）
② 点「头部插入」→ 只有新节点被创建，其它 li 只是「移动」
③ 点「追加」→ 只有新节点被创建（其余完全不动）
④ 如果把 key 换成 index（或在 `keyOf` 里忽略 key）→ 观察「重建」行为

八、与真实实现的差距

⭐ 关键结论：
手写简易 diff 能帮你看清「**diff 的判断依据只有两个：`type` 与 `key`**」——
① `type` 或 `key` 变了 → 卸载重建（状态丢失）
② 都相同 → 复用（只更新属性与子节点）
这正是「为什么不能用 index 作 key」与「为什么组件内定义组件会导致状态丢失」的根源。

九、面试追问

Q: diff 为什么是 O(n)？
A: 靠三个假设（同层比较、type 不同重建、key 匹配），
   把「树比较」降级为「同层数组比较」，再用 key 把数组匹配降到 O(n)。

Q: 多节点 diff 的两轮遍历是什么？
A: ① 第一轮「按顺序用 key 匹配」处理「更新」（遇到不匹配就跳出）；
   ② 第二轮「用 Map 处理剩余」的新增/删除/移动，移动判定用 lastPlacedIndex。

Q: 为什么「type 不同」就直接重建？
A: 因为「type 不同」意味着「这是不同的东西」（如 div → span、组件 A → 组件 B），
   复用没有意义（属性、行为、子结构都可能完全不同）。

Q: key 的作用是什么？
A: 「同层身份标识」——决定 React「复用」还是「重建」这个节点。
   key 相同 + type 相同 → 复用（保留 DOM 与状态）；否则重建。

Q: 用 index 作 key 为什么有问题？
A: index 表示「位置」而不是「身份」。列表增删/排序后，
   同一个数据的 index 变了，但 React 按 key 复用 →
   导致「状态错位」（如输入框内容跑到别的行）。

Q: 「跨层移动」会怎样？
A: 被当成「删除 + 新建」（同层比较的代价）→ 子树状态丢失。

Q: 可以在 diff 里做「副作用」吗？
A: 不行。diff 属于「render 阶段」（可中断、可重放），必须纯。

十、常见坑

① 用 index 作 key（列表变动时状态错位）
② key 加在「内层元素」上（外层没有 key → 只能按位置匹配）
③ 用随机值作 key（每次渲染都重建整列）
④ 在 diff 里做副作用（render 必须纯）
⑤ 忘了「移动判定」而只做「复用 + 新建删除」
   → 顺序错乱（如 [A,B,C] → [C,A,B] 会渲染成 [A,B,C]）
⑥ 用 `innerHTML` 做「整体替换」（丢掉 diff 的意义与状态）
⑦ 事件监听「每次都新建但不移除旧的」→ 内存泄漏 + 触发多次
⑧ 比较 props 时用「引用相等」却不做「不可变更新的提示」
   → 直接改对象时引用没变 → 属性不更新（这正是 React 要求不可变的原因）
⑨ 忘记「移除不再存在的属性」（旧属性残留在 DOM 上）
⑩ 认为「手写版与真实 React 等价」（缺 fiber/优先级/状态/Hooks/合成事件）

十一、面试延伸

1. 「React 的 diff 为什么是 O(n)？」
   因为 React 用了三个假设来降低复杂度：① 同层比较——只比较「同一层级」的节点，不跨层移动（跨层移动会被当成「删除 + 新建」）；② type 不同直接重建——div → span、组件 A → 组件 B 就卸载重挂；③ 用 key 标识同一层的元素——把「数组匹配」变成「用 key 查表」的 O(n) 过程。三者结合，把「树编辑距离」的理论 O(n³) 降到了 O(n)。

2. 「key 在 diff 里起什么作用？」
   它是「同一层元素的身份标识」——React 用「type + key」共同判断「新旧两个 vnode 是否是同一个节点」：都相同 → 复用（保留真实 DOM 与组件状态，只更新属性与子节点）；任一不同 → 卸载旧节点、创建新节点（状态丢失）。所以 key 直接决定了「性能」（复用的节点不做 DOM 创建）与「正确性」（用 index 会导致状态错位，见 4.5）。

3. 「多节点 diff 的两轮遍历是什么？」
   手写版可以简化为「Map + 一次遍历」，但真实 React 是两轮：① 第一轮——从左到右「按顺序用 key 比较」，能匹配上就复用并更新（处理「更新」的场景），一旦匹配失败就跳出；② 第二轮——把「剩余的旧节点」放进 Map（key → fiber），然后遍历「剩余的新节点」：能在 Map 里找到就复用、找不到就新建，最后把 Map 里剩下的旧节点删除。移动判定用 lastPlacedIndex。（Vue 3 用「双端比较 + LIS」，移动次数更接近最少。）

4. 「lastPlacedIndex 是干什么的？」
   它记录「已经复用的旧节点中最大的 index」。对一个「本轮复用」的节点：如果它的旧 index 小于 lastPlacedIndex，说明「它在旧数组里的位置在某个已复用节点的左边」，而现在要渲染到右边 → 需要移动（insertBefore），否则不需要移动。这是 React「判断是否移动」的核心逻辑，也是「单指针贪心」——不保证移动次数最少（这解释了「为什么 React 的移动次数不是理论最优」）。

5. 「为什么 type 不同就直接重建？」
   因为 type 代表「这是什么元素/组件」——div 与 span 的属性集、行为、内容模型都不同；组件 A 与组件 B 的状态形状、生命周期、子结构都可能完全不同。在这种情况下「复用 DOM 节点」没有意义（几乎所有东西都要换掉），而且容易出错（状态含义不同）。所以 React 选择「直接卸载重建」——这既简单又安全，代价是「跨类型切换会丢状态」（这也解释了「在组件内部定义组件」为什么要避免——每次都是新 type）。

6. 「跨层移动节点会怎样？」
   会被当成「删除旧节点 + 创建新节点」（因为「同层比较」根本不去别层找对应节点）→ 整棵子树被重建 → 状态全部丢失（输入框内容、展开态、动画进度）。这是「O(n) 化」的代价：React 假设「开发者不会频繁跨层移动节点」，而这个假设在业务代码里基本成立。实践建议：保持 DOM 结构稳定（用「条件渲染」而不是「改变嵌套层级」）。

7. 「怎么验证自己的 diff 实现是对的？」
   五个测试用例：① 文本变化——只改 textContent，DOM 节点不变；② 属性变化——只更新对应属性，其它属性保留；③ 追加——只新建新节点，已有节点不动（可用「给 DOM 挂自定义属性/事件」来验证「节点被复用」）；④ 头部插入——用 key 时只新建一个节点、其余移动；⑤ 乱序——用 key 时只移动节点、不重建；改成 index 作 key 后应观察到「重建」行为。此外要验证「删除不再存在的属性」与「事件监听的移除与重建」。

8. 「手写 diff 与真实 React 的核心差距是什么？」
   手写版只实现了「同层比较 + type/key 判断 + DOM 更新」；真实 React 还多了：① Fiber 架构——把递归改成「可中断的链表遍历」（支持时间切片与优先级）；② 优先级调度（Lane）；③ 组件状态（Hooks 链表）与生命周期/Effect；④ 合成事件系统（委托到根容器）；⑤ 批处理；⑥ Fragment / Portal / Suspense / 并发特性。但「diff 的核心判断依据」就是手写版里的那两条：type 与 key——理解了它们，就理解了「为什么 key 不能是 index」与「为什么组件内定义组件会丢状态」。

一句话速记

手写简易 diff 的核心是「同层比较（patchChildren）+ 两个判断依据（type 与 key）+ key 匹配（Map + lastPlacedIndex 判移动）」：type 或 key 变了就卸载重建（状态丢失）、都相同就复用（只更新属性与子节点）；多节点 diff 是「用 Map 做 key → vnode 查找，复用时按 lastPlacedIndex 判断是否需要 insertBefore 移动，最后删除未复用的旧节点」（真实 React 是两轮遍历，Vue 用双端 + LIS 更优）；diff 属于 render 阶段，必须纯（不能有副作用）；「用 index 作 key」「跨层移动」「组件内定义组件」都会导致重建（状态丢失）；手写版不含 Fiber/优先级/Hooks/合成事件/批处理，但「diff 只看 type 与 key」这个结论与真实 React 一致。