◆

前端为什么也要学数据结构与算法：从性能、状态管理到真实业务场景

2023-03-2273 分钟阅读0Max ZhangFrontend

数据结构算法JavaScript性能优化

◆

有天下午，我在做一个电商后台的商品管理页。

里面有五千多条商品。表格、筛选、批量操作、收藏标记、分类导航。刚开始做的时候只有几十条测试数据，代码写得很随意——find() 到处飞，sort() 随便上，所有数据堆在一个大数组里走来走去。那时候页面跑得飞起，觉得自己写得还挺优雅。

数据涨到几百条的时候，页面偶尔会顿一下。但刷新一下就好了，你没当回事。

涨到两千条的时候，筛选按钮点下去要等大概半秒。你心里开始飘过一丝隐隐的不对劲，但你告诉自己——没事，数据量正常增长嘛，等上了生产再看，实在不行加个 loading 遮一下。

涨到五千条的时候，筛选按钮点下去整整一秒多。切换分类 tab 的时候页面直接白屏一小会儿。全选 5000 条做批量下架的时候，你听见了 Mac 的风扇开始转。

妈的。这还没上生产。

接下来发生了什么，估计你跟我经历过差不多的剧本。

先怀疑是不是渲染太多了。给表格加虚拟滚动。好，滚动不卡了，但筛选和批量操作还是慢。

再怀疑是不是计算太多了。加 React.memo。加 useMemo。把一些派生计算挪到 useCallback 里。把复杂的条件渲染拆成细粒度的子组件。一整套组合拳打完，代码 review 的时候还能装模作样地讲几句"做了性能优化"。

卧槽。筛选按钮还是慢。

这时候我才把 Chrome DevTools 打开，认认真真看每一帧在干什么。然后我发现了几个让人脸红的瞬间。

每一行表格渲染的时候，为了显示"所属分类名称"，我都做了这件事：

categories.find((cat) => cat.id === product.categoryId)?.name ?? '未知'

单看这行代码，没有任何问题。但五千行表格，每行都 find 一次。五千次线性扫描。

再往下看：筛选区在 find。批量操作在 find。详情抽屉在 find。统计面板的汇总计算也在 find。同一个 categories 数组，在整个页面的生命周期里被反复扫描了几万次。

想想这件事的荒诞：我花了那么多时间给组件套 memo、给列表上虚拟滚动、给输入框写防抖——却从来没想到，问题的根是一行不起眼的 find。

那之后我才开始认真看待数据结构这件事。不是把它当面试题来背——是把它当饭碗来端。

如果你做前端超过两年，大概也经历过类似的时刻。不是那种"写不出来"的时刻——是写出来了、跑起来了、但总觉得哪儿不对劲。慢。乱。改一个地方要提心吊胆。加一个功能要思前想后。

你今天读到的这篇文章，就是我从那之后慢慢攒下来的东西。不是照念教材，是我自己在项目里撞过南墙之后，回头看才发现"卧槽这些结构早就被发明好了，我为什么要自己在那瞎试"。

读完你不会变成算法竞赛选手。你也不会在下次面试的时候突然手写红黑树。但再遇到类似的问题，你手里会有武器。真正的、能在代码里用的武器。

你可能不服，但我得先说清楚

前端不是不需要数据结构。

前端是需要不同于刷题模式的数据结构思维。

如果你跟我说"找工作的算法题库里那些红黑树、AVL 树、跳表、KMP 字符串匹配、动态规划递推式，我在写组件和页面的时候确实从来没手写过"——我同意。我自己也没写过几次，每次写都是在那个白板小房间里，对面坐着一个面无表情的面试官。

但如果你跟我说"数据结构和算法跟做前端的没关系"——那你可能还没被真实项目毒打过。或者你的项目还不够大，数据还不够多，交互还不够复杂，还没撞上这些东西偷偷给你埋的坑。

说几个你每天都在做的事。

你写表格的时候，脑子里想的"数据长什么样、我该用什么方式存它们让查找快一点"——这不是架构设计，这是数据结构。

你写搜索框的时候，脑子里冒出来"用户每敲一个字母我就重新扫一遍全量是不是有点傻逼"——这不是用户体验，这是算法。

你写撤销重做的时候，琢磨"上一个状态是什么、回退怎么恢复、重做记录什么时候清空、连续输入要不要合并成一条历史"——这他妈的不是组件设计，这他妈的是两个栈。

你看——你其实一直在做数据结构和算法的事，只是没把这件事翻译成"学科名词"而已。

而面试和工作的真正区别是什么？

面试让你守在白板前面，嘴里念念有词，把红黑树的旋转写完。真实项目让你在编辑器里停下来，看一眼自己写的三行 find，然后说"这不对，该换 Map 了"。

后者才是正经让你值钱的能力。

前端项目里反复犯的五种病

我这几年遇到的性能问题、状态混乱、代码腐化，不管表面症状长什么样——页面卡了、内存炸了、操作乱了——回头看，绝大部分根因都落在这五类里。

你记下来。不用背。下次排查诡异问题的时候对着找，大概率不会跑空。

第一种病：查找太他妈的多了

不是"找一次特别慢"。是"找了太多次，叠在一起就慢了"。

一个数组有5000条。你写个 .find()，没事。十次 .find()，也没事。但你要知道，前端的渲染是批量的、是反复的、是每个帧都在发生的。你这个查找如果被挂在渲染路径里面——表格五千行的每一行、批量操作的每一个 id 映射、统计面板的每一项汇总——实际累积次数就是几百上千次。

单独看一次 find，O(n) 没什么。几百次叠在一起，O(n * 5000) 就不是没代价的事了。

你可能会问，"那我在代码里也找不出哪个地方有几百次调用啊？"

这就是问题。它不是写在同一个 for 循环里的。它是散落在十几个不同组件、不同函数、不同 Hook 里面的。每个地方看起来都只是"做了一件小事"，合在一起就是一座大山。

第二种病：更新代价太高

打个比方。你在做树形菜单。用户双击一深层节点的标题，弹出一个编辑框，改成新标题，保存。

