一次学习彻底搞懂什么是虚拟列表

前言

虚拟滚动作为长列表的重要性能优化手段，能给用户带来体验感的飞跃提升，因此也成为前端页面仔的必备技能。今天我们就来瞅瞅到底什么是虚拟滚动，以及她的实现（React方式）。

什么是虚拟滚动/列表呢

一个虚拟列表是指当用户出现成千上万条数据需要展示，但是用户的“视窗“，也就是一次性可见的内容又不大。此时就可以使用一种巧妙的方法只渲染用户最大的可见条数个元素，并且在用户进行滚动的时候动态更新每个元素的内容从而达到一个和长list一样的滚动效果，但花费非常少的资源。

话不多说一图胜千言，上图

从上图可以发现，实际上用户每次能看到的其实只有item4 - item13 10个元素。那么既然如此，索性就不去渲染其他不可见的元素，这就是虚拟列表的奥秘。

实现“定高”的虚拟列表

在实现虚拟列表之前，首先我们应该要明确几个重要的变量。

• 从上图中可以知道用户实际可以看见的开始元素是item4，所以它在数组中的下标也就是我们的startIndex
• 那与之对应的就是可以看见的最后一个元素item13，所以它的下标就是我们的endIndex
• 那item1，item2以及item3是已经滚动上去的元素，也就是被用户滚动所隐藏的元素，其实就是scrollTop

我们实际上只渲染可视区域的内容，但为了保持容器的行为和长list一致（滚动），必须要保持原列表的高度，因此我们的HTML结构如下

<div className="list-container">
    <div className="phantom-container">
        ...
        <!-- item1 -->
        <!-- item2 -->
        <!-- item3 -->
        ...
    </div>
</div>

其中，

• list-container为可视区域的容器，具有overflow-y: auto的属性
• phantom-container就是我们的“幻影”容器，主要用来还原真实的列表高度从而模拟正常长list的滚动行为
• 而在“幻影”容器的内部item，也就是用户要看到的每一条数据，都具有position: absolute，目的是通过css定位的办法来确认每个元素的具体位置。

接着我们在可视区域的容器上绑定onScroll函数，通过原生滚动事件的scrollTop来计算我们的startIndex和endIndex。到了此时，除了之前确定的变量外，其余重要的变量也可以明确。

• 列表的总数，total
• 明确的每一个列表元素的高度，rowHeight
• 可视区域的高度，height
• 列表的总高度，phantomHeight = total * rowHeight
• 可视区域内可以展示的元素个数，limit = Math.ceil(height/rowHeight)

有了上述的重要变量之后，我们就可以根据滚动到的当前的元素下标和我们保存的startIndex进行比较，如果不同则说明我们需要更新可视区域的展示数据了，具体实现如下：

onScroll = (e: any) => {
    //判断滚动事件是否发生在可视区域
    if (e.target === this.scrollContainer.current) {
      const { scrollTop } = e.target;
      const { total, rowHeight, limit, startIndex } = this;

      //计算当前的startIndex
      const currentIndex = Math.floor(scrollTop / rowHeight);

      if (currentIndex !== startIndex) {
        this.startIndex = Math.max(currentIndex, 0);
        this.endIndex = Math.min(currentIndex + limit, total - 1);
        //触发重绘
        this.setState({ scrollTop });
      }
    }
};

而当我们已经可以拿到startIndex和endIndex，我们就可以渲染可视区域的内容，实现如下：

renderDisplayContent = () => {
    const { rowHeight } = this;
    const content: any[] = [];
    //使用 <= 是为了渲染x+1个元素，让滚动看起来更加连续
    for (let i = this.startIndex; i <= this.endIndex; ++i) {
      content.push(
        //组件外部传进来的元素渲染方法，top表示该元素的真正位置
        this.props.rowRender(i, {
            height: rowHeight - 1 + "px",
            lineHeight: rowHeight + "px",
            left: 0,
            right: 0,
            position: "absolute",
            top: i * rowHeight,
            borderBottom: "1px solid #000",
            width: "100%"
        })
      );
    }
    return content;
};

原理

首先我们在可视区域的容器中渲染了一个真实list高度的“幻影”容器，从而可以让用户进行滚动操作。接着我们在可视区域的容器上绑定了onScroll滚动事件。当每次用户触发滚动时，去计算当前的scrollTop（被滚上去隐藏了多少元素）所对应的开始元素下标index是多少。当发现新的index和我们当前展示的index不同时，则触发重绘，表示我们需要更新可视区域的展示内容。当用户的滚动未触发下标更新时，则因为本身“幻影”容器的高度关系让虚拟列表拥有和普通列表一样的滚动能力。触发重绘时，因为计算的是startIndex，所以滚动的下一帧和我们重绘的内容完全一致，最终用户感知不到页面的重绘。

优化

对于上述实现的虚拟滚动列表，如果在一开始就快速滚动，因为出现了来不及渲染的情况而导致列表闪烁，出现空白的现象。为了解决这一问题，我们可以加入bufferSize的概念，在可视区域上下多渲染几个元素，用来过渡快速滑动产生的空白问题。优化onScroll方法：

