使用 Vue 实现一个虚拟列表的方法

<列表项 top 坐标值> = <上一项 top 坐标值> + <上一项的高度值>

// 假设使用该数组存储列表每一项的高度const itemHeightStore = [20, 20, 20, 20, 20]// 使用该方法，可以算出列表中指定项的 top 坐标值const getTop = (index) => { let sum = 0 while (index--) sum += itemHeightStore[index] || 0 return sum}// 第一项getTop(0) // 0// 第二项getTop(1) // 20// ...

const range = { start: 0, end: 4, value: 20}

// Avl.tsconst SLIGHTLY_UNBALANCED_RIGHT = -1const SLIGHTLY_UNBALANCED_LEFT = 1const UNBALANCED_RIGHT = -2const UNBALANCED_LEFT = 2// 树结点class AvlNode<K extends any = any> { key: any left: AvlNode<K> | null right: AvlNode<K> | null parent: AvlNode<K> | null _height: number _prevHeight: number constructor(key: K) {  this.key = key  this.left = null  this.right = null  this.parent = null  this._height = 0  this._prevHeight = 0 } // 刷新前的高度，方便平衡操作 get prevHeight() {  return this._prevHeight | 0 } get height() {  return this._height | 0 } set height(value) {  this._prevHeight = this._height | 0  this._height = value | 0 } // 左子树高度 get leftHeight() {  if (this.left === null) return -1  return this.left.height | 0 } // 右子树高度 get rightHeight() {  if (this.right === null) return -1  return this.right.height | 0 } // 平衡因子 get balanceFactor() {  return this.leftHeight - this.rightHeight } updateHeight() {  const { leftHeight, rightHeight } = this  const height = ((leftHeight > rightHeight ? leftHeight : rightHeight) + 1) | 0  this.height = height }}// AVL 树export class Avl<K extends any = any> { _root: AvlNode<K> | null _size: number constructor() {  this._root = null  this._size = 0 } get size() {  return this._size } // 插入节点 insert(key: K) {  const node = new AvlNode<K>(key)  const insertPoint = this._nodeInsert(node)  // 本次插入是重复结点，直接更新 key / value  // 无新结点插入，所以无需进行插入后的调整  if (insertPoint == null) return  // 新增结点成功时，回溯调整搜索路径上的结点  this._adjustAfterInsertion(insertPoint) } // 删除节点，返回是否成功删除结点 delete(key: K): boolean {  // 搜索待删除结点  const targetNode = this._nodeSearch(key)  // 未找到 value 对应结点  if (targetNode == null) return false  // 执行删除结点操作  const backtracking = this._nodeErase(targetNode)  const parent = backtracking[0]  // 回溯调整搜索路径上的结点  if (parent !== null) {   this._adjustAfterRemoval(parent)  }  return true } // 通过 key 查找包含该 key 范围的节点 key search(key: K) {  const node = this._nodeSearch(key)  if (node !== null) return node.key  return null } // 搜索 start 、end 两个 key 之间的所有 key 列表 searchRange(start: K, end: K) {  const results: K[] = []  // 找到符合条件的 root 节点  let root = this._root  while (root !== null) {   const result1 = start.compareTo(root.key)   const result2 = end.compareTo(root.key)   // 当前节点比 start 小，不再搜索左子树   if (result1 > 0) {    root = root.right    continue   }   // 当前节点大于 end，不再搜索右子树   if (result2 < 0) {    root = root.left    continue   }   break  }  if (!root) return results  const stack = []  let current: AvlNode<K> | null = root  while (stack.length || current) {   while (current) {    stack.push(current)    // 当前节点比 start 小，不再搜索 current 的左子树    if (start.compareTo(current.key) > 0) break    current = current.left   }   if (stack.length) {    // 指向栈顶    current = stack[stack.length - 1]    const gteStart = start.compareTo(current.key) <= 0    const lteEnd = end.compareTo(current.key) >= 0    if (gteStart && lteEnd) {     results.push(current.key)    }    stack.pop()    // 只有 current 比 end 小，才继续搜索 current 的右子树    if (lteEnd) {     current = current.right    }    else {     current = null    }   }  }  return results } // 增加结点数量 _increaseSize() {  this._size += 1 } // 减少结点数量 _decreaseSize() {  this._size -= 1 } // 设置左子结点，同时维护 parent 关系 _setLeft(node: AvlNode<K>, child: AvlNode<K> | null) {  // 断开旧 left 结点  if (node.left !== null) {   node.left.parent = null  }  // 连接新结点  if (child !== null) {   // 从旧 parent 中断开   if (child.parent !== null) {    child.parent.left === child ? (child.parent.left = null) : (child.parent.right = null)   }   child.parent = node  }  node.left = child } // 设置右子结点，同时维护 parent 关系 _setRight(node: AvlNode<K>, child: AvlNode<K> | null) {  // 断开旧 right 结点  if (node.right !== null) {   node.right.parent = null  }  // 连接新结点  if (child !== null) {   // 从旧 parent 中断开   if (child.parent !== null) {    child.parent.left === child ? (child.parent.left = null) : (child.parent.right = null)   }   child.parent = node  }  node.right = child } // 获取中序遍历顺序的前驱结点 _inorderPredecessor(node: AvlNode<K> | null) {  if (node == null) return null  // 1. 有左子树，找到左子树最大元素  if (node.left !== null) {   return this._maximumNode(node.left)  }  // 2. 没有左子树，往上搜索  let parent = node.parent  while (parent != null) {   if (node == parent.right) {    return parent   }   node = parent   parent = node.parent  }  // 4. 搜索到根  return null } // 获取最大的结点 _maximumNode(subRoot: AvlNode<K>) {  let current = subRoot  while (current.right !== null) current = current.right  return current } // 设置根结点 _setRoot(node: AvlNode<K> | null) {  if (node === null) {   this._root = null   return  }  this._root = node  // 如果本身在树中，则从树中脱落，成为独立的树根  if (node.parent !== null) {   node.parent.left === node ? (node.parent.left = null) : (node.parent.right = null)   node.parent = null  } } // 将树上某个结点替换成另一个结点 private _replaceNode(node: AvlNode<K>, replacer: AvlNode<K> | null) {  if (node === replacer) return node  // node 为 root 的情况  if (node === this._root) {   this._setRoot(replacer)  }  else {   // 非 root，有父结点的情况   const parent = node.parent as AvlNode<K>   if (parent.left === node) this._setLeft(parent, replacer)   else this._setRight(parent, replacer)  }  return node } // 左旋，返回新顶点，注意旋转完毕会从原本的树上脱落 private _rotateLeft(node: AvlNode<K>) {  const parent = node.parent  // 记录原本在树上的位置  const isLeft = parent !== null && parent.left == node  // 旋转  const pivot = node.right as AvlNode<K>  const pivotLeft = pivot.left  this._setRight(node, pivotLeft)  this._setLeft(pivot, node)  // 旋转完毕  // 新顶点接上树上原本的位置  if (parent !== null) {   if (isLeft) this._setLeft(parent, pivot)   else this._setRight(parent, pivot)  }  // ---  if (node === this._root) {   this._setRoot(pivot)  }  node.updateHeight()  pivot.updateHeight()  return pivot } // 右旋，返回新顶点，注意旋转完毕会从原本的树上脱落 private _rotateRight(node: AvlNode<K>) {  const parent = node.parent  // 记录原本在树上的位置  const isLeft = parent !== null && parent.left === node  // 旋转  const pivot = node.left as AvlNode<K>  const pivotRight = pivot.right  this._setLeft(node, pivotRight)  this._setRight(pivot, node)  // 旋转完毕  // 新顶点接上树上原本的位置  if (parent !== null) {   if (isLeft) this._setLeft(parent, pivot)   else this._setRight(parent, pivot)  }  // ---  if (node === this._root) {   this._setRoot(pivot)  }  node.updateHeight()  pivot.updateHeight()  return pivot } // 搜索 Node private _nodeSearch(key: K) {  let current = this._root  while (current !== null) {   let result = key.compareTo(current.key)   if (result === 0) return current   if (result < 0) current = current.left   else current = current.right  }  return null } // 在树里插入结点或者刷新重复结点 // 返回新插入（或刷新）的结点 private _nodeInsert(node: AvlNode<K>) {  // 空树  if (this._root === null) {   this._setRoot(node)   this._increaseSize()   return null  }  const key = node.key  let current = this._root  // 查找待插入的位置  while (true) {   const result = key.compareTo(current.key)   if (result > 0) {    if (current.right === null) {     this._setRight(current, node)     this._increaseSize()     return current    }    current = current.right   }   else if (result < 0) {    if (current.left === null) {     this._setLeft(current, node)     this._increaseSize()     return current    }    current = current.left   }   else {    // No duplicates, just update key    current.key = key    return null   }  } } // 从树上移除一个结点 private _nodeErase(node: AvlNode<K>) {  // 同时拥有左右子树  // 先转换成只有一颗子树的情况再统一处理  if (node.left !== null && node.right !== null) {   const replacer = this._inorderPredecessor(node)!   // 使用前驱结点替换身份   // 此时问题转换成删掉替代结点（前驱），   // 从而简化成只有一个子结点的删除情况   node.key = replacer.key   // 修改 node 指针   node = replacer  }  // 删除点的父结点  const parent = node.parent  // 待删结点少于两颗子树时，使用子树 (或 null，没子树时) 顶替移除的结点即可  const child = node.left || node.right  this._replaceNode(node, child)  this._decreaseSize()  return [ parent, child, node ] } // AVL 树插入结点后调整动作 // 自底向上调整结点的高度 // 遇到离 current 最近的不平衡点需要做旋转调整  // 注意: 对最近的不平衡点调整后 或者 结点的高度值没有变化时 // 上层结点便不需要更新  // 调整次数不大于1 _adjustAfterInsertion(backtracking: AvlNode<K> | null) {  let current = backtracking  // 往上回溯，查找最近的不平衡结点  while (current !== null) {   // 更新高度   current.updateHeight()   // 插入前后，回溯途径结点的高度没有变化，则无需继续回溯调整   if (current.height === current.prevHeight) break   // 若找到不平衡结点，执行一次调整即可   if (this._isUnbalanced(current)) {    this._rebalance(current)    // 调整过，则上层无需再调整了    break   }   current = current.parent  } } // AVL树删除结点后调整动作 // 自底向上调整结点的高度 // 遇到离 current 最近的不平衡点需要做旋转调整 // 注意: 对最近的不平衡点调整后，其上层结点仍然可能需要调整 // 调整次数可能不止一次 _adjustAfterRemoval(backtracking: AvlNode<K> | null) {  let current = backtracking  while (current !== null) {   // 更新高度   current.updateHeight()   // 删除前后，回溯途径结点的高度没有变化，则无需继续回溯调整   if (current.height === current.prevHeight) break   if (this._isUnbalanced(current)) {    this._rebalance(current)   }   // 与插入不同，调整过后，仍然需要继续往上回溯   // 上层结点（若有）仍需判断是否需要调整   current = current.parent  } } // LL _adjustLeftLeft(node: AvlNode<K>) {  return this._rotateRight(node) } // RR _adjustRightRight(node: AvlNode<K>) {  return this._rotateLeft(node) } // LR _adjustLeftRight(node: AvlNode<K>) {  this._rotateLeft(node.left!)  return this._rotateRight(node) } // RL _adjustRightLeft(node: AvlNode<K>) {  this._rotateRight(node.right!)  return this._rotateLeft(node) } // 检查结点是否平衡 _isUnbalanced(node: AvlNode<K>) {  const factor = node.balanceFactor  return factor === UNBALANCED_RIGHT || factor === UNBALANCED_LEFT } // 重新平衡 _rebalance(node: AvlNode<K>) {  const factor = node.balanceFactor  // Right subtree longer (node.factor: -2)  if (factor === UNBALANCED_RIGHT) {   let right = node.right!   // RL, node.right.factor: 1   if (right.balanceFactor === SLIGHTLY_UNBALANCED_LEFT) {    return this._adjustRightLeft(node)   }   else {    // RR, node.right.factor: 0|-1    // 即 right.rightHeight >= right.leftHeight    return this._adjustRightRight(node)   }  }  else if (factor === UNBALANCED_LEFT) {   // Left subtree longer (node.factor: 2)   let left = node.left!   // LR, node.left.factor: -1   if (left.balanceFactor === SLIGHTLY_UNBALANCED_RIGHT) {    return this._adjustLeftRight(node)   }   else {    // LL, node.left.factor: 1 | 0    // 即 left.leftHeight >= left.rightHeight    return this._adjustLeftLeft(node)   }  }  return node }}export function createAvl() { return new Avl()}// SparseRangeList.tsimport { createAvl, Avl } from './Avl'// 区间类class Range { start: number end: number constructor(start: number, end?: number) {  this.start = start  this.end = end || start } // 用于 Avl 中节点的比较 // // 列表中项目范围是连续的，必定不会重叠的 // 如果传入的 key 为重叠的，则意味着希望通过构造一个子 Range 搜索所在的 RangeValue // 例如构造一个 { start: 10, end: 10, value: 'any' }，搜索树中 // 范围包含 10~10 的 RangeValue，如 { start: 0, end: 20, value: 'any' } compareTo(other: Range) {  if (other.start > this.end!) return -1  if (other.end! < this.start) return 1  return 0 }}// 区间-值 类class RangeValue<T> extends Range { value: T constructor(start: number, end: number, value: T) {  super(start, end)  this.value = value } clone(): RangeValue<T> {  return new RangeValue(this.start, this.end!, this.value) }}// 最终存储区间-值的类，内部使用 Avl 存储所有 RangeValueexport default class SparseRangeList<T> { _size: number defaultValue: T valueTree: Avl constructor(size: number, defaultValue: T) {  this._size = size  this.defaultValue = defaultValue  this.valueTree = createAvl() } get size() {  return this._size } resize(newSize: number) {  newSize = newSize | 0  // 无调整  if (this._size === newSize) return  // 扩容  if (this._size < newSize) {   this._size = newSize   return  }  // 缩小，清空超出的部分，再缩小  this.setRangeValue(newSize - 1, this._size - 1, this.defaultValue)  this._size = newSize } // 返回区间包含 index 的 RangeValue 的值 getValueAt(index: number): T {  const result = this.valueTree.search(new Range(index))  if (result) return result.value  return this.defaultValue }  /**  * 设值方法，  * 自动与相邻的相同值的合并成更大的 RangeValue，  * 导致原本的 RangeValue 不连续，则会  * 自动切分成两个或者三个 RangeValue。  *  *     a-------------a  * |a------------|b------------|c-----------|...  *   * 结果：  * |a-------------------|b-----|c-----------|...  *   *   *     d-------------d  * |a------------|b------------|c-----------|...  *   * 结果：  * |a-----|d------------|b-----|c-----------|...  *   */ setRangeValue(start: number, end: number, value: T) {  if (!this.size) return  if (end >= this.size) end = this.size - 1  // 所有与当前传入区间范围有重叠部分，  // -1，+1 将接壤的毗邻 RangeValue 也纳入（如果存在的话），  // 毗邻的 RangeValue 要检查否要合并。  let prevSiblingEnd = start - 1  let nextSiblingStart = end + 1  let rangeValues = this.treeIntersecting(prevSiblingEnd, nextSiblingStart)  // 如果没有重叠的部分，则作为新的 RangeValue 插入，直接结束  // 如果有重叠的部分，就要处理合并、拆分  if (rangeValues.length) {   let firstRange = rangeValues[0]   let lastRange = rangeValues[rangeValues.length - 1]   // end 边界比传入的 start 小，说明是接壤毗邻的更小的 RangeValue   //   // 1. 如果毗邻的 RangeValue 的值跟当前带插入的值不一致，   // 则直接将毗邻的 RangeValue 从列表中移除，   // 不需要做任何特殊操作，正常的插入操作即可   //   // 2. 否则如果毗邻的 RangeValue 的值跟当前待插入的值一致，   // 则将两个 RangeValue 的 Range 合并（修改 start即可），   // 然后这个毗邻的 RangeValue 也自然变成重叠的，正常执行后续   // 的重叠处理逻辑即可（拆分）   if (firstRange.end < start) {    if (firstRange.value !== value) {     rangeValues.shift()    }    else {     start = firstRange.start    }   }   // 接壤毗邻的更大的 RangeValue，处理思路   // 跟上面处理毗邻的更小的 RangeValue 一样的   if (lastRange.start > end) {    if (lastRange.value !== value) {     rangeValues.pop()    }    else {     end = lastRange.end    }   }   // 结束毗邻 RangeValue 合并逻辑   // 开始处理相交的 RangeValue 流程   const length = rangeValues.length   let index = 0   while (index < length) {    const currentRangeValue = rangeValues[index]    const { value: currentValue, start: currentStart, end: currentEnd } = currentRangeValue    // 先移除掉该重叠的 RangeValue，然后：    this.valueTree.delete(currentRangeValue)    // Case 1. 如果是当前 RangeValue 完整包含在传入的范围内，    // 则不需要处理，因为整个范围都将被传入的值覆盖。    if (currentStart >= start && currentEnd <= end) {     index += 1     continue    }    // Case2. 部分相交，该 RangeValue 的大的一侧在传入的范围内，而小的一侧不在。    // 需要做切分操作，以重叠的位置作为切分点，比较小的一侧（不重叠的部分）重新插入，    // 比较大的的那一部分，会被传入的值覆盖掉    if (currentStart < start) {     // 如果值不一样，则以相交的位置作为切分点，非重叠部分重新插入，重叠部分用待插入的值覆盖。     if (currentValue !== value) {      this._insert(currentStart, start - 1, currentValue)     }     else {      start = currentStart     }    }    // Case3. 部分相交，该 RangeValue 的小的一侧在传入的范围内，而大的一侧不在。    // 同 Case 2 做切分操作，只是反向。    if (currentEnd > end) {     if (currentValue !== value) {      this._insert(end + 1, currentEnd, currentValue)     }     else {      end = currentEnd     }    }    index += 1   }  }  this._insert(start, end, value) } setValue(index: number, value: T) {  this.setRangeValue(index, index, value) } /**  * 筛选出与指定区间有重叠的 RangeValue，即：  *   *       1. 相互部分重叠  *   * o----------o       o---------o  *   >start------------------end<  *   *   *      2. 相互完全重叠关系  *   *      o----------------o  *      >start--------end<  *   *   *      3. 包含或被包含关系  *   * o--------------------------------------o  *  o-------------------------------o  *   o-------------------------------o  *   o-----o   o-----o   o----o  *   >start--------------------end<  *   */ treeIntersecting(start: number, end: number): RangeValue[] {  const startRange = new Range(start)  const endRange = new Range(end)  return this.valueTree.searchRange(startRange, endRange) } /**  * 返回指定范围内所有 RangeValue  * 范围内有无值的 Range 的话，则使用  * 携带默认值的 RangeValue 代替  * 从而确保返回的结果是线性的、每个区间都有值的，如:  *   * start>...<end 范围内有 A、B 两个 RangeValue，所有空洞都用 Default 补足  * +-----------|-----|-----------|-----|-----------+  * | Default | A | Default | B | Default |  * >start------|-----|-----------|-----|--------end<  *  */ intersecting(start: number, end: number): RangeValue[] {  const ranges = this.treeIntersecting(start, end)  if (!ranges.length) {   if (!this.size) return []   return [ new RangeValue(start, end, this.defaultValue) ]  }  let result = []  let range  let index = 0  let length = ranges.length  while (index < length) {   range = ranges[index].clone()   // 传入的 (start, end) 右侧与某个 RangeValue 重叠，   // 左侧没有命中，则左侧区域手动塞入一个携带默认   // 值的 RangeValue   if (range.start > start) {    result.push(new RangeValue(start, range.start - 1, this.defaultValue))   }   result.push(range)   // 将 start 的位置右移，   // 以便下个 range 的比较   start = range.end + 1   index += 1  }  // 如果最后一个 range，与传入的范围只有左侧重叠，  // 而右侧没有重叠的地方，则手动塞入一个携带默认值  // 的 RangeValue  if (range.end < end) {   result.push(new RangeValue(range.end + 1, end, this.defaultValue))  }  else if (range.end > end) {   // 否则如果最后一个 range 的范围已经超出需要的范围，则裁剪   range.end = end  }  return result } values() {  if (!this.size) return []  return this.intersecting(0, this.size - 1) } _insert(start: number, end: number, value: T) {  if (value !== this.defaultValue) {   const rangeValue = new RangeValue(start, end, value)   this.valueTree.insert(rangeValue)  } }}export function create<T>(size: number, value: T) { return new SparseRangeList(size, value)}

