快捷導(dǎo)航

react?diff?算法實(shí)現(xiàn)思路及原理解析

更新時(shí)間：2022年05月23日 14:41:51 作者：測(cè)不準(zhǔn)

這篇文章主要介紹了react?diff?算法實(shí)現(xiàn)思路及原理解析,本節(jié)我們正式進(jìn)入基本面試必考的核心地帶?--?diff?算法，了解如何優(yōu)化和復(fù)用?dom?操作的，還有我們常見(jiàn)的?key?的作用,需要的朋友可以參考下

事例分析

按照之前的 diff 寫法，如果元素不同我們是直接刪了 a 再插入的：

按照上面圖的結(jié)構(gòu)，我們需要知道那個(gè)元素變化了，其實(shí)右邊相對(duì)左邊只是把 A 做了移動(dòng)，沒(méi)有 dom 元素的刪除和新增。

`diff` 特點(diǎn)

同級(jí)對(duì)比 On
類型不一樣銷毀老的，創(chuàng)建新的
通過(guò) key 標(biāo)識(shí)

key 這里需要標(biāo)識(shí)，主要是為了列表中有刪除新增時(shí)有優(yōu)化效果，如果純靜態(tài)列表，只是展示作用，key 意義不大。

diff 思路

使用 map 存儲(chǔ)節(jié)點(diǎn)狀態(tài)，格式如下：

let map = {
  keyA: ADOM,
  keyB: BDOM
}

定義 lastPlacedIndex 記錄上一個(gè)不需要移動(dòng)的老節(jié)點(diǎn)

默認(rèn) lastPlacedIndex = 0 ，上一個(gè)不需要移動(dòng)的節(jié)點(diǎn)，在循環(huán)新的子虛擬 dom 時(shí)，如果老節(jié)點(diǎn)的掛載索引小于當(dāng)前值，則改變 lastPlacedIndex。這里有點(diǎn)類似 vue 的最長(zhǎng)遞增子序列，最大的保證不變的 dom 元素，只是判斷方式不同。

循環(huán)新數(shù)組

先出 A，map 中如果有 A，表示可以復(fù)用
- 判斷 A 的老掛載索引和 lastPlacedIndex 對(duì)比，如果索引值大，A 節(jié)點(diǎn)不需要移動(dòng)，更新 lastPlacedIndex 的值；否則循環(huán)到 B，掛載索引小，需要移動(dòng) B；循環(huán)到 G，map 中沒(méi)有值，需要新增；新的數(shù)組節(jié)點(diǎn)循環(huán)完，未用到的老節(jié)點(diǎn)全部刪除。

實(shí)現(xiàn) diff 算法

修改入口文件

// src/index.js
class Counter extends React.Component {
  constructor(props) {
    super(props)
    this.state = {list: ['A','B', 'C', 'D', 'E', 'F']}
  }
  handleClick = () => {
    this.setState({
      list: ['A', 'C', 'E', 'B', 'G']
    })
  }
  render() {
    // 使用空標(biāo)簽
    return <React.Fragment>
      <ul>
      {this.state.list.map(item => {
        // 這里使用 key 標(biāo)識(shí)
        return <li key={item}>{item}</li>
      })}
      </ul>
      <button onClick={this.handleClick}>add 1</button>
    </React.Fragment>
  }
}

實(shí)現(xiàn) React.Fragment

Fragment 就是代碼片段，不占用 dom 結(jié)構(gòu)。簡(jiǎn)寫 <></>，對(duì)應(yīng) dom 操作為 createDocumentFragment。

是用原生庫(kù)打印，看結(jié)構(gòu)

可以發(fā)現(xiàn)就是一個(gè)簡(jiǎn)單的 Symbol，所以需要定義新的類型：

為什么一個(gè)簡(jiǎn)單的 Symbol 可以被渲染成片段呢？依賴于 babel 解析。

// src/constants.js
export const REACT_FRAGMENT = Symbol("react.fragment") // React.Fragment 標(biāo)簽
// 備用，diff 時(shí)做 patch 的 type 定義
// 新的插入
export const PLACEMENT = 'PLACEMENT'
// 復(fù)用的移動(dòng)
export const MOVE = 'MOVE'

在創(chuàng)建元素的時(shí)候進(jìn)行類型判斷，記得 react.js 中導(dǎo)出

// src/react-dom.js  
// createDOM 方法
else if (type === REACT_FRAGMENT) {
  // fragment 片段
  dom = document.createDocumentFragment()
}
// updateElement 方法
else if (oldVdom.type === REACT_FRAGMENT) {
  // fragment 不需要對(duì)比，直接對(duì)比 子 就可以了
  const currentDOM = newVdom.dom = findDOM(oldVdom)
    updateChildren(currentDOM, oldVdom.props.children, newVdom.props.children)
}

