Loading...

技术

82 分钟

虚拟 DOM 与 Diff 算法

JavaScript 进阶

Site Owner

发布于 2026-05-21

详解虚拟DOM设计权衡、双端Diff算法、最长递增子序列优化、React Fiber时间切片及key属性的正确使用

虚拟 DOM 与 Diff 算法

虚拟 DOM 与 Diff 算法

虚拟 DOM（VNode）的数据结构设计；同层 Diff 的核心假设与 O(n) 算法；key 在列表 Diff 中的关键作用；Vue 3 的最长递增子序列（LIS）优化；React Fiber 的可中断调度架构；以及 patchFlag 静态提升等编译期优化手段。

目录

虚拟 DOM 的本质
VNode 数据结构
Diff 算法基础
有 key 的列表 Diff
最长递增子序列（LIS）优化
React Fiber 架构
编译期优化
实战案例
深度追问

虚拟 DOM 的本质

虚拟 DOM 不是"更快"，而是可预测性与跨平台能力的权衡：

真实 DOM 操作成本
├── DOM 创建/删除    → 高
├── 样式重计算       → 高  
├── Layout（回流）   → 极高
└── 内存分配         → 高

VNode 操作成本
├── JS 对象创建      → 低
├── 对象比较（diff） → 中
└── 批量 DOM 更新    → 通过调度优化

核心价值：

最小化 DOM 操作：将多次状态变更合并为一次 patch
跨平台：VNode 可渲染到 DOM、Native（RN）、Canvas（Pixi.js）、SSR
可缓存性：静态 VNode 提升（hoisting），避免重复创建

VNode 数据结构

虚拟DOM与Diff算法深度解析—Vue双端Diff与React Fiber时间切片|新宇宙博客

// VNode 基础结构
const VNodeTypes = {
  TEXT: Symbol('Text'),
  COMMENT: Symbol('Comment'),
  FRAGMENT: Symbol('Fragment'),
  ELEMENT: 'element',
  COMPONENT: 'component'
};

// patchFlag：编译器静态分析的优化标记
const PatchFlags = {
  TEXT: 1,          // 动态文本
  CLASS: 2,         // 动态 class
  STYLE: 4,         // 动态 style
  PROPS: 8,         // 动态 props（非 class/style）
  FULL_PROPS: 16,   // 含动态 key 的 props
  STABLE_FRAGMENT: 64, // 稳定的 Fragment（子节点顺序不变）
  KEYED_FRAGMENT: 128, // 含 key 的 Fragment
  UNKEYED_FRAGMENT: 256,
  NEED_PATCH: 512,  // 只需要非 props patch（ref/onVnodeXxx）
  DYNAMIC_SLOTS: 1024, // 动态 slots
  HOISTED: -1,      // 静态提升节点（不参与 diff）
  BAIL: -2          // diff 退出标志（fallback 到完整 diff）
};

// VNode 完整结构
function createVNode(type, props = null, children = null, patchFlag = 0, shapeFlag = 0) {
  return {
    __v_isVNode: true,
    type,        // string | Component | Symbol
    props,
    key: props?.key ?? null,
    ref: props?.ref ?? null,
    children,    // string | Array<VNode> | object(slots)
    component: null, // 组件实例（仅 Component 类型）
    el: null,    // 对应的真实 DOM
    anchor: null, // Fragment 的锚点
    patchFlag,   // 编译优化标记
    shapeFlag,   // 节点形状标记（用于快速判断类型）
    dynamicProps: null, // 需要动态更新的 props 列表
    dynamicChildren: null, // 动态子节点列表（Block 收集）
  };
}

// 示例：h 函数
function h(type, props, children) {
  // 标准化 children
  let shapeFlag = 0;
  if (typeof type === 'string') {
    shapeFlag = 1; // ELEMENT
  } else if (typeof type === 'object') {
    shapeFlag = 4; // STATEFUL_COMPONENT
  }
  
  return createVNode(type, props, children, 0, shapeFlag);
}

1. 不同类型的节点 → 直接销毁重建（不尝试复用）
2. 相同 key 的节点 → 认为是同一节点，尝试复用
3. 只对同层节点进行比较（不跨层级）

function patch(n1, n2, container, anchor = null) {
  if (n1 === n2) return; // 完全相同，无需 patch

  // 类型不同 → 卸载旧节点，挂载新节点
  if (n1 && !isSameVNodeType(n1, n2)) {
    unmount(n1);
    n1 = null;
  }

  const { type, shapeFlag } = n2;

  switch (type) {
    case VNodeTypes.TEXT:
      processText(n1, n2, container);
      break;
    case VNodeTypes.FRAGMENT:
      processFragment(n1, n2, container);
      break;
    default:
      if (shapeFlag & 1 /* ELEMENT */) {
        processElement(n1, n2, container, anchor);
      } else if (shapeFlag & 4 /* STATEFUL_COMPONENT */) {
        processComponent(n1, n2, container);
      }
  }
}

