My Muri Life

切换主题

本页目录

Vue3中的diff算法 ​

VNode中key的作用？

用于diff算法的isSameVNodeType(n1, n2)函数中判断两个VNode是否是相同类型节点和建立求解LIS时的映射表。

JavaScript
const isSameVNodeType = (n1, n2) => {
  return n1.type === n2.type && n1.key === n2.key
}

何为最长递增子序列（LIS）？

最长递增子序列指，在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值依次递增，并且这个子序列的长度尽可能地大。

如何求解LIS？

Vue中是通过贪心 + 二分求解的LIS对应的下标
JavaScript
const getLIS = arr => {
  const copy = arr.slice(), len = arr.length
  const ret = [0]
  let i, j, l, r, mid
  for (i = 0; i < len; i++) {
    const A = arr[i]
    if (A !== 0) {
      j = ret[ret.length - 1]
      if (arr[j] < A) {
        copy[i] = j  // 记录ret更新前最后一个元素的索引值
        ret.push(i)
        continue
      }
      // 二分查找
      l = 0
      r = ret.length - 1
      while (l < r) {
        mid = (l + r) >> 1
        if (arr[ret[mid]] < A) {
          l = mid + 1
        } else {
          r = mid
        }
      }
      if (A < arr[ret[l]]) {
        if (l > 0) {
          copy[i] = ret[l - 1]
        }
        ret[l] = i
      }
    }
  }
  // 回溯
  l = ret.length
  r = ret[l - 1]
  while (l--) {
    ret[l] = r
    r = copy[r]
  }
  return ret
}

diff算法的五种场景（有处理顺序）： ​

1. 自前向后对比 ​

通过比对两节点是否为同类型节点，是就更新，不是就直接跳出，进入步骤2。

自前向后对比
JavaScript
const patchKeyedChildren = (c1, c2, container, parentAchor) => {
  let i = 0
  const l2 = c2.length
  let e1 = c1.length - 1
  let e2 = l2 - 1

  // 1. 自前向后对比
  // (a b) c
  // (a b) d
  while (i <= e1 && i <= e2) {
    const n1 = c1[i]
    const n2 = c2[i]
    if (isSameVNodeType(n1, n2)) {
      patch(n1, n2, container) // 更新节点
    } else {
      break // 不同就不管，交给后续情况处理
    }
    i++
  }
}

2. 自后向前对比 ​

通过比对两节点是否为同类型节点，是就更新，不是就直接跳出，进入步骤3。

自后向前对比
JavaScript
const patchKeyedChildren = (c1, c2, container, parentAchor) => {
  // 自后向前对比
  // a (b c)
  // d (b c)
  while (i <= e1 && i <= e2) {
    const n1 = c1[e1]
    const n2 = c2[e2]
    if (isSameVNodeType(n1, n2)) {
      patch(n1, n2, container) // 更新节点
    } else {
      break // 不同就不管，交给后续情况处理
    }
    e1--
    e2--
  }
}

3. 新节点多余旧节点 ​

当新节点多余旧节点时，经过步骤1和步骤2处理后，直接挂载新节点即可。

新节点多余旧节点
JavaScript
const patchKeyedChildren = (c1, c2, container, parentAchor) => {
  // 新节点多余旧节点（增加新节点）
  // (a b)
  // (a b) c
  // 此时有：i = 2, e1 = 1, e2 = 2
  // 或者
  // (a b)
  // c (a b)
  // 此时有：i = 0, e1 = -1, e2 = 0
  if (i > e1) {
    if (i <= e2) {
      const nextPos = e2 + 1
      // 新增节点插入位置
      const anchor = nextPos < l2 ? c2[nextPos].el : parentAchor
      while (i <= e2) {
        patch(null, c2[i], container, anchor)  // 挂载新节点
        i++
      }
    }
  }
}

4. 新节点少于余旧节点 ​

当新节点少余旧节点时，经过步骤1和步骤2处理后，直接卸载旧节点即可。

