本文仅用于笔者在学习Dom Diff算法的学习记录，如果想深入源码完整的学习，那么本篇文章可能不适合你。点个赞出门左转谢谢!(调皮)

若出现错误或者不严谨的地方，请大家指出！！！

React的假设

React需要同时维护两棵虚拟DOM树：一棵表示当前的DOM结构，另一棵在React状态变更将要重新渲染时生成。React通过比较这两棵树的差异，决定是否需要修改DOM结构，以及如何修改。这种算法称作Diff算法。

为了降低算法复杂度，React的diff会预设三个限制：

1. 只对同级元素进行Diff。如果一个DOM节点在前后两次更新中跨越了层级，那么React不会尝试复用他。
   
2. 两个不同类型的元素会产生出不同的树。如果元素由div变为p，React会销毁div及其子孙节点，并新建p及其子孙节点。
   
3. 开发者可以通过 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（删除）的一种或者多种情况

宏观思路：

1. 该节点能否进行复用，复用时是否需要移动位置，如果要移动位置应该移动到哪里？
2. 新节点元素中在老节点元素中没有找到可以复用的，就要新建节点插入
3. 老节点中存在剩余元素，就要进行删除

我们来推导一下如何复用节点：

复用子节点的前提是什么？---> 存在可以复用的节点 ---> 新的子节点在旧的节点中有对应节点---> 如果有相同的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还没有设置反向的链表。