JS動態(tài)高度虛擬列表實現(xiàn)原理解析

更新時間：2024年11月07日 11:19:24 作者：E_Yen

這篇文章將和大家一起探討一下動態(tài)高度虛擬列表原理并指出常見虛擬列表采用累計高度方式存在缺點,感興趣的小伙伴可以跟隨小編一起學習一下

前言

本文適合對虛擬列表技術已經(jīng)有基本了解的程序猿食用，僅提供一種理解和實現(xiàn)動態(tài)虛擬列表的思路，CV工程師（你知道我說的不是計算機視覺那個CV）謹慎使用?。?！

環(huán)境為瀏覽器原生JS環(huán)境，不涉及任何框架。

思考&設計

常見的虛擬列表都采用累計高度的方式，使用一張非遞減表來記錄虛擬列表中每個元素的起始位置，并且使用二分查找當前位置對應的需要渲染元素，這樣實現(xiàn)非常直觀易懂，但是會導致下面幾個缺點：

隨著列表不斷變長，用來記錄高度的數(shù)組會變得越來越大。簡單做一個計算，number使用雙精度數(shù)，這意味著一個number理論上占用8個字節(jié)，那么當數(shù)組長度到達131072時，將會至少占用1MB的空間，看起來其實還挺小的，只是對于強迫癥來說還是不夠優(yōu)雅，因此不算真正意義上的缺點。
如果列表一開始就在某個非零位置，那么在當前位置之前的元素高度都確定下來之前，列表沒法渲染任何元素（僅針對動態(tài)虛擬列表）。常見的解決方案是在不渲染元素前就估算元素高度。但估算元素高度是不是需要元素的內容？這些內容是不是要靠后端傳給你？后端吭哧吭哧把數(shù)據(jù)返回來了，結果你看一眼就“丟了”，實在是太“渣”了。前端是這樣的，只要調調后端api就好了，而后端要考慮的可就多了（
當某個位置的元素高度發(fā)生變化了，那么恭喜你，從這個元素開始，列表中后續(xù)的所有元素的起始位置都要重新計算，雖然實際上只需要將變化量向后傳導即可，但這始終不是一個好主意

列了這么多缺點，可以看到這些問題都圍繞一個前提：使用了一張記錄每個元素的起始位置的表，這張表中每一項都是基于前一項計算出來的，這意味著整張表天然具有前向依賴，或者說，改變表中的任意一項都會對后面的項產(chǎn)生副作用。所以解決方案就是丟掉這張礙事的表了，勞資掀桌不玩了！

那么丟掉了這張表之后，該如何確定渲染的范圍呢？仔細思考，實際上虛擬列表只需要起始元素索引值 startIndex和起始元素到可視區(qū)起始位置的距離 offset。結束的位置只需要從起始元素開始，不斷累加元素的高度，直到?jīng)]有更多的元素或者列表高度已經(jīng)超過渲染范圍即可。然后你就會發(fā)現(xiàn)在這種設計下：

虛擬列表天然支持任意的起始位置！如果我希望虛擬列表一開始就從第500個元素開始展示，那么只需要告訴虛擬列表 startIndex = 500 和 offset = 0 即可！
虛擬列表天然支持動態(tài)高度的元素！渲染區(qū)域外的元素高度發(fā)生變化，關我虛擬列表啥事，眼不見心不煩，接著奏樂接著舞！渲染區(qū)域內的元素高度發(fā)生了變化？好說，保持 startIndex 和 offset 不變，重新渲染一遍就是！

想法很美好，但是慢著，還有非常重要的滾動問題！在原本的虛擬列表中，只需要修改當前位置，然后重新渲染就好，但是現(xiàn)在換成了 startIndex 和 offset 的組合，這意味著在滾動時不僅需要重新計算 startIndex，還需要基于滾動距離 delta 和新的 startIndex 修改 offset：

約定索引為 i 的元素高度為 height[i]

獲取索引為 i 的元素高度的方法為 getHeight(i: number) => number，若元素不存在則返回 -1

基礎滾動

向下滾動

由于我們只關心 startIndex 和 offset，因此只有當 offset >= height[startIndex]，即起始元素已經(jīng)在渲染范圍外時才需要重新計算 startIndex，重新計算的方法也很簡單，只需要讓 offset 循環(huán)減去 height[startIndex]，然后 startIndex 加一，直到 offset < height[startIndex]：

let newOffset = offset + delta;
// 向后移動，直到offset >= height
let height = getHeight(startIndex);
while (height >= 0 && newOffset >= height) {
    newOffset -= height;
    height = getHeight(++startIndex);
}
if (height < 0 && startIndex > 0) startIndex--;

向上滾動

與上面類似，讓 offset 循環(huán)加上 height[startIndex-1]，然后 startIndex 減一，直到 offset >= 0：

let newOffset = offset + delta;
let height = getHeight(--startIndex);
while (newOffset < 0 && height >= 0) {
    newOffset += height;
    height = getHeight(--startIndex);
}
startIndex++;

邊界處理

約定已經(jīng)渲染在頁面上的列表高度為 listHeight，可視區(qū)域高度為 viewHeight