function isSameVNodeType(n1, n2) {
  return n1.type === n2.type && n1.key === n2.key;
}

// Element patch
function patchElement(n1, n2) {
  const el = (n2.el = n1.el); // 复用 DOM 节点

  const oldProps = n1.props ?? {};
  const newProps = n2.props ?? {};

  // 利用 patchFlag 精准更新
  if (n2.patchFlag > 0) {
    if (n2.patchFlag & PatchFlags.CLASS) {
      if (oldProps.class !== newProps.class) {
        el.className = newProps.class ?? '';
      }
    }
    if (n2.patchFlag & PatchFlags.STYLE) {
      patchStyle(el, oldProps.style, newProps.style);
    }
    if (n2.patchFlag & PatchFlags.TEXT) {
      if (n1.children !== n2.children) {
        el.textContent = n2.children;
      }
    }
    if (n2.patchFlag & PatchFlags.PROPS) {
      for (const key of n2.dynamicProps) {
        patchProp(el, key, oldProps[key], newProps[key]);
      }
    }
  } else {
    // 无 patchFlag，全量 diff props
    patchProps(el, n2, oldProps, newProps);
  }

  patchChildren(n1, n2, el);
}

function patchKeyedChildren(c1, c2, container) {
  let i = 0;
  const l2 = c2.length;
  let e1 = c1.length - 1;
  let e2 = l2 - 1;

  // ===== Step 1: 从头同步 =====
  // 跳过头部相同的节点
  while (i <= e1 && i <= e2) {
    if (isSameVNodeType(c1[i], c2[i])) {
      patch(c1[i], c2[i], container);
      i++;
    } else break;
  }

  // ===== Step 2: 从尾同步 =====
  // 跳过尾部相同的节点
  while (i <= e1 && i <= e2) {
    if (isSameVNodeType(c1[e1], c2[e2])) {
      patch(c1[e1], c2[e2], container);
      e1--; e2--;
    } else break;
  }

  // ===== Step 3: 旧节点遍历完，新节点有剩余 → 挂载 =====
  if (i > e1) {
    if (i <= e2) {
      const anchor = e2 + 1 < l2 ? c2[e2 + 1].el : null;
      while (i <= e2) {
        mount(c2[i++], container, anchor);
      }
    }
  }

  // ===== Step 4: 新节点遍历完，旧节点有剩余 → 卸载 =====
  else if (i > e2) {
    while (i <= e1) unmount(c1[i++]);
  }

  // ===== Step 5: 乱序对比（核心） =====
  else {
    const s1 = i; // 旧节点乱序起点
    const s2 = i; // 新节点乱序起点

    // 5.1 建立新节点 key → index 映射
    const keyToNewIndexMap = new Map();
    for (let j = s2; j <= e2; j++) {
      const key = c2[j].key;
      if (key != null) keyToNewIndexMap.set(key, j);
    }

    // 5.2 遍历旧节点，复用/删除
    let patched = 0;
    const toBePatched = e2 - s2 + 1; // 新节点乱序区间长度
    let moved = false;
    let maxNewIndexSoFar = 0;
    
    // newIndexToOldIndexMap：新节点位置 → 旧节点位置（用于计算 LIS）
    const newIndexToOldIndexMap = new Array(toBePatched).fill(0);

    for (let j = s1; j <= e1; j++) {
      const prevChild = c1[j];
      
      if (patched >= toBePatched) {
        unmount(prevChild); // 新节点已全部 patch，多余旧节点删除
        continue;
      }

      let newIndex;
      if (prevChild.key != null) {
        newIndex = keyToNewIndexMap.get(prevChild.key);
      } else {
        // 无 key：线性搜索
        for (let k = s2; k <= e2; k++) {
          if (newIndexToOldIndexMap[k - s2] === 0 &&
              isSameVNodeType(prevChild, c2[k])) {
            newIndex = k;
            break;
          }
        }
      }

      if (newIndex === undefined) {
        unmount(prevChild); // 新列表中没有，删除
      } else {
        newIndexToOldIndexMap[newIndex - s2] = j + 1; // 记录映射（+1 避免 0 歧义）
        if (newIndex >= maxNewIndexSoFar) {
          maxNewIndexSoFar = newIndex;
        } else {
          moved = true; // 节点发生移动
        }
        patch(prevChild, c2[newIndex], container);
        patched++;
      }
    }

    // 5.3 根据 LIS 最小化 DOM 移动
    const increasingNewIndexSequence = moved
      ? getSequence(newIndexToOldIndexMap) // 计算 LIS
      : [];

    let j = increasingNewIndexSequence.length - 1;
    for (let k = toBePatched - 1; k >= 0; k--) {
      const nextIndex = s2 + k;
      const nextChild = c2[nextIndex];
      const anchor = nextIndex + 1 < l2 ? c2[nextIndex + 1].el : null;

      if (newIndexToOldIndexMap[k] === 0) {
        mount(nextChild, container, anchor); // 新节点，挂载
      } else if (moved) {
        if (j < 0 || k !== increasingNewIndexSequence[j]) {
          move(nextChild, container, anchor); // 需要移动
        } else {
          j--; // 在 LIS 中，无需移动
        }
      }
    }
  }
}