看起来就改了四个字。但如果你的数据结构是"整个树存在一个 state 对象"里面，你的更新方式是"把整棵树重新赋一次值"——那 React 的调和算法就要过整棵树。如果这棵树有五百个节点，每个节点都是独立的 DOM——那这一次修改本质上触发了五百个组件的运算。为了四个字的改动。

问题的根源不是 React 太敏感。是你做不到"我只想改这一个节点，别的别动"——因为你没有精确到节点级别的引用能力。

第三种病：状态越来越乱

这病一般发生在需求不断叠加的中后期。

撤销重做。多步骤表单。标签页上的草稿缓存。多人协作里的本地历史和远端同步。浏览器自带的前进后退。

这些需求刚开始的时候你都觉得"不就是存一下之前的值吗"。然后产品来了——"撤销的时候只撤销内容，不要撤销标题"。"连续撤销三次之后如果用户做了新操作，就不能重做了"。"切到别的页再切回来，要保留未保存的草稿"。

你以为你在写交互逻辑。其实你一直在处理状态生命周期。而状态生命周期这个东西，如果你一开始没有用一个有名字的数据结构来框住它，写到后面就跟盘丝洞一样。

第四种病：同一件事干了太多遍

同一个分组结果——表格里算一遍，图表里又算一遍，导出功能里再算一遍。同一个排序——列表页排一遍，关联推荐列表再排一遍。同一个树结构拍平——搜索要用拍平结果，统计也要用拍平结果。

单看每一个调用，它的成本都小到你不觉得有优化的必要。

但关键是前端的重渲染是高频的。如果数据源每两秒推送一次（比如 WebSocket 实时订单更新），那这些重复计算就是每两秒跑三遍。一天下来，你等于白白多做了几千万次 reduce、sort、map。

第五种病：渲染性能不稳定

最无耻的一种。数据少的时候跑得呼呼生风，数据一多就开始赌——这次渲染快点，下次可能就顿一下。你在测试环境测不出来，因为测试环境只有几十条。上了生产，用户那里数据一上去，页面变得忽快忽慢。

查起来最费劲。因为没有一个具体的函数告诉你"我就是罪魁祸首"——是十几个函数各自多花了几十毫秒，在一个渲染帧里刚好叠到了人类能感知的阈值。

这时候你可能在想——"这五类问题，怎么看都是框架的事？React 渲染多了？Vue computed 没写好？虚拟滚动没上？"

我一开始也这么想。我甚至花了两周把一个页面从"React 默认渲染"改成了"每个组件精确 memo"。区别是有，但是有限的。

后来我才理解——框架层能做的事情，已经被框架做完了。你再往框架上加东西，是剪枝。真正的根，在数据组织那个层面。

你以为的框架问题，可能只是数据放错了位置

前端社区有个我不太喜欢的现象：一旦有人问"页面卡了怎么办"，回复区基本就是这两类：

A: "上虚拟滚动啊！" B: "用 computed 缓存计算结果！" C: "把组件 memo 化！"

不是说这些不对。这些都是好工具。但如果你没有先检查数据层，这些工具就是在给一辆轮胎没气的车换发动机。

说个最简单的例子。你有一个用户信息列表：

const users = [
  { id: 'u1', name: '张伟', department: '技术部', avatar: 'https://...' },
  { id: 'u2', name: '李娜', department: '产品部', avatar: 'https://...' },
  { id: 'u3', name: '王芳', department: '设计部', avatar: 'https://...' },
  { id: 'u4', name: '赵雷', department: '技术部', avatar: 'https://...' },
  { id: 'u5', name: '孙婷', department: '市场部', avatar: 'https://...' },
]

就五条数据。如果整个页面有且只有一个地方需要"根据 id 拿用户姓名"，你只需要写一行：

const userName = users.find((u) => u.id === ownerId)?.name ?? ''

完全合理。没有任何问题。

但真实项目从来不是这样。真实项目里，表格要显示 owner 名字，评论列表要显示评论者名字，通知列表要显示发起人名字，详情页要显示关联人员名字，权限弹窗要显示归属人名字。所有这些地方分布在十几个组件、分散在几个页面路由里。

如果每个地方都各自 find 一遍——在数据只有五条的时候你感觉不出来。在数据有五千条、而且每次重渲染都被触发的时候，这些 find 开始结伴出来作案。

正确的做法是什么？不复杂：

// 建一次索引
const userMap = new Map(users.map((u) => [u.id, u]))

// 以后所有查找走索引
function getUser(id: string) {
  return userMap.get(id)
}

从 O(n) 到 O(1)。从"每次找都要排队过安检"到"到了直接拿"。这件事简单到我自己第一次想明白的时候都笑了——就这？就这几行？这就叫数据结构？

对，这就叫数据结构。

不是所有数据结构都要像红黑树一样复面。恰恰相反，前端工程里真正有用的数据结构思维，大部分都长这样——低调、短小、但能救你的狗命。

再多点明白：这个模式不是前端发明的。数据库里有 B+ 树索引，操作系统内存管理有页表，DNS 有缓存层，浏览器本身对 CSS 选择器的匹配也做了索引优化。底层逻辑是一样的：你不想每次找东西的时候都翻箱倒柜，那就提前把东西变成"翻一页就能找到"。

很多框架层的优化，本质上是在补救数据层没做好的账。你把100条数据扔给框架，和把10000条数据扔给框架再要求它"你帮我优化一下"，这不是同一个问题。数据层的功课先做，再谈框架。

前端真的用得上的几种结构

好，终于到名单了。但我先说明：不会按教材顺序讲。教材从数组开始，经链表、栈、队列、哈希、树、堆、图一路往上堆，这是计算机科学体系的学习顺序，不是前端使用频率的顺序。

我按照——你遇到它们的方式——来讲。

第一组：你天天用但可能没用对

这四个东西构成了前端数据操作的基本面。把它们吃透了，你项目里至少一半的数据组织问题就有了明确答案。

数组

前端最能打的格式。渲染列表、维护顺序、管道式的数据流处理——这些天然就是数组的。

数组最擅长的是按位置访问：arr[3]——快到不用想。数组最不擅长的是按内容查找：arr.find((x) => x.id === 'abc')——慢到要找一圈。

