IAmor

# 虚拟DOM之更新子节点（二）

查看本文的示例代码 (opens new window)

# KEY的作用

在之前的内容中，我们通过减少 DOM 操作的次数使得更新的性能得到了提升，但它仍然存在可优化的空间，要明白如何优化，那首先我们需要知道问题出在哪里。

旧子节点：

[
  h('li', null, 1),
  h('li', null, 2),
  h('li', null, 3)
]

新子节点：

[
  h('li', null, 3),
  h('li', null, 1),
  h('li', null, 2)
]

先来看一下，在没有Key存在时，是如何更新这对新旧子节点的。

h('li', null, 1) // 旧1
// vs
h('li', null, 3) // 新1

h('li', null, 2) // 旧2
// vs
h('li', null, 1) // 新2

h('li', null, 2) // 旧3
// vs
h('li', null, 1) // 新3

在这个例子中，新旧子节点会依次进行比较调用patch函数。

但实际上，我们通过观察新旧子节点，可以很容易的发现，新旧子节点中只有顺序是不同的，所以最佳操作应该是通过移动元素的位置来达到更新的目的。

既然移动元素是最佳期望，那么我们就需要思考一下，能否通过移动元素来完成更新？ 能够移动元素的关键在于：我们需要在新旧 children 的节点中保存映射关系，以便我们能够在旧 children 的节点中找到可复用的节点。

这时候我们就需要给 children 中的节点添加唯一标识，也就是我们常说的 key，在没有 key 的情况下，我们是没办法知道新 children 中的节点是否可以在旧 children 中找到可复用的节点的。

所以，我们给h函数添加一个key属性：

export function h(tag, data = null, children = null) {
  // 省略...

  // 返回 VNode 对象
  return {
    // 省略...
    key: data && data.key ? data.key : null
    // 省略...
  }
}

再看之前的例子：

// 旧 children
[
  h('li', { key: 'a' }, 1),
  h('li', { key: 'b' }, 2),
  h('li', { key: 'c' }, 3)
]

// 新 children
[
  h('li', { key: 'c' }, 3)
  h('li', { key: 'a' }, 1),
  h('li', { key: 'b' }, 2)
]

有了 key 我们就能够明确的知道新旧 children 中节点的映射关系，如下图所示：

知道了映射关系，我们就可以判断新子节点是否可被复用。

// 遍历新的 children
for (let i = 0; i < nextChildren.length; i++) {
  const nextVNode = nextChildren[i]
  // 遍历旧的 children
  for (let j = 0; j < prevChildren.length; j++) {
    const prevVNode = prevChildren[j]
    // 如果找到了具有相同 key 值的两个节点，则调用 `patch` 函数更新之
    if (nextVNode.key === prevVNode.key) {
      patch(prevVNode, nextVNode, container)
      break // 这里需要 break
    }
  }
}

这段代码中有两层嵌套的 for 循环语句，外层循环用于遍历新 children，内层循环用于遍历旧 children，其目的是尝试寻找具有相同 key 值的两个节点，如果找到了，则认为新 children 中的节点可以复用旧 children 中已存在的节点，这时我们仍然需要调用 patch 函数对节点进行更新，如果新节点相对于旧节点的 VNodeData 和子节点都没有变化，则 patch 函数什么都不会做

# 找到需要移动的节点

在我们已经找到了可复用的节点，并进行了合适的更新操作，下一步需要做的，就是判断一个节点是否需要移动以及如何移动。如何判断节点是否需要移动呢？

先看一个不需要移动的例子：

  • 取出新children的第一个节点，即li-a，并尝试在旧children中寻找 li-a，结果是我们找到了，并且li-a在旧children中的索引为0。
  • 取出新children的第二个节点，即li-b，并尝试在旧children中寻找 li-b，也找到了，并且li-b在旧children中的索引为1。
  • 取出新children的第三个节点，即li-c，并尝试在旧children中寻找li-c，同样找到了，并且li-c在旧children中的索引为2。

我们在寻找的过程中，先后遇到的索引顺序为：0->1->2。这是一个递增的顺序，说明新旧子节点中节点顺序相同，不需要移动。

再看一个需要移动的例子：

  • 取出新children的第一个节点，即li-c，并尝试在旧children中寻找 li-c，结果是我们找到了，并且li-c在旧children中的索引为2。
  • 取出新children的第二个节点，即li-a，并尝试在旧children中寻找 li-a，也找到了，并且li-a在旧children中的索引为0。

此时递增的趋势被打破了，我们在寻找中先需要的索引是2，接着又遇到了比2小的0。此时说明li-a是那个需要被移动的节点。

  • 取出新children的第三个节点，即li-b，并尝试在旧children中寻找li-b，同样找到了，并且li-b在旧children中的索引为1。

我们发现1同样小于2，这说明在旧children中节点li-b的位置也要比li-c的位置靠前，所以li-b也需要被移动。

