Vue2의 Diff 알고리즘에 대한 심층 분석

diff 알고리즘은 동일한 수준의 트리 노드를 비교하는 효율적인 알고리즘으로, 트리를 계층별로 검색하고 탐색할 필요가 없습니다. 그렇다면 diff 알고리즘에 대해 얼마나 알고 있나요? 다음 글은 vue2의 diff 알고리즘에 대한 심층 분석을 제공할 것입니다. 도움이 되길 바랍니다!

예전에 라이브 인터뷰를 볼 때 Diff 알고리즘에 대해 자주 질문을 받았고, 작가님도 Vue2를 많이 사용하기 때문에 Vue2의 Diff 알고리즘을 실제로 배우고 싶었습니다. 오랜만인데 Diff 알고리즘이 상대적으로 난해하다고 느껴서 배우기를 미루고 있었는데 최근에 인터뷰를 준비하다가 조만간 배워볼까 하는 생각이 들었습니다. Diff 알고리즘을 이해할 수 있는 기회가 있었나요? 저자가 하루 종일 공부했지만 Diff의 본질을 완전히 이해하지 못했을 수도 있습니다.

이것은 실제로 작성자의 연구 노트로 간주되며 작성자의 수준이 제한되어 있습니다. 수정된 글은 작성자의 개인적인 의견일 뿐이며, 오류가 있는 경우 댓글로 지적하시면 계속해서 지적해 드리겠습니다. 동시에 이 글은 매우 길기 때문에 독자들은 인내심을 갖고 읽어보시기 바랍니다. 저자는 여러분이 Diff 알고리즘에 대해 더 깊이 이해하게 될 것이라고 믿습니다. 현재 Diff 알고리즘을 설명하는 인터넷상의 대부분의 기사보다 이 기사가 더 낫다고 생각합니다. 왜냐하면 이 기사는 답에서 바로 시작하기보다는 문제에서 시작하여 모든 사람에게 생각하는 방법을 가르치기 때문입니다. 이 기사에서는 모든 사람이 Diff 알고리즘의 미묘함을 느낄 수 있도록 단계별로 설명합니다. 동시에 모든 사람에게 Diff 알고리즘을 보다 직관적으로 경험할 수 있도록 작은 실험도 수행했습니다.

Diff 알고리즘을 사용하는 이유

Virtual DOM

Vue2의 최하위 레이어는 페이지 구조를 표현하기 위해 가상 DOM을 사용하기 때문에 가상 DOM을 생성하는 방법을 알고 싶다면, 대략적인 프로세스는 다음과 같습니다.

• 먼저 .vue 파일인 템플릿 문자열을 구문 분석합니다
• 그런 다음 이를 AST 구문 트리로 변환합니다
• 그런 다음 렌더링 함수를 생성합니다.
• 마지막으로 렌더링 함수를 호출하여 가상 DOM을 생성합니다. [관련 권장 사항 : vuejs 비디오 튜토리얼, 웹 프론트엔드 개발]

최소 업데이트

사실 프레임워크는 성능을 위해 가상 DOM만 사용합니다. 왜냐하면 js는 DOM을 생성한 다음 페이지를 표시하기 때문입니다. 이는 매우 성능적인 것입니다. 업데이트할 때마다 전체 페이지가 다시 생성되므로 확실히 두 페이지에서 변경 사항을 찾은 다음 js로 변경 사항을 업데이트해야 합니다(추가, 삭제 또는 업데이트 중일 수 있음). 한 번의 클릭으로, 이는 최소한의 업데이트 양입니다. 그렇다면 최소 업데이트 양을 달성하는 방법은 무엇입니까? 그렇다면 Diff 알고리즘을 사용해야 합니다. 그러면 Diff 알고리즘은 정확히 무엇을 비교합니까? 아마도 이것이 Diff 알고리즘을 처음 배울 때 오해하기 쉬운 부분일 것입니다. 사실 이전 가상 DOM과 새 가상 DOM을 비교하는 것이기 때문에 Diff 알고리즘은 차이점을 찾는 것입니다. 두 가상 DOM의 차이점을 찾는 것입니다. , 그리고 그 차이를 페이지에 반영합니다. 이렇게 하면 변경된 위치만 업데이트되면 성능이 확실히 좋아집니다.

페이지 업데이트 프로세스