所以数组适合的场景是"我有一堆东西，我有它们的顺序，我要遍历它们"。不适合的场景是"我有一堆东西，我要频繁地按照某个 key 找到特定的那一个"。

你如果从头到尾只用数组，那就是拿着一把锤子，把所有的钉子、螺丝、榫卯全用锤子敲——能敲进去，但结果不是最优的。

对象

{ key: value }——最简单的字典。

适合：key 是静态的几个字符串，数据量不大，操作以读取为主。不适合：key 的类型不是字符串（比如你想用对象、数字做 key），或者你需要保留插入顺序，或者你要频繁增删。

很多人一说字典就写对象，不考虑场景。对象真正的软肋：它没有"size"属性你得自己数；它的原型链可能会对 hasOwnProperty 判断产生干扰；它的迭代顺序早在 ES2015 之后虽然在规范上有了 [[OwnPropertyKeys]] 的描述，但远不如 Map 的插入顺序保证来得直接。

Map

我发自内心觉得 Map 被低估了。

它做的事情很简单：你给它一个 key，它立刻还你一个 value。速度是常数级别。key 可以是任何类型——字符串、数字、对象、甚至 DOM 节点。

你把它当一个缓存用——map.set(key, result) 以后 map.get(key)。你把它当实体索引表用——配合一个 ids: string[] 维护顺序，entities: Map<string, Entity> 维护索引。你甚至可以用它在不同组件之间共享计算结果而不需要引入状态管理库。

说句大白话：很多你一开始不会设计、后来靠着各种框架特性硬撑过去的数据访问模式，如果一开始就多建一个 Map，根本不会有后来的问题。

这里有一条核心认知我想单独放大：

数组负责顺序，Map 负责索引。各司其职。

这不是在背概念，这是你以后设计任何复杂数据模型时的起点。当你发现你的代码里同时需要"按顺序渲染"和"按 id 快速查找"的时候——不要二选一。两个都要。

Set

使用场景非常集中：你想知道"XX 在不在这堆东西里面"。

权限校验："这个按钮的权限 key 在不在当前用户的权限集合里？" → Set。全选态管理："这一行选中了没有？" → 用一个 selectedSet → selectedSet.has(rowId)。树形展开："这个菜单节点展开了没有？" → expandedKeys.has(nodeKey)。批量操作："是不是已经处理过了？" → processedIds.has(id)。

如果你用的是 array.includes() ——对，数据少的时候没有区别。但如果你的展开 keys 有几百个，或者你的选中 ids 有上千个，includes 每次都是 O(n)，has 每次都是 O(1)。

这不是"理论上更快"的问题，是肉眼能感知的区别。

把这四个用好——不是"知道"，是"用对"——你项目里一半以上的数据组织问题就变得可解。

第二组：你已经在用但没名字的

这三样东西，你的项目里大概率已经有了实例，只是你没有意识到它有个学科名字。

栈

故事是这样的。

如果我让你实现一个撤销重做功能，你想一分钟后写出来的代码可能是：

let previousState: AppState | null = null

function commit(newState: AppState) {
  previousState = deepClone(currentState)
  currentState = newState
}

function undo() {
  if (!previousState) return
  currentState = previousState
  previousState = null
}

能跑。但只能撤一次。第二次撤销就没有了。

然后你开始打补丁——改成数组。存所有历史。

然后产品来提需求——"连续快速输入应该合并成一步""撤销后做了新操作就要清掉重做记录"。这时候你发现你的 history: AppState[] 开始不够用，因为它没有"未来"和"过去"的分野。

真正成熟的设计是双栈：

past: [s0, s1, s2]     present: s3     future: [s4, s5]

每次提交新状态：当前 present 压入 past，present 刷新，future 清空。撤销：past 弹出顶部变成 present，旧的 present 推入 future。重做：symmetrical，从 future 往外弹。

三个数组。五种操作。不需要任何额外的 flag 变量。不用纠结"现在能不能撤"——past 空就是不能撤。不用纠结"撤完能不能重做"——future 空就是不能重做。状态本身就是答案。

从工程角度看，这个结构跟 UI 零耦合。你可以在任何框架里用它——先把它测稳了，再接线到按钮上。

队列

你知道吗，浏览器自己的任务调度就是个队列。宏任务一个接一个被推进执行栈，微任务排在宏任务之后清空。这整个机制就是队列。

前端里队列用得比你想的多：

消息通知——五个弹窗不能同时蹦出来，得排队，一个一个出。
上传调度——50个文件不可能50个请求同时发。得有一个并发控制的调度队列。
请求串行——A 拿到了 id 才能发 B，B 拿到了 token 才能发 C。这东西本质上就是一个串行队列。

队列不复杂。但你有意识把一个问题定义成"这是一个队列问题"之后，解决思路就定型了。

树

这个结构在前端躲不开。因为你用的 DOM 本身就是一棵树。

抛开 DOM 不说——前端做的菜单、目录、组织架构、权限模型、评论嵌套——全是树。

你要在这个树上做的操作基本是固定的几个东西：遍历（DFS 或 BFS）、拍平（把层级拉成数组）、按 key 查找节点、按 key 回溯父路径、在树上做增删改。

这些东西如果你每次遇到都用"这里递归一下"的思路临时拼凑——写出来能跑，但一定会在某个边缘情况炸掉（比如你意外修改了原引用，导致整棵树的渲染状态错乱）。

学习树不是为了在面试里写二叉树遍历。是为了在真实业务里少出现"为什么展开了一个节点，整棵树刷新了？"这类诡异的 bug。

这三样东西，你大概率已经在用了，只是你不知道它们叫这个名。知道名字有什么用呢？下次设计功能的时候，直接拿现成模型，不用从零拼凑。

第三组：你现在用不到但值得记个名字

这里面的结构，我对你的建议是：现在不学也没关系。但看到它们的名字的时候脑子里有一个大致印象——"哦这个东西适合XXX场景"。将来场景真的来了，你至少知道去哪里翻。

堆