旧节点：[a, b, c, d, e]
新节点：[a, d, b, c, e]

newIndexToOldIndexMap（乱序区间）: [4, 2, 3]
                                   d  b  c
                                   
LIS（最长递增子序列）: [2, 3] (即 b, c 的位置)
→ b, c 不需要移动，只移动 d

没有 LIS：d, b, c 全部移动（3次 DOM 操作）
有 LIS：只移动 d（1次 DOM 操作）

// 求最长递增子序列的索引数组（贪心 + 二分，O(n log n)）
function getSequence(arr) {
  const p = arr.slice();    // 前驱索引记录
  const result = [0];       // 存储 LIS 元素的索引
  
  for (let i = 1; i < arr.length; i++) {
    const arrI = arr[i];
    
    if (arrI !== 0) { // 0 表示新节点，跳过
      const j = result[result.length - 1];
      
      if (arr[j] < arrI) {
        p[i] = j;
        result.push(i);
        continue;
      }
      
      // 二分查找：找第一个大于 arrI 的位置
      let left = 0;
      let right = result.length - 1;
      while (left < right) {
        const mid = (left + right) >> 1;
        if (arr[result[mid]] < arrI) {
          left = mid + 1;
        } else {
          right = mid;
        }
      }
      
      if (arrI < arr[result[left]]) {
        if (left > 0) p[i] = result[left - 1];
        result[left] = i;
      }
    }
  }
  
  // 回溯还原实际 LIS 索引序列
  let u = result.length;
  let v = result[u - 1];
  while (u-- > 0) {
    result[u] = v;
    v = p[v];
  }
  
  return result;
}

// 示例
console.log(getSequence([4, 2, 3])); // [1, 2] (即索引 1, 2 对应值 2, 3)

// Fiber 节点 = VNode + 工作单元
const FiberTypes = {
  FunctionComponent: 0,
  ClassComponent: 1,
  HostRoot: 3,
  HostElement: 5,
  HostText: 6,
};

class FiberNode {
  constructor(tag, pendingProps, key) {
    // 节点信息
    this.tag = tag;          // 节点类型
    this.key = key;
    this.type = null;        // 函数/类/字符串
    this.stateNode = null;   // 对应真实 DOM 或类组件实例
    
    // 树结构（链表）
    this.return = null;      // 父 Fiber
    this.child = null;       // 第一个子 Fiber
    this.sibling = null;     // 下一个兄弟 Fiber
    this.index = 0;

    // 工作单元
    this.pendingProps = pendingProps;
    this.memoizedProps = null;
    this.memoizedState = null;
    this.updateQueue = null;

    // 副作用标记
    this.flags = 0;          // Placement | Update | Deletion
    this.subtreeFlags = 0;
    this.deletions = null;
    
    // 双缓冲（current ↔ workInProgress）
    this.alternate = null;
    
    // 优先级（Concurrent 模式）
    this.lanes = 0;
    this.childLanes = 0;
  }
}

// 副作用标记
const Flags = {
  NoFlags:   0b0000000,
  Placement: 0b0000010, // 插入/移动
  Update:    0b0000100, // 更新
  Deletion:  0b0001000, // 删除
  Passive:   0b1000000, // useEffect
};

// 工作循环（简化版）
let workInProgress = null;
let shouldYield = false;

function workLoopConcurrent() {
  // 与 workLoopSync 的区别：检查是否需要让出控制权
  while (workInProgress !== null && !shouldYield) {
    performUnitOfWork(workInProgress);
    shouldYield = scheduler.shouldYield(); // 检查剩余时间
  }
}

function performUnitOfWork(fiber) {
  // Render 阶段：深度优先遍历（可中断）
  const next = beginWork(fiber); // 处理当前 fiber，返回子 fiber
  
  if (next === null) {
    // 没有子节点，向上完成
    completeUnitOfWork(fiber);
  } else {
    workInProgress = next;
  }
}

