Virtual DOM diff算法原理与同层比较策略
请详细解释React中Virtual DOM的diff算法原理，包括同层比较（level-by-level comparison）策略、key的作用、以及为什么采用O(n)复杂度的启发式算法而非标准的树编辑距离算法。
回答
我还是少年
React的diff算法基于三个核心策略实现O(n)复杂度：
1. 同层比较（Tree Level Comparison）
- 只对同一层级的节点进行逐层比较，不跨层级移动节点
- 如果某节点跨层级移动（如从A子树移到B子树），React直接销毁重建而非移动
- 这大大降低了算法复杂度（树编辑距离O(n³) → O(n)）
2. Key的作用
- 当同一层级多个子节点类型相同，key帮助React识别哪些节点是新增、删除或移动的
- 索引key（index作为key）可能导致性能问题：列表头部插入元素时，所有已有元素索引变化，React会全部重建
- 稳定唯一key（如id）让React复用DOM节点，只更新变化内容
3. 类型决定策略
- 根元素类型不同（div→span）：直接卸载旧树，挂载新树（触发完整生命周期）
- 类型相同：更新属性，递归diff子节点
- 组件类型相同：更新props，调用shouldComponentUpdate/React.memo决定是否继续
为什么不使用标准树编辑距离？ 标准最小编辑距离算法（如张骞算法）复杂度O(n³)或O(n²)，对真实DOM操作不可接受。React通过假设相同层级节点操作有限（列表调整仅排序）来达到O(n)。