Diff算法的设计思想 VS 40行代码实现React核心Diff算法

这样，以O(1)的复杂度，我们就可以在❝❝❝

function diff(before: NodeList, after: NodeList): NodeList {
  const result: NodeList = [];

  // ...遍历前的准备工作

  for (let i = 0; i < after.length; i++) {
    // ...核心遍历逻辑
  }

  // ...遍历后的收尾工作

  return result;
}

中找到对应的节点：

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

遍历

遍历after时，如果在和after中同时存在节点和after(键同） ，我们称之为 node 可重用。

例如下面的例子中，b是可复用的：

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

对于可复用的节点来说，本次更新必然属于以下两种情况之一： ❀未移动♝ 如何判断伙计，如果可重复使用的节点已被移动？ ？ 时间，每一轮穿过的节点必须是当前穿过的所有节点中最右边的一个。

如果这个节点是一个可复用节点，那么之前是相同的lastPlacedIndex 有两种关系：

注意：nodeBefore 表示对应的node

• nodeBefore.index lastPlacedIndex对应的node。

  更新后，节点不在lastPlacedIndex对应的节点左侧，不是所有“当前遍历到的”）。

  这意味着节点已移至右侧，必须标记为位置。

  • nodeBefore.index >= lastPlacedIndex

  Node 已就位，不得移动。

  // 遍历到的最后一个可复用node在before中的index
  let 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);
  }
  

  遍历结束工作

  遍历结束后，如果Map❝之前的还剩下节点，则代表❝无disse❝不可复用d 并且必须标记为删除。

  例如下面的情况，遍历完after后，ap中的中仍然有{key: 'a'}：

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

  这意味着a 必须标记为删除。

  所以，最后，添加标签删除逻辑：

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

  完整代码请参见在线演示地址 [1]

  总结 ♼❝ Diff

算法为 last放置索引相关逻辑。

按照Demo多调试几次。我想你能明白其中的原理。

参考资料

[1]在线演示地址：https://codesandbox.io/s/naughty-matan-6fq7n6?file=/src/diff.ts