前端虚拟列表的实现原理

285次阅读  |  发布于3年以前

近期在某平台开发迭代的过程中遇到了超长List嵌套在antd Modal里加载慢，卡顿的情况。于是心血来潮决定从零自己实现一个虚拟滚动列表来优化一下整体的体验。

改造前：

img

我们可以看出来在改造之前，打开编辑窗口Modal的时候会出现短暂的卡顿，并且在点击Cancel关闭后也并不是立即响应而是稍作迟疑之后才关闭的

改造后：

img

改造完成后我们可以观察到整个Modal的打开比之前变得流畅了不少，可以做到立即响应用户的点击事件唤起/关闭Modal

0x0 基础知识

所以什么是虚拟滚动/列表呢？

一个虚拟列表是指当我们有成千上万条数据需要进行展示但是用户的“视窗”（一次性可见内容）又不大时我们可以通过巧妙的方法只渲染用户最大可见条数+“BufferSize”个元素并在用户进行滚动时动态更新每个元素中的内容从而达到一个和长list滚动一样的效果但花费非常少的资源。

img

(从上图中我们可以发现实际用户每次能看到的元素/内容只有item-4 ~ item-13 也就是9个元素)

0x1 实现一个“定高”虚拟列表

因为我们只对可视区域的内容做了渲染，所以为了保持整个容器的行为和一个长列表相似（滚动）我们必须保持原列表的高度，所以我们将HTML结构设计成如下

<!--ver 1.0 -->
<div className="vListContainer">
  <div className="phantomContent">
    ...
    <!-- item-1 -->
    <!-- item-2 -->
    <!-- item-3 -->
    ....
  </div>
</div>

（注意此处我们用的是向上取整）

onScroll(evt: any) {
  // 判断是否是我们需要响应的滚动事件
  if (evt.target === this.scrollingContainer.current) {
    const { scrollTop } = evt.target;
    const { startIndex, total, rowHeight, limit } = this;

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

    // 如果currentStartIndex 和 startIndex 不同（我们需要更新数据了）
    if (currentStartIndex !== startIndex ) {
      this.startIndex = currentStartIndex;
      this.endIndex = Math.min(currentStartIndedx + limit, total - 1);
      this.setState({ scrollTop });
    }
  }
}
renderDisplayContent = () => {
  const { rowHeight, startIndex, endIndex } = this;
  const content = [];

  // 注意这块我们用了 <= 是为了渲染x+1个元素用来在让滚动变得连续（永远渲染在判断&渲染x+2）
  for (let i = startIndex; i <= endIndex; ++i) {
    // rowRenderer 是用户定义的列表元素渲染方法，需要接收一个 index i 和
    //    当前位置对应的style
    content.push(
      rowRenderer({
        index: i, 
        style: {
          width: '100%',
          height: rowHeight + 'px',
          position: "absolute",
          left: 0,
          right: 0,
          top: i * rowHeight,
          borderBottom: "1px solid #000",
        }
      })
    );
  }

  return content;
};

线上Demo：https://codesandbox.io/s/a-naive-v-list-f0ghm

原理：

优化：

onScroll(evt: any) {
  ........
  // 计算当前startIndex
  const currentStartIndex = Math.floor(scrollTop / rowHeight);

  // 如果currentStartIndex 和 startIndex 不同（我们需要更新数据了）
  if (currentStartIndex !== originStartIdx) {
    // 注意，此处我们引入了一个新的变量叫originStartIdx，起到了和之前startIndex
    //    相同的效果，记录当前的 真实 开始下标。
    this.originStartIdx = currentStartIndex;
    // 对 startIndex 进行 头部 缓冲区 计算
    this.startIndex = Math.max(this.originStartIdx - bufferSize, 0);
    // 对 endIndex 进行 尾部 缓冲区 计算
    this.endIndex = Math.min(
      this.originStartIdx + this.limit + bufferSize,
      total - 1
    );

    this.setState({ scrollTop: scrollTop });
  }
}

线上Demo：https://codesandbox.io/s/A-better-v-list-bkw1t

0x2 列表元素高度自适应

现在我们已经实现了“定高”元素的虚拟列表的实现，那么如果说碰到了高度不固定的超长列表的业务场景呢？

  1. 对输入数据进行更改，传入每一个元素对应的高度 dynamicHeight[i] = x x 为元素i 的行高

需要实现知道每一个元素的高度（不切实际） 2. 将当前元素先在屏外进行绘制并对齐高度进行测量后再将其渲染到用户可视区域内

这种方法相当于双倍渲染消耗（不切实际） 3. 传入一个estimateHeight 属性先对行高进行估计并渲染，然后渲染完成后获得真实行高并进行更新和缓存

会引入多余的transform（可以接受），会在后边讲为什么需要多余的transform...

<!--ver 1.0 -->
<div className="vListContainer">
  <div className="phantomContent">
    ...
    <!-- item-1 -->
    <!-- item-2 -->
    <!-- item-3 -->
    ....
  </div>
</div>


<!--ver 1.1 -->
<div className="vListContainer">
  <div className="phantomContent" />
  <div className="actualContent">
    ...
    <!-- item-1 -->
    <!-- item-2 -->
    <!-- item-3 -->
    ....
  </div>