사실 이건 설명하기 어려운데, Vue를 공부해본 사람이라면 누구나 이 프레임워크의 특징 중 하나가 데이터 반응성, 즉 반응성이라는 것을 알고 있을 것입니다. 데이터 업데이트 페이지 또한 업데이트되었으므로 페이지가 곧 업데이트된다는 것을 페이지에서 어떻게 알 수 있습니까? 사실 이것이 이 프레임워크의 영리한 부분입니다. 일반적인 프로세스는 다음과 같습니다.

앞서 언급한 대로 렌더링 기능이 실행되므로 렌더링 기능이 실행되면 데이터가 하이재킹됩니다. Object.defineProperty의 get을 입력하면 여기에 종속성이 수집되고, 종속성은 누가 수집합니까? 이는 각 구성 요소이며 각 구성 요소는 이 구성 요소의 모든 변수
• (즉, 종속성) Object.defineProperty 的 get，那么在这里收集依赖，那么是谁收集依赖呢？是每个组件，每个组件就是一个 Watcher，会记录这个组件内的所有变量 (也就是依赖)，当然每个依赖 (Dep) 也会收集自己所在组件的 Watcher；
• 然后当页面中的数据发生变化，那么就会出发 Object.defineProperty 的 set，在这个函数里面数据就会通知每个 Watcher 更新页面，然后每个页面就会调用更新方法，这个方法就是 patch을 기록하는 Watcher입니다. 물론 각 종속성
(Dep)
• 은 자체 구성 요소의 Watcher도 수집합니다.
• 그런 다음 페이지의 데이터가 변경되면 Object.defineProperty의 set가 트리거됩니다. 이 함수에서는 데이터가 각 Watcher에게 페이지를 업데이트하도록 알립니다. , 그러면 각 페이지가 업데이트 메소드가 호출됩니다. 이 메소드는 patch입니다.

그런 다음 두 페이지 간의 변경 정도를 찾은 다음 Diff 알고리즘을 사용해야 합니다.

드디어 변경된 금액을 찾아보세요. 페이지가 업데이트되었습니다

🎜🎜🎜사실 모두가 이해하기 쉽도록 두 부분을 분리했습니다🎜

Diff 알고리즘에 대한 간략한 소개

인터뷰에서 Diff 알고리즘이 무엇인지 물으면 모두가 다음과 같이 몇 마디 말할 것입니다. 头头、尾尾、尾头、头尾、深度优先遍历(dfs)、同层比较 이와 비슷한 단어는 한두 문장으로 말할 수 있지만 그냥 맛이에요. 실제로 저자는 CSDN에 게재된 Diff 알고리즘에 대한 기사를 읽었는데, 이는 많이 읽힌 기사입니다. 저자는 자신이 그것을 명확하게 이해하지 못했을 수도 있고, 이해했지만 설명하지 않았을 수도 있습니다. 그러면 저자는 자신의 통찰력을 여러분과 공유하겠습니다.

Diff 알고리즘의 전제

모두가 명확하게 이해할 수 있도록 함수 호출 프로세스는 다음과 같습니다.

• patch
• patchVnode
• updateChildren

Diff 알고리즘 前提 这个是很重要的，可能大家会问什么是前提？不就是之前说的那些比较嘛？说的没错但也不对，因为 Diff 算法到达之前说的 头头、尾尾、尾头、头尾 这一步的前提就是两次对比的节点是 相同的，这里的相同不是大家想的完全相同，只是符合某些条件就是相同了，为了简化说明，文章就只考虑一个标签只包含 key 和 标签名(tag)，那么之前说的相同就是 key 相同以及 tag 相同, 저자의 진술을 증명하기 위해 약간 맞다면 소스 코드도 여기에 게시되어 있습니다:

// https://github.com/vuejs/vue/blob/main/src/core/vdom/patch.ts
// 36行
function sameVnode(a, b) {
  return (
    a.key === b.key &&
    a.asyncFactory === b.asyncFactory &&
    ((a.tag === b.tag &&
      a.isComment === b.isComment &&
      isDef(a.data) === isDef(b.data) &&
      sameInputType(a, b)) ||
      (isTrue(a.isAsyncPlaceholder) && isUndef(b.asyncFactory.error)))
  )
}

혼란이 두려운 경우 다음을 생략해도 되며 전체적인 이해에는 영향을 미치지 않습니다. 다음은 모든 상황을 고려하여 추가한 판단입니다. 따라서 두 개의 가상 DOM이 동일하지 않으면 계속 비교할 필요가 없고, 동일하다면 비교할 필요가 없습니다. 여기서 유사성은 실제로 정확히 동일합니다. 즉, 두 가상 DOM의 주소입니다. 가상 DOM은 동일하므로 소스 코드도 붙여넣으세요.

