Vue 与 React 的 Diff 算法差异

问题

Vue 和 React 的 diff 算法有什么区别？

解答

两者都基于同层比较的策略，但具体实现不同。

React Diff 策略

React 采用单向遍历，从左到右依次比较：

// React diff 简化逻辑
function diffChildren(oldChildren, newChildren) {
  let lastPlacedIndex = 0;
  
  // 第一轮：从左到右遍历，处理可复用节点
  for (let i = 0; i < newChildren.length; i++) {
    const newChild = newChildren[i];
    const oldChild = oldChildren.find(c => c.key === newChild.key);
    
    if (oldChild) {
      // 找到可复用节点
      const oldIndex = oldChildren.indexOf(oldChild);
      if (oldIndex < lastPlacedIndex) {
        // 需要移动：老节点在 lastPlacedIndex 左边
        move(newChild);
      } else {
        // 不需要移动，更新 lastPlacedIndex
        lastPlacedIndex = oldIndex;
      }
    } else {
      // 新增节点
      insert(newChild);
    }
  }
  
  // 删除多余的老节点
  oldChildren.forEach(child => {
    if (!newChildren.find(c => c.key === child.key)) {
      remove(child);
    }
  });
}

示例：A B C D → D A B C

React 处理过程：

1. D 在老列表索引 3，lastPlacedIndex = 3
2. A 在老列表索引 0 < 3，需要移动
3. B 在老列表索引 1 < 3，需要移动
4. C 在老列表索引 2 < 3，需要移动

结果：移动 3 次

Vue Diff 策略

Vue 2/3 采用双端比较，同时从两端向中间遍历：

// Vue 双端 diff 简化逻辑
function diffChildren(oldChildren, newChildren) {
  let oldStart = 0, oldEnd = oldChildren.length - 1;
  let newStart = 0, newEnd = newChildren.length - 1;
  
  while (oldStart <= oldEnd && newStart <= newEnd) {
    const oldStartNode = oldChildren[oldStart];
    const oldEndNode = oldChildren[oldEnd];
    const newStartNode = newChildren[newStart];
    const newEndNode = newChildren[newEnd];
    
    if (oldStartNode.key === newStartNode.key) {
      // 头头相同
      patch(oldStartNode, newStartNode);
      oldStart++;
      newStart++;
    } else if (oldEndNode.key === newEndNode.key) {
      // 尾尾相同
      patch(oldEndNode, newEndNode);
      oldEnd--;
      newEnd--;
    } else if (oldStartNode.key === newEndNode.key) {
      // 头尾相同：老头 = 新尾，移动到右边
      patch(oldStartNode, newEndNode);
      move(oldStartNode, afterNode(oldEndNode));
      oldStart++;
      newEnd--;
    } else if (oldEndNode.key === newStartNode.key) {
      // 尾头相同：老尾 = 新头，移动到左边
      patch(oldEndNode, newStartNode);
      move(oldEndNode, oldStartNode);
      oldEnd--;
      newStart++;
    } else {
      // 四种都不匹配，用 key 查找
      // Vue 3 在这里使用最长递增子序列优化
      handleKeyedChildren();
    }
  }
}

同样示例：A B C D → D A B C

Vue 处理过程：

1. 老尾 D = 新头 D，移动 D 到最前面
2. 老头 A = 新头 A，不动
3. 老头 B = 新头 B，不动
4. 老头 C = 新头 C，不动

结果：移动 1 次

Vue 3 的最长递增子序列优化

// Vue 3 使用 LIS 减少移动次数
function getSequence(arr) {
  const result = [0];
  const p = arr.slice();
  
  for (let i = 1; i < arr.length; i++) {
    const current = arr[i];
    if (current !== 0) {
      const lastIndex = result[result.length - 1];
      if (arr[lastIndex] < current) {
        p[i] = lastIndex;
        result.push(i);
        continue;
      }
      // 二分查找插入位置
      let left = 0, right = result.length - 1;
      while (left < right) {
        const mid = (left + right) >> 1;
        if (arr[result[mid]] < current) {
          left = mid + 1;
        } else {
          right = mid;
        }
      }
      if (current < arr[result[left]]) {
        if (left > 0) p[i] = result[left - 1];
        result[left] = i;
      }
    }
  }
  
  // 回溯得到最长递增子序列
  let len = result.length;
  let last = result[len - 1];
  while (len-- > 0) {
    result[len] = last;
    last = p[last];
  }
  return result;
}

关键点

• 遍历方向：React 单向从左到右，Vue 双端从两头向中间
• 移动策略：React 用 lastPlacedIndex 判断，Vue 用头尾交叉比较
• 性能差异：节点整体移动（如首尾互换）时，Vue 更高效
• Vue 3 优化：引入最长递增子序列算法，进一步减少 DOM 操作
• key 的作用：两者都依赖 key 来识别节点，没有 key 会退化为逐个比较