图解快速diff

面试题：讲一讲 Vue3 的 diff 算法做了哪些改变？

双端存在的问题

在 Vue2 的双端 diff 中，主要的步骤如下：

新头和旧头比较
新尾和旧尾比较
旧头和新尾比较
新头和旧尾比较
暴力对比

这种对比策略其实会存在额外的移动操作。

对于 e 节点匹配不到，新建 e 节点对应的 DOM 节点，放置于旧头对应的 DOM 节点的前面
对于 b 节点，通过暴力比对能够找到，将 b 节点移动到旧头对应的 DOM 节点的前面
依此类推，c 节点、d 节点所对应的 DOM 节点都会进行移动操作

问题：其实完全不需要移动 bcd 节点，因为在新旧列表里面，这几个节点的顺序是一致的。只需要将 a 节点对应的 DOM 移动到 d 节点后即可。

Vue3快速diff

头头比对
尾尾比对
非复杂情况处理
复杂情况处理

和双端相同步骤

头头比对
尾尾比对
非复杂情况：指的是经历了头头比对和尾尾比对后，新旧列表有任意一方结束，此时会存在两种情况：
- 旧节点列表有剩余：对应的旧 DOM 节点全部删除
- 新节点列表有剩余：创建对应的 DOM 节点，放置于新头节点对应的 DOM 节点之后

和双端不同的步骤

经历了头头比对，尾尾比对后，新旧节点列表都有剩余，之后的步骤就和双端 diff 不一样：

初始化keyToNewIndexMap
初始化newIndexToOldIndexMap
更新newIndexToOldIndexMap
计算最长递增子序列
移动和挂载节点

1. 初始化keyToNewIndexMap

首先，定义了一个用于保存新节点下标的容器 keyToNewIndexMap，它的形式是 key - index，遍历还未处理的新节点，将它们的key和下标的映射关系存储到 keyToNewIndexMap 中。

const keyToNewIndexMap = new Map();
for (let i = newStartIdx; i <= newEndIdx; i++) {
  const key = newChildren[i].key;
  keyToNewIndexMap.set(key, i);
}

示意图：

也就是说，该 map 存储了所有未处理的新节点的 key 和 index 的映射关系。

2. 初始化newIndexToOldIndexMap

然后，定义了一个和未处理新节点个数同样大小的数组newIndexToOldIndexMap，默认每一项均为 0

const toBePatched = newEndIdx - newStartIdx + 1; // 计算没有处理的新节点的个数
const newIndexToOldIndexMap = new Array(toBePatched).fill(0);

示意图：

之所以一开始初始化为 0 ，其实是为了一开始假设新节点不存在于旧节点列表，之后就会对这个数组进行更新，倘若更新之后当前某个位置还为 0 ，就代表这一位对应的新节点在旧节点列表中不存在。

3. 更新newIndexToOldIndexMap

遍历未处理的旧节点，查找旧节点在新节点中的位置，决定是更新、删除还是移动。

遍历未处理的旧节点（从 oldStartIdx 到 oldEndIdx）
对于每个旧节点，执行以下操作：
- 查找对应的新节点索引 newIndex：
  - 如果旧节点有 key，通过 keyToNewIndexMap 获取 newIndex
  - 如果没有 key，需要遍历新节点列表，找到第一个与旧节点相同的节点
- 判断节点是否存在与新节点列表：
  - 如果 newIndex 没有找到，说明旧节点已经被删除，需要卸载
  - 如果 newIndex 找到，说明节点需要保留，执行以下操作：
    - 更新节点：调用 patch 函数更新节点内容
    - 记录映射关系：将旧节点的索引 +1 记录到 newIndexToOldIndexMap[newIndex - newStartIdx] 中
      思考🤔：为什么要把旧节点的索引 +1 然后进行存储？
      答案：因为前面我们在初始化newIndexToOldIndexMap这个数组的时候，所有的值都初始化为了0，代表新节点在旧节点列表中不存在。如果直接存储旧节点的索引，而恰好这个旧节点的索引又为0，那么此时是无法区分究竟是索引值还是不存在。
    - 标记节点是否需要移动：通过比较当前的遍历顺序和 newIndex，初步判断节点是否需要移动。