function patchVnode(......) {
  if (oldVnode === vnode) {
    return
  }
  ......
}

지금까지 모두가 혼란스러울 수 있습니다. 이제 요약해 보겠습니다.

• patch 함수에서 이전 버전과 새 버전의 비교가 표시됩니다. virtual DOM은 키가 동일한지, 태그가 동일한지 여부를 확인하며, 동일하지 않은 경우에는 patchVnode를 사용하여 직접 교체하세요. patch 函数里比较的是新老虚拟 DOM 是否是 key 相同以及 tag 相同，如果不相同那么就直接替换，如果相同用 patchVnode

说了这么多，其实作者也就想表达一个观点，就是只有当两次比较的虚拟 DOM 是 相同的 才会考虑 Diff 算法，如果不符合那直接把原来的删除，替换新的 DOM 就行了。

patchVnode 函数

这个函数里的才是真正意义上的 Diff 算法，那么接下来会结合源码向大家介绍一下。

源码中核心代码在 patch.ts 的 638 行至 655 行。

其实，目前介绍 patchVnode 的都是直接对着源码来介绍的，但是大家可能不清楚为啥要这么分类，那么作者在这里就让大家明白为什么这么分类，首先在这里说一个结论：

• 就是 text 属性和 children 属性不可能同时存在，这个需要大家看模板解析源码部分

那么在对比新旧节点的情况下，主要比较的就是是否存在 text 和 children

너무 많이 말했지만 사실 저자도 관점을 표현하고 싶은데, 즉 둘 사이에 비교되는 가상 DOM이 일 때만 Diff 알고리즘은 동일할 경우에만 고려하게 된다. . 일관성이 없으면 원본을 삭제하고 새 DOM으로 바꾸세요.

patchVnode 함수

사실 현재 patchVnode의 소개는 소스코드에 직접 소개되어 있는데, 왜 이렇게 분류되었는지 모를 수도 있으니, 먼저 저자는 왜 이렇게 분류되었는지 여러분에게 알려드리고자 합니다. , 결론을 내리겠습니다. 즉, text 속성과 children 속성은 동시에 존재할 수 없습니다. 이를 위해서는 모든 사람이 템플릿 구문 분석을 살펴봐야 합니다. 그래서 이전 노드와 새 노드를 비교할 때 주요 비교는 즉, text와 children이 있는지 여부에 따라 다음 9개가 있을 것입니다. 상황새 노드 텍스트❎✅❎❎✅❎❎✅

	이 함수는 실제 Diff 알고리즘이므로 다음에는 소스코드를 토대로 소개해드리겠습니다.	소스 코드의 핵심 코드는 patch.ts의 655행까지.
		situation	이전 노드 텍스트	이전 노드 하위
새 노드 하위			1	❎
❎	❎		2	❎
❎	❎		3	✅
❎	❎		4	❎
❎	✅		5	❎
❎	✅		6	✅
❎	✅		7	❎
✅	❎		8	❎

✅🎜🎜❎🎜🎜🎜🎜9🎜 🎜✅🎜🎜❎🎜🎜✅🎜🎜❎🎜🎜🎜 🎜

按照上面的表格，因为如果新节点有文本节点，其实老节点不管是什么都会被替换掉，那么就可以按照 新节点 text 是否存在来分类，其实 Vue 源码也是这么来分类的：

if (isUndef(vnode.text)) {
  // 新虚拟 DOM 有子节点
} else if (oldVnode.text !== vnode.text) {
  // 如果新虚拟 DOM 是文本节点，直接用 textContent 替换掉
  nodeOps.setTextContent(elm, vnode.text)
}

那么如果有子节点的话，那应该怎么分类呢？我们可以按照每种情况需要做什么来进行分类，比如说：

• 第一种情况，我们啥都不用做，因此也可以不用考虑
• 第二种情况，我们应该把原来 DOM 的 textContent 设置为 ''
• 第三种情况，我们也应该把原来 DOM 的 textContent 设置为 ''
• 第四种情况，我们应该加入新的子节点
• 第五种情况，这个情况比较复杂，需要对比新老子节点的不同
• 第六种情况，我们应该把原来的 textContent 设置为 '' 后再加入新的子节点

