前言

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

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

思考&設(shè)計(jì)

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

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

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

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

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

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

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

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

基礎(chǔ)滾動(dòng)

向下滾動(dòng)

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

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

向上滾動(dòng)

與上面類似，讓 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)渲染在頁(yè)面上的列表高度為 listHeight，可視區(qū)域高度為 viewHeight

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

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

let restHeight = listHeight - offset - viewHeight;
if (restHeight < delta) {
    // 計(jì)算剩余高度，限制移動(dòng)距離
    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);
}

對(duì)于向上滾動(dòng)，只需要保證 offset 的值大于等于0即可：

newOffset = Math.max(0, newOffset);

緩沖區(qū)

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

實(shí)現(xiàn)方式也非常簡(jiǎn)單，只需要對(duì)上面基礎(chǔ)滾動(dòng)的循環(huán)退出條件稍微進(jìn)行修改即可：

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

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

實(shí)現(xiàn)

將上述滾動(dòng)代碼整合一下：

/**
 * 根據(jù)起始位置和移動(dòng)距離計(jì)算新的起始位置
 * @param {[number, number]} startPosition 起始位置 [起始元素索引，起始元素offset]
 * @param {number} delta 移動(dòng)距離
 * @param {[number, number, number]} renderInfo 渲染信息 [視口高度，預(yù)渲染高度，列表高度]
 * @param {(index: number) => number} getHeight 高度計(jì)算函數(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) {
    // 向下滾動(dòng)
    let restHeight = listHeight - offset - viewHeight;
    if (restHeight < delta) {
      // 計(jì)算剩余高度，限制移動(dòng)距離
      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;

    // 向后移動(dòng)，直到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) {
    // 向上滾動(dòng)
    newOffset = offset + delta;
    if (newOffset < paddingHeight) {
      // 向前移動(dòng)，直到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];
}

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

/**
 * 根據(jù)起始位置計(jì)算渲染范圍
 * @param {[number, number]} startPosition 起始位置 [起始元素索引，起始元素offset]
 * @param {[number, number]} renderInfo 渲染信息 [視口高度，預(yù)渲染高度]
 * @param {(index: number) => number} getHeight 高度計(jì)算函數(shù)
 * @returns {[number, number, number]} 計(jì)算結(jié)果 [起始索引，結(jié)束索引，列表長(zhǎng)度]
 */
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];
}

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

• 用于獲取元素高度的函數(shù) getHeight(index:number) => number
• 根據(jù) getRenderRange 返回值進(jìn)行渲染的函數(shù) render() => void
• 監(jiān)聽已渲染的元素高度變化并重新執(zhí)行 render
• 監(jiān)聽 wheel 和 touchmove 事件并按順序執(zhí)行 move 和 render
• 為滾動(dòng)添加動(dòng)畫效果

此外，為了避免頻繁調(diào)用 getHeight，還可以基于 LRUCache 或 LFUCache 等緩存技術(shù)對(duì)高度進(jìn)行緩存。

考慮到 getHeight 和 render 在不同環(huán)境可能會(huì)和瀏覽器原生JS的實(shí)現(xiàn)方式有所出入，而且這些內(nèi)容太長(zhǎng)就不放在這里了

以上就是JS動(dòng)態(tài)高度虛擬列表實(shí)現(xiàn)原理解析的詳細(xì)內(nèi)容，更多關(guān)于JS虛擬列表的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論