前端场景算法深度解析

一、虚拟列表计算

为什么需要虚拟列表

当我们要渲染 10 万条数据时，直接创建 10 万个 DOM 节点会带来灾难性后果：

指标	1000 条	100,000 条
DOM 节点数	~1,000	~100,000
内存占用	~10MB	~800MB+
首次渲染耗时	~50ms	~5000ms+
滚动帧率	60fps	<10fps

浏览器的渲染流水线（Parse → Style → Layout → Paint → Composite）中，Layout 阶段的复杂度与 DOM 节点数近似线性相关。10 万个节点意味着每次重排都要计算 10 万个盒模型的几何信息。

虚拟列表的核心思想：只渲染可视区域内的少量 DOM 节点（通常 20~50 个），通过计算滚动偏移量来动态替换渲染内容，用户看起来像是在浏览完整列表。

核心原理

三大核心概念：

可视区域计算：根据容器高度和滚动偏移量，计算当前应该显示哪些数据项
Buffer 缓冲区：在可视区域上下各多渲染几条数据，避免快速滚动时出现白屏
动态高度处理：当每行高度不固定时，需要预估+缓存+二分查找的策略

ASCII 图解

                        ┌─ scrollTop (已滚动距离)
                        │
  ┌─────────────────┐   │   paddingTop = startIndex * itemHeight
  │   Item 0        │   │   (用 padding 撑起上方不可见区域)
  │   Item 1        │   │
  │   ...           │   ▼
  │   Item start-1  │ ──┘
  ├═════════════════╤═══════════════════════════════╗
  │ ░░ Item start  ░│ ◄── startIndex               ║
  │ ░░ Item start+1░│     (首个可见项)               ║
  │ ░░ ...         ░│                               ║  可视区域
  │ ░░ ...         ░│     visibleData               ║  (容器高度
  │ ░░ Item end    ░│ ◄── endIndex                  ║   viewportHeight)
  ├═════════════════╧═══════════════════════════════╝
  │   Item end+1    │
  │   ...           │   paddingBottom = (total - endIndex - 1) * itemHeight
  │   Item N-1      │   (用 padding 撑起下方不可见区域)
  └─────────────────┘

  totalHeight = total * itemHeight (整个列表的逻辑总高度)

关键公式（固定高度场景）：

startIndex = Math.floor(scrollTop / itemHeight)
endIndex   = startIndex + Math.ceil(viewportHeight / itemHeight) - 1
paddingTop    = startIndex * itemHeight
paddingBottom = (total - endIndex - 1) * itemHeight

完整实现：FixedHeightVirtualList

typescript

interface VirtualListOptions {
  container: HTMLElement;
  itemHeight: number;
  total: number;
  bufferSize?: number;
  renderItem: (index: number) => HTMLElement;
}

class FixedHeightVirtualList {
  private container: HTMLElement;
  private contentEl: HTMLElement;
  private itemHeight: number;
  private total: number;
  private bufferSize: number;
  private renderItem: (index: number) => HTMLElement;
  private viewportHeight: number;

  constructor(options: VirtualListOptions) {
    this.container = options.container;
    this.itemHeight = options.itemHeight;
    this.total = options.total;
    this.bufferSize = options.bufferSize ?? 5;
    this.renderItem = options.renderItem;

    this.container.style.overflow = 'auto';
    this.container.style.position = 'relative';
    this.viewportHeight = this.container.clientHeight;

    this.contentEl = document.createElement('div');
    this.container.appendChild(this.contentEl);

    this.container.addEventListener('scroll', () => this.onScroll());
    this.onScroll();
  }

  private onScroll(): void {
    const scrollTop = this.container.scrollTop;

    const rawStart = Math.floor(scrollTop / this.itemHeight);
    const rawEnd = rawStart + Math.ceil(this.viewportHeight / this.itemHeight);

    const startIndex = Math.max(0, rawStart - this.bufferSize);
    const endIndex = Math.min(this.total - 1, rawEnd + this.bufferSize);

    const paddingTop = startIndex * this.itemHeight;
    const paddingBottom = (this.total - endIndex - 1) * this.itemHeight;

    this.contentEl.style.paddingTop = `${paddingTop}px`;
    this.contentEl.style.paddingBottom = `${paddingBottom}px`;

    this.contentEl.innerHTML = '';

    for (let i = startIndex; i <= endIndex; i++) {
      const el = this.renderItem(i);
      el.style.height = `${this.itemHeight}px`;
      el.style.boxSizing = 'border-box';
      this.contentEl.appendChild(el);
    }
  }

  updateTotal(newTotal: number): void {
    this.total = newTotal;
    this.onScroll();
  }

  destroy(): void {
    this.container.removeEventListener('scroll', () => this.onScroll());
  }
}

动态高度虚拟列表的思路

固定高度场景用除法就能算出 startIndex，但当每行高度不同时，需要三步策略：

第一步：预估高度

初始化时给每行一个预估高度 estimatedHeight（如 50px）
positions = [
  { index: 0, top: 0,   bottom: 50,  height: 50 },
  { index: 1, top: 50,  bottom: 100, height: 50 },
  { index: 2, top: 100, bottom: 150, height: 50 },
  ...
]

第二步：实际高度缓存

渲染后通过 ResizeObserver 或 getBoundingClientRect() 获取真实高度
positions[i].height = realHeight
positions[i].bottom = positions[i].top + realHeight
// 后续所有项的 top/bottom 都需要更新