"销量最高的前10个商品"、"过去一周最活跃的50个用户"——这种问题叫 Top K。

你可以全量排序再截前 K 个，在数据量不大的时候没问题。但如果数据量非常大，全排是很贵的。堆能让你只排"必要的那部分"。

JavaScipt 没有原生堆实现，但你不需要自己每次都写。LeetCode 上练过一次之后，你就知道堆能干什么了。

图

图才是真实世界关系的真实模型。

假设你在做一个工作流编辑器。用户可以拖动节点，节点之间有前置、后置、并行、分支关系。这个东西看起来像树——但节点之间可以有多个前驱后继，这就是图。

页面的跳转关系也可以建模成图——哪些页面可以互相到达，有没有死路径。

图不是一个"日常需求"，但当你遇到它的时候，如果你脑子里连"这可能是图问题"这个概念都没有，你就会用数组和对象在上面硬拼——拼到后面一定爆炸。

Trie（前缀树）

搜索联想和代码补全的天然宠儿。

你输入"Bei"，Trie 直接告诉你：Beijing, Beirut, Belfast——全部以"Bei"开头的节点。不需要遍历全量，不需要动态计算匹配——结构本身就是答案。

前端里用 Trie 的场景：命令面板（类似 VS Code 的 Ctrl + Shift + P 那种）、搜索框的联想下拉、代码补全、URL 路径匹配。不是所有搜索都需要上 Trie——只有当"我这里是高频率的前缀匹配"时它才值。

链表

前端直接手写链表的情况确实很少。但"链"这个思想出现频率比你想象的高——LRU 缓存淘汰的核心就是双向链表，编辑器操作历史在某些实现里也是链表，React 自己的 Fiber 内部就是链表结构。

知道它的存在，知道它适合"频繁在任意位置插入删除"的场景就够了。

六个你真会撞上的场景

概念讲得差不多了。下面是血肉——六个我在真实项目里面撞得头破血流的场景。每个场景里，问题的起点、为什么常规解法不够、以及一个比常规解法更好的方式。

场景一：大列表里的查找——你为什么不该把所有东西都存成数组

这是万恶之源。真的。

我做过的每一个前端项目，只要数据量上了1000以后，90% 的性能问题的第一案发现场都是这里——列表查找。

场景：商品管理后台。页面上有五六个功能区域，每个区域都需要"按商品 id 快速拿到商品详情"。新手的基本写法：

function getProductById(products: Product[], id: string) {
  return products.find((p) => p.id === id)
}

这个函数单看没有任何问题。清晰。易懂。符合直觉。

但你的错误是把它放在了"被频繁调用的位置"上。表格的每一行里、批量操作的每一个 id 映射上、统计面板的每一个分类汇总下、详情抽屉的每一次打开——这些调用加在一起，让同一个 5000 条的数组被扫描了几万次。

更聪明的做法是保留两份数据：

// 数组 - 负责渲染顺序
const productList: Product[] = [...]
// Map - 负责索引查找
const productMap = new Map(productList.map((p) => [p.id, p]))

// 后续所有查找走 Map
function getProductById(id: string): Product | undefined {
  return productMap.get(id)
}

思考一下：你失去了什么？多存了一份引用，内存多了几十到几百 KB。你获得了什么？每次查找从 O(n) 变成了 O(1)。在 n = 5000 的情况下，这个区别不是心理安慰，是肉眼可见的页面响应速度。

这其实就是很多状态管理库底层做"状态规范化"的逻辑——用 ids 数组维护顺序，用 entities 字典维护索引。Redux Toolkit 把它做成了 createEntityAdapter，很多其他状态库也都有一个内部版本。你不需要重新发明它，但你需要理解它为什么要这么做。

场景二：搜索联想——别把所有计算绑在用户的键盘上

也许你做过这东西：用户输入"北京"，下面的下拉框自动弹出以"北京"开头的所有城市。第一版几乎每个人都这么写：

const cities = [...] // 3000个城市

function searchCities(keyword: string) {
  return cities.filter((c) =>
    c.name.toLowerCase().includes(keyword.toLowerCase())
  )
}

// 然后挂到 input 的 onChange 或 onInput 上
<input onChange={(e) => {
  const result = searchCities(e.target.value)
  setSuggestions(result)
}} />

看起来没错。但实际运行中，用户打字快的时候一秒钟能敲四五个键。你一秒钟要扫四五千条数据四五次。而这段代码执行在浏览器的主线程上——就是同样那条还要处理渲染、事件、网络回调的线程。

键一多，页面开始丢帧。

问题不在于"筛选本身是慢的"——扫一条也就几微秒。问题是筛选被绑定在了一个高频事件上，而且每次筛选都从零开始。

更合理的做法分三步走：

第一步：防抖。 不是每一次 onInput 都执行。等用户停手大概 200ms 再触发筛选。这一步能把执行频率降一个数量级。

第二步：预处理搜索文本。 不要每次搜索时都重新做 toLowerCase()、拼接多个字段。这些转换做一次就够了：

const searchableCities = cities.map((c) => ({
  ...c,
  _searchText: `${c.name}${c.pinyin}${c.alias}`.toLowerCase(),
}))

以后搜索时直接检查 _searchText.includes(...)。成本从"每次搜索都要转换"变成"一次性处理后永久生效"。

第三步（可选的）：如果场景对前缀匹配要求极高——比如做一个跟 VS Code 类似的命令面板——那就考虑 Trie。Trie 的结构是：每个节点是一个字符，深度搜索天然就是前缀匹配。查询时间是和你输入的字符长度成正比的，和数据总量几乎无关。

大多数常规业务场景其实用前两步就够了。但关键是——当你看到用户输入和页面响应之间的滞后感时，你的第一反应不是"JavaScript 怎么这么慢"，而是"我是不是把不该高频执行的东西挂在高频事件上了"。

场景三：树形权限——难的从来不是递归本身

前端的树太多了。菜单是树，权限是树，组织架构是树，文件目录是树，评论回复是树。但太多人——包括曾经的我——对待树的唯一方式是："这里用递归搞一下"。

递归本身没问题。但问题是当你把"递归整棵树"作为每一个树操作的默认方式时，这些操作之间会产生大量的重复遍历。