import { create as createSparseRangeList } from './SparseRangeList'// 创建一个默认预估高度为 20 的列表项存储对象const itemHeightStore = createSparseRangeList(wrappedItems.length, 20)// 设置第二项为 40pxitemHeightStore.setValue(1, 40)// 获取第二项的高度itemHeightStore.getValueAt(1) // 40// 获取列表项的 top 坐标const top = (index: number): number => { if (index === 0) return 0 // 0 ～ 上一项的高度累加 const rangeValues = itemHeightStore.intersecting(0, index - 1) const sumHeight = rangeValues.reduce((sum: number, rangeValue: any) => {  const span = rangeValue.end - rangeValue.start + 1  return sum + rangeValue.value * span }, 0) return sumHeight}top(1) // 20// 计算列表总高度：const listHeight = itemHeightStore .values() .reduce((acc: number, rangeValue: any) => {  const span = rangeValue.end - rangeValue.start + 1  const height = rangeValue.value * span  return acc + height }, 0)

// 内部方法，计算局部渲染数据切片的起止点private _calcSliceRange() { if (!this.dataView.length) {  return { sliceFrom: 0, sliceTo: 0 } } // 数据总量 const MAX = this.dataView.length // 视口上边界 const viewportTop = (this.$refs.viewport as any).scrollTop || 0 // 视口下边界 const viewportBottom = viewportTop + this.viewportHeight // 预估条目高度 const estimatedItemHeight = this.defaultItemHeight // 从估算值开始计算起始序号 let sliceFrom = Math.floor(viewportTop / estimatedItemHeight!) if (sliceFrom > MAX - 1) sliceFrom = MAX - 1 while (sliceFrom >= 0 && sliceFrom <= MAX - 1) {  const itemTop = this._top(sliceFrom)  // 条目顶部相对于 viewport 顶部的偏移  const itemOffset = itemTop - viewportTop  // 1. 该条目距离视口顶部有距离，说明上方还有条目元素需要显示，继续测试上一条  if (itemOffset > 0) {   // 二分法快速估算下一个尝试位置   const diff = itemOffset / estimatedItemHeight!   sliceFrom -= Math.ceil(diff / 2)   continue  }  // 2. 恰好显示该条目的顶部，则该条目为本次视口的首条元素  if (itemOffset === 0) break  // 以下都是 itemOffset < 0  const itemHeight = this._itemHeight(sliceFrom)  // 3. 该条目在顶部露出了一部分，则该条目为本次视口的首条元素  if (itemOffset < itemHeight) break  // 4. 该条目已被滚出去视口，继续测试下一条  // 二分法快速估算下一个尝试位置  const diff = -itemOffset / estimatedItemHeight!  sliceFrom += Math.ceil(diff / 2) } // 从估算值开始计算结束序号 let sliceTo = sliceFrom + 1 + Math.floor(this.viewportHeight / estimatedItemHeight!) if (sliceTo > MAX) sliceTo = MAX while (sliceTo > sliceFrom && sliceTo <= MAX) {  const itemTop = this._top(sliceTo)  const itemHeight = this._itemHeight(sliceTo)  const itemBottom = itemTop + itemHeight  // 条目底部相对于 viewport 底部的偏移  const itemOffset = itemBottom - viewportBottom  // 1. 该条目的底部距离视口底部有距离，说明下方还有条目元素需要显示，继续测试下一条  if (itemOffset < 0) {   // 二分法快速估算下一个尝试位置   const diff = -itemOffset / estimatedItemHeight!   sliceTo += Math.ceil(diff / 2)   continue  }  // 2. 恰好显示该条目的底部，则该条目为视口中最后一项  if (itemOffset === 0) break  // 3. 该条目在底部被裁剪了一部分，则该条目为本次视口的末项  if (itemOffset < itemHeight) break  // 该条目还未出场，继续测试上一条  // 二分法快速估算下一个尝试位置  const diff = itemOffset / estimatedItemHeight!  sliceTo -= Math.ceil(diff / 2) } // slice 的时候，不含 end，所以 + 1 sliceTo += 1 return { sliceFrom, sliceTo }}