第三步：二分查找定位 startIndex

给定 scrollTop，在 positions 数组中二分查找
找到第一个 bottom > scrollTop 的项，即为 startIndex

typescript

function findStartIndex(positions: Array<{ bottom: number }>, scrollTop: number): number {
  let low = 0;
  let high = positions.length - 1;
  let result = 0;

  while (low <= high) {
    const mid = (low + high) >>> 1;
    if (positions[mid].bottom > scrollTop) {
      result = mid;
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }

  return result;
}

复杂度分析

操作	固定高度	动态高度
计算 startIndex	O(1) 除法	O(log n) 二分
渲染	O(k)，k = 可见条数	O(k)
高度更新	无需	O(n) 最坏情况
空间	O(k) DOM 节点	O(n) 位置缓存 + O(k) DOM

二、DOM Diff 算法核心思路

为什么需要 Diff

直接操作真实 DOM 的代价极高：

JS 对象属性访问:   ~0.001ms
DOM 属性访问:      ~0.01ms   (10x)
DOM 节点创建:      ~0.1ms    (100x)
触发 Layout/Repaint: ~1ms+   (1000x+)

虚拟 DOM 的策略是：用 JS 对象（VNode）描述 UI 结构，当数据变化时，生成新 VNode 树，通过 Diff 算法比较新旧两棵树，计算出最小操作集，再批量应用到真实 DOM 上。

完全对比两棵树的复杂度是 O(n³)，框架通过三个假设将其优化为 O(n)：

同层比较：不跨层级移动节点
类型判断：不同类型的节点直接替换整棵子树
key 标识：同层的同类型节点通过 key 区分

        旧树             新树
         A                A
        / \              / \
       B   C            B   D     ← 只比较同层：C→D 是替换
      / \              / \
     D   E            D   E

  ❌ 不会尝试把旧树的 D 移动到新树的 A→D 位置
  ✅ 只做同层对比: A↔A, B↔B, C↔D, D↔D, E↔E

简化版 Diff 实现

四种情况：

情况1: 新增节点    oldChildren: [A, B]     newChildren: [A, B, C]
情况2: 删除节点    oldChildren: [A, B, C]  newChildren: [A, B]
情况3: 更新节点    oldChildren: [A, B]     newChildren: [A, B'] (B 属性变化)
情况4: 移动节点    oldChildren: [A, B, C]  newChildren: [C, A, B]

React Diff vs Vue Diff 策略对比

React Diff（单链表，从左到右）:
  旧: A B C D E
  新: A C E B D

  Step 1: A↔A 匹配，lastIndex=0
  Step 2: C 在旧中 index=2 > lastIndex=0, 不动, lastIndex=2
  Step 3: E 在旧中 index=4 > lastIndex=2, 不动, lastIndex=4
  Step 4: B 在旧中 index=1 < lastIndex=4, 移动B
  Step 5: D 在旧中 index=3 < lastIndex=4, 移动D
  结果: 移动了 2 个节点

Vue Diff（双端对比）:
  旧: A B C D E
  新: A C E B D

  头头比较: A↔A ✓
  尾尾比较: E↔D ✗
  头尾比较: B↔D ✗
  尾头比较: E↔C ✗
  → 在旧列表中查找 C，找到后移动
  ...
  Vue 使用最长递增子序列(LIS)来最小化移动操作

核心区别：

React 维护 lastIndex，从左到右遍历新列表，右移操作可能产生冗余移动
Vue3 使用双端对比 + 最长递增子序列（LIS），移动次数更少

完整简化版 Diff 代码

typescript

interface VNode {
  tag: string;
  key?: string;
  props: Record<string, any>;
  children: VNode[] | string;
}

interface Patch {
  type: 'CREATE' | 'REMOVE' | 'REPLACE' | 'UPDATE_PROPS' | 'MOVE';
  node?: VNode;
  from?: number;
  to?: number;
  props?: Record<string, any>;
}

function diff(oldChildren: VNode[], newChildren: VNode[]): Patch[] {
  const patches: Patch[] = [];
  const oldKeyMap = new Map<string, number>();

  oldChildren.forEach((child, i) => {
    const key = child.key ?? String(i);
    oldKeyMap.set(key, i);
  });

  const usedOldIndices = new Set<number>();
  let lastIndex = 0;

  for (let i = 0; i < newChildren.length; i++) {
    const newChild = newChildren[i];
    const key = newChild.key ?? String(i);
    const oldIndex = oldKeyMap.get(key);

    if (oldIndex === undefined) {
      patches.push({ type: 'CREATE', node: newChild, to: i });
    } else {
      usedOldIndices.add(oldIndex);
      const oldChild = oldChildren[oldIndex];

      if (oldChild.tag !== newChild.tag) {
        patches.push({ type: 'REPLACE', node: newChild, to: i });
      } else {
        const propPatches = diffProps(oldChild.props, newChild.props);
        if (propPatches) {
          patches.push({ type: 'UPDATE_PROPS', props: propPatches, to: i });
        }

        if (oldIndex < lastIndex) {
          patches.push({ type: 'MOVE', from: oldIndex, to: i });
        } else {
          lastIndex = oldIndex;
        }
      }
    }
  }

  for (let i = oldChildren.length - 1; i >= 0; i--) {
    if (!usedOldIndices.has(i)) {
      patches.push({ type: 'REMOVE', from: i });
    }
  }

  return patches;
}

function diffProps(
  oldProps: Record<string, any>,
  newProps: Record<string, any>
): Record<string, any> | null {
  const patches: Record<string, any> = {};
  let hasChanges = false;

  for (const key in newProps) {
    if (newProps[key] !== oldProps[key]) {
      patches[key] = newProps[key];
      hasChanges = true;
    }
  }

  for (const key in oldProps) {
    if (!(key in newProps)) {
      patches[key] = undefined;
      hasChanges = true;
    }
  }

  return hasChanges ? patches : null;
}

复杂度分析

算法	时间复杂度	空间复杂度	移动策略
朴素树 Diff	O(n³)	O(n)	最优编辑距离
React Diff	O(n)	O(n)	lastIndex 右移
Vue3 Diff	O(n) ~ O(n log n)	O(n)	双端 + LIS
简化版 Diff	O(n)	O(n)	lastIndex 右移

三、LRU 缓存

原理

LRU（Least Recently Used，最近最少使用）是一种缓存淘汰策略：当缓存满时，优先淘汰最久没有被访问的数据。

核心要求：get 和 put 操作均为 O(1) 时间复杂度。

ASCII 图解操作过程

容量 capacity = 3

操作                   缓存状态 (左=最近, 右=最久)     返回
─────────────────────────────────────────────────────────
put(1, "A")           [1:A]                           -
put(2, "B")           [2:B, 1:A]                      -
put(3, "C")           [3:C, 2:B, 1:A]                 -
get(1)                [1:A, 3:C, 2:B]                 "A"  ← 1被访问,移到最前
put(4, "D")           [4:D, 1:A, 3:C]                 -    ← 满了,淘汰最久的2:B
get(2)                [4:D, 1:A, 3:C]                 -1   ← 2已被淘汰
put(3, "C'")          [3:C', 4:D, 1:A]                -    ← 更新3,移到最前

HashMap + 双向链表结构:

  HashMap
  ┌────────┐
  │ key: 3 │───▶ ┌───────────────────────────────────────────┐
  │ key: 4 │───┐ │  head ◄──► [3:C'] ◄──► [4:D] ◄──► [1:A] ◄──► tail  │
  │ key: 1 │─┐ │ │             最新                    最旧          │
  └────────┘ │ │ └───────────────────────────────────────────┘
             │ └──────────────────┘
             └────────────────────────────────────┘

  get/put 时：
  1. HashMap O(1) 定位到节点
  2. 从链表中摘出节点 O(1)
  3. 插入到链表头部 O(1)
  淘汰时：删除链表尾部节点 O(1)

实现一：用 Map 的有序性（最简洁版）

ES6 的 Map 按插入顺序维护键的迭代顺序，利用这一特性可以极其简洁地实现 LRU：

typescript

class LRUCacheMap<K, V> {
  private capacity: number;
  private cache: Map<K, V>;

  constructor(capacity: number) {
    this.capacity = capacity;
    this.cache = new Map();
  }

  get(key: K): V | -1 {
    if (!this.cache.has(key)) return -1;
    const value = this.cache.get(key)!;
    this.cache.delete(key);
    this.cache.set(key, value);
    return value;
  }

  put(key: K, value: V): void {
    if (this.cache.has(key)) {
      this.cache.delete(key);
    }
    this.cache.set(key, value);
    if (this.cache.size > this.capacity) {
      const oldestKey = this.cache.keys().next().value!;
      this.cache.delete(oldestKey);
    }
  }
}

实现二：HashMap + 双向链表（经典版 LeetCode 146）

typescript

class DLinkedNode {
  key: number;
  value: number;
  prev: DLinkedNode | null = null;
  next: DLinkedNode | null = null;

  constructor(key: number = 0, value: number = 0) {
    this.key = key;
    this.value = value;
  }
}

class LRUCache {
  private capacity: number;
  private size: number;
  private cache: Map<number, DLinkedNode>;
  private head: DLinkedNode;
  private tail: DLinkedNode;

  constructor(capacity: number) {
    this.capacity = capacity;
    this.size = 0;
    this.cache = new Map();
    this.head = new DLinkedNode();
    this.tail = new DLinkedNode();
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  get(key: number): number {
    const node = this.cache.get(key);
    if (!node) return -1;
    this.moveToHead(node);
    return node.value;
  }

  put(key: number, value: number): void {
    const node = this.cache.get(key);
    if (node) {
      node.value = value;
      this.moveToHead(node);
      return;
    }

    const newNode = new DLinkedNode(key, value);
    this.cache.set(key, newNode);
    this.addToHead(newNode);
    this.size++;

    if (this.size > this.capacity) {
      const removed = this.removeTail();
      this.cache.delete(removed.key);
      this.size--;
    }
  }

  private addToHead(node: DLinkedNode): void {
    node.prev = this.head;
    node.next = this.head.next;
    this.head.next!.prev = node;
    this.head.next = node;
  }

  private removeNode(node: DLinkedNode): void {
    node.prev!.next = node.next;
    node.next!.prev = node.prev;
  }

  private moveToHead(node: DLinkedNode): void {
    this.removeNode(node);
    this.addToHead(node);
  }

  private removeTail(): DLinkedNode {
    const node = this.tail.prev!;
    this.removeNode(node);
    return node;
  }
}

复杂度分析

实现方式	get	put	空间	适用场景
Map 有序性	O(1)	O(1)	O(n)	快速实现、面试简洁版
HashMap + 双向链表	O(1)	O(1)	O(n)	生产环境、经典面试题
数组模拟	O(n)	O(n)	O(n)	不推荐

四、大文件切片上传

为什么需要切片

大文件直接上传面临的问题：

问题1: 超时       200MB 文件在 2Mbps 上传带宽下需要 ~800秒
问题2: 失败重传    上传到 99% 断网 → 从头开始
问题3: 内存溢出    一次性读取 2GB 文件到内存
问题4: 无进度感知   用户看不到上传进度

完整流程

┌──────────┐    ┌────────────┐    ┌─────────────┐    ┌──────────────┐    ┌──────────┐
│ 文件切片  │──▶│ 计算hash   │──▶│ 检查已上传   │──▶│  并发上传     │──▶│ 合并请求  │
│ File.slice│    │ SparkMD5   │    │ (断点续传)   │    │ (并发池控制)  │    │ /merge   │
└──────────┘    └────────────┘    └─────────────┘    └──────────────┘    └──────────┘
      │                │                 │                   │                 │
      ▼                ▼                 ▼                   ▼                 ▼
  按固定大小        Web Worker       服务端返回已          上传未完成          所有切片
  切割为多个        中计算避免       上传的切片            的切片              上传完成后
  Blob 切片        阻塞主线程       hash 列表                                发送合并

SparkMD5 计算文件哈希（Web Worker）

typescript

function createHashWorker(): Worker {
  const blob = new Blob([
    `
    self.importScripts('https://cdn.jsdelivr.net/npm/spark-md5@3.0.2/spark-md5.min.js');
    self.onmessage = function(e) {
      const { chunks } = e.data;
      const spark = new self.SparkMD5.ArrayBuffer();
      let index = 0;
      function loadNext() {
        const reader = new FileReader();
        reader.onload = function(event) {
          spark.append(event.target.result);
          index++;
          if (index < chunks.length) {
            loadNext();
          } else {
            self.postMessage({ hash: spark.end() });
          }
        };
        reader.readAsArrayBuffer(chunks[index]);
      }
      loadNext();
    };
    `
  ], { type: 'application/javascript' });

  return new Worker(URL.createObjectURL(blob));
}

function calculateHash(chunks: Blob[]): Promise<string> {
  return new Promise((resolve) => {
    const worker = createHashWorker();
    worker.onmessage = (e) => {
      resolve(e.data.hash);
      worker.terminate();
    };
    worker.postMessage({ chunks });
  });
}

并发控制上传

typescript

async function concurrentUpload(
  tasks: Array<() => Promise<any>>,
  maxConcurrency: number
): Promise<any[]> {
  const results: any[] = new Array(tasks.length);
  let index = 0;

  async function run(): Promise<void> {
    while (index < tasks.length) {
      const currentIndex = index++;
      results[currentIndex] = await tasks[currentIndex]();
    }
  }

  const workers = Array.from({ length: Math.min(maxConcurrency, tasks.length) }, () => run());
  await Promise.all(workers);
  return results;
}

完整实现：大文件切片上传

typescript

interface UploadOptions {
  file: File;
  chunkSize?: number;
  maxConcurrency?: number;
  uploadUrl: string;
  mergeUrl: string;
  checkUrl: string;
  onProgress?: (progress: number) => void;
}

interface ChunkInfo {
  index: number;
  chunk: Blob;
  hash: string;
  fileName: string;
}

async function uploadLargeFile(options: UploadOptions): Promise<void> {
  const {
    file,
    chunkSize = 5 * 1024 * 1024,
    maxConcurrency = 4,
    uploadUrl,
    mergeUrl,
    checkUrl,
    onProgress,
  } = options;

  const chunks = sliceFile(file, chunkSize);
  const fileHash = await calculateHash(chunks);
  const uploadedChunks = await checkUploaded(checkUrl, fileHash);

  let uploadedCount = uploadedChunks.length;
  const totalChunks = chunks.length;

  const tasks = chunks
    .map((chunk, index): [ChunkInfo, number] => [
      { index, chunk, hash: fileHash, fileName: file.name },
      index,
    ])
    .filter(([, index]) => !uploadedChunks.includes(index))
    .map(
      ([chunkInfo]) =>
        () =>
          uploadChunk(uploadUrl, chunkInfo).then(() => {
            uploadedCount++;
            onProgress?.(Math.round((uploadedCount / totalChunks) * 100));
          })
    );

  await concurrentUpload(tasks, maxConcurrency);
  await mergeChunks(mergeUrl, fileHash, file.name, totalChunks);
}

function sliceFile(file: File, chunkSize: number): Blob[] {
  const chunks: Blob[] = [];
  let cur = 0;
  while (cur < file.size) {
    chunks.push(file.slice(cur, cur + chunkSize));
    cur += chunkSize;
  }
  return chunks;
}

async function checkUploaded(url: string, fileHash: string): Promise<number[]> {
  const res = await fetch(`${url}?hash=${fileHash}`);
  const data = await res.json();
  return data.uploadedChunks ?? [];
}

async function uploadChunk(url: string, chunkInfo: ChunkInfo): Promise<void> {
  const formData = new FormData();
  formData.append('chunk', chunkInfo.chunk);
  formData.append('index', String(chunkInfo.index));
  formData.append('hash', chunkInfo.hash);
  formData.append('fileName', chunkInfo.fileName);
  await fetch(url, { method: 'POST', body: formData });
}

async function mergeChunks(
  url: string,
  hash: string,
  fileName: string,
  totalChunks: number
): Promise<void> {
  await fetch(url, {
    method: 'POST',
    headers: { 'Content-Type': 'application/json' },
    body: JSON.stringify({ hash, fileName, totalChunks }),
  });
}

复杂度分析

操作	时间复杂度	说明
文件切片	O(1) per chunk	File.slice 是零拷贝操作
计算 hash	O(n)	n = 文件大小，线性读取
检查已上传	O(1)	单次网络请求
并发上传	O(n/m)	n = 切片数，m = 并发数
合并请求	O(1)	单次网络请求

五、List ↔ Tree 互转

扁平列表转树

典型数据结构：

扁平列表:
[
  { id: 1, name: "根节点",  pid: null },
  { id: 2, name: "节点A",   pid: 1    },
  { id: 3, name: "节点B",   pid: 1    },
  { id: 4, name: "节点A-1", pid: 2    },
  { id: 5, name: "节点A-2", pid: 2    },
  { id: 6, name: "节点B-1", pid: 3    },
]

目标树:
{
  id: 1, name: "根节点", children: [
    { id: 2, name: "节点A", children: [
      { id: 4, name: "节点A-1", children: [] },
      { id: 5, name: "节点A-2", children: [] },
    ]},
    { id: 3, name: "节点B", children: [
      { id: 6, name: "节点B-1", children: [] },
    ]},
  ]
}

方法一：递归（O(n²)）

typescript

interface ListItem {
  id: number;
  name: string;
  pid: number | null;
}

interface TreeNode extends ListItem {
  children: TreeNode[];
}

function listToTreeRecursive(list: ListItem[], pid: number | null = null): TreeNode[] {
  return list
    .filter((item) => item.pid === pid)
    .map((item) => ({
      ...item,
      children: listToTreeRecursive(list, item.id),
    }));
}

每层递归都要遍历整个列表来过滤子节点，总时间 O(n²)。

方法二：Map 映射（O(n)）

typescript

function listToTree(list: ListItem[]): TreeNode[] {
  const map = new Map<number, TreeNode>();
  const roots: TreeNode[] = [];

  for (const item of list) {
    map.set(item.id, { ...item, children: [] });
  }

  for (const item of list) {
    const node = map.get(item.id)!;
    if (item.pid === null) {
      roots.push(node);
    } else {
      const parent = map.get(item.pid);
      parent?.children.push(node);
    }
  }

  return roots;
}

两次遍历即可完成，时间 O(n)，空间 O(n)。

还可以合并为一次遍历：

typescript

function listToTreeOnePass(list: ListItem[]): TreeNode[] {
  const map = new Map<number, TreeNode>();
  const roots: TreeNode[] = [];

  for (const item of list) {
    const node: TreeNode = map.get(item.id) ?? { ...item, children: [] };
    node.id = item.id;
    node.name = item.name;
    node.pid = item.pid;
    map.set(item.id, node);

    if (item.pid === null) {
      roots.push(node);
    } else {
      if (!map.has(item.pid)) {
        map.set(item.pid, { id: item.pid, name: '', pid: null, children: [] });
      }
      map.get(item.pid)!.children.push(node);
    }
  }

  return roots;
}

树转扁平列表

DFS（深度优先）

typescript

function treeToListDFS(tree: TreeNode[]): ListItem[] {
  const result: ListItem[] = [];

  function dfs(nodes: TreeNode[]): void {
    for (const node of nodes) {
      const { children, ...item } = node;
      result.push(item);
      dfs(children);
    }
  }

  dfs(tree);
  return result;
}

BFS（广度优先）

typescript

function treeToListBFS(tree: TreeNode[]): ListItem[] {
  const result: ListItem[] = [];
  const queue: TreeNode[] = [...tree];

  while (queue.length > 0) {
    const node = queue.shift()!;
    const { children, ...item } = node;
    result.push(item);
    queue.push(...children);
  }

  return result;
}

复杂度对比

方法	时间复杂度	空间复杂度	说明
递归转树	O(n²)	O(n) 递归栈	每层都遍历完整列表
Map 转树（两次遍历）	O(n)	O(n)	推荐，最清晰
Map 转树（一次遍历）	O(n)	O(n)	适合数据乱序场景
DFS 转列表	O(n)	O(h) 递归栈	h = 树高
BFS 转列表	O(n)	O(w) 队列	w = 最大宽度

六、并发请求控制

问题描述

实现 concurrentRequest(urls, maxConcurrency)：给定一组 URL 和最大并发数，控制同时最多只有 maxConcurrency 个请求在进行，所有请求完成后返回结果数组（顺序与输入一致）。

原理

maxConcurrency = 3, urls = [u0, u1, u2, u3, u4, u5]

时间线:
  t0: 启动 u0, u1, u2           (并发池满: 3/3)
  t1: u1 完成 → 启动 u3          (并发池: u0, u2, u3)
  t2: u0 完成 → 启动 u4          (并发池: u2, u3, u4)
  t3: u2 完成 → 启动 u5          (并发池: u3, u4, u5)
  t4: u3 完成                    (并发池: u4, u5)
  t5: u4, u5 完成                (全部完成)

                    ┌──────┐
  u0: ████████████████      │
  u1: ██████████│           │
  u2: ████████████████████  │
  u3:           ████████████│
  u4:                ████████████
  u5:                       ████████████
                    ▲
                    │
              max=3 条并行线

完整实现

typescript

type RequestFn<T> = () => Promise<T>;

async function concurrentRequest<T>(
  requestFns: RequestFn<T>[],
  maxConcurrency: number
): Promise<T[]> {
  const results: T[] = new Array(requestFns.length);
  let index = 0;

  async function run(): Promise<void> {
    while (index < requestFns.length) {
      const currentIndex = index++;
      try {
        results[currentIndex] = await requestFns[currentIndex]();
      } catch (e) {
        results[currentIndex] = e as T;
      }
    }
  }

  const poolSize = Math.min(maxConcurrency, requestFns.length);
  const workers = Array.from({ length: poolSize }, () => run());
  await Promise.all(workers);
  return results;
}

也可以使用 Promise.race 实现另一种风格：

typescript

async function concurrentRequestWithRace<T>(
  requestFns: RequestFn<T>[],
  maxConcurrency: number
): Promise<T[]> {
  const results: T[] = new Array(requestFns.length);
  const executing: Set<Promise<void>> = new Set();
  let index = 0;

  for (const fn of requestFns) {
    const currentIndex = index++;
    const p = fn()
      .then((res) => {
        results[currentIndex] = res;
      })
      .catch((err) => {
        results[currentIndex] = err;
      })
      .finally(() => {
        executing.delete(p);
      });

    executing.add(p);

    if (executing.size >= maxConcurrency) {
      await Promise.race(executing);
    }
  }

  await Promise.all(executing);
  return results;
}

复杂度分析

实现方式	时间复杂度	空间复杂度	特点
Worker 池模式	O(n)	O(m)	m = 并发数，代码简洁
Promise.race 模式	O(n)	O(m)	更精确的并发控制

两种实现总执行时间取决于最慢的那批请求，实际时间约为 总请求时间 / 并发数。

七、面试题精选（5 道，含详细解答）

面试题 1：实现一个支持过期时间的 LRU 缓存

题目：在 LRU 缓存的基础上，为每个 key 支持设置过期时间（TTL），过期的 key 在访问时自动删除。

解答：

typescript

class LRUCacheWithTTL<K, V> {
  private capacity: number;
  private cache: Map<K, { value: V; expireAt: number }>;

  constructor(capacity: number) {
    this.capacity = capacity;
    this.cache = new Map();
  }

  get(key: K): V | -1 {
    const entry = this.cache.get(key);
    if (!entry) return -1;

    if (Date.now() > entry.expireAt) {
      this.cache.delete(key);
      return -1;
    }

    this.cache.delete(key);
    this.cache.set(key, entry);
    return entry.value;
  }

  put(key: K, value: V, ttl: number = Infinity): void {
    this.cache.delete(key);
    this.cache.set(key, { value, expireAt: Date.now() + ttl });

    if (this.cache.size > this.capacity) {
      const oldestKey = this.cache.keys().next().value!;
      this.cache.delete(oldestKey);
    }
  }
}

要点：

利用 Map 的有序性实现 LRU
每个条目额外存储 expireAt 时间戳
get 时检查是否过期，过期则删除并返回 -1
惰性删除策略，不需要定时器扫描

面试题 2：虚拟列表中，如何处理列表项包含图片等异步加载资源导致的高度变化？

题目：虚拟列表的列表项中包含图片，图片加载完成后高度会发生变化，如何确保滚动位置不发生跳变？

解答：

typescript

interface PositionEntry {
  index: number;
  top: number;
  bottom: number;
  height: number;
}

class DynamicVirtualList {
  private positions: PositionEntry[];
  private estimatedHeight: number;
  private observer: ResizeObserver;

  constructor(total: number, estimatedHeight: number = 80) {
    this.estimatedHeight = estimatedHeight;
    this.positions = Array.from({ length: total }, (_, i) => ({
      index: i,
      top: i * estimatedHeight,
      bottom: (i + 1) * estimatedHeight,
      height: estimatedHeight,
    }));

    this.observer = new ResizeObserver((entries) => {
      for (const entry of entries) {
        const el = entry.target as HTMLElement;
        const index = Number(el.dataset.index);
        const newHeight = entry.contentRect.height;
        this.updateHeight(index, newHeight);
      }
    });
  }

  private updateHeight(index: number, newHeight: number): void {
    const oldHeight = this.positions[index].height;
    const diff = newHeight - oldHeight;
    if (Math.abs(diff) < 1) return;

    this.positions[index].height = newHeight;
    this.positions[index].bottom += diff;

    for (let i = index + 1; i < this.positions.length; i++) {
      this.positions[i].top = this.positions[i - 1].bottom;
      this.positions[i].bottom = this.positions[i].top + this.positions[i].height;
    }
  }

  findStartIndex(scrollTop: number): number {
    let low = 0;
    let high = this.positions.length - 1;
    let result = 0;

    while (low <= high) {
      const mid = (low + high) >>> 1;
      if (this.positions[mid].bottom > scrollTop) {
        result = mid;
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }

    return result;
  }

  observeElement(el: HTMLElement): void {
    this.observer.observe(el);
  }

  unobserveElement(el: HTMLElement): void {
    this.observer.unobserve(el);
  }

  getTotalHeight(): number {
    return this.positions[this.positions.length - 1]?.bottom ?? 0;
  }

  getItemOffset(index: number): number {
    return this.positions[index]?.top ?? 0;
  }
}

要点：

使用 ResizeObserver 监听每个已渲染列表项的尺寸变化
高度变化时更新 positions 数组中对应项及其后续所有项的 top/bottom
通过二分查找在 O(log n) 时间内定位 startIndex
优化点：可以用「前缀和 + 树状数组」将后续项的更新从 O(n) 优化到 O(log n)

面试题 3：实现一个带重试机制的并发请求控制器

题目：在并发请求控制的基础上，支持失败自动重试（最多重试 maxRetry 次），且重试不占用额外的并发位。

解答：

typescript

interface RetryRequestOptions<T> {
  requestFns: Array<() => Promise<T>>;
  maxConcurrency: number;
  maxRetry?: number;
}

async function concurrentRequestWithRetry<T>(
  options: RetryRequestOptions<T>
): Promise<Array<{ success: boolean; data?: T; error?: Error }>> {
  const { requestFns, maxConcurrency, maxRetry = 3 } = options;
  const results: Array<{ success: boolean; data?: T; error?: Error }> = new Array(
    requestFns.length
  );
  let index = 0;

  async function executeWithRetry(fn: () => Promise<T>, retries: number): Promise<T> {
    try {
      return await fn();
    } catch (err) {
      if (retries > 0) {
        return executeWithRetry(fn, retries - 1);
      }
      throw err;
    }
  }

  async function run(): Promise<void> {
    while (index < requestFns.length) {
      const currentIndex = index++;
      try {
        const data = await executeWithRetry(requestFns[currentIndex], maxRetry);
        results[currentIndex] = { success: true, data };
      } catch (err) {
        results[currentIndex] = { success: false, error: err as Error };
      }
    }
  }

  const poolSize = Math.min(maxConcurrency, requestFns.length);
  await Promise.all(Array.from({ length: poolSize }, () => run()));
  return results;
}

要点：

重试逻辑封装在 executeWithRetry 中，递归减少 retries 计数
重试在当前 worker 内进行，不释放并发位给其他请求
结果统一包装为 { success, data?, error? } 格式
所有重试耗尽后才标记为失败

面试题 4：实现一个 DOM Diff 并生成最小操作序列，应用到真实 DOM

题目：基于简化版 Diff 算法，将计算出的 patches 应用到真实 DOM 上。

解答：

typescript

interface SimplePatch {
  type: 'INSERT' | 'REMOVE' | 'MOVE' | 'UPDATE';
  index: number;
  node?: HTMLElement;
  props?: Record<string, string>;
}

function applyPatches(parent: HTMLElement, patches: SimplePatch[]): void {
  const removes: SimplePatch[] = [];
  const moves: SimplePatch[] = [];
  const inserts: SimplePatch[] = [];
  const updates: SimplePatch[] = [];

  for (const patch of patches) {
    switch (patch.type) {
      case 'REMOVE':
        removes.push(patch);
        break;
      case 'MOVE':
        moves.push(patch);
        break;
      case 'INSERT':
        inserts.push(patch);
        break;
      case 'UPDATE':
        updates.push(patch);
        break;
    }
  }

  removes
    .sort((a, b) => b.index - a.index)
    .forEach((patch) => {
      const child = parent.children[patch.index];
      if (child) parent.removeChild(child);
    });

  moves.forEach((patch) => {
    const child = parent.children[patch.index];
    if (child && patch.node) {
      parent.insertBefore(patch.node, parent.children[patch.index] || null);
    }
  });

  inserts.forEach((patch) => {
    if (patch.node) {
      const ref = parent.children[patch.index] || null;
      parent.insertBefore(patch.node, ref);
    }
  });

  updates.forEach((patch) => {
    const child = parent.children[patch.index] as HTMLElement;
    if (child && patch.props) {
      for (const [key, value] of Object.entries(patch.props)) {
        if (value === undefined) {
          child.removeAttribute(key);
        } else {
          child.setAttribute(key, value);
        }
      }
    }
  });
}

要点：

操作顺序很关键：先删除、再移动、再插入、最后更新属性
删除操作从后往前执行，避免索引偏移
插入操作使用 insertBefore 实现精确定位
实际框架中会使用 DocumentFragment 批量操作以减少重排次数

面试题 5：将扁平列表转树时，如何处理多根节点和循环引用？

题目：扁平列表中可能存在多个根节点（pid 为 null），也可能存在循环引用（A 的 pid 指向 B，B 的 pid 指向 A），如何安全处理？

解答：

typescript

interface SafeListItem {
  id: number;
  name: string;
  pid: number | null;
}

interface SafeTreeNode extends SafeListItem {
  children: SafeTreeNode[];
}

interface BuildResult {
  roots: SafeTreeNode[];
  orphans: SafeTreeNode[];
  hasCycle: boolean;
}

function safeListToTree(list: SafeListItem[]): BuildResult {
  const map = new Map<number, SafeTreeNode>();
  const roots: SafeTreeNode[] = [];
  const childSet = new Set<number>();

  for (const item of list) {
    map.set(item.id, { ...item, children: [] });
  }

  for (const item of list) {
    const node = map.get(item.id)!;
    if (item.pid === null) {
      roots.push(node);
    } else {
      const parent = map.get(item.pid);
      if (parent) {
        parent.children.push(node);
        childSet.add(item.id);
      }
    }
  }

  const orphans: SafeTreeNode[] = [];
  for (const [id, node] of map) {
    if (node.pid !== null && !childSet.has(id)) {
      orphans.push(node);
    }
  }

  const hasCycle = detectCycle(map);

  return { roots, orphans, hasCycle };
}

function detectCycle(map: Map<number, SafeTreeNode>): boolean {
  const visited = new Set<number>();
  const inStack = new Set<number>();

  function dfs(id: number): boolean {
    if (inStack.has(id)) return true;
    if (visited.has(id)) return false;

    visited.add(id);
    inStack.add(id);

    const node = map.get(id);
    if (node) {
      for (const child of node.children) {
        if (dfs(child.id)) return true;
      }
    }

    inStack.delete(id);
    return false;
  }

  for (const id of map.keys()) {
    if (dfs(id)) return true;
  }

  return false;
}

要点：

多根节点：所有 pid === null 的节点都作为根节点收集
孤儿节点：pid 不为 null 但在 map 中找不到父节点的节点
循环引用检测：使用 DFS + 递归栈（inStack）检测有向图中的环
生产环境中还可以加深度限制防止栈溢出

八、追问思考（5 道）

虚拟列表 + 动态高度场景下，如果使用「树状数组（Binary Indexed Tree）」来维护前缀高度和，查找 startIndex 和更新单项高度的复杂度分别是多少？相比朴素遍历更新有什么优势？
React 的 Diff 算法在 [A, B, C, D] → [D, A, B, C] 这种「头部插入」场景下会产生多少次移动操作？Vue3 的最长递增子序列（LIS）策略能将其优化到多少次？请画出具体的执行过程。
大文件切片上传中，如果服务端使用「内容寻址存储」（即以文件内容的 hash 作为存储 key），如何实现跨用户的「秒传」功能？这种方案在安全性上有什么隐患（提示：哈希碰撞、文件探测攻击）？
并发请求控制器中，如果某些请求有依赖关系（如请求 B 依赖请求 A 的返回结果），如何扩展 concurrentRequest 使其支持 DAG（有向无环图）依赖拓扑？请设计接口和核心调度逻辑。
LRU 缓存在多线程/Web Worker 并发访问场景下会出现什么问题？如何设计一个线程安全的 LRU（提示：读写锁、分段锁、无锁数据结构）？在 JavaScript 单线程模型下，SharedArrayBuffer + Atomics 能否实现类似效果？

前端场景算法深度解析 ​

一、虚拟列表计算 ​

为什么需要虚拟列表 ​

核心原理 ​

ASCII 图解 ​

完整实现：FixedHeightVirtualList ​

动态高度虚拟列表的思路 ​

复杂度分析 ​

二、DOM Diff 算法核心思路 ​

为什么需要 Diff ​

简化版 Diff 实现 ​

React Diff vs Vue Diff 策略对比 ​

完整简化版 Diff 代码 ​

复杂度分析 ​

三、LRU 缓存 ​

原理 ​

ASCII 图解操作过程 ​

实现一：用 Map 的有序性（最简洁版） ​

实现二：HashMap + 双向链表（经典版 LeetCode 146） ​

复杂度分析 ​

四、大文件切片上传 ​

为什么需要切片 ​

完整流程 ​

SparkMD5 计算文件哈希（Web Worker） ​

并发控制上传 ​

完整实现：大文件切片上传 ​

复杂度分析 ​

五、List ↔ Tree 互转 ​

扁平列表转树 ​

方法一：递归（O(n²)） ​

方法二：Map 映射（O(n)） ​

树转扁平列表 ​

DFS（深度优先） ​

BFS（广度优先） ​

复杂度对比 ​

六、并发请求控制 ​

问题描述 ​

原理 ​

完整实现 ​

复杂度分析 ​

七、面试题精选（5 道，含详细解答） ​

面试题 1：实现一个支持过期时间的 LRU 缓存 ​

面试题 2：虚拟列表中，如何处理列表项包含图片等异步加载资源导致的高度变化？ ​

面试题 3：实现一个带重试机制的并发请求控制器 ​

面试题 4：实现一个 DOM Diff 并生成最小操作序列，应用到真实 DOM ​

面试题 5：将扁平列表转树时，如何处理多根节点和循环引用？ ​

八、追问思考（5 道） ​

前端场景算法深度解析

一、虚拟列表计算

为什么需要虚拟列表

核心原理

ASCII 图解

完整实现：FixedHeightVirtualList

动态高度虚拟列表的思路

复杂度分析

二、DOM Diff 算法核心思路

为什么需要 Diff

简化版 Diff 实现

React Diff vs Vue Diff 策略对比

完整简化版 Diff 代码

复杂度分析

三、LRU 缓存

原理

ASCII 图解操作过程

实现一：用 Map 的有序性（最简洁版）

实现二：HashMap + 双向链表（经典版 LeetCode 146）

复杂度分析

四、大文件切片上传

为什么需要切片

完整流程

SparkMD5 计算文件哈希（Web Worker）

并发控制上传

完整实现：大文件切片上传

复杂度分析

五、List ↔ Tree 互转

扁平列表转树

方法一：递归（O(n²)）

方法二：Map 映射（O(n)）

树转扁平列表

DFS（深度优先）

BFS（广度优先）

复杂度对比

六、并发请求控制

问题描述

原理

完整实现

复杂度分析

七、面试题精选（5 道，含详细解答）

面试题 1：实现一个支持过期时间的 LRU 缓存

面试题 2：虚拟列表中，如何处理列表项包含图片等异步加载资源导致的高度变化？

面试题 3：实现一个带重试机制的并发请求控制器

面试题 4：实现一个 DOM Diff 并生成最小操作序列，应用到真实 DOM

面试题 5：将扁平列表转树时，如何处理多根节点和循环引用？

八、追问思考（5 道）