Virtual DOM 与 Diff 算法

问题

解释 Virtual DOM 的工作原理，说明 Diff 算法如何实现 O(n) 复杂度，以及 React 中 key 的作用。

解答

什么是 Virtual DOM

Virtual DOM 是用 JavaScript 对象描述真实 DOM 结构的一种方式：

// 真实 DOM
<div class="container">
  <span>Hello</span>
</div>

// Virtual DOM
const vnode = {
  tag: 'div',
  props: { class: 'container' },
  children: [
    {
      tag: 'span',
      props: {},
      children: ['Hello']
    }
  ]
}

简易 Virtual DOM 实现

// 创建虚拟节点
function createElement(tag, props, ...children) {
  return {
    tag,
    props: props || {},
    children: children.flat()
  }
}

// 渲染为真实 DOM
function render(vnode) {
  // 文本节点
  if (typeof vnode === 'string' || typeof vnode === 'number') {
    return document.createTextNode(vnode)
  }

  const el = document.createElement(vnode.tag)

  // 设置属性
  for (const [key, value] of Object.entries(vnode.props)) {
    if (key.startsWith('on')) {
      // 事件处理
      el.addEventListener(key.slice(2).toLowerCase(), value)
    } else {
      el.setAttribute(key, value)
    }
  }

  // 递归渲染子节点
  vnode.children.forEach(child => {
    el.appendChild(render(child))
  })

  return el
}

Diff 算法实现

传统树 Diff 复杂度是 O(n³)，React 通过三个策略将其优化到 O(n)：

1. 同层比较：只比较同一层级的节点
2. 类型判断：不同类型的节点直接替换
3. key 标识：通过 key 识别节点身份

function diff(oldVNode, newVNode) {
  // 新节点不存在，删除
  if (!newVNode) {
    return { type: 'REMOVE' }
  }

  // 旧节点不存在，新增
  if (!oldVNode) {
    return { type: 'CREATE', newVNode }
  }

  // 类型不同，替换
  if (typeof oldVNode !== typeof newVNode ||
      (typeof oldVNode === 'string' && oldVNode !== newVNode) ||
      oldVNode.tag !== newVNode.tag) {
    return { type: 'REPLACE', newVNode }
  }

  // 同类型元素节点，比较属性和子节点
  if (newVNode.tag) {
    return {
      type: 'UPDATE',
      props: diffProps(oldVNode.props, newVNode.props),
      children: diffChildren(oldVNode.children, newVNode.children)
    }
  }

  // 无变化
  return null
}

// 比较属性
function diffProps(oldProps, newProps) {
  const patches = []

  // 检查新增和修改的属性
  for (const key in newProps) {
    if (oldProps[key] !== newProps[key]) {
      patches.push({ type: 'SET', key, value: newProps[key] })
    }
  }

  // 检查删除的属性
  for (const key in oldProps) {
    if (!(key in newProps)) {
      patches.push({ type: 'REMOVE', key })
    }
  }

  return patches
}

// 比较子节点（带 key 优化）
function diffChildren(oldChildren, newChildren) {
  const patches = []

  // 构建 key -> index 映射
  const oldKeyMap = new Map()
  oldChildren.forEach((child, index) => {
    if (child.props?.key != null) {
      oldKeyMap.set(child.props.key, index)
    }
  })

  newChildren.forEach((newChild, newIndex) => {
    const key = newChild.props?.key
    let oldIndex = -1

    if (key != null && oldKeyMap.has(key)) {
      // 通过 key 找到对应旧节点
      oldIndex = oldKeyMap.get(key)
    } else {
      // 无 key，按索引匹配
      oldIndex = newIndex < oldChildren.length ? newIndex : -1
    }

    const oldChild = oldIndex >= 0 ? oldChildren[oldIndex] : null
    patches.push({
      index: newIndex,
      patch: diff(oldChild, newChild)
    })
  })

  return patches
}

应用补丁

function patch(parent, patches, index = 0) {
  const el = parent.childNodes[index]

  switch (patches.type) {
    case 'CREATE':
      parent.appendChild(render(patches.newVNode))
      break

    case 'REMOVE':
      parent.removeChild(el)
      break

    case 'REPLACE':
      parent.replaceChild(render(patches.newVNode), el)
      break

    case 'UPDATE':
      // 更新属性
      patches.props.forEach(p => {
        if (p.type === 'SET') {
          el.setAttribute(p.key, p.value)
        } else {
          el.removeAttribute(p.key)
        }
      })
      // 更新子节点
      patches.children.forEach(childPatch => {
        patch(el, childPatch.patch, childPatch.index)
      })
      break
  }
}

key 的作用演示

// 没有 key：删除第一项时，React 认为是依次修改
// [A, B, C] -> [B, C]
// 实际操作：A->B, B->C, 删除C（3次操作）

// 有 key：React 能识别节点身份
// [A:1, B:2, C:3] -> [B:2, C:3]
// 实际操作：删除A（1次操作）

// 错误用法：用 index 作为 key
{items.map((item, index) => (
  <Item key={index} data={item} />  // ❌ 列表变化时会出问题
))}

// 正确用法：用唯一标识作为 key
{items.map(item => (
  <Item key={item.id} data={item} />  // ✅
))}

关键点

• Virtual DOM 本质：用 JS 对象描述 DOM，减少直接操作真实 DOM 的开销
• O(n) 复杂度：通过同层比较、类型判断、key 标识三个策略实现
• key 的作用：帮助 Diff 算法识别节点身份，实现最小化 DOM 操作
• key 的选择：使用稳定唯一的标识（如 id），避免使用数组索引
• 批量更新：Virtual DOM 可以将多次修改合并，一次性更新真实 DOM