function completeUnitOfWork(fiber) {
  let completedWork = fiber;
  do {
    completeWork(completedWork); // 创建/更新真实 DOM（但不插入）
    
    const sibling = completedWork.sibling;
    if (sibling) {
      workInProgress = sibling; // 处理兄弟节点
      return;
    }
    completedWork = completedWork.return; // 回到父节点
  } while (completedWork);
}

// Commit 阶段：不可中断，同步执行副作用
function commitRoot(root) {
  // 三个子阶段
  commitBeforeMutationEffects(root); // getSnapshotBeforeUpdate
  commitMutationEffects(root);       // 实际 DOM 操作
  commitLayoutEffects(root);         // componentDidMount/Update, useLayoutEffect
  
  // 调度 useEffect（异步）
  schedulePassiveEffects(root);
}

// 模板：
// <div>
//   <span class="static">静态内容</span>
//   <p>{{ dynamic }}</p>
// </div>

// 未优化：每次渲染都创建所有 VNode
function render() {
  return h('div', null, [
    h('span', { class: 'static' }, '静态内容'), // 每次都创建！
    h('p', null, dynamic.value)
  ]);
}

// 编译器优化：静态节点提升到渲染函数外部
const _hoisted_1 = h('span', { class: 'static' }, '静态内容'); // 只创建一次

function render() {
  return h('div', null, [
    _hoisted_1,                                  // 直接复用
    h('p', { patchFlag: PatchFlags.TEXT }, dynamic.value)
  ]);
}

// Block 树：只收集动态节点，跳过静态节点的 diff
const blockStack = [];

function openBlock() {
  blockStack.push([]);
}

function createBlock(type, props, children) {
  const vnode = createVNode(type, props, children);
  vnode.dynamicChildren = blockStack.pop(); // 当前 block 收集的动态节点
  return vnode;
}

// 在创建动态 VNode 时，自动收集到当前 block
function createVNodeWithFlag(type, props, children, patchFlag) {
  const vnode = createVNode(type, props, children, patchFlag);
  if (patchFlag > 0 && blockStack.length) {
    blockStack[blockStack.length - 1].push(vnode); // 收集！
  }
  return vnode;
}

// Diff 时只需遍历 dynamicChildren，跳过静态节点
function patchBlock(n1, n2, container) {
  const dynamicChildren = n2.dynamicChildren;
  if (dynamicChildren) {
    for (let i = 0; i < dynamicChildren.length; i++) {
      // 直接 patch 动态节点，无需完整树遍历
      patchElement(n1.dynamicChildren[i], dynamicChildren[i]);
    }
  } else {
    patchChildren(n1, n2, container); // fallback
  }
}

// 最简版渲染器
function createRenderer(options) {
  const { createElement, insert, setElementText, patchProp } = options;
  
  function mount(vnode, container) {
    const el = (vnode.el = createElement(vnode.type));
    
    // 处理 props
    if (vnode.props) {
      for (const key in vnode.props) {
        patchProp(el, key, null, vnode.props[key]);
      }
    }
    
    // 处理 children
    if (typeof vnode.children === 'string') {
      setElementText(el, vnode.children);
    } else if (Array.isArray(vnode.children)) {
      vnode.children.forEach(child => mount(child, el));
    }
    
    insert(el, container);
  }

  function patch(n1, n2, container) {
    if (n1.type !== n2.type) {
      n1.el.remove();
      mount(n2, container);
      return;
    }
    
    const el = (n2.el = n1.el);
    
    // 更新 props
    const oldProps = n1.props ?? {};
    const newProps = n2.props ?? {};
    for (const key in newProps) {
      patchProp(el, key, oldProps[key], newProps[key]);
    }
    for (const key in oldProps) {
      if (!(key in newProps)) patchProp(el, key, oldProps[key], null);
    }
    
    // 更新 children
    patchChildren(n1, n2, el);
  }

  return { mount, patch };
}

// DOM 平台适配器
const domRenderer = createRenderer({
  createElement: tag => document.createElement(tag),
  insert: (el, parent, anchor = null) => parent.insertBefore(el, anchor),
  setElementText: (el, text) => el.textContent = text,
  patchProp: (el, key, oldVal, newVal) => {
    if (key.startsWith('on')) {
      const event = key.slice(2).toLowerCase();
      if (oldVal) el.removeEventListener(event, oldVal);
      if (newVal) el.addEventListener(event, newVal);
    } else if (newVal == null) {
      el.removeAttribute(key);
    } else {
      el.setAttribute(key, newVal);
    }
  }
});