🗒️react diff算法
type
status
date
slug
summary
tags
category
icon
password
Blocking
Blocked by
top
URL
Sub-item
Parent item
本质
通过对比新旧两株虚拟 DOM 树的变更差异，将更新补丁作用于真实 DOM，以最小成本完成视图更新。
diff所在阶段
- beginWork进行新旧虚拟DOM的diff比较
- completeWork,仅执行在beginWork产生的副作用列表。
- 在commit阶段一次性操作到真实DOM上
算法优化
传统diff算法
正常两棵树完全比对的算法复杂度是O(n 3 )。
将两颗树中所有的节点一一对比需要O(n²)的复杂度，在对比过程中发现旧节点在新的树中未找到，那么就需要把旧节点删除，删除一棵树的一个节点(找到一个合适的节点放到被删除的位置)的时间复杂度为O(n),同理添加新节点的复杂度也是O(n),合起来diff两个树的复杂度就是O(n³)
react diff算法
react为了降低复杂度，提出了三个前提：
- 只对同级比较，跨层级的dom不会进行复用
- 不同类型节点生成的dom树不同，此时会直接销毁老节点及子孙节点，并新建节点
- 可以通过key来对元素diff的过程提供复用的线索，例如：
diff算法可以总结为三个策略，分别从树、组件及元素三个层面进行复杂度的优化：
策略一（tree diff）
只比对同级的dom节点。
这一策略需要进行树比对，即对树进行分层比较。树比对的处理手法是非常“暴力”的，即两棵树只对同一层次的节点进行比较，如果发现节点已经不存在了，则该节点及其子节点会被完全删除掉，不会用于进一步的比较，这就提升了比对效率。
策略二（component diff）
如果组件类型一致，则默认为相似的树结构，否则默认为不同的树结构。（基于组件进行对比）
- 如果组件是同一类型则进行树比对。
- 只要类型不同，则不进行比对，直接替换组件所有节点。
策略三（element diff）
同一层级的子节点，可以通过标记 key 的方式进行列表对比。（基于节点进行对比）
元素比对主要发生在同层级中，通过标记节点操作生成补丁。节点操作包含了插入、移动、删除等。其中节点重新排序同时涉及插入、移动、删除三个操作，所以效率消耗最大，此时策略三起到了至关重要的作用。通过标记 key 的方式，React 可以直接移动 DOM 节点，降低内耗。如果不适用key，则只进行同索引比较通过类型和属性进行判断。
key的作用
当同一层级的某个节点添加了对于其他同级节点唯一的key属性，当它在当前层级的位置发生了变化后。react diff算法通过新旧节点比较后，如果发现了key值相同的新旧节点，就会执行移动操作（然后依然按原策略深入节点内部的差异对比更新），而不会执行原策略的删除旧节点，创建新节点的操作。这无疑大大提高了React性能和渲染效率。
移动优化
在移动前，会将节点在新集合中的位置和在老集合中lastIndex进行比较，如果if (newIndex>oldIndex) 进行移动操作（即从后到前），否则不进行移动操作。
如果遍历的过程中，发现在新集合中没有，但是在老集合中的节点，会进行删除操作
多节点diff更新过程
Diff算法的整体逻辑会经历两轮遍历：第一轮遍历：处理
更新的节点。第二轮遍历：处理剩下的不属于
更新的节点。详细
Vue与react diff算法区别
Vue 元素对比使用了双端比较
Vue diff在节点对比时使用了双端比较的算法，同时从新旧children的两端开始进行比较，借助key值找到可复用的节点，再进行相关操作。相比React的Diff算法，同样情况下可以减少移动节点次数。
问题
为什么 React 不采用 Vue 的双端对比算法。
React 不能通过双端对比进行 Diff 算法优化是因为目前 Fiber 上没有设置反向链表，
面试题
写 React / Vue 项目时为什么要在列表组件中写 key，其作用是什么？
主要是为了提升diff【同级比较】的效率。如果对列表的每一项增加一个key，即唯一索引，那就可以很清楚的知道两个列表谁少了谁没变。而如果不加key的话，就只能一个个对比了。
