文章目录
一文讲清楚React的diff算法
1. 为什么需要diff
- 首先,diff只有在更新的时候才会有,首次渲染是全量渲染,不存在对比一说
- 那为什么更新的时候需要diff呢,我们知道React通过VDOM减少对DOM的操作,但是当我们state或者props变化的时候,不能只要有变化就重新生成整个DOM吧,我们最好是知道哪变了,变啥了,影不影响目前的渲染,要不要全部重新渲染还是是渲染部分就可以
- diff算法就是干这个事
2. diff的具体策略和实现
- React将传统的时间复杂度为O(n3)循环递归遍历VDOM优化为时间复杂度为O(n1)的diff算法,主要通过一下三个策略
-
- 节点的跨层级移动忽略不计,针对TreeDiff优化
-
- 相同类的两个组件会生成相似的树状结构,不同类的两个组件将会生成不同的树状结构,针对Component Diff进行优化
-
- 同一层的节点,通过key进行区分,针对Element Diff进行优化
2.1 Tree Diff
- 只删除创建不移动
- 简单点来说就是同一层级上,旧节点有子节点A,新节点没有,但是新节点的子节点B下面有A节点,这时候不会把旧的节点A移动到D节点下面,而是直接在B节点下面新建子节点A,并删除原来的子节点A
2.2 Component Diff
- 对比前后,如果组件的类型相同,则继续下走
- 如果组件类型不同,删除旧组件,创建新组建
2.3 Element Diff
Element Diff 对应三种节点操作,分别为 INSERT_MARKUP(插入)、MOVE_EXISTING(移动) 和 REMOVE_NODE(删除)。
-
- INSERT_MARKUP:新的组件类型不在旧集合中,即全新的节点,需要对新节点进行插入操作。
-
- MOVE_EXISTING:旧集合中有新组件类型,且 element 是可更新的类型,generateComponent 已调用 recevieComponent,这种情况下 prevChild = nextChild,这时候就需要做移动操作,可以复用以前的 DOM 节点。
-
- REMOVE_NODE:旧组件类型,在新集合里也有,但对应的 element 不同则不能直接复用和更新,需要执行删除操作,或者旧组件不在新集合里的,也需要执行删除操作。
- REMOVE_NODE:旧组件类型,在新集合里也有,但对应的 element 不同则不能直接复用和更新,需要执行删除操作,或者旧组件不在新集合里的,也需要执行删除操作。
index: 新集合的遍历下标。
oldIndex:当前节点在⽼集合中的下标
maxIndex:在新集合访问过的节点中,其在⽼集合的最⼤下标
如果当前节点在新集合中的位置⽐⽼集合中的位置靠前的话,是不会影响后续节点操作的,这⾥这时候
被动字节不⽤动
操作过程中只⽐较oldIndex和maxIndex,规则如下:当oldIndex>maxIndex时,将oldIndex的值赋值给maxIndex
当oldIndex=maxIndex时,不操作
当oldIndex<maxIndex时,将当前节点移动到index的位置
diff 过程如下:节点B:此时 maxIndex=0,oldIndex=1;满⾜ maxIndex< oldIndex,因此B节点不动,此时
maxIndex= Math.max(oldIndex, maxIndex),就是1节点A:此时maxIndex=1,oldIndex=0;不满⾜maxIndex< oldIndex,因此A节点进⾏移动操作,
此时maxIndex= Math.max(oldIndex, maxIndex),还是1节点D:此时maxIndex=1, oldIndex=3;满⾜maxIndex< oldIndex,因此D节点不动,此时
maxIndex= Math.max(oldIndex, maxIndex),就是3节点C:此时maxIndex=3,oldIndex=2;不满⾜maxIndex< oldIndex,因此C节点进⾏移动操作,
当前已经⽐较完了
当ABCD节点⽐较完成后, diff 过程还没完,还会整体遍历⽼集合中节点,看有没有没⽤到的节点,
有的话,就删除
2.4 diff算法源码
_updateChildren: function(nextNestedChildrenElements, transaction, context) {
// 存储之前渲染的子元素
var prevChildren = this._renderedChildren;
// 存储已经移除的子元素
var removedNodes = {};
// 存储将要挂载的子元素
var mountImages = [];
// 获取新的子元素数组,并执行子元素的更新
var nextChildren = this._reconcilerUpdateChildren(
prevChildren,
nextNestedChildrenElements,
mountImages,
removedNodes,
transaction,
context
);
// 如果新旧子元素都不存在,直接返回
if (!nextChildren && !prevChildren) {
return;
}
var updates = null;
var name;
var nextIndex = 0;
var lastIndex = 0;
var nextMountIndex = 0;
var lastPlacedNode = null;
for (name in nextChildren) {
if (!nextChildren.hasOwnProperty(name)) {
continue;
}
var prevChild = prevChildren && prevChildren[name];
var nextChild = nextChildren[name];
if (prevChild === nextChild) {
// 同一个引用,说明是使用的同一个component,需要进行移动操作
// 移动已有的子节点
// 注意:这里根据nextIndex, lastIndex决定是否移动
updates = enqueue(
updates,
this.moveChild(prevChild, lastPlacedNode, nextIndex, lastIndex)
);
// 更新lastIndex
lastIndex = Math.max(prevChild._mountIndex, lastIndex);
// 更新component的.mountIndex属性
prevChild._mountIndex = nextIndex;
} else {
if (prevChild) {
// 更新lastIndex
lastIndex = Math.max(prevChild._mountIndex, lastIndex);
}
// 添加新的子节点在指定的位置上
updates = enqueue(
updates,
this._mountChildAtIndex(
nextChild,
mountImages[nextMountIndex],
lastPlacedNode,
nextIndex,
transaction,
context
)
);
nextMountIndex++;
}
// 更新nextIndex
nextIndex++;
lastPlacedNode = ReactReconciler.getHostNode(nextChild);
}
// 移除掉不存在的旧子节点,和旧子节点和新子节点不同的旧子节点
for (name in removedNodes) {
if (removedNodes.hasOwnProperty(name)) {
updates = enqueue(
updates,
this._unmountChild(prevChildren[name], removedNodes[name])
);
}
}
}