專欄分享：vue2源碼專欄，vue3源碼專欄，vue router源碼專欄，玩具項目專欄，硬核??推薦??
歡迎各位ITer關(guān)注點贊收藏??????

Vue2 Diff算法可以參考此篇文章【Vue2.x源碼系列08】Diff算法原理

前后元素不一致

兩個不同虛擬節(jié)點不需要進(jìn)行比較，直接移除老節(jié)點，將新的虛擬節(jié)點渲染成真實DOM進(jìn)行掛載即可

// 判斷兩個虛擬節(jié)點是否是相同節(jié)點，標(biāo)簽名相同 && key是一樣的
export function isSameVnode(n1, n2) {
  return n1.type === n2.type && n1.key === n2.key
}

//  核心的patch方法，包括初始化DOM 和 diff算法
const patch = (n1, n2, container) => {
  if (n1 == n2) return

  // 判斷兩個元素是否相同，不相同卸載在添加
  if (n1 && !isSameVnode(n1, n2)) {
    unmount(n1) // 刪除老的
    n1 = null
  }

  const { type, shapeFlag } = n2
  switch (type) {
    case Text:
      processText(n1, n2, container)
      break
    default:
      if (shapeFlag & ShapeFlags.ELEMENT) {
        processElement(n1, n2, container)
      }
  }
}

前后元素一致

兩個相同的虛擬節(jié)點，先復(fù)用節(jié)點，再比較兩個節(jié)點的屬性和孩子節(jié)點

判斷是否是相同的虛擬節(jié)點：type類型相同 && key相同

1. 處理文本類型的虛擬節(jié)點

// 處理文本，初始化文本和patch文本
const processText = (n1, n2, container) => {
  if (n1 === null) {
    // 初始化文本
    const el = (n2.el = hostCreateText(n2.children))
    hostInsert(el, container)
  } else {
    // patch文本，文本的內(nèi)容變化了，我可以復(fù)用老的節(jié)點
    const el = (n2.el = n1.el)
    if (n1.children !== n2.children) {
      hostSetText(el, n2.children) // 文本的更新
    }
  }
}

2. 處理元素類型的虛擬節(jié)點

// 處理元素，初始化元素和patch元素
const processElement = (n1, n2, container) => {
  if (n1 === null) {
    // 初始化元素
    mountElement(n2, container)
  } else {
    // patch元素
    patchElement(n1, n2)
  }
}

// 對比元素打補(bǔ)丁，先復(fù)用節(jié)點、再比較屬性、再比較兒子
const patchElement = (n1, n2) => {
  let el = (n2.el = n1.el)
  let oldProps = n1.props || {} // 對象
  let newProps = n2.props || {} // 對象

  patchProps(oldProps, newProps, el)
  patchChildren(n1, n2, el)
}

// 對比屬性打補(bǔ)丁
const patchProps = (oldProps, newProps, el) => {
  for (let key in newProps) {
    // 新的里面有，直接用新的蓋掉即可
    hostPatchProp(el, key, oldProps[key], newProps[key])
  }
  for (let key in oldProps) {
    // 如果老的里面有新的沒有，則是刪除
    if (newProps[key] == null) {
      hostPatchProp(el, key, oldProps[key], undefined)
    }
  }
}

const patchChildren = (n1, n2, el) => {
  // 核心Diff算法
}

子元素比較情況

新兒子	舊兒子	操作方式
文本	數(shù)組	（刪除老兒子，更新文本內(nèi)容）
文本	文本	（更新文本內(nèi)容）
文本	空	（更新文本內(nèi)容)
數(shù)組	數(shù)組	（diff算法）
數(shù)組	文本	（清空文本，掛載元素）
數(shù)組	空	（掛載元素）
空	數(shù)組	（刪除所有子節(jié)點）
空	文本	（清空文本）
空	空	（不做任何處理）

// 刪除所有的子節(jié)點
const unmountChildren = children => {
  for (let i = 0; i < children.length; i++) {
    unmount(children[i])
  }
}