那么通过以上六种情况 (新虚拟 DOM 不含有 text，也就是不是文本节点的情况)，我们可以很容易地进行归类：

• 分类 1️⃣： 第二种情况 和 第三种情况。进行的是操作是：把原来 DOM 的 textContent 设置为 ''
• 分类 2️⃣： 第四种情况 和 第六种情况。进行的是操作是：如果老虚拟 DOM 有 text，就置空，然后加入新的子节点
• 分类 3️⃣：第五种情况。进行的是操作是：需要进行精细比较，即对比新老子节点的不同

其实源码也是这么来进行分类的，而且之前说的 同层比较 也就得出来了，因为每次比较都是比较的同一个父节点每一个子元素 (这里的子元素包括文本节点和子节点) 是否相同，而 深度优先遍历(dfs) 是因为每次比较中，如果该节点有子节点 (这里的子节点指的是有 children 属性，而不包括文本节点) 的话需要进行递归遍历，知道最后到文本节点结束。

⭕️ 这里需要搞清楚子节点和子元素的区别和联系

然后我们来看看源码是怎么写吧，只看新虚拟 DOM 不含有 text，也就是不是文本节点的情况：

if (isUndef(vnode.text)) {
  if (isDef(oldCh) && isDef(ch)) {
    if (oldCh !== ch)
      // 递归处理，精细比较
      // 对应分类 3️⃣
      updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)
  } else if (isDef(ch)) {
    if (__DEV__) {
      checkDuplicateKeys(ch) // 可以忽略不看
    }
    // 对应分类 2️⃣
    if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '')
    addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
  } else if (isDef(oldCh)) {
  	// 对应分类 1️⃣
    removeVnodes(oldCh, 0, oldCh.length - 1)
  } else if (isDef(oldVnode.text)) {
  	// 对应分类 1️⃣
    nodeOps.setTextContent(elm, '')
  }
}

❓我们可以看到源码把分类 1️⃣ 拆开来了，这是因为如果老虚拟 DOM 有子节，那么可能绑定了一些函数，需要进行解绑等一系列操作，作者也没自信看，大致瞄了一眼，但是如果我们要求不高，如果只是想自己手动实现 Diff 算法，那么没有拆开的必要。

作者觉得这么讲可能比网上其他介绍 Diff 算法的要好，其他的可能直接给你说源码是怎么写的，可能没有说明白为啥这么写，但是通过之前这么分析讲解后可能你对为什么这么写会有更深的理解和帮助吧。

updateChildren 函数

同层比较

因为当都含有子节点，即都包含 children 属性后，需要精细比较不同，不能像之前那些情况一样进行简单处理就可以了 那么这个函数中就会介绍大家经常说的 头头、尾尾、尾头、头尾 比较了，其实这不是 Vue 提出来的，是很早就提出来的算法，就一直沿用至今，大家可以参考【snabbdom 库】

? 在这之前我们要定义四个指针 newStartIdx、newEndIdx、oldStartIdx 和 oldEndIdx，分别指向 新头节点、新尾节点、旧头节点 与 旧尾节点

循环条件如下：

while(oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  ......
}

其实这个比较也就是按人类的习惯来进行比较的，比较顺序如下 ：

• 1️⃣ 新头节点与旧头节点：++newStartIdx 和 ++oldStartIdx
• 2️⃣ 新尾节点与旧尾节点：--newEndIdx 和 --oldEndIdx
• 3️⃣ 新尾节点与旧头节点：需要将 旧头节点 移动到 旧尾节点之前，为什么要这么做，讲起来比较复杂，记住就好，然后 --newEndIdx 和 ++oldStartIdx
• 4️⃣ 新头节点与旧尾节点：需要将 旧尾节点 移动到 旧头节点之前，为什么要这么做，讲起来比较复杂，记住就好，然后 ++newStartIdx 和 --oldEndIdx
• 5️⃣ 如果都没有匹配的话，就把 新头节点 在旧节点列表 (也就是 children 属性的值) 中进行查找，查找方式按照如下：
  • 如果有 key 就把 key 在 oldKeyToIdx 进行匹配，oldKeyToIdx 根据旧节点列表中元素的 key 生成对应的下标
  • 如果没有，就按顺序遍历旧节点列表找到该节点所在的下标
  • 如果在旧节点列表是否找到也分为两种情况：
    • 找到了，那么只要将 新头节点 添加到 旧头节点 之前即可
    • 没找到，那么需要创建新的元素然后添加到 旧头节点 之前
    • 然后把这个节点设置为 undefined