// 刷新局部渲染数据切片范围private _updateSliceRange(forceUpdate?: boolean) { // 上下方额外多渲染的条目波动量 const COUNT = this._preRenderingCount() // 预渲染触发阈值 const THRESHOLD = this._preRenderingThreshold()   // 数据总量 const MAX = this.dataView.length // 计算出准确的切片区间 const range = this._calcSliceRange()   // 检查计算出来的切片范围，是否被当前已经渲染的切片返回包含了 // 如果是，无需更新切片，（如果 forceUpdate，则无论如何都需要重新切片） let fromThreshold = range.sliceFrom - THRESHOLD if (fromThreshold < 0) fromThreshold = 0 let toThreshold = range.sliceTo + THRESHOLD if (toThreshold > MAX) toThreshold = MAX // 无需强制刷新，且上下两端都没有触达阈值时，无需重新切片 if (!forceUpdate && ((this.sliceFrom <= fromThreshold) && (this.sliceTo >= toThreshold))) {  return } // 下面是更新切片的情况 // 在切片区间头部、尾部，追加预渲染的条目 let { sliceFrom, sliceTo } = range sliceFrom = sliceFrom > COUNT ? sliceFrom - COUNT : 0 sliceTo = sliceTo + COUNT > MAX ? MAX : sliceTo + COUNT this.sliceFrom = sliceFrom this.sliceTo = sliceTo if (forceUpdate) this._doSlice()}