// 對比子節(jié)點打補(bǔ)丁   el: 虛擬節(jié)點對應(yīng)的真實DOM元素
const patchChildren = (n1, n2, el) => {
  const c1 = n1.children
  const c2 = n2.children
  const prevShapeFlag = n1.shapeFlag // 之前的
  const shapeFlag = n2.shapeFlag // 之后的

  if (shapeFlag & ShapeFlags.TEXT_CHILDREN) {
    if (prevShapeFlag & ShapeFlags.ARRAY_CHILDREN) {
      // 文本	數(shù)組	（刪除所有子節(jié)點，更新文本內(nèi)容）
      unmountChildren(c1)
    }
    if (c1 !== c2) {
      // 文本	文本	| 文本 空 （更新文本內(nèi)容）
      hostSetElementText(el, c2)
    }
  } else if (shapeFlag & ShapeFlags.ARRAY_CHILDREN) {
    if (prevShapeFlag & ShapeFlags.ARRAY_CHILDREN) {
      // 數(shù)組 數(shù)組 （diff算法；全量比對）
      patchKeyedChildren(c1, c2, el)
    } else {
      if (prevShapeFlag & ShapeFlags.TEXT_CHILDREN) {
        // 數(shù)組 文本  清空文本，掛載元素）
        hostSetElementText(el, '')
      }
      // 數(shù)組 文本 | 數(shù)組 空 （清空文本，掛載元素）
      mountChildren(c2, el)
    }
  } else {
    // 空 數(shù)組
    if (prevShapeFlag & ShapeFlags.ARRAY_CHILDREN) {
      unmountChildren(c1)
    } else if (prevShapeFlag & ShapeFlags.TEXT_CHILDREN) {
      // 空 文本
      hostSetElementText(el, '')
    }
  }
}

核心Diff算法

前序比對、后序比對、同序列加掛載、同序列加卸載的目的都是：盡可能減少后面亂序比對的元素

在正式介紹diff算法之前，我們先了解幾個問題

1. 如何判斷是否是相同的虛擬節(jié)點？

   答：虛擬節(jié)點的 type類型相同 && key相同 即可

2. c1、c2 指的是什么？

   答：patch對比元素打補(bǔ)丁，先復(fù)用節(jié)點、再比較屬性、最后比較兒子節(jié)點。c1指的是舊的兒子節(jié)點；c2指的是新的兒子節(jié)點

3. e1、e2 指的是什么？

   答：尾指針，初始值分別指向新舊孩子的最后一個節(jié)點，e1 = c1.length - 1 ；e2 = c2.length - 1

h('div',[ h('li', { key: 'a' }, 'a'), h('li', { key: 'b' }, 'b'), h('li', { key: 'c' }, 'c') ]) : h('div',[ h('li', { key: 'a' }, 'a'), h('li', { key: 'b' }, 'b'), h('li', { key: 'd' }, 'd'), h('li', { key: 'e' }, 'e'), h('li', { key: 'f' }, 'f'), ])

// diff算法；全量比對，比較兩個兒子數(shù)組的差異
const patchKeyedChildren = (c1, c2, container) => {
  let i = 0
  // 結(jié)尾位置
  let e1 = c1.length - 1
  let e2 = c2.length - 1

  // 特殊處理，盡可能減少比對元素
  // sync from start 從頭部開始處理 O(n)
  // (a b) c
  // (a b) d e
  while (i <= e1 && i <= e2) {
    // 有任何一方停止循環(huán)則直接跳出
    const n1 = c1[i]
    const n2 = c2[i]
    // vnode type相同 && key相同
    if (isSameVnode(n1, n2)) {
      patch(n1, n2, container) // 這樣做就是比較兩個節(jié)點的屬性和子節(jié)點
    } else {
      break
    }
    i++
  }
}

// sync from end 從尾部開始處理 O(n) // a (b c) // d e (b c) while (i <= e1 && i <= e2) { const n1 = c1[e1] const n2 = c2[e2] if (isSameVnode(n1, n2)) { patch(n1, n2, container) } else { break } e1-- e2-- }

common sequence+mount 同序列加掛載

分為 頭部掛載 和 尾部掛載 兩種場景

i 比 e1 大說明有要新增的，i 和 e2 之間的是新增的節(jié)點

// common sequence + mount 同序列加掛載
// i要比e1大說明有新增的；i和e2之間的是新增的部分
// (a b c)
// (a b c) d e
//     (a b c)
// e d (a b c)
if (i > e1) {
  if (i <= e2) {
    while (i <= e2) {
      const nextPos = e2 + 1
      // 根據(jù)下一個人的索引來看參照物
      const anchor = nextPos < c2.length ? c2[nextPos].el : null
      patch(null, c2[i], container, anchor) // 創(chuàng)建新節(jié)點 扔到容器中
      i++
    }
  }
}