根据循环条件我们可以得到两种剩余情况，如下：

• 6️⃣ 如果 oldStartIdx > oldEndIdx 说明老节点先遍历完成，那么新节点比老节点多，就要把 newStartIdx 与 newEndIdx 之间的元素添加
• 7️⃣ 如果 newStartIdx > newEndIdx 说明新节点先遍历完成，那么老节点比新节点多，就要把 oldStartIdx 与 oldEndIdx 之间的元素删除

其实我们上面还没有考虑如果节点为 undefined 的情况，因为在上面也提到过，如果四种都不匹配后会将该节点置为 undefined，也只有旧节点列表中才有，因此要在开头考虑这两种情况：

• 8️⃣ 当 oldStartVnode 为 undefined：++oldStartIdx
• 9️⃣ 当 oldEndVnode 为 undefined：--oldEndIdx

那么我们来看源码怎么写的吧，其中用到的函数可以查看源码附录：

// https://github.com/vuejs/vue/blob/main/src/core/vdom/patch.ts
// 439 行至 556 行
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  if (isUndef(oldStartVnode)) {
  	// 情况 8️⃣
    oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left
  } else if (isUndef(oldEndVnode)) {
  	// 情况 9️⃣
    oldEndVnode = oldCh[--oldEndIdx]
  } else if (sameVnode(oldStartVnode, newStartVnode)) {
  	// 情况 1️⃣
    patchVnode(...)
    oldStartVnode = oldCh[++oldStartIdx]
    newStartVnode = newCh[++newStartIdx]
  } else if (sameVnode(oldEndVnode, newEndVnode)) {
  	// 情况 2️⃣
    patchVnode(...)
    oldEndVnode = oldCh[--oldEndIdx]
    newEndVnode = newCh[--newEndIdx]
  } else if (sameVnode(oldStartVnode, newEndVnode)) {
    // Vnode moved right
    // 情况 3️⃣
    patchVnode(...)
    canMove &&
      nodeOps.insertBefore(
        parentElm,
        oldStartVnode.elm,
        nodeOps.nextSibling(oldEndVnode.elm)
      )
    oldStartVnode = oldCh[++oldStartIdx]
    newEndVnode = newCh[--newEndIdx]
  } else if (sameVnode(oldEndVnode, newStartVnode)) {
    // Vnode moved left
    // 情况 4️⃣
    patchVnode(...)
    canMove &&
      nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
    oldEndVnode = oldCh[--oldEndIdx]
    newStartVnode = newCh[++newStartIdx]
  } else {
  	// 情况 5️⃣
    if (isUndef(oldKeyToIdx)) // 创建 key -> index 的 Map
      oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx) 
    // 找到 新头节点 的下标
    idxInOld = isDef(newStartVnode.key)
      ? oldKeyToIdx[newStartVnode.key]
      : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
    if (isUndef(idxInOld)) {
      // New element
      // 如果没找到
      createElm(...)
    } else {
      // 如果找到了
      vnodeToMove = oldCh[idxInOld]
      if (sameVnode(vnodeToMove, newStartVnode)) {
        patchVnode(...)
        oldCh[idxInOld] = undefined
        canMove &&
          nodeOps.insertBefore(
            parentElm,
            vnodeToMove.elm,
            oldStartVnode.elm
          )
      } else {
        // same key but different element. treat as new element
        createElm(...)
      }
    }
    newStartVnode = newCh[++newStartIdx]
  }
}
if (oldStartIdx > oldEndIdx) {
  // 情况 6️⃣
  refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm
  addVnodes(...)
} else if (newStartIdx > newEndIdx) {
  // 情况 7️⃣
  removeVnodes(...)
}

如果问为什么这么比较，回答就是经过很多人很多年的讨论得出的，其实只要记住过程就行了，如果想要更深了解 Diff 算法，可以去 B 站看【尚硅谷】Vue源码解析之虚拟DOM和diff算法

v-for 中为什么要加 key

这个问题面试很常见，但是可能大部分人也就只会背八股，没有完全理解，那么经过以上的介绍，我们可以得到自己的理解：

• 首先，如果不加 key 的话，那么就不会去 Map 里匹配 (O(1))，而是循环遍历整个列表 (O(n))，肯定加 key 要快一点，性能更高
• 其次，如果不加 key 那么在插入或删除的时候就会出现，原本不是同一个节点的元素被认为是相同节点，上面也有说过是 sameVnode 函数判断的，因此可能会有额外 DOM 操作

