淺談React Hook采用環(huán)形鏈表的原因

更新時間：2026年06月10日 08:55:44 作者：卷簾依舊

本文主要介紹了淺談React Hook采用環(huán)形鏈表的原因,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

React Hooks 更新采用環(huán)形鏈表的原因

React Hooks 的更新隊列采用環(huán)形鏈表結(jié)構(gòu)，這是一個精心設(shè)計的決策。讓我從源碼層面解釋為什么。

1. 環(huán)形鏈表的核心優(yōu)勢

優(yōu)勢一：O(1) 時間的合并操作

// 環(huán)形鏈表結(jié)構(gòu)
type UpdateQueue<T> = {
  pending: Update<T> | null,  // 指向最后一個更新
}

type Update<T> = {
  action: T | ((T) => T),
  next: Update<T> | null,
}

// 添加新更新 - O(1) 時間復(fù)雜度
function appendUpdate(queue, update) {
  const pending = queue.pending
  
  if (pending === null) {
    // 第一個更新，指向自己形成環(huán)
    update.next = update
  } else {
    // 插入到環(huán)形鏈表的頭部
    // pending 指向最后一個節(jié)點(diǎn)
    // pending.next 指向第一個節(jié)點(diǎn)
    update.next = pending.next  // 新節(jié)點(diǎn)的 next 指向第一個節(jié)點(diǎn)
    pending.next = update       // 最后一個節(jié)點(diǎn)的 next 指向新節(jié)點(diǎn)
  }
  queue.pending = update  // 更新 pending 指向新節(jié)點(diǎn)（新的最后一個）
}

// 如果是單向鏈表（非環(huán)形）
function appendUpdateLinear(head, update) {
  // 需要遍歷到末尾才能添加 - O(n) 時間復(fù)雜度
  if (head === null) {
    return update
  }
  let current = head
  while (current.next !== null) {  // 遍歷！
    current = current.next
  }
  current.next = update
  return head
}

實際性能對比：

// React 中頻繁的批量更新場景
function handleClick() {
  // 同一個狀態(tài)連續(xù)更新多次
  setCount(1)
  setCount(2)
  setCount(3)
  setCount(4)
  setCount(5)
}

// 環(huán)形鏈表：每次 O(1)，5次操作 = 5個單位時間
// 單向鏈表：第1次 O(1)，第2次 O(2)，第3次 O(3)... 總計 O(n2)

優(yōu)勢二：高效的雙向遍歷能力

// React 處理更新時的遍歷
function processUpdateQueue(queue) {
  const pending = queue.pending
  
  if (pending !== null) {
    // 關(guān)鍵：通過 pending.next 獲取第一個更新
    const first = pending.next  // O(1) 獲取頭部
    let newState = currentState
    
    // 正向遍歷所有更新
    let update = first
    do {
      newState = applyUpdate(newState, update.action)
      update = update.next
    } while (update !== first)  // 回到起點(diǎn)，遍歷完成
    
    // 如果需要反向遍歷（比如優(yōu)先級調(diào)度）
    // 也可以輕松實現(xiàn)
    let last = pending
    let prev = first
    while (prev.next !== last) {
      // 反向遍歷邏輯
    }
  }
}

2. 解決并發(fā)渲染中的問題

問題場景：高優(yōu)先級更新打斷

// 環(huán)形鏈表在并發(fā)渲染中的優(yōu)勢
function concurrentUpdateExample() {
  const [count, setCount] = useState(0)
  
  // 場景：用戶快速點(diǎn)擊，產(chǎn)生多個更新
  setCount(1)  // 低優(yōu)先級更新 A
  setCount(2)  // 高優(yōu)先級更新 B（打斷 A）
  setCount(3)  // 低優(yōu)先級更新 C
  
  // 環(huán)形鏈表的處理方式：
  // pending → [C] → [B] → [A] → (回到 [C])
  //            ↑_______________|
  // 
  // 渲染時可以從任意節(jié)點(diǎn)開始，靈活調(diào)整優(yōu)先級順序
}

React 的實際實現(xiàn)

// React 源碼中的環(huán)形鏈表實現(xiàn)（簡化）
function dispatchSetState(fiber, queue, action) {
  const update = {
    action,
    next: null,
    priority: getCurrentPriorityLevel(),
  }
  
  // 獲取當(dāng)前待處理的更新環(huán)
  const pending = queue.pending
  
  if (pending === null) {
    // 第一個更新，形成環(huán)
    update.next = update
  } else {
    // 插入到環(huán)中
    update.next = pending.next
    pending.next = update
  }
  
  queue.pending = update
  
  // 并發(fā)渲染時可以安全地 fork 更新隊列
  if (fiber.lanes !== NoLanes) {
    // 如果正在進(jìn)行渲染，創(chuàng)建 interleaved 隊列
    const interleaved = queue.interleaved
    if (interleaved === null) {
      queue.interleaved = update
    } else {
      update.next = interleaved.next
      interleaved.next = update
    }
    queue.interleaved = update
  }
  
  scheduleUpdateOnFiber(fiber)
}