common sequence+unmount 同序列加卸載

分為 頭部卸載 和 尾部卸載 兩種場景

i 比 e2 大說明有要卸載的，i 到 e1 之間的就是要卸載的節(jié)點

// common sequence + unmount 同序列加卸載
// i比e2大說明有要卸載的；i到e1之間的就是要卸載的
// (a b c) d e
// (a b c)
// e d (a b c)
//     (a b c)
else if (i > e2) {
  if (i <= e1) {
    while (i <= e1) {
      unmount(c1[i])
      i++
    }
  }
}

// 優(yōu)化完畢************************************ // unknown sequence 亂序比對 // (a b) 【c d e w】 (f g) // (a b) 【e d c v】 (f g) let s1 = i let s2 = i const keyToNewIndexMap = new Map() // 新節(jié)點中 key -> newIndex 的 Map 映射表，子元素中如果存在相同的key 或者 有多個子元素沒有key，值會被后面的索引覆蓋 for (let i = s2; i <= e2; i++) { keyToNewIndexMap.set(c2[i].key, i) } const toBePatched = e2 - s2 + 1 // 新的節(jié)點中亂序比對總個數(shù) // 一個記錄是否比對過的數(shù)組映射表，作用：已對比過的節(jié)點需移動位置；未對比過的節(jié)點需新創(chuàng)建 const newIndexToOldIndexMap = new Array(toBePatched).fill(0) // 遍歷老的亂序節(jié)點 看一下其是否存在于新的亂序節(jié)點里面，如果有則patch比較差異；如果沒有則要刪除老節(jié)點 for (let i = s1; i <= e1; i++) { const oldChild = c1[i] // 老的節(jié)點 let newIndex = keyToNewIndexMap.get(oldChild.key) // 用老的節(jié)點去新的里面找 if (newIndex == undefined) { unmount(oldChild) // 多余老節(jié)點刪掉 } else { // 新的位置對應(yīng)的老的位置，如果數(shù)組里放的值 >0 說明已經(jīng)pactch過了。+1的目的：防止i為0 newIndexToOldIndexMap[newIndex - s2] = i + 1 // 用來標(biāo)記當(dāng)前亂序新節(jié)點索引 對應(yīng)的 全部老節(jié)點的加1后的索引，最長遞增子序列會用到 patch(oldChild, c2[newIndex], container) } } // 到這只是新老屬性和兒子的比對 和 多余老節(jié)點卸載操作，沒有移動位置 // 亂序節(jié)點需要移動位置，倒序遍歷亂序節(jié)點 for (let i = toBePatched - 1; i >= 0; i--) { let index = i + s2 // i是亂序節(jié)點中的index，需要加上s2代表全部新節(jié)點中的index let current = c2[index] // 找到當(dāng)前節(jié)點 let anchor = index + 1 < c2.length ? c2[index + 1].el : null if (newIndexToOldIndexMap[i] === 0) { // 創(chuàng)建新元素 patch(null, current, container, anchor) } else { // 不是0，說明已經(jīng)執(zhí)行過patch操作了 hostInsert(current.el, container, anchor) } // 目前無論如何都做了一遍倒敘插入，性能浪費，可以根據(jù)剛才的數(shù)組newIndexToOldIndexMap來減少插入次數(shù) // 用最長遞增子序列來實現(xiàn)，vue3新增算法，vue2在移動元素的時候則會有性能浪費 }

目前無論如何都做了一遍倒敘插入，性能浪費。

思考一下！我們是不是可以只移動一部分節(jié)點。既減少了移動次數(shù)，又能保證節(jié)點順序是正確的呢？

例如舊節(jié)點 1, 3, 4, 2，新節(jié)點 1, 2, 3, 4。那我們完全可以只將 2 移動到 3 前面，只需移動一次！就能保證順序是正確的！！！

可以用 vue3 新增算法 - 最長遞增子序列 來實現(xiàn)，下一篇文章吃透透！！！

總結(jié)

以上是生活随笔為你收集整理的【源码系列#06】Vue3 Diff算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。