JS动态高度虚拟列表实现原理解析_Javascript

前言

本文适合对虚拟列表技术已经有基本了解的程序猿食用，仅提供一种理解和实现动态虚拟列表的思路，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];
}

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