示意代码：

let moved = false;
let maxNewIndexSoFar = 0;
for (let i = oldStartIdx; i <= oldEndIdx; i++) {
  const oldNode = oldChildren[i];
  let newIndex;
  if (oldNode.key != null) {
    // 旧节点存在 key，根据 key 找到该节点在新节点列表里面的索引值
    newIndex = keyToNewIndexMap.get(oldNode.key);
  } else {
    // 遍历新节点列表匹配
  }
  if (newIndex === undefined) {
    // 旧节点在新节点中不存在，卸载
  } else {
    // 更新节点
    patch(oldNode, newChildren[newIndex], container);
    // 记录映射关系，注意这里在记录的时候，旧节点的索引要加1
    newIndexToOldIndexMap[newIndex - newStartIdx] = i + 1;
    // 判断是否需要移动
    if (newIndex >= maxNewIndexSoFar) {
      maxNewIndexSoFar = newIndex;
    } else {
      moved = true;
    }
  }
}

详细步骤：

i = 0：[0, 0, 0, 0, 1, 0]
i = 1：[0, 2, 0, 0, 1, 0]
i = 2：[0, 2, 3, 0, 1, 0]
i = 3：：[0, 2, 3, 4, 1, 0]

经过遍历旧节点列表这一操作之后，newIndexToOldIndexMap 就被更新，里面存储了每个新节点在旧节点列表里面的位置，不过要注意，这个索引位置是 +1. 更新后如果某一项仍然是 0，说明这一个节点确实在旧节点列表中不存在

if (newIndex >= maxNewIndexSoFar) {
  maxNewIndexSoFar = newIndex;
} else {
  moved = true;
}

maxNewIndexSoFar 用于判断节点的相对顺序是否保持递增，以决定是否需要移动节点。

如果当前的新节点索引大于等于 maxNewIndexSoFar，更新 maxNewIndexSoFar，节点相对顺序正确，无需标记移动
如果小于，说明节点相对顺序发生变化，标记 moved = true，后续需要根据 LIS 决定是否移动节点。

4. 计算最长递增子序列

通过 LIS，确定哪些节点的相对顺序未变，减少需要移动的节点数量。如果在前面的步骤中标记了 moved = true，说明有节点需要移动。使用 newIndexToOldIndexMap 计算最长递增子序列 increasingNewIndexSequence.

const increasingNewIndexSequence = moved ? getSequence(newIndexToOldIndexMap) : [];

上一步我们得到的 newIndexToOldIndex 为 [0, 2, 3, 4, 1, 0]，之后得到的最长递增子序列为 [1, 2, 3]，注意，Vue3内部在计算最长递增子序列的时候，返回的是元素对应的索引值。

思考🤔：注意这里的最长递增子序列不是记录的具体元素，而是元素对应的下标值。这样有什么好处？

答案：这样刚好抵消了前面+1的操作，重新变回了旧节点的下标。

5. 移动和挂载节点

根据计算结果，对需要移动和新建的节点进行处理。倒序遍历未处理的新节点。

思考🤔：为什么要倒序遍历？

答案：因为后续的节点位置是确定了的，通过倒序的方式能够避免锚点引用的时候不会出错。

具体步骤：

计算当前新节点在新节点列表中的索引 newIndex = newStartIdx + i
- newStartIdx 是未处理节点的起始索引
- i 为倒序遍历时的索引值
获取锚点 DOM，其目的是为了作为节点移动的参照物，当涉及到移动操作时，都移动到锚点 DOM 的前面
- 计算方法为 newIndex + 1 < newChildren.length ? newChildren[newIndex + 1].el : null
- 如果计算出来为 null，表示没有对应的锚点 DOM ，那么就创建并挂载到最后
判断节点究竟是新挂载还是移动
- 判断节点是否需要挂载：如果 newIndexToOldIndexMap[i] === 0，说明该节点在旧节点中不存在，需要创建并插入到锚点DOM位置之前。
  js
