React Router
React 18+ 源码深度解读/React 核心机制

Diff 算法实现

深入理解 React Diff 算法的实现原理，包括单节点 Diff、多节点 Diff 和数组 Diff 算法

Diff 算法实现

Diff 算法是 React 性能优化的核心，它通过比较新旧虚拟 DOM 树的差异，最小化真实 DOM 的操作次数。本文将深入分析 React 18+ 中 Diff 算法的实现原理。

🎯 核心概念

Diff 算法的限制

React 的 Diff 算法基于两个假设：

  1. 相同类型的元素产生相同的树结构
  2. 开发者可以通过 key 属性标识哪些子元素在不同渲染中保持稳定

Diff 策略

React 采用以下策略进行 Diff：

  1. 只对同级元素进行 Diff
  2. 通过 key 和 type 判断元素是否可复用
  3. 采用双指针算法优化数组 Diff

🔍 源码实现分析

1. Diff 入口函数

// packages/react-reconciler/src/ReactChildFiber.js

function reconcileChildFibers(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  newChild: any,
  lanes: Lanes,
): Fiber | null {
  // 处理 null 或 undefined
  if (newChild === null || newChild === undefined) {
    return null;
  }

  // 处理单个元素
  if (typeof newChild === 'object' && newChild !== null) {
    switch (newChild.$$typeof) {
      case REACT_ELEMENT_TYPE:
        return placeSingleChild(
          reconcileSingleElement(
            returnFiber,
            currentFirstChild,
            newChild,
            lanes,
          ),
        );
      case REACT_PORTAL_TYPE:
        return placeSingleChild(
          reconcileSinglePortal(
            returnFiber,
            currentFirstChild,
            newChild,
            lanes,
          ),
        );
      case REACT_LAZY_TYPE:
        // 处理 lazy 组件
        const payload = newChild._payload;
        const init = newChild._init;
        return reconcileChildFibers(
          returnFiber,
          currentFirstChild,
          init(payload),
          lanes,
        );
    }

    // 处理数组
    if (isArray(newChild)) {
      return reconcileChildrenArray(
        returnFiber,
        currentFirstChild,
        newChild,
        lanes,
      );
    }

    // 处理迭代器
    if (getIteratorFn(newChild)) {
      return reconcileChildrenIterator(
        returnFiber,
        currentFirstChild,
        newChild,
        lanes,
      );
    }
  }

  // 处理文本节点
  if (typeof newChild === 'string' || typeof newChild === 'number') {
    return placeSingleChild(
      reconcileSingleTextNode(
        returnFiber,
        currentFirstChild,
        '' + newChild,
        lanes,
      ),
    );
  }

  return null;
}

2. 单节点 Diff

// packages/react-reconciler/src/ReactChildFiber.js

function reconcileSingleElement(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  element: ReactElement,
  lanes: Lanes,
): Fiber {
  const key = element.key;
  let child = currentFirstChild;

  // 遍历当前子节点，寻找可复用的节点
  while (child !== null) {
    if (child.key === key) {
      // key 相同，检查 type
      if (child.elementType === element.type) {
        // type 也相同，可以复用
        deleteRemainingChildren(returnFiber, child.sibling);
        const existing = useFiber(child, element.props);
        existing.return = returnFiber;
        return existing;
      } else {
        // key 相同但 type 不同，删除所有子节点
        deleteRemainingChildren(returnFiber, child);
        break;
      }
    } else {
      // key 不同，删除当前节点
      deleteChild(returnFiber, child);
    }
    child = child.sibling;
  }

  // 创建新的 Fiber 节点
  const created = createFiberFromElement(element, returnFiber.mode, lanes);
  created.return = returnFiber;
  return created;
}

3. 文本节点 Diff

// packages/react-reconciler/src/ReactChildFiber.js

function reconcileSingleTextNode(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  textContent: string,
  lanes: Lanes,
): Fiber {
  // 如果当前第一个子节点是文本节点，可以复用
  if (currentFirstChild !== null && currentFirstChild.tag === HostText) {
    deleteRemainingChildren(returnFiber, currentFirstChild.sibling);
    const existing = useFiber(currentFirstChild, textContent);
    existing.return = returnFiber;
    return existing;
  }

  // 删除所有子节点
  deleteRemainingChildren(returnFiber, currentFirstChild);
  
  // 创建新的文本 Fiber
  const created = createFiberFromText(textContent, returnFiber.mode, lanes);
  created.return = returnFiber;
  return created;
}

4. 数组 Diff（核心算法）

