大家好，我卡颂。

凡是依赖虚拟DOM的框架，都需要「比较前后节点变化」的Diff算法。

网上有大量讲解Diff算法逻辑的文章。然而，即使作者语言再精练，再图文并茂，相信大部分同学看完用不了多久就忘了。

今天，我们换一种一劳永逸的学习方法 —— 实现React的核心Diff算法。

不难，只有40行代码。不信?往下看。

Diff算法的设计思路

试想，Diff算法需要考虑多少种情况呢?大体分三种，分别是：

节点属性变化，比如：

// 更新前
  
0
  
1
// 更新后
  
0
  
1

节点增删，比如：

// 更新前
  
0
  
1
  
2
// 更新后 情况1 —— 新增节点
  
0
  
1
  
2
  
3
// 更新后 情况2 —— 删除节点
  
0
  
1

节点移动，比如：

// 更新前
  
0
  
1
// 更新后
  
1
  
0

该如何设计Diff算法呢?考虑到只有以上三种情况，一种常见的设计思路是：

首先判断当前节点属于哪种情况。如果是增删，执行增删逻辑。如果是属性变化，执行属性变化逻辑。如果是移动，执行移动逻辑。

按这个方案，其实有个隐含的前提—— 「不同操作的优先级是相同的」。但在日常开发中，「节点移动」发生较少，所以Diff算法会优先判断其他情况。

基于这个理念，主流框架(React、Vue)的Diff算法都会经历多轮遍历，先处理「常见情况」，后处理「不常见情况」。

所以，这就要求「处理不常见情况的算法」需要能给各种边界case兜底。

换句话说，完全可以仅使用「处理不常见情况的算法」完成Diff操作。主流框架之所以没这么做是为了性能考虑。

本文会砍掉「处理常见情况的算法」，保留「处理不常见情况的算法」。

这样，只需要40行代码就能实现Diff的核心逻辑。

Demo介绍

首先，我们定义虚拟DOM节点的数据结构：

type Flag = "Placement" | "Deletion";interface Node {  key: string;  flag?: Flag;  index?: number;}

key是node的唯一标识，用于将节点在变化前、变化后关联上。

flag代表node经过Diff后，需要对相应的真实DOM执行的操作，其中：

Placement对于新生成的node，代表对应DOM需要插入到页面中。对于已有的node，代表对应DOM需要在页面中移动。Deletion代表node对应DOM需要从页面中删除。

index代表该node在同级node中的索引位置。

注：本Demo仅实现「为node标记flag」，没有实现「根据flag执行DOM操作」。

我们希望实现的diff方法，接收更新前与更新后的NodeList，为他们标记flag：

type NodeList = Node[];function diff(before: NodeList, after: NodeList): NodeList {  // ...代码}

比如对于：

// 更新前const before = [  {key: "a"}]// 更新后const after = [  {key: "d"}]// diff(before, after) 输出[  {key: "d", flag: "Placement"},  {key: "a", flag: "Deletion"}]

{key: "d", flag: "Placement"}代表d对应DOM需要插入页面。

{key: "a", flag: "Deletion"}代表a对应DOM需要被删除。

执行后的结果就是：页面中的a变为d。

再比如：

// 更新前const before = [  {key: "a"},  {key: "b"},  {key: "c"},]// 更新后const after = [  {key: "c"},  {key: "b"},  {key: "a"}]// diff(before, after) 输出[  {key: "b", flag: "Placement"},  {key: "a", flag: "Placement"}]

由于b之前已经存在，{key: "b", flag: "Placement"}代表b对应DOM需要向后移动(对应parentNode.appendChild方法)。abc经过该操作后变为acb。

由于a之前已经存在，{key: "a", flag: "Placement"}代表a对应DOM需要向后移动。acb经过该操作后变为cba。

执行后的结果就是：页面中的abc变为cba。

Diff算法实现

核心逻辑包括三步：

遍历前的准备工作。遍历after。遍历后的收尾工作。

function diff(before: NodeList, after: NodeList): NodeList {  const result: NodeList = [];  // ...遍历前的准备工作  for (let i = 0; i < after.length; i++) {    // ...核心遍历逻辑  }  // ...遍历后的收尾工作  return result;}

遍历前的准备工作

我们将before中每个node保存在以node.key为key，node为value的Map中。

这样，以O(1)复杂度就能通过key找到before中对应node：

// 保存结果const result: NodeList = [];  // 将before保存在map中const beforeMap = new Map();before.forEach((node, i) => {  node.index = i;  beforeMap.set(node.key, node);})

遍历after

当遍历after时，如果一个node同时存在于before与after(key相同)，我们称这个node可复用。

比如，对于如下例子，b是可复用的：

// 更新前const before = [  {key: "a"},  {key: "b"}]// 更新后const after = [  {key: "b"}]

对于可复用的node，本次更新一定属于以下两种情况之一：

不移动。移动。

如何判断可复用的node是否移动呢?

我们用lastPlacedIndex变量保存「遍历到的最后一个可复用node在before中的index」：

// 遍历到的最后一个可复用node在before中的indexlet lastPlacedIndex = 0;  

当遍历after时，每轮遍历到的node，一定是当前遍历到的所有node中最靠右的那个。

如果这个node是可复用的node，那么nodeBefore与lastPlacedIndex存在两种关系：

注：nodeBefore代表该可复用的node在before中的对应node。

nodeBefore.index < lastPlacedIndex。

代表更新前该node在lastPlacedIndex对应node左边。

而更新后该node不在lastPlacedIndex对应node左边(因为他是「当前遍历到的所有node中最靠右的那个」)。

这就代表该node向右移动了，需要标记Placement。

nodeBefore.index >= lastPlacedIndex。

该node在原地，不需要移动。

// 遍历到的最后一个可复用node在before中的indexlet lastPlacedIndex = 0;  for (let i = 0; i < after.length; i++) {const afterNode = after[i];afterNode.index = i;const beforeNode = beforeMap.get(afterNode.key);if (beforeNode) {  // 存在可复用node  // 从map中剔除该 可复用node  beforeMap.delete(beforeNode.key);  const oldIndex = beforeNode.index as number;  // 核心判断逻辑  if (oldIndex < lastPlacedIndex) {    // 移动    afterNode.flag = "Placement";    result.push(afterNode);    continue;  } else {    // 不移动    lastPlacedIndex = oldIndex;  }} else {  // 不存在可复用node，这是一个新节点  afterNode.flag = "Placement";  result.push(afterNode);}

遍历后的收尾工作

经过遍历，如果beforeMap中还剩下node，代表这些node没法复用，需要被标记删除。

比如如下情况，遍历完after后，beforeMap中还剩下{key: "a"}：

// 更新前const before = [  {key: "a"},  {key: "b"}]// 更新后const after = [  {key: "b"}]

这意味着a需要被标记删除。

所以，最后还需要加入标记删除的逻辑：

beforeMap.forEach(node => {  node.flag = "Deletion";  result.push(node);});

完整代码见在线Demo地址[1]。

总结

整个Diff算法的难点在于lastPlacedIndex相关逻辑。

跟着Demo多调试几遍，相信你能明白其中原理。

参考资料

[1]在线Demo地址:

https://codesandbox.io/s/naughty-matan-6fq7n6?file=/src/diff.ts。

关键词： 准备工作 设计思路 两种情况 一劳永逸