JS动态高度虚拟列表实现原理解析-牛翰网

前言

本文适合对虚拟列表技术已经有基本了解的程序猿食用，仅提供一种理解和实现动态虚拟列表的思路，CV工程师（你知道我说的不是计算机视觉那个CV）谨慎使用！！！

环境为浏览器原生JS环境，不涉及任何框架。

思考&设计

常见的虚拟列表都采用累计高度的方式，使用一张非递减表来记录虚拟列表中每个元素的起始位置，并且使用二分查找当前位置对应的需要渲染元素，这样实现非常直观易懂，但是会导致下面几个缺点：

随着列表不断变长，用来记录高度的数组会变得越来越大。简单做一个计算，number使用双精度数，这意味着一个number理论上占用8个字节，那么当数组长度到达131072时，将会至少占用1MB的空间，看起来其实还挺小的，只是对于强迫症来说还是不够优雅，因此不算真正意义上的缺点。
如果列表一开始就在某个非零位置，那么在当前位置之前的元素高度都确定下来之前，列表没法渲染任何元素（仅针对动态虚拟列表）。常见的解决方案是在不渲染元素前就估算元素高度。但估算元素高度是不是需要元素的内容？这些内容是不是要靠后端传给你？后端吭哧吭哧把数据返回来了，结果你看一眼就“丢了”，实在是太“渣”了。前端是这样的，只要调调后端api就好了，而后端要考虑的可就多了（
当某个位置的元素高度发生变化了，那么恭喜你，从这个元素开始，列表中后续的所有元素的起始位置都要重新计算，虽然实际上只需要将变化量向后传导即可，但这始终不是一个好主意

列了这么多缺点，可以看到这些问题都围绕一个前提：使用了一张记录每个元素的起始位置的表，这张表中每一项都是基于前一项计算出来的，这意味着整张表天然具有前向依赖，或者说，改变表中的任意一项都会对后面的项产生副作用。所以解决方案就是丢掉这张碍事的表了，劳资掀桌不玩了！

那么丢掉了这张表之后，该如何确定渲染的范围呢？仔细思考，实际上虚拟列表只需要起始元素索引值 startIndex和起始元素到可视区起始位置的距离 offset。结束的位置只需要从起始元素开始，不断累加元素的高度，直到没有更多的元素或者列表高度已经超过渲染范围即可。然后你就会发现在这种设计下：

虚拟列表天然支持任意的起始位置！如果我希望虚拟列表一开始就从第500个元素开始展示，那么只需要告诉虚拟列表 startIndex = 500 和 offset = 0 即可！
虚拟列表天然支持动态高度的元素！渲染区域外的元素高度发生变化，关我虚拟列表啥事，眼不见心不烦，接着奏乐接着舞！渲染区域内的元素高度发生了变化？好说，保持 startIndex 和 offset 不变，重新渲染一遍就是！

想法很美好，但是慢着，还有非常重要的滚动问题！在原本的虚拟列表中，只需要修改当前位置，然后重新渲染就好，但是现在换成了 startIndex 和 offset 的组合，这意味着在滚动时不仅需要重新计算 startIndex，还需要基于滚动距离 delta 和新的 startIndex 修改 offset：

约定索引为 i 的元素高度为 height[i]

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

基础滚动

向下滚动

由于我们只关心 startIndex 和 offset，因此只有当 offset >= height[startIndex]，即起始元素已经在渲染范围外时才需要重新计算 startIndex，重新计算的方法也很简单，只需要让 offset 循环减去 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 循环加上 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++;

边界处理

约定已经渲染在页面上的列表高度为 listHeight，可视区域高度为 viewHeight

获取渲染结果方法为 getRenderRange(startPosition: [number, number], viewHeight, getHeight) => [number, number]

对于向下滚动，这里从 delta 入手，通过计算可用的剩余高度 restHeight，限制 delta 的最大值，考虑到后续的元素，需要让 restHeight 循环加上 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);

缓冲区

缓冲区是可视区域与不可视区域的过渡地带，主要作用是让元素能够在进入可视区域之前就渲染好，尤其是在元素的高度不确定时。虽然虚拟列表天然支持可视区域内元素高度的变化，但是将元素加载的时机提前到展示之前，可以减少向用户展示未加载页面的情况，减轻列表元素位置突然变化导致的晃动。

实现方式也非常简单，只需要对上面基础滚动的循环退出条件稍微进行修改即可：

约定缓冲区长度为 paddingHeight，取值范围为 [0, Infinity]

向下滚动：offset 循环减去 height[startIndex]，直到 offset - height[startIndex] < paddingHeight 向上滚动：offset 循环加上 height[startIndex-1]，直到 offset >= paddingHeight

实现

将上述滚动代码整合一下：

/**
 * 根据起始位置和移动距离计算新的起始位置
 * @param {[number, number]} startPosition 起始位置 [起始元素索引，起始元素offset]
 * @param {number} delta 移动距离
 * @param {[number, number, number]} renderInfo 渲染信息 [视口高度，预渲染高度，列表高度]
 * @param {(index: number) => number} getHeight 高度计算函数
 * @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];
}

实现计算渲染范围的函数 getRenderRange，需要注意返回的取值范围为 [startIndex, endIndex)：

/**
 * 根据起始位置计算渲染范围
 * @param {[number, number]} startPosition 起始位置 [起始元素索引，起始元素offset]
 * @param {[number, number]} renderInfo 渲染信息 [视口高度，预渲染高度]
 * @param {(index: number) => number} getHeight 高度计算函数
 * @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];
}

至此，动态虚拟列表的核心代码就结束了！但是距离完成一个完整的虚拟列表，至少还要实现以下内容：