举个例子：你有一个权限树，后端给了你 100 个权限节点。产品有以下几个需求：(1) 初始化时后端返回了用户已有的权限 keys，你要把树上对应的节点勾上并把它们的父级整个链路展开。(2) 用户勾选一个父级节点时，子节点全选。(3) 用户反选一个子节点时，父级节点变成半选态。(4) 搜索框中输入关键词时高亮匹配节点并自动展开父路径。

如果你对每个需求都"从头递归树"来解决——能跑。但当这四件事相继发生在同一套树上时，每次递归都在扫同一些节点，而你的代码开始变成一团相互交缠的递归调用。

更好的方式是：提前把索引建好。

type TreeNode = {
  key: string
  title: string
  children?: TreeNode[]
}

function buildTreeIndex(tree: TreeNode[]) {
  const nodeMap = new Map<string, TreeNode>()
  const parentMap = new Map<string, string | null>()

  function walk(nodes: TreeNode[], parentKey: string | null) {
    for (const node of nodes) {
      nodeMap.set(node.key, node)
      parentMap.set(node.key, parentKey)
      if (node.children?.length) {
        walk(node.children, node.key)
      }
    }
  }

  walk(tree, null)
  return { nodeMap, parentMap }
}

nodeMap 让你 O(1) 拿到任何一个节点——不需要递归。 parentMap 让你从任意节点一路追溯到根——一个 while 循环就够了，不需要反向遍历整棵树。

然后"找到某节点并高亮它所在的整条父路径"就变成了 O(depth) 的操作。原来你是 O(n) 甚至 O(n²) 地在做这些事。

树在前端里的难点从来不是"你知不知道递归怎么写"。难的是——你有没有意识把高频的树操作从"每次都从根重新找"变成"常驻索引"。

场景四：撤销与重做——是数据结构问题，不是 UI 问题

你看着这个标题，可能会觉得"撤销不就是一个按钮加上一个备份的 state 嘛"。

如果你这样写过，你应该也经历过以下这一幕：用户撤了三次，然后拖动了一个东西，然后再撤——发现结果不对。或者用户切到另一个 tab，回来再撤，页面状态错乱了。或者你只记了"上一个状态"，用户点两次撤销就直接跳回初始值，丢掉了中间的所有内容。

撤销重做不是"记住上次的值"的问题。它是一个"如何维护状态的时间线"的问题。

经典解法是用两个栈——past 和 future——和一个中间态 present。

past: [s0, s1, s2]     present: s3     future: [s4, s5]

每次提交新状态：present → past, 新状态 → present, future 清空。撤销：past.pop → present, 旧present → future. 重做：future.pop → present, 旧present → past.

为什么这个设计普遍存活了几十年（从编辑器的出现就一直用）？因为它简单到不需要解释。三个数组，五种操作。past 长度为零 = 不能撤。future 长度为零 = 不能重做。所有边界情况全部被结构本身消化了。

用 TypeScript 表示出来就是这样：

class HistoryStack<T> {
  private past: T[] = []
  private present: T
  private future: T[] = []

  constructor(initial: T) {
    this.present = initial
  }

  getState() {
    return this.present
  }

  push(next: T) {
    this.past.push(this.present)
    this.present = next
    this.future = [] // 新的现在，未来作废
  }

  undo(): T {
    const prev = this.past.pop()
    if (prev == null) return this.present
    this.future.push(this.present)
    this.present = prev
    return this.present
  }

  redo(): T {
    const next = this.future.pop()
    if (next == null) return this.present
    this.past.push(this.present)
    this.present = next
    return this.present
  }

  canUndo() {
    return this.past.length > 0
  }
  canRedo() {
    return this.future.length > 0
  }
}

不到四十行。但这就是一个工业级的解决方案的核心骨架。你把基础打好之后，再往上加"连续输入合并""操作分组记录"这类需求，都是有地方落脚的了。

而且它还有一个工程上的大优点：纯数据结构。不依赖框架，不依赖 DOM，不依赖事件。你可以先写完、单独测、把它所有的状态流转都变成单元测试。测稳了你再把它接到任何框架的按钮上。

绝大多数前端交互之所以越做越难，不是因为组件太多——是因为你在设计组件之前，没有先把状态历史想清楚。

场景五：缓存和记忆化——少算几遍，比什么都强

我见过太多次这种情况：一个派生计算——比如把 2000 条订单按状态分组成四个类别——在表格组件里算了一遍，在统计面板里又算了一遍，在导出文件模块里又算了一遍。每一遍都是把同一个数据源扫描一次。

单独看一次分组：不贵。2000 条数据，reduce 一下就几毫秒。

但从整个页面的角度看：这些分组发生在同一个渲染周期内——一帧之内。三次几毫秒加在一起，再加上其他地方的耗时，就开始靠近 16.67ms 的帧预算了。

该做的事情其实只有一件：不要让同一份输入被重复消费。

const cache = new Map<string, Record<string, Order[]>>()

function getOrdersGroupedByStatus(orders: Order[], cacheKey: string) {
  if (cache.has(cacheKey)) {
    return cache.get(cacheKey)!
  }

  const result = orders.reduce(
    (acc, o) => {
      acc[o.status] ??= []
      acc[o.status].push(o)
      return acc
    },
    {} as Record<string, Order[]>,
  )

  cache.set(cacheKey, result)
  return result
}

关键是失效策略。缓存不同于一次性预处理——它需要你知道什么时候扔掉旧结果。大部分情况很简单：源数据变了，整份缓存就废了。

有一种更精细的方式是 memoize 按依赖变化来决定是否重算——框架内部的 useMemo / computed 就是做这件事的。但框架替你做的那些只能用在它们能追踪到的地方。组件树之外、跨组件的共享派生计算，还是要有手动缓存。

缓存不是什么高深的算法。它就是个直觉：一件事我算过了，下次别算。

前端里——分组结果能缓存、拍平过的树能缓存、格式化过的展示字段能缓存、请求的响应能缓存。名字不一样，本质是一样的。

场景六：列表渲染——页面卡顿的真凶可能不在渲染层

