乱序比对

本节目标：理解“乱序比对”的核心思路，并能把它用于实际开发或面试表达。

说明：原 OneNote 中有图片引用，但图片未包含在导出目录中；本页保留了可用的文字与代码内容。 s2到e2之间的为新旧列表有差异的元素的元素；我们建立一个map，然后遍历旧列表，取出每个元素，在map中看一下是否存在：

如果存在，即可复用，要比较差异；

如果新列表中不存在，即为删除的元素；

此外还有的情况是新列表中有，旧列表中没有，即新增 ；
let s1 = i;
let s2 = i;
const keyToNewIndexMap = new Map(); // key -> newIndex
for (let i = s2; i <= e2; i++) {
  keyToNewIndexMap.set(c2[i].key, i)
}

for (let i = s1; i <= e1; i++) {
  // 老的孩子
  const oldChild = c1[i];
  // 用老的孩子去新的里面找
  let newIndex = keyToNewIndexMap.get(oldChild.key);
  if (newIndex === void (0)) {
    // 多余的删掉
    unmount(oldChild);
  } else {
    patch(oldChild, c2[newIndex], el)
  }
}

// 新的总个数
==const== ==toBePatched== ===== ==e2== ==-== ==s2== ==+== ==1====;==
// 一个记录是否比对过的映射表
==const== ==newIndexToOldIndexMap== ===== ==new== ==Array====(====toBePatched====).====fill====(====0====);==
for (let i = s1; i <= e1; i++) {
  // 老的孩子
  const oldChild = c1[i];
  // 用老的孩子去新的里面找
  let newIndex = keyToNewIndexMap.get(oldChild.key);
  if (newIndex === void (0)) {
    // 多余的删掉
    unmount(oldChild);
  } else {
    // 新的位置对应的老的位置, 如果数组里放的值>0说明 已经pactch过了
    // 用来标记当前所patch过的结果
    ==newIndexToOldIndexMap====[====newIndex== ==-== ==s2====]== ===== ==i== ==+== ==1====;==
    patch(oldChild, c2[newIndex], el)
  }
}
// 到这只是新老属性和儿子的比对，没有移动位置

// 乱序比对
let s1 = i;
let s2 = i;
const keyToNewIndexMap = new Map(); // key -> newIndex
for (let i = s2; i <= e2; i++) {
  keyToNewIndexMap.set(c2[i].key, i)
}
// 新的总个数
const toBePatched = e2 - s2 + 1;
// 一个记录是否比对过的映射表
const newIndexToOldIndexMap = new Array(toBePatched).fill(0);
for (let i = s1; i <= e1; i++) {
  // 老的孩子
  const oldChild = c1[i];
  // 用老的孩子去新的里面找
  let newIndex = keyToNewIndexMap.get(oldChild.key);
  if (newIndex === void (0)) {
    // 多余的删掉
    unmount(oldChild);
  } else {
    // 用来标记当前所patch过的结果
    // i是在老列表中的索引，可能是0，加1跳过0
    // 如果不加0，即新老列表首元素就不同，但0表示没有patch所以加1
    // 如果是老列表中没有的新元素，其值为fill的0值；
    // 新老列表索引映射，如果数组里放的值>0说明 已经pactch过了
    newIndexToOldIndexMap[newIndex - s2] = i + 1;
    patch(oldChild, c2[newIndex], el)
  }
}
// 到这只是新老属性和儿子的比对，没有移动位置
// 需要移动位置
// 从最后一个元素往前倒序插入
for (let i = toBePatched - 1; i >= 0; i--) {
  // 找到h，即最末元素，i表示的是差异列表的索引，我们倒序来
  // i+s2的话，表示加上了之前相同元素的部分，index则为新列表中真实索引
  let index = i + s2;
  let current = c2[index];
  // 找到参照物，即最末元素后的第一个元素
  let anchor = index + 1 < c2.length ? c2[index + 1].el : null;
  // 如果已经patch过了，就不用创建元素了，可以复用
  // 如果为0，表示新列表新增的元素
  if (newIndexToOldIndexMap[i] === 0) {
    // 没有patch过，创建元素，  5 3 4 0
    patch(null, current, el, anchor)
  } else {
    // 不是0，说明是已经比对过属性和儿子的了
    // 目前无论如何都做了一遍倒叙插入，其实可以不用的
    // 可以根据刚才的数组来减少插入次数
    hostInsert(current.el, el, anchor);
  }
  // 这里发现缺失逻辑 我需要看一下current有没有el。如果没有el说明是新增的逻辑
  // 最长递增子序列来实现，vue2在移动元素的时候会有浪费，需优化
}

需要优化的部分，列表项整体插入：

由于之前我们得到了5,3,4,0，可知3，4顺序没变化，可以整体，即最长递增子序列

乱序比对 ​

乱序比对