以上我们过程就是我们寻找需要移动的节点的过程，在这个过程中我们发现一个重要的数字：2，是这个数字的存在才使得我们能够知道哪些节点需要移动，我们可以给这个数字一个名字，叫做：寻找过程中在旧节点中所遇到的最大索引值。如果在后续寻找的过程中发现存在索引值比最大索引值小的节点，意味着该节点需要被移动。

// 用来存储寻找过程中遇到的最大索引值
let lastIndex = 0
// 遍历新的 children
for (let i = 0; i < nextChildren.length; i++) {
  const nextVNode = nextChildren[i]
  // 遍历旧的 children
  for (let j = 0; j < prevChildren.length; j++) {
    const prevVNode = prevChildren[j]
    // 如果找到了具有相同 key 值的两个节点，则调用 `patch` 函数更新之
    if (nextVNode.key === prevVNode.key) {
      patch(prevVNode, nextVNode, container)
      if (j < lastIndex) {
        // 需要移动...
      } else {
        // 更新 lastIndex
        lastIndex = j
      }
      break // 这里需要 break
    }
  }
}

# 移动节点

现在我们已经有办法找到需要移动的节点了，接下来要解决的问题就是：应该如何移动这些节点？

新children中的第一个节点是li-c，它在旧children中的索引为2，由于li-c是新children中的第一个节点，所以它始终都是不需要移动的，只需要调用patch函数更新即可，如下图：

li-c节点更新完毕，接下来是新children中的第二个节点li-a，它在旧children中的索引是0，由于 0 < 2 所以li-a是需要移动的节点，那应该怎么移动呢？很简单，新children中的节点顺序实际上就是更新完成之后，节点应有的最终顺序，通过观察新children可知，新children中li-a节点的前一个节点是li-c，所以我们的移动方案应该是：把li-a节点对应的真实 DOM移动到li-c节点所对应真实DOM的后面。

// 用来存储寻找过程中遇到的最大索引值
let lastIndex = 0
// 遍历新的 children
for (let i = 0; i < nextChildren.length; i++) {
  const nextVNode = nextChildren[i]
  // 遍历旧的 children
  for (let j = 0; j < prevChildren.length; j++) {
    const prevVNode = prevChildren[j]
    // 如果找到了具有相同 key 值的两个节点，则调用 `patch` 函数更新之
    if (nextVNode.key === prevVNode.key) {
      patch(prevVNode, nextVNode, container)
      if (j < lastIndex) {
        // 需要移动
        // refNode 是为了下面调用 insertBefore 函数准备的
        const refNode = nextChildren[i - 1].el.nextSibling
        // 调用 insertBefore 函数移动 DOM
        container.insertBefore(prevVNode.el, refNode)
      } else {
        // 更新 lastIndex
        lastIndex = j
      }
      break // 这里需要 break
    }
  }
}

# 添加新元素

在上面的讲解中，我们一直忽略了一个问题，即新children中可能包含那些不能够通过移动来完成更新的节点，例如新children中包含了一个全新的节点，这意味着在旧children中是找不到该节点的，如下图所示：

节点li-d在旧的children中是不存在的，所以当我们尝试在旧的children中寻找li-d节点时，是找不到可复用节点的，这时就没办法通过移动节点来完成更新操作，所以我们应该使用mount函数将li-d节点作为全新的VNode挂载到合适的位置。

let lastIndex = 0
for (let i = 0; i < nextChildren.length; i++) {
  const nextVNode = nextChildren[i]
  let find = false
  for (let j = 0; j < prevChildren.length; j++) {
    const prevVNode = prevChildren[j]
    if (nextVNode.key === prevVNode.key) {
      find = true
      patch(prevVNode, nextVNode, container)
      if (j < lastIndex) {
        // 需要移动
        const refNode = nextChildren[i - 1].el.nextSibling
        container.insertBefore(prevVNode.el, refNode)
        break
      } else {
        // 更新 lastIndex
        lastIndex = j
      }
    }
  }
  if (!find) {
    // 挂载新节点
    // 找到 refNode
    const refNode =
      i - 1 < 0
        ? prevChildren[0].el
        : nextChildren[i - 1].el.nextSibling
    mount(nextVNode, container, false, refNode)
  }
}

# 删除元素

除了要将全新的节点添加到容器元素之外，我们还应该把已经不存在了的节点移除，如下图所示：

可以看出，新的children中已经不存在li-c节点了，所以我们应该想办法将li-c节点对应的真实DOM从容器元素内移除。

// 移除已经不存在的节点
// 遍历旧的节点
for (let i = 0; i < prevChildren.length; i++) {
  const prevVNode = prevChildren[i]
  // 拿着旧 VNode 去新 children 中寻找相同的节点
  const has = nextChildren.find(
    nextVNode => nextVNode.key === prevVNode.key
  )
  if (!has) {
    // 如果没有找到相同的节点，则移除
    container.removeChild(prevVNode.el)
  }
}

# 结语

至此，第一个完整的Diff算法我们就讲解完毕了，这个算法就是React所采用的Diff算法。但该算法仍然存在可优化的空间，在下一次分享中继续讨论。

← 虚拟DOM之更新子节点（三） →