虚拟列表能解决"DOM 节点太多了"的问题，但它解决不了"为了生成这些 DOM 节点，你做了多少计算"的问题。

这段代码，我猜你写过类似的：

const visibleRows = rows
  .filter((r) => r.status === activeFilter)
  .sort((a, b) => b.updatedAt - a.updatedAt)
  .map((r) => ({
    ...r,
    ownerName: users.find((u) => u.id === r.ownerId)?.name ?? '未知',
  }))

这段代码功能性上是一点问题没有的。筛选需要的行、排序、同时把关联的用户名映射进来。一行链式调用，清晰利落。

性能上是另一回事：过滤要扫一遍、排序要消耗计算、映射过程中又给每一行做了一次 find。这仨东西如果都在渲染入口写死——那每次组件重新渲染，就重新走一遍这三层。

1000 条数据可能无感，5000 条开始有体感，10000 条就明显拖帧了。

更合理的分层是：

第一步，用户索引预建，跟渲染解耦：

const userMap = new Map(users.map((u) => [u.id, u]))

第二步，过滤和排序在依赖条件没变的情况下不重复执行：

const filteredRows = useMemo(() => rows.filter((r) => r.status === activeFilter), [rows, activeFilter])

const sortedRows = useMemo(() => [...filteredRows].sort((a, b) => b.updatedAt - a.updatedAt), [filteredRows])

第三步，行级映射不再做昂贵查找：

const visibleRows = sortedRows.map((r) => ({
  ...r,
  ownerName: userMap.get(r.ownerId)?.name ?? '未知',
}))

你会发现这三个步骤跟"框架选型"完全无关——你可以在 React、Vue、Solid 里面做完全相同的事情。因为它们处理的是"数据怎么流"——不是"组件怎么渲染"。

把这件事再展开一点：渲染性能从来不只关于"框架怎么渲染"，更关于"你在渲染开始前做了多少多余的工作"。

前端最值钱的五种算法思维

"算法"这个词在前端圈里被污染得有点严重。大多数人听到算法，脑子里弹出来的都是东西——反转链表、二叉树遍历、动态规划递推式。这些当然都是算法，但它们是应试型的算法，不是你早上九点半打开 VS Code 时会直接调用的算法。

前端工程里天天在发生、但你从来没把它叫"算法"的东西，我数了数，就这么五种。

1. 遍历

你今天写的代码里的每一个 for、每一个 map、每一个 filter、每一个 reduce——这些都是在遍历。递归遍历树也是遍历（DFS/BFS），查表单字段也是遍历（遍历 schema），匹配路由也是遍历（扫描路由表）。

遍历本身没问题。遍历是一切数据操作的基础。问题在于"无意识地遍历"——你不知道自己在遍历，所以你也不去想"这次遍历能不能只做一次""这次遍历能不能不做""这次遍历能不能挪到更外层让它被更少触发"。

从前端新手的脑子里装上"遍历成本"这根弦的那一天起，很多事情就不一样了。你会开始纠结的不是"功能能不能实现"，而是"这个结构里我到底要过多少克数据才能拿到我要的东西"。

说个例子。你有一个 2000 条数据的表格，加上一个统计面板。统计面板需要知道"每个分类下面有多少条数据"。如果你在统计面板的渲染函数里写了一个 reduce 来统计，每次表格数据更新——统计面板就重新 reduce 一遍。这件事写起来没什么，但它意味着你的统计逻辑被渲染周期"绑定"了。正确的做法是把统计结果作为派生数据，在数据源头算一遍，统计面板只管消费。

这个例子里的算法思想几乎为零——就是"别把同样的事反复做"——但它需要的恰恰是对"遍历成本"的敏感性。

2. 哈希索引

这是我重复次数最多的一个词，我会再重复一遍——因为它可能是你在这篇文章里带走的最划算的一个念头：

本来应该建个索引，但你一直在做线性扫描。

你在找东西。你老是 find。你 find 了十次、一百次、一千次。你每次 find 的成本在叠加。

换成 Map，建一次索引。以后不再 find。map.get(key) 就行。

代价：多几行代码，多几百 KB 内存。收益：重复查找从 O(n) → O(1)。

你不需要把所有东西都哈希化。你只需要识别出那些"被频繁查找"的热点路径，然后在这些路径上建索引。

这件事再往深里说一点。哈希索引的思想不是"让查找更快"——它是"把你的数据结构从'按顺序排列'变成了'按内容可直达到达'"。它给数组赋了一个额外的维度——原先你只能按序号拜访数组里的成员，现在你可以按任意一个 key 直接跳到对应的成员。这种能力叫"随机存取"，不是你发明的，但你会用之后整个世界都不一样了。

3. 分治与局部更新

只改了一行数据 → 不要重建整个统计面板。只展开了一个节点 → 不要重跑整个树的遍历。只加了一页新数据 → 不要重新处理之前的全部数据。

这个想法不难理解。但执行起来需要有意识地去设计数据边界——让你的数据结构允许你做"局部操作"，而不是随便一碰就触发全局连锁反应。

很多高性能前端代码，底下的核心逻辑就是这个：让一个局部的变化，只触发局部的影响。

4. 排序与优先级

不是让你手写快排。是让你意识到排序是一个有成本的活。

不要在每次 render 里面没有条件地对同一批数据重复排序。这个场景太常见了——列表每次从 store 拿了数据，不检查有没有变化就开始排。排了一样的东西一百次。

还要意识到——有些场景只需要 Top K，不需要给全部东西排好座次。"销量前十"这类需求，只要找前十就够了。

脑子里有"排序不免费"这根弦，你就不会在渲染路径里随手塞一个 .sort()。

5. 空间换时间

这是上述四种思想的终极抽象。

建索引——空间换时间。缓存派生结果——空间换时间。预处理搜索文本——空间换时间。多存一份拍平树——空间换时间。

凡事都有代价。你用空间换了时间之后：内存上去了，同步逻辑多了一层，要有失效策略。

但工程就是权衡。当你的页面因为 100ms 的延迟开始失去用户时，多花几百 KB 换这 100ms —— 值。