```
if (newIndexToOldIndexMap[i] === 0) {
  // 创建新节点并插入到锚点DOM位置之前
  patch(/*参数略 */);
}
```
- 判断节点是否需要移动：如果节点在 increasingNewIndexSequence 中，说明位置正确，无需移动。如果不在，则需要移动节点到锚点DOM位置之前。
  js
```
else if (moved) {
  if (!increasingNewIndexSequence.includes(i)) {
    // 移动节点到锚点DOM之前
    move(/*参数略 */);
  }
}
```

详细步骤：

i = 5
- newIndex = 5
- 锚点DOM：null
- 创建 m 对应的真实 DOM，挂载到最后
i = 4
- newIndex = 4
- 锚点DOM：m --> 真实DOM
- newIndexToOldIndexMap[4] 是否为 0，不是说明在旧节点列表里面是有的，能够复用
- 接下来看 i 是否在最长递增子序列里面，发现没有在最长递增子序列里面，那么这里就涉及到移动，移动到锚点DOM的前面，也就是 m 前面
i = 3
- newIndex = 3
- 锚点DOM：a --> 真实DOM
- newIndexToOldIndexMap[3] 不为0，说明旧节点列表里面是有的，能够复用
- 接下来需要看 i 是否在最长递增子序列里面，发现存在，所以不做任何操作
i = 2
- newIndex = 2
- 锚点DOM：d --> 真实DOM
- newIndexToOldIndexMap[2] 不为0，说明旧节点列表里面是有的，能够复用
- 接下来需要看 i 是否在最长递增子序列里面，发现存在，所以不做任何操作
i = 1
- newIndex = 1
- 锚点DOM：c --> 真实DOM
- newIndexToOldIndexMap[1] 不为0，说明旧节点列表里面是有的，能够复用
- 接下来需要看 i 是否在最长递增子序列里面，发现存在，所以不做任何操作
i = 0
- newIndex = 0
- 锚点DOM：b --> 真实DOM
- newIndexToOldIndexMap[0] 为0，说明旧节点列表里面没有
- 创建新的 DOM 节点，插入到锚点 DOM 节点之前

最终经过上面的操作：

e：新建并且插入到 b 之前
b：位置不变，没有做移动操作
c：位置不变，没有做移动操作
d：位置不变，没有做移动操作
a：移动到 m 之前
m：新建并且插入到末尾

整个 diff 下来 DOM 操作仅仅有 1 次移动，2 次新建。做到了最最最小化 DOM 操作次数，没有一次 DOM 操作是多余的。

面试题：讲一讲 Vue3 的 diff 算法做了哪些改变？
参考答案：
Vue2 采用的是双端 diff 算法，而 Vue3 采用的是快速 diff. 这两种 diff 算法前面的步骤都是相同的，先是新旧列表的头节点进行比较，当发现无法复用则进行新旧节点列表的尾节点比较。
一头一尾比较完后，如果旧节点列表有剩余，就将对应的旧 DOM 节点全部删除掉，如果新节点列表有剩余：将新节点列表中剩余的节点创建对应的 DOM，放置于新头节点对应的 DOM 节点后面。
之后两种 diff 算法呈现出不同的操作，双端会进行旧头新尾比较、无法复用则进行旧尾新头比较、再无法复用这是暴力比对，这样的处理会存在多余的移动操作，即便一些新节点的前后顺序和旧节点是一致的，但是还是会产生移动操作。
而 Vue3 快速 diff 则采用了另外一种做法，找到新节点在旧节点中对应的索引列表，然后求出最长递增子序列，凡是位于最长递增子序列里面的索引所对应的元素，是不需要移动位置的，这就做到了只移动需要移动的 DOM 节点，最小化了 DOM 的操作次数，没有任何无意义的移动。可以这么说，Vue3 的 diff 再一次将性能优化到了极致，整套操作下来，没有一次 DOM 操作是多余的，仅仅执行了最必要的 DOM 操作。

-EOF-

图解快速diff ​

图解快速diff