本文仅用于笔者在学习Dom Diff算法的学习记录,如果想深入源码完整的学习,那么本篇文章可能不适合你。点个赞出门左转谢谢!(调皮)
若出现错误或者不严谨的地方,请大家指出!!!
React的假设
React需要同时维护两棵虚拟DOM树:一棵表示当前的DOM结构,另一棵在React状态变更将要重新渲染时生成。React通过比较这两棵树的差异,决定是否需要修改DOM结构,以及如何修改。这种算法称作Diff算法。
为了降低算法复杂度,React的diff会预设三个限制:
- 只对同级元素进行Diff。如果一个DOM节点在前后两次更新中跨越了层级,那么React不会尝试复用他。
- 两个不同类型的元素会产生出不同的树。如果元素由
div
变为p
,React会销毁div
及其子孙节点,并新建p
及其子孙节点。 - 开发者可以通过
key
属性 来暗示哪些子元素在不同的渲染下能保持稳定
tree diff
tree diff主要针对的是React dom节点跨层级的操作。由于跨层级的DOM移动操作较少,所以React diff算法的tree diff没有针对此种操作进行深入比较,只是简单进行了删除和创建操作
如图所示,A 节点(包括其子节点)整个被移动到 D 节点下,由于 React 只会简单地考虑同层级节点的位置变换,而对于不同层级的节点,只有创建和删除操作。
当根节点发现子节点中 A 消失了,就会直接销毁 A;当 D 发现多了一个子节点 A,则会创建新的 A(包括子节点)作为其子节点。此时,diff 的执行情况:create A → create B → create C → delete A
由此可以发现,当出现节点跨层级移动时,并不会出现想象中的移动操作,而是以 A 为根节点的整个树被重新创建。这是一种影响 React 性能的操作,因此官方建议不要进行 DOM 节点跨层级的操作。
component diff
component diff是专门针对更新前后的同一层级间的React组件比较的diff 算法:
component diff:组件比较,React
对于组件的策略有两种方式,一种是相同类型的组件和不同类型的组件
- 对同种类型组件对比,按照层级比较继续比较虚拟DOM树即可,但有种特殊的情况,当组件A如果变化为组件B的时候,有可能子组件并没有任何变化。但是React会将父节点下的所有子节点删除再重新挂载,所以用户可以通过shouldComponentUpdate() 来判断是否需要更新子组件
- 对于不同组件来说,
React
会直接判定该组件为dirty component(脏组件) ,无论结构是否相似,只要判断为脏组件就会直接替换整个组件的所有节点
element diff
element diff是专门针对同一层级的所有节点(包括元素节点和组件节点)的diff算法。当节点处于同一层级时,diff 提供了 3 种节点操作,分别为 INSERT_MARKUP(插入)
、MOVE_EXISTING(移动)
和 REMOVE_NODE(删除)
。
同一层级只有一个元素
React通过先判断key
是否相同,如果key
相同则判断type
是否相同,只有都相同时一个DOM节点才能复用。
同级有多个元素
同一层级多个元素的diff算法,会涉及到上述INSERT_MARKUP(插入)
、MOVE_EXISTING(移动)
和 REMOVE_NODE(删除)
的一种或者多种情况
宏观思路:
- 该节点能否进行复用,复用时是否需要移动位置,如果要移动位置应该移动到哪里?
- 新节点元素中在老节点元素中没有找到可以复用的,就要新建节点插入
- 老节点中存在剩余元素,就要进行删除
我们来推导一下如何复用节点:
复用子节点的前提是什么?---> 存在可以复用的节点 ---> 新的子节点在旧的节点中有对应节点---> 如果有相同的key和type,则代表可以复用节点,只需要通过移动Dom操作就可以完成更新。
移动操作的过程
diff算法整体会进行两轮的遍历
- 第一轮:处理可以复用,需要更新的节点
复用时判断需不需要移动,其实移动的过程,整体是向后移动的
如果不需要移动的话,lastIndex应该是0,1,2,3...递增的,如果顺序被打乱,则需要移动,则oldIndex < lastPlacedIndex。
- 第二轮:处理剩下不属于更新的节点,包括删除和插入
在遍历之前,会将旧节点的key(如果没有key会存index)和对应的节点存到map中
第一次遍历
- 遍历
newChildren
,i = 0
,将newChildren[i]
与oldFiber
比较,判断DOM节点是否可复用。 - 如果可复用,
i++
,比较newChildren[i]
与oldFiber.sibling
是否可复用。可以复用则重复步骤2。 - 如果不可复用,立即跳出整个遍历。
- 如果
newChildren
遍历完或者oldFiber
遍历完(即oldFiber.sibling === null
),跳出遍历。
第二次遍历
newChildren
遍历完,oldFiber
没遍历完, 就把多余的节点删除newChildren
没遍历完,oldFiber
遍历完, 就将新节点新增
那么如果两个都没有遍历完呢?
处理位置交换的节点
由于有节点交换了位置,所以不能再用位置索引对比前后的节点,那么怎样才能将同一个节点在两次更新中对应上呢?
你一定想到了,我们需要用key
属性了。
为了快速的找到key
对应的oldFiber
,我们将所有还没处理的oldFiber
放进以key
属性为key,Fiber
为value的map
。
再遍历剩余的newChildren
,通过newChildren[i].key
就能在existingChildren
中找到key
相同的oldFiber
再利用我们之前说的, 复用时判断需不需要移动,其实移动的过程,整体是向后移动的
如果不需要移动的话,lastIndex应该是0,1,2,3...递增的,如果顺序被打乱,则需要移动,则oldIndex < lastPlacedIndex。
type NodeList = Node[]; type Flag = "Placement" | "Deletion"; interface Node { key: string; flag?: Flag; index?: number; } // 用于调试 Diff算法 的Demo export default function diff(before: NodeList, after: NodeList): NodeList { let lastPlacedIndex = 0; const result: NodeList = []; const beforeMap = new Map<string, Node>(); before.forEach((node, i) => { node.index = i; beforeMap.set(node.key, node); }); for (let i = 0; i < after.length; i++) { const afterNode = after[i]; afterNode.index = i; const beforeNode = beforeMap.get(afterNode.key); if (beforeNode) { // 复用老节点 beforeMap.delete(beforeNode.key); const oldIndex = beforeNode.index as number; // 需要移动节点 if (oldIndex < lastPlacedIndex) { afterNode.flag = "Placement"; result.push(afterNode); continue; } else { lastPlacedIndex = oldIndex; } } else { // 创建新节点 afterNode.flag = "Placement"; result.push(afterNode); } } beforeMap.forEach((node) => { node.flag = "Deletion"; result.push(node); }); return result; }
存在的问题
明明只需要将D移动到最开头就可以完成目的,却分别将ABC移动到D的后面,移动了三次。所以在开发的过程中应该尽量减少节点移入首部的操作,会影响其性能。
在vue中,引入了双端Diff算法来进行优化,大家感兴趣的可以去了解一下。但是React却不能通过双端Diff算法进行优化,因为在目前的Fiber架构中,Fiber还没有设置反向的链表。