为什么说可能有额外 DOM 操作呢？这个和插入的地方有关，之后会讨论，同理删除也一样

证明 key 的性能

我们分为三个实验：没有 key、key 为 index、key 唯一，仅证明加了 key 可以进行最小化更新操作。

实验代码

有小伙伴评论说可以把代码贴上这样更好，那么作者就把代码附上 ?：

<!DOCTYPE html>
<html>

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
  <script src="https://cdn.jsdelivr.net/npm/vue@2/dist/vue.js"></script>
  <style>
    .box {
      display: flex;
      flex-direction: row;
    }
    .item {
      flex: 1;
    }
  </style>
</head>

<body>
  <div id="app">
    <div>
      <div>
        <h3>没有 key</h3>
        <p v-for="(item, index) in list">{{ item }}</p>
      </div>
      <div>
        <h3>key 为 index</h3>
        <p v-for="(item, index) in list" :key="index">{{ item }}</p>
      </div>
      <div>
        <h3>key 唯一</h3>
        <p v-for="(item, index) in list" :key="item">{{ item }}</p>
      </div>
    </div>
    <button @click="click1">push(4)</button>
    <button @click="click2">splice(1, 0, 666)</button>
    <button @click="click3">unshift(999)</button>
    <br /><br />
    <button @click="click4">pop()</button>
    <button @click="click5">splice(1, 1)</button>
    <button @click="click6">shift()</button>
  </div>
  <script>
    var app = new Vue({
      el: &#39;#app&#39;,
      data: {
        show: false,
        list: [1, 2, 3],
      },
      methods: {
        click1() {
          this.list.push(4);
        },
        click2() {
          this.list.splice(1, 0, 666);
        },
        click3() {
          this.list.unshift(999);
        },
        click4() {
          this.list.pop();
        },
        click5() {
          this.list.splice(1, 1);
        },
        click6() {
          this.list.shift();
        }
      },
    })
  </script>
</body>

</html>

增加实验

实验如下所示，我们首先更改原文字，然后点击按钮**「观察节点发生变化的个数」**：

在队尾增加

在队内增加

在队首增加

删除实验

在队尾删除

在队内删除

在队首删除

实验结论

增加实验

表格为每次实验中，每种情况的最小更新量，假设列表原来的长度为 n

实验	没有 key	key 为 index	key 唯一
在队尾增加	1	1	1
在队中增加	n - i + 1	n - i + 1	1
在队首增加	n + 1	n + 1	1

删除实验

表格为每次实验中，每种情况的最小更新量，假设列表原来的长度为 n

实验	没有 key	key 为 index	key 唯一
在队尾删除	1	1	1
在队中删除	n - i	n - i	1
在队首删除	n	n	1

通过以上实验和表格可以得到加上 key 的性能和最小量更新的个数是最小的，虽然在 在队尾增加 和 在队尾删除 的最小更新量相同，但是之前也说了，如果没有 key 是要循环整个列表查找的，时间复杂度是 O(n)，而加了 key 的查找时间复杂度为 O(1)，因此总体来说加了 key 的性能要更好。

写在最后

本文从源码和实验的角度介绍了 Diff 算法，相信大家对 Diff 算法有了更深的了解了，如果有问题可私信交流或者评论区交流，如果大家喜欢的话可以点赞 ➕ 收藏 ?

源码函数附录

列举一些源码中出现的简单函数

setTextContent

function setTextContent(node: Node, text: string) {
  node.textContent = text
}

isUndef

function isUndef(v: any): v is undefined | null {
  return v === undefined || v === null
}

isDef

function isDef<T>(v: T): v is NonNullable<T> {
  return v !== undefined && v !== null
}

insertBefore

function insertBefore(
  parentNode: Node,
  newNode: Node,
  referenceNode: Node
) {
  parentNode.insertBefore(newNode, referenceNode)
}

nextSibling

function nextSibling(node: Node) {
  return node.nextSibling
}

createKeyToOldIdx

function createKeyToOldIdx(children, beginIdx, endIdx) {
  let i, key
  const map = {}
  for (i = beginIdx; i <= endIdx; ++i) {
    key = children[i].key
    if (isDef(key)) map[key] = i
  }
  return map
}

（学习视频分享：vuejs入门教程、编程基础视频）

위 내용은 Vue2의 Diff 알고리즘에 대한 심층 분석의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!