獲取渲染結果方法為 getRenderRange(startPosition: [number, number], viewHeight, getHeight) => [number, number]

對于向下滾動，這里從 delta 入手，通過計算可用的剩余高度 restHeight，限制 delta 的最大值，考慮到后續(xù)的元素，需要讓 restHeight 循環(huán)加上 height[++endIndex]，直到 restHeight >= delta 或者沒有更多可渲染的元素：

let restHeight = listHeight - offset - viewHeight;
if (restHeight < delta) {
    // 計算剩余高度，限制移動距離
    let [_, endIndex] = getRenderRange(
        [startIndex, offset],
        viewHeight,
        getHeight
    );
    let nextElementHeight = getHeight(endIndex);
    while (restHeight < delta && nextElementHeight >= 0) {
        restHeight += nextElementHeight;
        nextElementHeight = getHeight(++endIndex);
    }
    delta = Math.min(delta, restHeight);
}

對于向上滾動，只需要保證 offset 的值大于等于0即可：

newOffset = Math.max(0, newOffset);

緩沖區(qū)

緩沖區(qū)是可視區(qū)域與不可視區(qū)域的過渡地帶，主要作用是讓元素能夠在進入可視區(qū)域之前就渲染好，尤其是在元素的高度不確定時。雖然虛擬列表天然支持可視區(qū)域內元素高度的變化，但是將元素加載的時機提前到展示之前，可以減少向用戶展示未加載頁面的情況，減輕列表元素位置突然變化導致的晃動。

實現(xiàn)方式也非常簡單，只需要對上面基礎滾動的循環(huán)退出條件稍微進行修改即可：

約定緩沖區(qū)長度為 paddingHeight，取值范圍為 [0, Infinity]

向下滾動：offset 循環(huán)減去 height[startIndex]，直到 offset - height[startIndex] < paddingHeight 向上滾動：offset 循環(huán)加上 height[startIndex-1]，直到 offset >= paddingHeight

實現(xiàn)

將上述滾動代碼整合一下：

/**
 * 根據(jù)起始位置和移動距離計算新的起始位置
 * @param {[number, number]} startPosition 起始位置 [起始元素索引，起始元素offset]
 * @param {number} delta 移動距離
 * @param {[number, number, number]} renderInfo 渲染信息 [視口高度，預渲染高度，列表高度]
 * @param {(index: number) => number} getHeight 高度計算函數(shù)
 * @returns {[number, number]} 新的起始位置
 */
function move(startPosition, delta, renderInfo, getHeight) {
  let [startIndex, offset] = startPosition;
  const [viewHeight, paddingHeight, listHeight] = renderInfo;

  let newOffset = offset;

  if (delta > 0) {
    // 向下滾動
    let restHeight = listHeight - offset - viewHeight;
    if (restHeight < delta) {
      // 計算剩余高度，限制移動距離
      let [_, endIndex] = getRenderRange(startPosition, renderInfo, getHeight);
      let nextElementHeight = getHeight(endIndex);
      while (restHeight < delta && nextElementHeight >= 0) {
        restHeight += nextElementHeight;
        nextElementHeight = getHeight(++endIndex);
      }
      delta = Math.min(delta, restHeight);
    }
    newOffset = offset + delta;

    // 向后移動，直到offset >= paddingHeight
    let height = getHeight(startIndex);
    while (height >= 0 && newOffset - height >= paddingHeight) {
      newOffset -= height;
      height = getHeight(++startIndex);
    }
    if (height < 0 && startIndex > 0) startIndex--;
  } else if (delta < 0) {
    // 向上滾動
    newOffset = offset + delta;
    if (newOffset < paddingHeight) {
      // 向前移動，直到offset >= paddingHeight
      let height = getHeight(--startIndex);
      while (newOffset < paddingHeight && height >= 0) {
        newOffset += height;
        height = getHeight(--startIndex);
      }
      startIndex++;
      newOffset = Math.max(0, newOffset);
    }
  }

  return [startIndex, newOffset];
}

實現(xiàn)計算渲染范圍的函數(shù) getRenderRange，需要注意返回的取值范圍為 [startIndex, endIndex)：

/**
 * 根據(jù)起始位置計算渲染范圍
 * @param {[number, number]} startPosition 起始位置 [起始元素索引，起始元素offset]
 * @param {[number, number]} renderInfo 渲染信息 [視口高度，預渲染高度]
 * @param {(index: number) => number} getHeight 高度計算函數(shù)
 * @returns {[number, number, number]} 計算結果 [起始索引，結束索引，列表長度]
 */
function getRenderRange(startPosition, renderInfo, getHeight) {
  const [startIndex, offset] = startPosition;
  const [viewHeight, paddingHeight] = renderInfo;
  const renderHeight = offset + viewHeight + paddingHeight;
  let endIndex = startIndex;
  let height = getHeight(endIndex);
  let currentPosition = 0;
  while (height >= 0 && currentPosition < renderHeight) {
    currentPosition += height;
    height = getHeight(++endIndex);
  }
  return [startIndex, endIndex, currentPosition];
}

至此，動態(tài)虛擬列表的核心代碼就結束了！但是距離完成一個完整的虛擬列表，至少還要實現(xiàn)以下內容：