// packages/react-reconciler/src/ReactChildFiber.js

function reconcileChildrenArray(
  returnFiber: Fiber,
  currentFirstChild: Fiber | null,
  newChildren: Array<*>,
  lanes: Lanes,
): Fiber | null {
  let resultingFirstChild: Fiber | null = null;
  let previousNewFiber: Fiber | null = null;

  let oldFiber = currentFirstChild;
  let lastPlacedIndex = 0;
  let newIdx = 0;
  let nextOldFiber = null;

  // 第一轮遍历：处理更新的节点
  for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
    if (oldFiber.index > newIdx) {
      nextOldFiber = oldFiber;
      oldFiber = null;
    } else {
      nextOldFiber = oldFiber.sibling;
    }

    const newFiber = updateSlot(returnFiber, oldFiber, newChildren[newIdx], lanes);
    
    if (newFiber === null) {
      if (oldFiber === null) {
        oldFiber = nextOldFiber;
      }
      break;
    }

    if (shouldTrackSideEffects) {
      if (oldFiber && newFiber.alternate === null) {
        // 新 Fiber 没有复用旧 Fiber，标记删除
        deleteChild(returnFiber, oldFiber);
      }
    }

    lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
    
    if (previousNewFiber === null) {
      resultingFirstChild = newFiber;
    } else {
      previousNewFiber.sibling = newFiber;
    }
    previousNewFiber = newFiber;
    oldFiber = nextOldFiber;
  }

  // 处理剩余的新节点
  if (newIdx === newChildren.length) {
    deleteRemainingChildren(returnFiber, oldFiber);
    return resultingFirstChild;
  }

  // 处理剩余的旧节点
  if (oldFiber === null) {
    for (; newIdx < newChildren.length; newIdx++) {
      const newFiber = createChild(returnFiber, newChildren[newIdx], lanes);
      if (newFiber === null) {
        continue;
      }
      lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
      if (previousNewFiber === null) {
        resultingFirstChild = newFiber;
      } else {
        previousNewFiber.sibling = newFiber;
      }
      previousNewFiber = newFiber;
    }
    return resultingFirstChild;
  }

  // 将剩余的旧节点添加到 Map 中
  const existingChildren = mapRemainingChildren(returnFiber, oldFiber);

  // 第二轮遍历：处理剩余的节点
  for (; newIdx < newChildren.length; newIdx++) {
    const newFiber = updateFromMap(
      existingChildren,
      returnFiber,
      newIdx,
      newChildren[newIdx],
      lanes,
    );

    if (newFiber !== null) {
      if (shouldTrackSideEffects) {
        if (newFiber.alternate !== null) {
          // 复用了旧节点，从 Map 中删除
          existingChildren.delete(
            newFiber.key === null ? newIdx : newFiber.key,
          );
        }
      }
      lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
      if (previousNewFiber === null) {
        resultingFirstChild = newFiber;
      } else {
        previousNewFiber.sibling = newFiber;
      }
      previousNewFiber = newFiber;
    }
  }

  if (shouldTrackSideEffects) {
    // 删除剩余的旧节点
    existingChildren.forEach(child => deleteChild(returnFiber, child));
  }

  return resultingFirstChild;
}

5. 节点复用判断

// packages/react-reconciler/src/ReactChildFiber.js

function updateSlot(
  returnFiber: Fiber,
  oldFiber: Fiber | null,
  newChild: any,
  lanes: Lanes,
): Fiber | null {
  const key = oldFiber !== null ? oldFiber.key : null;

  if (typeof newChild === 'string' || typeof newChild === 'number') {
    // 文本节点
    if (key !== null) {
      return null;
    }
    return updateTextNode(returnFiber, oldFiber, '' + newChild, lanes);
  }

  if (typeof newChild === 'object' && newChild !== null) {
    switch (newChild.$$typeof) {
      case REACT_ELEMENT_TYPE: {
        if (newChild.key === key) {
          return updateElement(returnFiber, oldFiber, newChild, lanes);
        } else {
          return null;
        }
      }
      case REACT_PORTAL_TYPE: {
        if (newChild.key === key) {
          return updatePortal(returnFiber, oldFiber, newChild, lanes);
        } else {
          return null;
        }
      }
    }
  }

  return null;
}

6. 最长递增子序列算法

// packages/react-reconciler/src/ReactChildFiber.js