// 處理并發(fā)更新時的隊列合并
function mergeQueues(baseQueue, interleavedQueue) {
  if (baseQueue === null) {
    return interleavedQueue
  }
  if (interleavedQueue === null) {
    return baseQueue
  }
  
  // 環(huán)形鏈表的合并：O(1) 完成
  // baseQueue: ... → last1 → first1 → ...
  // interleavedQueue: ... → last2 → first2 → ...
  
  const first1 = baseQueue.next
  const last1 = baseQueue
  const first2 = interleavedQueue.next
  const last2 = interleavedQueue
  
  // 將兩個環(huán)連接成一個環(huán)
  last1.next = first2
  last2.next = first1
  
  return interleavedQueue  // 返回新的尾部
}

3. 批量更新與狀態(tài)計算

批量更新機(jī)制

// React 18 的自動批處理
function batchUpdate() {
  // 所有更新被收集到環(huán)形鏈表
  setCount(1)  // update1
  setCount(2)  // update2
  setCount(3)  // update3
  setName('John')  // 另一個 Hook 的更新
  
  // 環(huán)形鏈表結(jié)構(gòu)：
  // pending → update3 → update2 → update1 → (回到 update3)
  //            ↑____________________|
  
  // 一次渲染處理所有更新
  // 遍歷環(huán)形鏈表只需 O(n) 時間
}

// 處理環(huán)形鏈表的代碼
function processUpdateQueue(workInProgress, queue) {
  let pending = queue.pending
  
  if (pending !== null) {
    // 關(guān)鍵：解除環(huán)形，變成單向鏈表方便處理
    const first = pending.next
    let last = pending
    let newState = currentState
    
    // 斷開環(huán)形
    last.next = null
    
    // 現(xiàn)在變成了單向鏈表，可以安全遍歷
    let update = first
    while (update !== null) {
      newState = applyUpdate(newState, update.action)
      update = update.next
    }
    
    return newState
  }
}

4. 與單向鏈表的對比

// 性能對比測試
function benchmark() {
  const updates = Array(1000).fill().map((_, i) => ({ action: i }))
  
  // 環(huán)形鏈表插入
  console.time('Circular Linked List')
  let circularQueue = null
  for (let update of updates) {
    if (circularQueue === null) {
      update.next = update
      circularQueue = update
    } else {
      update.next = circularQueue.next
      circularQueue.next = update
      circularQueue = update
    }
  }
  console.timeEnd('Circular Linked List')  // ~0.1ms
  
  // 單向鏈表插入
  console.time('Singly Linked List')
  let linearHead = null
  let linearTail = null
  for (let update of updates) {
    if (linearHead === null) {
      linearHead = update
      linearTail = update
    } else {
      linearTail.next = update
      linearTail = update
    }
  }
  console.timeEnd('Singly Linked List')  // ~0.15ms（略慢）
  
  // 但環(huán)形鏈表在特定操作上優(yōu)勢明顯
  // 比如：獲取第一個和最后一個元素都是 O(1)
}

5. 實際應(yīng)用場景

場景一：優(yōu)先級提升

// React 中的優(yōu)先級提升機(jī)制
function promoteUpdatePriority(queue, targetPriority) {
  const pending = queue.pending
  if (pending === null) return
  
  // 環(huán)形鏈表可以輕松調(diào)整順序
  let update = pending.next
  let highestPriorityUpdate = null
  
  do {
    if (update.priority > targetPriority) {
      // 找到高優(yōu)先級更新，提升它
      highestPriorityUpdate = update
      break
    }
    update = update.next
  } while (update !== pending.next)
  
  if (highestPriorityUpdate) {
    // 將高優(yōu)先級更新移到環(huán)的頭部
    // 這樣渲染時會優(yōu)先處理
    queue.pending = highestPriorityUpdate
  }
}

場景二：狀態(tài)回滾

// 時間切片中的狀態(tài)回滾
function rollbackUpdates(queue, rollbackPoint) {
  const pending = queue.pending
  if (pending === null) return
  
  // 找到回滾點(diǎn)
  let update = pending.next
  let found = false
  
  do {
    if (update === rollbackPoint) {
      found = true
      break
    }
    update = update.next
  } while (update !== pending.next)
  
  if (found) {
    // 截斷環(huán)形鏈表，丟棄回滾點(diǎn)之后的更新
    queue.pending = rollbackPoint
    rollbackPoint.next = rollbackPoint  // 重新形成環(huán)
  }
}

6. 內(nèi)存和 GC 優(yōu)勢

// 環(huán)形鏈表的垃圾回收優(yōu)勢
function cleanupQueue(queue) {
  // 斷開環(huán)形引用，幫助 GC
  const pending = queue.pending
  
  if (pending !== null) {
    // 打破循環(huán)引用
    const first = pending.next
    pending.next = null  // 斷開環(huán)
    
    // 現(xiàn)在可以安全地清理
    let update = first
    while (update !== null) {
      const next = update.next
      update.next = null  // 幫助 GC
      update = next
    }
  }
  
  queue.pending = null
}

// 單向鏈表需要更多遍歷才能完全清理