onScroll = (e: any) => {
    if (e.target === this.scrollContainer.current) {
      const { scrollTop } = e.target;
      const { total, rowHeight, limit, originStartIdx, bufferSize } = this;

      //计算当前的startIndex
      const currentIndex = Math.floor(scrollTop / rowHeight);
      
      //引入originStartIdx，用来记录真实的开始下标
      if (originStartIdx !== currentIndex) {
        this.originStartIdx = currentIndex;
        //增加头部的缓冲区，startIndex变小
        this.startIndex = Math.max(currentIndex - bufferSize, 0);
        //增加尾部的缓冲区，endIndex变大
        this.endIndex = Math.min(currentIndex + limit + bufferSize, total - 1);
        this.setState({ scrollTop });
      }
    }
};

具体代码实现，可以到github上查看，欢迎star github.com/confuciusth…

实现“不定高”的虚拟列表

在日常的实际开发中，我们大部分情况下无法保证列表中的每一个元素在其开始渲染前就确定它的真实高度。我们希望它的高度自适应的同时，也能进行虚拟滚动。那么如果一开始不知道具体的高度，怎么计算startIndex，怎么确定当前滚动到哪个元素了呢？

办法：传入estimateHeight属性，这个属性代表每个元素预估的高度，然后开始渲染，等到初次渲染完成后我们就知道了真实的高度，此时再进行位置的更新和缓存。会引入多余的transform来控制位置的变化。

首先，让我们回到HTML部分，由于“幻影”列表此时高度不确定，所以就不能对每个元素使用定位的方式来进行位置的跟踪。那么我们需要使用另外一个容器来帮我们实现这个绝对定位。

<!-- version1.0 -->
<div className="list-container">
    <div className="phantom-container">
        ...
        <!-- item1 -->
        <!-- item2 -->
        <!-- item3 -->
        ...
    </div>
</div>


<!-- version2.0 -->
<div className="list-container">
    <div className="phantom-container"></div>
    <div className="actual-container">
        ...
        <!-- item1 -->
        <!-- item2 -->
        <!-- item3 -->
        ...
    </div>
</div>

• actual-container就是我们新创建的列表渲染容器，在此容器上设置position: absolute。这样我们就不需要考虑每个元素的定位位置，而是当用户滚动时直接动态的对这个容器进行一个y-transform的移动，让其始终保持在可视区域的容器中，具体实现：

//当前滑动的scrollTop - 没有消失完全的高度 - 缓冲区的高度
getTransform = () => `
    translate3d(0, ${
        scrollTop -  
        (scrollTop % rowHeight) -  
        Math.min(originStartIdx, bufferSize) * rowHeight
    }px, 0)
`;

• phantom-container作为“幻影”容器，仍需要进行高度的设置，而这个设置需要在位置进行更新时，动态计算，以达到原先“幻影”容器的作用。

• 那么现在就可以通过这个预估的高度，先将元素渲染到列表渲染容器中，此时：

limit = Math.ceil(height/estimateHeight);

phantomHeight = total * estimateHeight;

• 接着为了避免重复计算每一个元素的实际高度我们需要一个数组cachedPositions来缓存每一个元素的位置以及高度信息

interface CachedPosition {
  /**
   * 元素的下标
   */
  index: number;
  /**
   * 顶部距离定位的偏移位置
   */
  top: number;
  /**
   * 底部距离定位的偏移位置
   */
  bottom: number;
  /**
   * 元素的高度
   */
  height: number;
  /**
   * 元素渲染后和之前估计的高度的差值
   */
  dValue: number;
}

cachedPositions: CachedPosition[] = [];

//constructor时，使用预估的高度初始化所有元素的位置
initCachedPositions = () => {
    for (let i = 0; i < this.total; ++i) {
        this.cachedPositions[i] = {
            index: i,
            top: i * this.estimateRowHeight,
            bottom: (i + 1) * this.estimateRowHeight,
            height: this.estimateRowHeight,
            dValue: 0
        };
    }
};

• 当我们根据estimateHeight渲染完用户视窗内的元素后，我们需要对渲染出来的元素做实际高度更新，则在componentDidMount生命周期内进行；而当发生滚动需要渲染更多的元素时我们可以利用componentDidUpdate生命周期钩子来重新进行计算、判断和更新：

updateCachedPositions = () => {
    if (!this.actualContentRef.current) {
      return;
    }
    //获取到实际的列表渲染容器中的所有元素
    const nodes: NodeListOf<any> = this.actualContentRef.current.childNodes;
    const start = nodes[0];

    //计算显示当前已经渲染的每个元素的高度的不同
    nodes.forEach((node: HTMLDivElement) => {
      if (!node) return;
      const rect = node.getBoundingClientRect();
      const { height } = rect;
      const index = Number(node.id.split("-")[1]);
      const oldHeight = this.cachedPositions[index].height;
      const dValue = oldHeight - height;

      if (dValue) {
        this.cachedPositions[index].bottom -= dValue;
        this.cachedPositions[index].height = height;
        this.cachedPositions[index].dValue = dValue;
      }
    });
    
    let startIdx = 0;
    if (start) {
      startIdx = Number(start.id.split("-")[1]);
    }
    
    //只要一个元素存在高度的不同，那么其后续的所有元素的位置都需要进行更新，
    //这个操作可能会很耗时，所以将其放到webworker中计算
    if (this.worker) {
        this.worker.postMessage(["update", startIdx, this.cachedPositions]);
        this.worker.onmessage = (e) => {
            const [newCachedPositions, height] = e.data;
            this.phantomHeight = height;
            this.cachedPositions = newCachedPositions;
            
            //动态设置“幻影”容器的高度
            if (this.phantomContentRef.current) {
                this.phantomContentRef.current.style.height = `${height}px`;
            }
        };
    }
};