import { Component, Vue, Prop, Watch } from 'vue-property-decorator'import { createSparseRangeList } from './SparseRangeList'// 列表项数据包裹，data 字段存放原始数据// 组件所有操作不应该改变 data 的内容，而是修改该包裹对象的属性class ItemWrapper { // 原始数据 data: any // 数据唯一 key key: any // 条目高度 // 1. 正数代表已经计算出来的高度 // 2. 0 代表未计算的高度，不显示 // 3. 负数代表需要隐藏的高度，绝对值为已经计算出来的高度，方便取消隐藏 height: number // 记录是否已经根据实际 DOM 计算过高度 realHeight: boolean // 条目在当前过滤视图中的序号 viewIndex: number constructor(data: any, key: any, height: number) {  this.data = data  // 数据的唯一id，是初始化数据时候的序号  // 每次传入的 data 改变，都会重新生成  this.key = key  // 条目的高度缓存  // 1. 用于重建高度存储时快速恢复  // 2. 用于快速通过数据取高度  this.height = height >> 0  this.realHeight = false  // 每次生成 dataView 都刷新  this.viewIndex = -1 }}@Component({ name: 'VList' })export default class VList extends Vue { [key: string]: any // 高度存储 不响应式 private itemHeightStore: any // 组件宽度，不设置则为容器的 100% @Prop({ type: Number }) private width?: number // 组件高度，不设置则为容器的 100% @Prop({ type: Number }) private height?: number // 传入高度值，固定条目高度 @Prop({ type: Number }) private fixedItemHeight?: number // 预估元素高度， // 在高度不确定的列表中，未计算出高度时使用， // 该值与元素平均高度越相近，则越高效（修正时估算次数越少） @Prop({ type: Number, default: 30 }) private estimatedItemHeight!: number // 数据列表 @Prop({ type: Array, default: () => ([]) }) private data!: any[] // 计算条目高度的方法 @Prop({  type: Function,  default(node: Node, wrappedData: ItemWrapper) {   return (node as HTMLElement).clientHeight  } }) private itemHeightMethod!: (node: Node, wrappedItem: ItemWrapper) => number // 数据过滤方法（可以用于外部实现搜索框过滤） @Prop({ type: Function }) private filterMethod?: (data: any) => boolean // 数据排序方法（可以用于外部实现数据自定义过滤） @Prop({ type: Function }) private sortMethod?: (a: any, b: any) => number // 包裹后的数据列表（必须 freeze，否则大列表性能撑不住） private wrappedData: ReadonlyArray<ItemWrapper> = Object.freeze(this._wrapData(this.data)) // 真实渲染上屏的数据列表切片 private dataSlice: ReadonlyArray<ItemWrapper> = [] // viewport 宽度 private viewportWidth = this.width || 0 // viewport 高度 private viewportHeight = this.height || 0 // 当前 viewport 中第一条数据的序号 private sliceFrom = 0 // 当前 viewport 中最后一条数据的序号 private sliceTo = 0 // 列表高度 private listHeight = 0 // 检查是否固定高度模式 private get isFixedHeight() {  return this.fixedItemHeight! >= 0 } // 获取默认条目高度 private get defaultItemHeight() {  return this.isFixedHeight ? this.fixedItemHeight! : this.estimatedItemHeight } // 当前筛选条件下的数据列表 // 依赖：wrappedData, filterMethod, sortMethod private get dataView() {  const { wrappedData, filterMethod, sortMethod } = this  let data = []  if (typeof filterMethod === 'function') {   const len = wrappedData.length   for (let index = 0; index < len; index += 1) {    const item = wrappedData[index]    if (filterMethod(item.data)) {     data.push(item)    }   }  } else {   data = wrappedData.map(i => i)  }  if (typeof sortMethod === 'function') {   data.sort((a, b) => {    return sortMethod(a, b)   })  }  // 重新记录数据在视图中的位置，用于隐藏部分条目时，可以精确计算高度、坐标  const size = data.length  for (let index = 0; index < size; index += 1) {   const wrappedItem = data[index]   wrappedItem.viewIndex = index  }  return Object.freeze(data) } // 原始列表数据变化，重新包裹数据 @Watch('data') private onDataChange(data: any[]) {  this.wrappedData = Object.freeze(this._wrapData(data)) } // 当前过滤、排序视图变化，重新布局 @Watch('dataView') private onDataViewChange(wrappedItems: ItemWrapper[]) {  // 重建高度存储  const estimatedItemHeight = this.defaultItemHeight  this.itemHeightStore = createSparseRangeList(wrappedItems.length, estimatedItemHeight)  // 从缓存中快速恢复已计算出高度的条目的高度  wrappedItems.forEach((wrappedItem, index) => {   // 小于零的需要隐藏，所以高度为 0   this.itemHeightStore.setValue(index,    wrappedItem.height > 0 ? wrappedItem.height : 0)  })  // 刷新列表高度  this.updateListHeight()  // 重置滚动位置  // TODO, 锚定元素  const { viewport } = this.$refs as any  if (viewport) viewport.scrollTop = 0  // 重新切片当前 viewport 需要的数据  this._updateSliceRange(true)  this.$emit('data-view-change', this.dataSlice.map((wrappedItem) => wrappedItem.data)) } private created() {  const estimatedItemHeight = this.defaultItemHeight  this.itemHeightStore = createSparseRangeList(this.dataView.length, estimatedItemHeight)  this.layoutObserver = new MutationObserver(this.redraw.bind(this))  this.childObserver = new MutationObserver((mutations: MutationRecord[]) => {   this._updateHeightWhenItemInserted(mutations)  })  this.$watch(((vm: any) => `${vm.sliceFrom},${vm.sliceTo}`) as any, this._doSlice) } private mounted() {  this.redraw()  this.layoutObserver.observe(this.$el, { attributes: true })  // 非固定高度场景，监听子元素插入，提取高度  if (!this.isFixedHeight) {   this.childObserver.observe(this.$refs.content, { childList: true })  } } private beforeDestory() {  this.layoutObserver.disconnect()  if (!this.isFixedHeight) {   this.childObserver.disconnect()  }  this.itemHeightStore = null } // DOM 结构比较简单，无需 template，直接使用渲染函数输出 VDOM private render(createElement: any) {  return createElement(   'div', // 组件容器，与外部布局   {    class: 'VList',    style: {     'box-sizing': 'border-box',     display: 'inline-block',     margin: '0',     padding: '0',     width: this.width ? this.width + 'px' : '100%',     height: this.height ? this.height + 'px' : '100%',    }   },   [    createElement(     'div', // 滚动区域的可见范围     {      ref: 'viewport',      class: 'VList_viewport',      style:       'box-sizing:border-box;position:relative;overflow:hidden;width:100%;height:100%;margin:0;padding:0;overflow:auto;overflow-scrolling:touch;',      on: { scroll: this._onScroll }     },     [      createElement(       'div', // 内容容器，内容真实高度由此容器体现       {        class: 'VList_scollable',        ref: 'content',        style: {         'box-sizing': 'border-box',         position: 'relative',         margin: '0',         padding: '0',         height: this.listHeight + 'px'        }       },       // 列表项       this.dataSlice.map((wrappedItem) => {        return createElement(         'div',         {          key: wrappedItem.key,          class: `VList_item VList_item-${wrappedItem.key % 2 === 0 ? 'even' : 'odd'}`,          attrs: {           'data-key': wrappedItem.key          },          style: {           'box-sizing': 'border-box',           'z-index': '1',           position: 'absolute',           right: '0',           bottom: 'auto',           left: '0',           margin: '0',           padding: '0',           cursor: 'default',           // 注：使用 transfrom 有黑屏 bug           // transform: `translate(0, ${top})`           // transform: `translate3d(0, ${top}, 0)`           top: this._top(wrappedItem.viewIndex) + 'px'          }         },         // 将原始数据，key 注入到 slot 里，         // 以便自定义条目内容使用         this.$scopedSlots.default!({          item: wrappedItem.data,          listKey: wrappedItem.key         })        )       })      )     ]    )   ]  ) } // 重绘界面，确保列表渲染正确 public redraw() {  const viewport = this.$refs.viewport as HTMLElement  const { clientWidth, clientHeight } = viewport  this.viewportWidth = clientWidth  this.viewportHeight = clientHeight  this.updateListHeight()  this._updateSliceRange(true) } // 刷新列表总高度 public updateListHeight() {  const { itemHeightStore } = this  const rangeValues = itemHeightStore.values()  if (!rangeValues.length) {   this.listHeight = 0   return  }  const listHeight = rangeValues.reduce((sum: number, rangeValue: any) => {   const span = rangeValue.end - rangeValue.start + 1   const height = rangeValue.value * span   return sum + height  }, 0)  this.listHeight = listHeight } // Dom 插入时候，计算高度，然后 // 批量刷新高度，避免频繁调整列表高度带来性能问题 public batchUpdateHeight(records: Array<{ wrappedItem: ItemWrapper, height: number }>) {  records.forEach(({ wrappedItem, height }) => {   this._updateHeight(wrappedItem, height, true)  })  this.updateListHeight()  this._updateSliceRange() } // 通过数据 key，设置对应条目的高度 public updateHeightByKey(key: any, height: number) {  const wrappedItem = this.wrappedData[key]  if (!wrappedItem) return  this._updateHeight(wrappedItem, height)  this.updateListHeight()  this._updateSliceRange() } // 通过数据 key，设置对应条目的显示状态 public showByKey(key: any) {  const wrappedItem = this.wrappedData[key]  if (!wrappedItem) return  if (wrappedItem.height <= 0) {   const height = -wrappedItem.height || this.defaultItemHeight   this._updateHeight(wrappedItem, height!)   this.updateListHeight()   this._updateSliceRange()   // 强制重绘   this._doSlice()  } } // 通过数据 key，设置对应条目的显示状态 public hideByKey(key: any) {  const wrappedItem = this.wrappedData[key]  if (!wrappedItem) return  if (wrappedItem.height > 0) {   const height = -wrappedItem.height   wrappedItem.height = height   this._updateHeight(wrappedItem, height)   this.updateListHeight()   // 强制重绘   this._updateSliceRange(true)  } } // 通过数据 key 列表，设置对应条目的显示状态 public showByKeys(keys: any[]) {  const wrappedItems = keys.map((key) => this.wrappedData[key])   .filter((wrappedItem) => wrappedItem && wrappedItem.height <= 0)  wrappedItems.forEach((wrappedItem) => {   const height = (-wrappedItem.height || this.defaultItemHeight)!   this._updateHeight(wrappedItem, height)  })  this.updateListHeight()  // 强制重绘  this._updateSliceRange(true) } // 通过数据 key 列表，设置对应条目的显示状态 public hideByKeys(keys: any[]) {  const wrappedItems = keys.map((key) => this.wrappedData[key])   .filter(wrappedItem => wrappedItem && wrappedItem.height > 0)  wrappedItems.forEach((wrappedItem) => {   // 设置为负数，表示隐藏   const height = -wrappedItem.height   wrappedItem.height = height   this._updateHeight(wrappedItem, height)  })  this.updateListHeight()  // 强制重绘  this._updateSliceRange(true) } // 内部方法，计算局部渲染数据切片的起止点 private _calcSliceRange() {  if (!this.dataView.length) {   return { sliceFrom: 0, sliceTo: 0 }  }  // 数据总量  const MAX = this.dataView.length  // 视口上边界  const viewportTop = (this.$refs.viewport as any).scrollTop || 0  // 视口下边界  const viewportBottom = viewportTop + this.viewportHeight  // 预估条目高度  const estimatedItemHeight = this.defaultItemHeight  // 从估算值开始计算起始序号  let sliceFrom = Math.floor(viewportTop / estimatedItemHeight!)  if (sliceFrom > MAX - 1) sliceFrom = MAX - 1  while (sliceFrom >= 0 && sliceFrom <= MAX - 1) {   const itemTop = this._top(sliceFrom)   // 条目顶部相对于 viewport 顶部的偏移   const itemOffset = itemTop - viewportTop   // 1. 该条目距离视口顶部有距离，说明上方还有条目元素需要显示，继续测试上一条   if (itemOffset > 0) {    // 二分法快速估算下一个尝试位置    const diff = itemOffset / estimatedItemHeight!    sliceFrom -= Math.ceil(diff / 2)    continue   }   // 2. 恰好显示该条目的顶部，则该条目为本次视口的首条元素   if (itemOffset === 0) break   // 以下都是 itemOffset < 0   const itemHeight = this._itemHeight(sliceFrom)   // 3. 该条目在顶部露出了一部分，则该条目为本次视口的首条元素   if (itemOffset < itemHeight) break   // 4. 该条目已被滚出去视口，继续测试下一条   // 二分法快速估算下一个尝试位置   const diff = -itemOffset / estimatedItemHeight!   sliceFrom += Math.ceil(diff / 2)  }  // 从估算值开始计算结束序号  let sliceTo = sliceFrom + 1 + Math.floor(this.viewportHeight / estimatedItemHeight!)  if (sliceTo > MAX) sliceTo = MAX  while (sliceTo > sliceFrom && sliceTo <= MAX) {   const itemTop = this._top(sliceTo)   const itemHeight = this._itemHeight(sliceTo)   const itemBottom = itemTop + itemHeight   // 条目底部相对于 viewport 底部的偏移   const itemOffset = itemBottom - viewportBottom   // 1. 该条目的底部距离视口底部有距离，说明下方还有条目元素需要显示，继续测试下一条   if (itemOffset < 0) {    // 二分法快速估算下一个尝试位置    const diff = -itemOffset / estimatedItemHeight!    sliceTo += Math.ceil(diff / 2)    continue   }   // 2. 恰好显示该条目的底部，则该条目为视口中最后一项   if (itemOffset === 0) break   // 3. 该条目在底部被裁剪了一部分，则该条目为本次视口的末项   if (itemOffset < itemHeight) break   // 该条目还未出场，继续测试上一条   // 二分法快速估算下一个尝试位置   const diff = itemOffset / estimatedItemHeight!   sliceTo -= Math.ceil(diff / 2)  }  // slice 的时候，不含 end，所以 + 1  sliceTo += 1  return { sliceFrom, sliceTo } } // 上下两端预先批量渲染的项目波动量 // 原理是，每次插入删除都是一个小批量动作， // 而不是每次只插入一条、销毁一条 // 计算出的局部渲染数据范围，跟上一次计算出来的结果，差距 // 在这个波动量范围内，则不重新切片渲染，用于 // 防止 IE 11 频繁插入内容导致性能压力 private _preRenderingCount() {  // 默认预渲染 2 屏  return Math.ceil(this.viewportHeight / this.defaultItemHeight!) * 2 } // 滚动到上下方剩下多少个条目时，加载下一批 // 缓解 Macbook & iOS 触摸滚动时的白屏 private _preRenderingThreshold() {  // 默认触达预渲染的一半数量时，加载下一批切片  return Math.floor(this._preRenderingCount() / 2) } // 刷新局部渲染数据切片范围 private _updateSliceRange(forceUpdate?: boolean) {  // 上下方额外多渲染的条目波动量  const COUNT = this._preRenderingCount()  // 预渲染触发阈值  const THRESHOLD = this._preRenderingThreshold()    // 数据总量  const MAX = this.dataView.length  // 计算出准确的切片区间  const range = this._calcSliceRange()    // 检查计算出来的切片范围，是否被当前已经渲染的切片返回包含了  // 如果是，无需更新切片，（如果 forceUpdate，则无论如何都需要重新切片）  let fromThreshold = range.sliceFrom - THRESHOLD  if (fromThreshold < 0) fromThreshold = 0  let toThreshold = range.sliceTo + THRESHOLD  if (toThreshold > MAX) toThreshold = MAX  // 无需强制刷新，且上下两端都没有触达阈值时，无需重新切片  if (!forceUpdate && ((this.sliceFrom <= fromThreshold) && (this.sliceTo >= toThreshold))) {   return  }  // 更新切片的情况  // 在切片区间头部、尾部，追加预渲染的条目  let { sliceFrom, sliceTo } = range  sliceFrom = sliceFrom > COUNT ? sliceFrom - COUNT : 0  sliceTo = sliceTo + COUNT > MAX ? MAX : sliceTo + COUNT  this.sliceFrom = sliceFrom  this.sliceTo = sliceTo  if (forceUpdate) this._doSlice() } // 当前需要渲染的数据切片 private _doSlice() {  const { dataView, sliceFrom, sliceTo } = this  const slice = dataView.slice(sliceFrom, sliceTo)   .filter((wrappedItem) => wrappedItem.height > 0)  this.dataSlice = Object.freeze(slice)  this.$emit('slice', slice.map((wrappedItem) => wrappedItem.data)) } // `index` 数据在 dataView 中的 index private _itemHeight(index: number): number {  return this.itemHeightStore.getValueAt(index) } // `index` 数据在 dataView 中的 index private _top(index: number): number {  if (index === 0) return 0  // 0 ～ 上一项的高度累加  const rangeValues = this.itemHeightStore.intersecting(0, index - 1)  const sumHeight = rangeValues.reduce((sum: number, rangeValue: any) => {   const span = rangeValue.end - rangeValue.start + 1   return sum + rangeValue.value * span  }, 0)  return sumHeight } // 包裹原始数据列表 private _wrapData(list: any[]): ItemWrapper[] {  return list.map((item, index) => new ItemWrapper(item, index, this.defaultItemHeight!)) } // 通过 DOM Node 获取对应的数据 private _getDataByNode(node: Node): ItemWrapper {  return this.wrappedData[(node as any).dataset.key] } // 刷新列表项高度 private _updateHeight(wrappedItem: ItemWrapper, height: number, isRealHeight?: boolean) {  height = height >> 0  // 更新结点高度缓存  wrappedItem.height = height  if (isRealHeight) {   wrappedItem.realHeight = true  }  // 如果 wrappedItem 为当前过滤下的项目，  // 则同时刷新高度存储 store  const index = this.dataView.indexOf(wrappedItem)  if (index !== -1) {   // 小于等于零表示折叠不显示，计算高度为零   // 负值存在 wrappedItem 中，用于反折叠时恢复   this.itemHeightStore.setValue(index, height > 0 ? height : 0)  } } // 节点插入时，检查是否首次插入，如果是，计算高度并更新对应的 ItemWrapper private _updateHeightWhenItemInserted(mutations: MutationRecord[]) {  const addedNodes: Node[] = mutations   .map((mutation: MutationRecord) => mutation.addedNodes)   .reduce((result: any, items: NodeList) => {    result.push(...items)    return result   }, [])  const batch: Array<{ wrappedItem: ItemWrapper, height: number }> = []  addedNodes.forEach((node: Node) => {   const wrappedItem = this._getDataByNode(node)   // 如果 wrappedItem 中已经存储了计算过的高度，   // 则直接返回，不访问 clientHeight   // 以避免性能开销（IE 11 中访问 clientHeight 性能非常差）   if (wrappedItem.realHeight) {    return   }   const height = this.itemHeightMethod(node, wrappedItem) >> 0   if (wrappedItem.height !== height) {    batch.push({ wrappedItem, height })   } else {    // 计算出来的高度跟默认值一致，    // 则无需更新，但是设置已经计算状态    // 以便下次可以直接使用缓存    wrappedItem.realHeight = true   }  })  if (batch.length) {   this.batchUpdateHeight(batch)  } } // 滚动事件处理器 private _onScroll() {  this._updateSliceRange() }}