function placeChild(newFiber: Fiber, lastPlacedIndex: number, newIndex: number): number {
  newFiber.index = newIndex;
  
  if (!shouldTrackSideEffects) {
    // 不需要追踪副作用，直接返回
    return lastPlacedIndex;
  }

  const current = newFiber.alternate;
  if (current !== null) {
    const oldIndex = current.index;
    if (oldIndex < lastPlacedIndex) {
      // 需要移动
      newFiber.flags |= Placement;
      return lastPlacedIndex;
    } else {
      // 不需要移动
      return oldIndex;
    }
  } else {
    // 新节点，需要插入
    newFiber.flags |= Placement;
    return lastPlacedIndex;
  }
}

🎯 实际应用示例

1. 列表渲染优化

// ✅ 正确：使用稳定的 key
function TodoList({ todos }) {
  return (
    <ul>
      {todos.map(todo => (
        <TodoItem 
          key={todo.id} // 使用稳定的 ID
          todo={todo} 
        />
      ))}
    </ul>
  );
}

// ❌ 错误：使用不稳定的 key
function TodoList({ todos }) {
  return (
    <ul>
      {todos.map((todo, index) => (
        <TodoItem 
          key={index} // 使用索引，不稳定
          todo={todo} 
        />
      ))}
    </ul>
  );
}

2. 条件渲染优化

// ✅ 正确：使用 key 强制重新渲染
function ConditionalComponent({ showA }) {
  return (
    <div>
      {showA ? (
        <ComponentA key="a" />
      ) : (
        <ComponentB key="b" />
      )}
    </div>
  );
}

// ❌ 错误：相同类型组件可能导致状态混乱
function ConditionalComponent({ showA }) {
  return (
    <div>
      {showA ? (
        <ComponentA />
      ) : (
        <ComponentB />
      )}
    </div>
  );
}

3. 动态列表优化

// 使用 React.memo 优化子组件
const TodoItem = React.memo(({ todo, onToggle }) => {
  return (
    <li>
      <input
        type="checkbox"
        checked={todo.completed}
        onChange={() => onToggle(todo.id)}
      />
      <span>{todo.text}</span>
    </li>
  );
});

// 使用 useCallback 优化回调函数
function TodoList({ todos, onToggle }) {
  const handleToggle = useCallback((id) => {
    onToggle(id);
  }, [onToggle]);

  return (
    <ul>
      {todos.map(todo => (
        <TodoItem 
          key={todo.id}
          todo={todo}
          onToggle={handleToggle}
        />
      ))}
    </ul>
  );
}

🚀 性能优化技巧

1. 避免不必要的重新渲染

// 使用 React.memo 包装组件
const ExpensiveComponent = React.memo(({ data }) => {
  return <div>{/* 昂贵的渲染逻辑 */}</div>;
});

// 使用 useMemo 缓存计算结果
function ParentComponent({ items }) {
  const processedItems = useMemo(() => {
    return items.map(item => ({
      ...item,
      processed: expensiveProcessing(item)
    }));
  }, [items]);

  return <ExpensiveComponent data={processedItems} />;
}

2. 优化列表渲染

// 使用虚拟滚动处理大量数据
import { FixedSizeList as List } from 'react-window';

function VirtualizedList({ items }) {
  const Row = ({ index, style }) => (
    <div style={style}>
      {items[index]}
    </div>
  );

  return (
    <List
      height={400}
      itemCount={items.length}
      itemSize={35}
    >
      {Row}
    </List>
  );
}

3. 合理使用 key

// 使用稳定的 key
function UserList({ users }) {
  return (
    <div>
      {users.map(user => (
        <UserCard 
          key={user.id} // 使用唯一且稳定的 ID
          user={user}
        />
      ))}
    </div>
  );
}

// 避免使用随机数作为 key
function BadExample({ items }) {
  return (
    <div>
      {items.map(item => (
        <Item 
          key={Math.random()} // ❌ 每次渲染都会不同
          item={item}
        />
      ))}
    </div>
  );
}

📝 总结

React 的 Diff 算法通过以下策略实现高效更新：

  1. 分层比较：只对同级元素进行 Diff
  2. 类型检查：通过 key 和 type 判断元素是否可复用
  3. 双指针算法：优化数组 Diff 的性能
  4. 最长递增子序列：最小化节点移动次数

理解这些原理有助于我们编写更高效的 React 组件，避免不必要的重新渲染，提升应用性能。

下一步：渲染流程分析 - 深入分析 React 的渲染流程

React 核心机制

React 18+ 核心机制，包括 Diff 算法、渲染流程、状态管理等核心实现

React 高级特性

React 18+ 高级特性，包括并发特性、自动批处理、事件系统等新功能