//worker.ts
let cachedPositions: any[] = [];
const updateCachedPositions = (startIdx: number) => {
    const cachedPositionsLen = cachedPositions.length;
    //之前的元素高度的差值的累计
    let cumulativeDiffHeight = cachedPositions[startIdx].dValue;
    cachedPositions[startIdx].dValue = 0;

    for (let i = startIdx + 1; i < cachedPositionsLen; ++i) {
      //因为高度的差异，导致元素的位置一定需要更新，其实就是更改每个后续元素的top,bottom值
      const item = cachedPositions[i];
      cachedPositions[i].top = cachedPositions[i - 1].bottom;
      //计算一律当作减法处理
      cachedPositions[i].bottom = cachedPositions[i].bottom - cumulativeDiffHeight;
      if (item.dValue !== 0) {
        cumulativeDiffHeight += item.dValue;
        item.dValue = 0;
      }
    }

    return cachedPositions[cachedPositionsLen - 1].bottom;
};

onmessage = (e) => {
    if (e.data[0] === 'update') {
        cachedPositions = e.data[2];
        const bottom = updateCachedPositions(e.data[1]);
        postMessage([cachedPositions, bottom]);
    }
};

• 当我们初始化完cachedPositions之后由于我们计算了每一个元素的top和bottom，所以“幻影”容器的高度就是cachedPositions中最后一个元素的bottom值

this.phantomHeight = this.cachedPositions[cachedPositionsLen - 1].bottom;

• 元素的top和bottom值说明
• 当我们有了每个渲染元素的具体实际的高度和位置时，我们获取当前scrollTop所对应的开始元素的方法也需要修改为从cachedPositions获取

实际上cachedPositions是一个有序的数组，为了提升查找速度，可以采用二分查找的方式降低时间复杂度

getStartIndex = (scrollTop = 0) => {
    let idx = binarySearch<CachedPosition, number>(
      this.cachedPositions,
      scrollTop,
      (currentValue, targetValue) => {
        const currentCompareValue = currentValue.bottom;
        if (currentCompareValue === targetValue) {
          return CompareResult.eq;
        }
        if (currentCompareValue < targetValue) {
          return CompareResult.lt;
        }

        return CompareResult.gt;
      }
    );

    const targetItem = this.cachedPositions[idx];

    //如果找到的是一个不可见的元素，则+1处理显示下一个
    if (targetItem.bottom < scrollTop) {
      idx += 1;
    }

    return idx;
};

onScroll = (evt: any) => {  
  if (evt.target === this.scrollingContainer.current) {  
    ....  
    const currentStartIndex = this.getStartIndex(scrollTop);  
    ....  
  }  
};


//bst.ts 实现二分查找
export enum CompareResult {
    eq = 1,
    lt,
    gt
}
  
export function binarySearch<T, VT>(
    list: T[],
    value: VT,
    compareFn: (current: T, value: VT) => CompareResult
  ) {
    let start = 0;
    let end = list.length - 1;
    let tempIndex = 0;
  
    while (start <= end) {
      tempIndex = Math.floor((start + end) / 2);
      const midValue = list[tempIndex];
  
      const compareRes: CompareResult = compareFn(midValue, value);
      if (compareRes === CompareResult.eq) {
        return tempIndex;
      }
      if (compareRes === CompareResult.lt) {
        start = tempIndex + 1;
      }
      if (compareRes === CompareResult.gt) {
        end = tempIndex - 1;
      }
    }
  
    return tempIndex;
}

• 最后，滚动获取transform值的方法也需要改造

getTransform = () => `
    translate3d(0, ${
      this.startIndex >= 1
        ? this.cachedPositions[this.startIndex - 1].bottom
        : 0
    }px, 0)
`;

原理

“不定高”的虚拟列表，实际上在初始化时仍依据预估的高度进行渲染，在等到渲染完成后根据元素的实际高度动态更新各个元素的位置，并通过transform的方式，让列表渲染容器移动位置，使其始终保持在可视容器中。

具体的代码实现，可以到github上查看，欢迎star github.com/confuciusth…

总结

通过上述的描述，相信大家可以体会到，一个不算太难的虚拟列表，真正实现起来实际上有好多细节需要处理以及考虑。所以我们起码应该对我们所写的代码抱有敬畏之心，要不停地从细节处多多打磨自己，相信最后我们都会成为技术大牛。

创作不易，欢迎点赞！