新节点少于余旧节点
JavaScript
const patchKeyedChildren = (c1, c2, container, parentAchor) => {
  // 新节点少于余旧节点（删除旧节点）
  // (a b) c
  // (a b)
  // 此时有：i = 2, e1 = 2, e2 = 1
  // 或者
  // a (b c)
  // (b c)
  // 此时有：i = 0, e1 = 0, e2 = -1
  else if (i > e2) {
    while (i <= e1) {
      unmount(c1[i])  // 多了就直接卸载
      i++
    }
  }
}

5. 乱序 ​

这是diff算法里最复杂的一种情况，里面又有三种情境：

  1. 建立索引表keyToNewIndexMap：建立经过前面步骤处理后剩余的乱序新节点的索引表，使用Map数据结构，其key为新节点的key值，value为数组下标index；
  2. 卸载无对应新节点的旧节点：根据索引表与旧节点的key建立newIndexToOldIndexMap（用于求LIS），若不存在就卸载旧节点；
  3. 移动节点与挂载新节点：根据newIndexToOldIndexMap求出LISIndex，若newIndexToOldIndexMap[i] === 0则挂载新节点，否则根据LISIndex的值移动节点到正确位置。
乱序
JavaScript
const patchKeyedChildren = (c1, c2, container, parentAchor) => {
  // 乱序
  // a b [c d e] f g
  // a b [e d c h ] f g
  // 此时有：i = 2，e1 = 4, e2 = 5
  else {
    const s1 = i // 旧节点的开始索引
    const s2 = i // 新节点的开始索引
    // 5.1 构建乱序节点Map => {key : index} 
    const keyToNewIndexMap = new Map()
    for (i = s2; i <= e2; i++) {
      const nextChild = c2[i]
      if (nextChild.key != null) {
        if (keyToNewIndexMap.has(nextChild.key)) {
          throw `${JSON.stringify(nextChild.key)}已存在`
        }
        keyToNewIndexMap.set(nextChild.key, i)
      }
    }
    // 5.2 对旧节点进行patch操作（）
    let j, patched = 0 // 以patch节点数
    const toBePatched = e2 - s2 + 1 // 带patch节点数
    let moved = false
    let maxNewIndexSoFar = 0
    // 用于求LIS
    const newIndexToOldIndexMap = new Array(toBePatched).fill(0)
    for (i = s1; i < e1; i++) {
      const prevChild = c1[i]
      if (patched >= toBePatched) {
        unmount(prevChild)
        continue
      }
      let newIndex
      if (prevChild.key != null) {
        newIndex = keyToNewIndexMap.get(prevChild.key)
      } else { // 找到没有对应的旧节点的新节点
        for (j = s2; j <= e2; j++) {
          if (newIndexToOldIndexMap[j - s2] === 0 && isSameVNodeType(prevChild, c2[j])) {
            newIndex = j
            break
          }
        }
      }
      if (newIndex === undefined) {  // 旧节点无对应的新节点（即删除）
        unmount(prevChild)
      } else {
        // 跳过已处理节点（场景1~4中处理的节点）
        newIndexToOldIndexMap[j - s2] = i + 1
        if (newIndex >= maxNewIndexSoFar) {  // 是否需要一定节点
          maxNewIndexSoFar = newIndex
        } else {
          moved = true
        }
        patch(prevChild, c2[newIndex], container)
        patched++
      }
    }
    // 5.3 节点移动与挂载
    const LISIndex = moved ? getLIS(newIndexToOldIndexMap) : EMPTY_ARR
    j = LISIndex.length - 1
    for (i = toBePatched - 1; i >= 0; i--) {
      const nextIndex = s2 + i // 需要更新的节点的下标
      const nextChild = c2[nextIndex]
      // 判断有无越界
      const anchor = nextIndex + 1 < l2 ? c2[nextIndex + 1].el : parentAchor
      if (newIndexToOldIndexMap[i] === 0) {
        // 挂载新节点
        patch(null, nextChild, container, anchor)
      } else if (moved) {
        // 移动节点
        if (j < 0 || i !== LISIndex[j]) { // LIS不存在或者已越界
          move(nextChild, container, anchor)
        } else {
          j--
        }
      }
    }
  }
}