我們需要修改 children 對(duì)比

之前邏輯：

// src/react-dom.js
// diff  沒(méi)有做復(fù)用，直接做的替換
function updateChildren(parentDOM, oldVChildren, newVChildren) {
  // 拿到最長(zhǎng)的
  let maxLength = Math.max(oldVChildren.length, newVChildren.length);
  for (let i = 0; i < maxLength; i++) {
  // 不能直接 appendChild 進(jìn)父，需要找到當(dāng)前操作的節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)。在其前面插入
    const nextVdom = oldVChildren.find((item, index) => index > i && item && findDOM(item))
    compareTwoVdom(parentDOM, oldVChildren[i], newVChildren[i], findDOM(nextVdom));
  }
}

新的邏輯（參考上面的流程）：

// diff
function updateChildren(parentDOM, oldVChildren, newVChildren) {
  oldVChildren = Array.isArray(oldVChildren) ? oldVChildren : [oldVChildren];
  newVChildren = Array.isArray(newVChildren) ? newVChildren : [newVChildren];

 // 1.循環(huán)老結(jié)構(gòu)， 構(gòu)建map存儲(chǔ)  key: dom
  const keydOldMap = {}
  let lastPlacedIndex = 0
  oldVChildren.forEach((oldVChild, index) => {
    let oldKey = oldVChild?.key || index //  寫key 了就用key，沒(méi)寫默認(rèn) index
    keydOldMap[oldKey] = oldVChild
  })
  // 2. 創(chuàng)建 dom 補(bǔ)丁包，收集 dom 操作
  const patch = []
  newVChildren.forEach((newVChild, index) => {
    newVChild.mountIndex = index // 為新元素每個(gè)添加索引標(biāo)識(shí)
    const newKey = newVChild?.key || index
    const oldVChild = keydOldMap[newKey] // 看有沒(méi)有存
    if(oldVChild) {
      // 如果有老的，就去更新老節(jié)點(diǎn) 這里直接可以復(fù)用
      updateElement(findDOM(oldVChild).parentNode, oldVChild, newVChild)
      if(oldVChild.mountIndex < lastPlacedIndex) {
        patch.push({
          type: MOVE,
          oldVChild,
          newVChild,
          mountIndex: index // 舊的移動(dòng)到新的的位置
        })
      }
      // 復(fù)用過(guò)了 刪除掉
      delete keydOldMap[newKey]
      lastPlacedIndex = Math.max(lastPlacedIndex, oldVChild.mountIndex)// 取最大
    } else {
      // 新的
      patch.push({
        type: PLACEMENT,
        newVChild,
        mountIndex: index
      })
    }
  })
  // 找到需要移動(dòng)的老節(jié)點(diǎn)
  const moveVChildren = patch.filter(action => action.type === MOVE).map(action => action.oldVChild)
  // 把要?jiǎng)h除的節(jié)點(diǎn) 和  要移動(dòng)的節(jié)點(diǎn)先全刪除     （頁(yè)面里沒(méi)有了，但是內(nèi)存中還存在  patch 中有存）
  Object.values(keydOldMap).concat(moveVChildren).forEach(oldVdom => {
    let currentDOM = findDOM(oldVdom)
    currentDOM.remove()
  })
  patch.forEach(action => {
    const {type, oldVChild, newVChild, mountIndex} = action
    // 老的真實(shí)子節(jié)點(diǎn)
    const childNodes = parentDOM.childNodes
    // 新的插入
    if (type === PLACEMENT) {
      let newDOM = createDOM(newVChild)
      let childNode = childNodes[mountIndex] // 老真實(shí)節(jié)點(diǎn)
      if (childNode) {
        // 往 老的父對(duì)應(yīng)位置插入
        parentDOM.insertBefore(newDOM, childNode)
      } else {
        parentDOM.appendChild(newDOM)
      }
    } else if (type === MOVE) {
      // 移動(dòng)不用創(chuàng)建 新 dom，復(fù)用
      let oldDOM = findDOM(oldVChild)
      let childNode = childNodes[mountIndex] // 老真實(shí)節(jié)點(diǎn)
      if (childNode) {
        // 往 老的父對(duì)應(yīng)位置插入
        parentDOM.insertBefore(oldDOM, childNode)
      } else {
        parentDOM.appendChild(oldDOM)
      }
    }
  })
}

實(shí)現(xiàn)如下跟原生一致，可以看到，三個(gè)節(jié)點(diǎn)實(shí)現(xiàn)了復(fù)用，即 A, C, E