这五种思路不是孤立的。你在设计同一个页面的时候，常常是几个思路一起用：遍历是底层成本意识，哈希索引是最高频的优化手段，局部更新是你对状态设计的要求，排序意识让你不浪费计算资源，空间换时间是所有优化的共同底色。

你不应该把它们当五门要分别通过的考试。你应该把它们当成你写代码时脑子里同时开的五盏探照灯——哪盏亮了说明哪里该留意了。

学到什么程度就算不亏

我不打算给你开必读书单。你不需要从《算法导论》第一章啃到最后一章来做一个合格的前端。

你要的是"具备什么能力之后，就可以不打转地去干别的"。

有两个极端必须躲开。

第一个极端：完全不碰。认为数据结构是后端的事，算法是面试的事，跟日常工作无关。结果就是——代码纯凭直觉写，数据一大就慢，状态一复杂就乱，出了性能问题只能靠往上面堆更多的框架 API 当补丁。

第二个极端：沉迷刷题。LeetCode 几百道刷下来了，各种题型能解，但是回到真实项目里，从来没被训练过"把业务需求翻译成数据结构"这件事。给他一个背景——"树形权限的回显需要从根展开到叶子"——他懵了。他能在白板上反转二叉树，但他不会在编辑器里给一棵树配上索引。

真正需要的是什么？三个东西：

第一：对常见结构的代价有本能。

不翻资料就能判断——这个场景该继续用数组还是该上 Map。做过很多次"判断存在"的操作了，下次是该用 array.includes 还是 Set.has。这个判断做得越快、越准，你的代码在数据量涨上去之后就越不容易翻车。

第二：对复杂度有感觉。

不需要每次都用笔算大O。但你能感觉到——这个查找是不是在扫全量？这个渲染是不是叠了好几层循环？这个派生计算是不是同一个东西被算了太多遍？

第三：能把业务需求翻译成结构问题。

这是终极目标。看到一个"撤销重做"需求 → 脑子浮出双栈。看到一个"树形权限回显"需求 → 脑子浮出 nodeMap + parentMap。看到一个"多选维护"需求 → 脑子浮出 Set。看到一个"搜索联想"需求 → 脑子浮出"预处理 + 防抖 + 可能需要的前缀索引"。

这种翻译能力一旦变成你的肌肉记忆，你就不会再问"前端该不该学数据结构"了——因为你会发现你每天都在用，只是以前是瞎用，现在是明白地用。

一条不绕路的学习路径

如果你真决定开始学，我建议这么走——跟教材的目录倒过来。

第一步：死磕数组、Map、Set、对象。

做到这种程度：随意扔给你一个数据场景，你能不假思索地说出——哪些东西继续放数组，哪些转成 Map 做索引，哪些状态适合用 Set 维护。检验标准——想象 5000 条订单，要按状态筛选、按金额排序、按 id 快速查找、维护一批选中的 id，你能不能五分钟内画出数据布局。

第一步的投资回报率最高。高到你会吃惊。

第二步：学会树遍历和树做索引。

DFS/BFS 至少一种要能随手写出来。会把嵌套结构拍平成线性的数组。会用 nodeMap 替代递归查找。会用 parentMap 替代反向搜索来追溯父路径。这些东西在菜单、权限、组织架构这些场景里每天都出现。

第三步：理解栈、队列、缓存的基本模型。

不是为了学结构而学，而是你的设计能力会提升——撤销重做就是对栈的经典应用。请求调度就是队列。跨组件共享派生计算就是缓存实践。

第四步：补复杂度意识。

不需要背大O表。但要能识别——什么地方在重复叠加（嵌套循环 + 多次触发），什么派生计算被多方消费（适合上提到共享层），什么场景可以用空间换时间（热点查找路径）。

第五步：有精力的话，把堆、图、Trie 过一遍。

不是必须的。但可以让你在搜索联想、工作流编排、实时排行榜这些特殊场景出现时——不至于裸体。

该带走的就这些——一个判断框架

这篇文章写了这么多，最后给的不是总结——是一个框架。你下次遇到任何"数据一多就开始不对劲"的问题时，问自己三件事：

第一问：这件事本质上是在对数据做什么？

找东西（查找）？维护前后关系（顺序/栈）？排优先序（排序/堆）？表达层级（树）？表达多对多关系（图）？把这个问题想清楚——你离选对结构就只差一步。

第二问：当前写法里有没有我肉眼能看到的不必要重复？

同一个查找做了很多次？同一个排序被频繁触发在同一个不变的数据上？同一个分组结果出现在三个不同的组件里各自算了一遍？——不要找微妙的重复，找最明显的。从最明显的下手。

第三问：我能不能用非常少的空间代价把这类重复消掉？

加一个 Map。加一份预处理字段。加一份缓存。拍平一次树。

代价通常很小——通常就是几行代码，几十到几百 KB 的内存开销。但收益是整个页面从"开始不太对"变成"稳定流畅"。

这种交换是不是每次都要做？当然不是。如果你的数据只有50条，一个 find 的代价可以完全忽略。辨别"这里该优化了"和"这里过度设计了"的判断力，恰恰来自你对数据量和调用频率的敏感性。而这种敏感性，只有在你在"不优化→被毒打→回头优化"这个循环里跑过几圈之后，才能真正长出来。

这三个问题不是看一遍就能学会的。是你要在自己写的每一段有超过50条数据的代码里问自己。

问多了，它变成直觉。变成了直觉，你就不会在下一次看到 users.find((u) => u.id === ownerId) 的时候只是轻描淡写地掠过——你会停下来，看一眼这行代码调用的频率，然后问自己：这里是不是该有一个 Map 了。

到那一天，前端到底要不要学数据结构这个问题，你自己就有答案了——因为你已经在用了。以前是瞎用，现在是用明白。

全景关系图

把你在这篇文章里遇到的所有数据结构和它们对应的前端场景，画成一张图。下次碰到"数据组织不对劲"的感觉时，可以对着这张图找——你的问题大概落在哪根线上了。

Loading diagram...

怎么读这张图：