</div>
getTransform() {
  const { scrollTop } = this.state;
  const { rowHeight, bufferSize, originStartIdx } = this;

  // 当前滑动offset - 当前被截断的（没有完全消失的元素）距离 - 头部缓冲区距离
  return `translate3d(0,${
    scrollTop -
    (scrollTop % rowHeight) -
    Math.min(originStartIdx, bufferSize) * rowHeight
  }px,0)`;

}

线上Demo：https://codesandbox.io/s/a-v-list-achieved-by-transform-container-29mbc

(注：当没有高度自适应要求时且没有实现cell复用时，把元素通过absolute渲染在phantom里会比通过transform的性能要好一些。因为每次渲染content时都会进行重排，但是如果使用transform时就相当于进行了( 重排 + transform) > 重排）

interface CachedPosition {
  index: number;         // 当前pos对应的元素的下标
  top: number;           // 顶部位置
  bottom: number;        // 底部位置
  height: number;        // 元素高度
  dValue: number;        // 高度是否和之前(estimate)存在不同
}

cachedPositions: CachedPosition[] = [];

// 初始化cachedPositions
initCachedPositions = () => {
  const { estimatedRowHeight } = this;
  this.cachedPositions = [];
  for (let i = 0; i < this.total; ++i) {
    this.cachedPositions[i] = {
      index: i,
      height: estimatedRowHeight,             // 先使用estimateHeight估计
      top: i * estimatedRowHeight,            // 同上
      bottom: (i + 1) * estimatedRowHeight,   // same above
      dValue: 0,
    };
  }
};
this.phantomHeight = this.cachedPositions[cachedPositionsLen - 1].bottom;

componentDidUpdate() {
  ......
  // actualContentRef必须存在current （已经渲染出来） + total 必须 > 0
  if (this.actualContentRef.current && this.total > 0) {
    this.updateCachedPositions();
  }
}

updateCachedPositions = () => {
  // update cached item height
  const nodes: NodeListOf<any> = this.actualContentRef.current.childNodes;
  const start = nodes[0];

  // calculate height diff for each visible node...
  nodes.forEach((node: HTMLDivElement) => {
    if (!node) {
      // scroll too fast?...
      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;
    }
  });

  // perform one time height update...
  let startIdx = 0;

  if (start) {
    startIdx = Number(start.id.split('-')[1]);
  }

  const cachedPositionsLen = this.cachedPositions.length;
  let cumulativeDiffHeight = this.cachedPositions[startIdx].dValue;
  this.cachedPositions[startIdx].dValue = 0;

  for (let i = startIdx + 1; i < cachedPositionsLen; ++i) {
    const item = this.cachedPositions[i];
    // update height
    this.cachedPositions[i].top = this.cachedPositions[i - 1].bottom;
    this.cachedPositions[i].bottom = this.cachedPositions[i].bottom - cumulativeDiffHeight;

    if (item.dValue !== 0) {
      cumulativeDiffHeight += item.dValue;
      item.dValue = 0;
    }
  }

  // update our phantom div height
  const height = this.cachedPositions[cachedPositionsLen - 1].bottom;
  this.phantomHeight = height;
  this.phantomContentRef.current.style.height = `${height}px`;
};
getStartIndex = (scrollTop = 0) => {
  let idx = binarySearch<CachedPosition, number>(this.cachedPositions, scrollTop, 
    (currentValue: CachedPosition, targetValue: number) => {
      const currentCompareValue = currentValue.bottom;
      if (currentCompareValue === targetValue) {
        return CompareResult.eq;
      }

      if (currentCompareValue < targetValue) {
        return CompareResult.lt;
      }

      return CompareResult.gt;
    }
  );

  const targetItem = this.cachedPositions[idx];

  // Incase of binarySearch give us a not visible data(an idx of current visible - 1)...
  if (targetItem.bottom < scrollTop) {
    idx += 1;
  }

  return idx;
};



onScroll = (evt: any) => {
  if (evt.target === this.scrollingContainer.current) {
    ....
    const currentStartIndex = this.getStartIndex(scrollTop);
    ....
  }
};
export enum CompareResult {
  eq = 1,
  lt,
  gt,
}



export function binarySearch<T, VT>(list: T[], value: VT, compareFunc: (current: T, value: VT) => CompareResult) {
  let start = 0;
  let end = list.length - 1;
  let tempIndex = null;

  while (start <= end) {
    tempIndex = Math.floor((start + end) / 2);
    const midValue = list[tempIndex];
    const compareRes: CompareResult = compareFunc(midValue, value);

    if (compareRes === CompareResult.eq) {
      return tempIndex;
    }

    if (compareRes === CompareResult.lt) {
      start = tempIndex + 1;
    } else if (compareRes === CompareResult.gt) {
      end = tempIndex - 1;
    }
  }

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

线上Demo: https://codesandbox.io/s/a-v-list-has-dynamic-inner-height-yh0r7

Copyright© 2013-2020

All Rights Reserved 京ICP备2023019179号-8