实线箭头（→）：这个结构"天生就该干这个事"。比如 Map 最擅长按 key 做 O(1) 直达，它连向"按 ID 快速查找"。
虚线（-.->）：这两种结构在实际工程里经常搭档。"数组存顺序 + Map 存索引"是你设计任何中等以上数据量的页面时都会用到的组合。"树拍平成数组"是为了让搜索和遍历从递归复杂度降为线性。你不一定每次都全用上，但知道它们能这样配对，设计的时候就不会走"只用锤子敲一切"的老路。
关键认知：左边这些结构不是互斥的——同一个页面里你完全可以同时拥有数组、Map 和 Set，各自负责不同维度。数组管渲染顺序，Map 管按 ID 找人，Set 管"选中了没有"。"各司其职"才是这篇文章从头到尾在说的东西。

FAQ：读者困惑预判

Q1: Map 和普通对象到底什么时候用哪个？

别纠结"理论上谁更好"——看场景。

用 Map 的情况（三个硬条件满足任一就上 Map）：

key 的类型不限于字符串——你想用对象、数字、甚至 DOM 节点做 key。
需要频繁增删键值对——Map 的增删性能比对象稳定，对象在大规模动态 key 下有隐藏类退化的风险。
需要保证迭代顺序和插入顺序一致——Map 天然保证，对象的 key 顺序虽然 ES2015 之后有了规范描述，但细节绕到你懒得记。

用对象的情况：

key 是一组固定的、提前就知道的字符串（比如 { name, age, email }）。
你需要序列化成 JSON 或者通过 HTTP 传输——对象天然支持 JSON.stringify，Map 得先转成数组。
你只是做一个"配置项字典"，增删极少，以读为主。

一句大白话：数据量一大、key 一动态，直接 Map。你以后会感谢现在的自己。

Q2: 拍平后的树和原始树怎么同步更新？

这个问题问到点子上了——拍平不是免费的，多存一份数据就多了一份"要保持一致"的代价。

三种策略，从简单到精细：

最简单：修改原始树后重新拍平。 适合树不大（几百个节点以内）或者修改频率极低（比如初始化一次以后几乎不变）。一劳永逸，没同步 bug。缺点：每次拍平都要重走整棵树，源数据一改全废。
中等：用 immutable 的方式更新原始树，然后触发拍平。 如果你的树是用不可变数据维护的（比如 immer、zustand + immer 中间件），改一个节点会得到一棵新树的引用，你可以在监听到引用变化后重新拍平。好处是"改动可追踪"，不会出现"改了但忘了拍平"的情况。
最精细：拍平结果本身就是主数据源。 把拍平的数组作为渲染用的主数据（比如 flatNodes: FlatNode[]），同时保留原始树结构以备需要层级操作的场景（导出、逐层递回）。每次增删改同时更新树和拍平数组——代码上多写几行，但不需要"重新生成"。

核心原则：不要同时维护两份互相独立的权威数据源——选一个做主数据，另一个做派生。主数据一改，派生数据立刻失效并重建。 同步问题怕的从来不是"更新代码难写"，而是"不知道该信哪个"。

Q3: 前端需要学到什么程度的数据结构和算法？

这篇文章全文都在回答这个问题，但如果你想要一句压缩版：

数组、Map、Set 吃透 → 树遍历 + 树索引会写 → 栈和队列的基本模型能随手搭出来 → 剩下的（堆、图、Trie）知道它们各自适合什么场景就够了，遇到再查。

具体判断标准不是"你刷了多少题"，而是——当你看到一个需求的时候，能不能在 30 秒内说出一句话："这个问题本质上是 XXX 结构的问题，我应该用 YYY 来组织数据。"如果你能说出这句话——不管你有没有手写过红黑树——你就已经过线了。

至于刷题：如果要跳槽面试，该刷刷。如果只是为了把工作做好——把上面那个阶梯走到第三步，你项目里 95% 的数据问题就都有答案了。

Q4: 虚拟列表和普通分页渲染性能差多少？什么量级才需要上虚拟列表？

先说结论：不是你数据多了就必须上虚拟列表——是你 DOM 节点多了才需要。

普通分页一次渲染几十到几百个 DOM 节点，浏览器处理得很从容。虚拟列表的意义是让你"渲染窗口内的节点数"保持恒定——不管总量是一万条还是十万条，DOM 数都不变。

量级参考（经验值，不是绝对阈值）：

< 200 条：啥都不用管，裸渲染足够。
200 ~ 1000 条：加 useMemo / computed，防一手不必要重复计算。虚拟列表可上可不上——上了更稳，不上也死不了。
1000 ~ 5000 条：虚拟列表开始明显改善滚动流畅度。同时注意检查有没有把 .find() 挂在行渲染里——这个量级下查找成本比 DOM 成本先炸。
5000+ 条：虚拟列表基本是必选项。但更要命的是——这个时候你的瓶颈大概率不在 DOM 数量上，而在"为了算出这 5000 条数据要展示什么，你做了多少额外的查找和计算"。虚拟列表解决了渲染层的问题，数据层的问题（索引、缓存、预处理）你得自己搞定。

一个关键误解：虚拟列表解决的是"浏览器生成和布局 DOM 太贵了"，而不是"你的 JavaScript 计算太贵了"。 如果你在 renderRow 里写了一个对 5000 条数据的 find，上了虚拟列表也没救——每行渲染的时候还是要扫 5000 条。先把查找改成 Map（O(1)），再上虚拟列表——这才是正确顺序。这他妈的也是这篇文章最想让你记住的东西。

写到这里想起一个朋友，前端做了五年，前段时间去面试。面试官问他："项目里用过哪些数据结构？"

他愣了一下："数组...还有对象？"

后来他跟我说，其实他项目里写过栈（撤销重做）、写过索引表（Map 做权限节点查找）、写过队列（上传并发控制）。但他说不出口——因为从来没人告诉过他"你做的这堆东西就是数据结构"。

如果你合上这篇文章，脑子里只留下一个东西——我希望是这句话：你不是没用到数据结构。你用到了，只是不知道它叫什么。现在你知道了。

☏

读者来信

暂无来信，期待你的分享。