JavaScript 数据结构与算法 — 全书拆解¶
30 秒导读: 这是一本 2025 年的大学教材式 DSA 书,18 章约 79 万字, 我们的拆解是 18 章 + 总纲。它回答一个工程问题: 「同一个抽象数据类型,哪实现更快、为什么、代价是什么」。 真正的价值不在某个算法,而在贯穿全书的方法论: 先立操作契约(ADT)→ 拿大 O 当尺子 → 沿「更多空间 / 更强假设 / 更复杂代码」的阶梯逐级换性能 → 函数式视角从第 2 章一路收到第 18 章。 全部代码是可运行的现代 JavaScript。读完不必看原书。
1. 先交代清楚:这是谁在什么时候写的¶
| 作者 | Federico Kereki,乌拉圭软件工程师、技术作家;No Starch Press 作者 |
| 出版 | 2025 年首版,No Starch Press;技术审稿 Daniel Zingaro(以算法教材著称) |
| 代码 | 全书在当时的 Node.js 上跑通,Prettier 排版,GitHub 开源(fkereki/data-structures-and-algorithms-book) |
| 读者定位 | 前端/Node 开发者、CS 学生、面试准备者(原书序自述三类读者) |
| 利益相关 | 无;典型教材,无产品推销 |
成书时间值得记住:2025 年——ES2023 的 toSorted、.at() 都已可用,
Math.random() 照旧当随机源;没有 TypeScript,没有 WASM,没有并发数据结构。
2. 全书一条主线(读完这一节,你就能把这本书讲给别人听)¶
这本书是一条「问题逼出工具,工具逼出新问题」的推理链,共九步:
① 先把「好代码」立成规矩¶
动手前先立风格宪章:函数是一等公民、声明式数组方法、纯函数 (不读全局、不存内部状态、不改参数)、高阶函数做包装。 这套纪律后面每一行代码都要还。(第 1–2 章)
② 数据结构不按「是什么」讲,按「能干什么」讲¶
每个结构先写成一张操作表(ADT):操作名、签名、行为。 实现的自由度全在表外——同一套操作,数组、链表、树都能交货, 「哪种交货快」才是问题。(第 3 章)
③ 快慢要用同一把尺子量¶
大 O:只看输入放大时增长有多快,不看常数;默认最坏口径; 七种阶(1 < log n < n < n log n < n² < kⁿ < n!)排成梯子; 时间换空间可以反着来(预计算前缀和换 O(1) 查询);摊还口径解释 「偶尔一次很贵」的账本。梯子立好,后面所有章都是爬梯子。(第 4 章)
④ 遇到全新问题,有五类策略可想¶
递归(函数自己调用自己)四步法(假设函数已存在 → 基础情况 → 化解 → 调用)、回溯 (试错加撤销)、动态规划(子问题存起来不重算)、蛮力(全排列,反面教材)、 贪心(每步最优,可能翻车)。快排是递归的分治、记忆化(把算过的结果存起来下次直接用) 是递归加一张缓存表、断行问题是动态规划实战——第 5 章是全书算法的母体。(第 5 章)
⑤ 经典四问(排序、选择、洗牌、搜索)把策略用熟¶
排序章给出全书最重要的下界:比较排序 ≥ O(n log n)(信息论论证), 不比就能到 O(n) 但钥匙受限;快排的 pivot 三增强与 TimSort 是 「理论到工程」的完整样本。选择(quickselect)、洗牌(Fisher-Yates, 均匀性是计数问题)、搜索(无序 Ω(n)、有序 O(log n))依次收线。(第 6–9 章)
⑥ 指针是基本功,收束操作集是赚钱手艺¶
链表本身不赢数组;把操作集收窄(只动顶=栈、头尾双指针=队列、 双向=双端队列、无头尾=循环列表),四个结构全部操作 O(1)。 「表示的升级换操作的提速」是第 10 章的全部教诲。(第 10 章)
⑦ 查找要 O(1)?三把钥匙:受限、随机、哈希¶
集合与映射(键 → 数据的对子表)的实现阶梯:有序链表 O(n) → 跳表随机分层平均 O(log n) → 位图 O(1) 但钥匙受限 → 哈希平均 O(1) 但要用装载因子、懒惰删除、 双散列步长来驯服它的概率性(最坏仍是 O(n))。三种妥协对应三种真实负载。(第 11 章)
⑧ 形状决定速度;不够快就把树做矮、做宽、做懒¶
BST 的形状焦虑催生两条修复路线——旋转派(AVL 高度差≤1,保证 O(log n)) 与概率/自调整派(随机化 BST、伸展树摊还 O(log n));多叉化让 B 树凭「半满+叶同层」自动平衡(磁盘友好),红黑树是它的二叉化身; 堆用完全树住进数组,O(1) 取最值,再沿着「更懒」的路线 (斜堆→二项→惰性→斐波那契→配对)把合并和降键逐个攻到摊还最优; 字典树按字符走路径,O(k) 与词库大小无关。(第 12–16 章)
⑨ 收官:同一招「路径复制」扫遍全书¶
最后一章把第 2 章的纯度纪律变成结构改造:更新只复制改动路径上的节点, 旧版本原样保留(持久化)。数组与哈希救不了(O(1) 与持久化不可兼得), 栈天生合规,队列靠双栈重生,树与 trie 全部可救—— 约束不会消失,只会换记账方式,与第 15 章的摊还哲学首尾呼应。(第 18 章)
3. 十八章地图¶
这张表不用记任何术语——每章名字后面写的是「读完你能回答什么」。
| 章 | 读完你就能回答 |
|---|---|
| 01 用 JavaScript | 后面所有代码建立在哪些语言特性上?工具链怎么配? |
| 02 函数式编程 | 「纯函数」怎么检查?不纯的东西(随机、I/O)怎么处理? |
| 03 抽象数据类型 | 为什么这本书每个结构都先列一张操作表? |
| 04 分析算法 | 两个实现摆在一起,凭什么说谁快?摊还是什么? |
| 05 设计算法 | 从没见过的问题,从哪儿开始想?递归为什么不会乱? |
| 06 排序 | 十种排序怎么选?为什么说 O(n log n) 撞不破? |
| 07 选择 | 只找中位数,为什么要比全排序快?怎么快? |
| 08 洗牌与采样 | 「随机得均匀」凭什么保证?写错的随机代码为什么测不出来? |
| 09 搜索 | 有序 vs 无序差几个量级?按数值猜位置的插值搜索(线性插值估下标)为什么敢赌键的分布是否均匀? |
| 10 列表 | 链表哪里不划算?栈/队列/双端队列怎么做到全 O(1)? |
| 11 集合与哈希 | O(1) 查找的三条路线各付什么代价?懒惰删除删的是什么? |
| 12 二叉树 | 树的形状怎么毁掉性能?AVL、随机化、伸展各买哪份保险? |
| 13 树与森林 | 多叉树为什么更矮?红黑树为什么等于 2-3 树? |
| 14 堆 | 数组怎么装树?优先队列为什么是堆的专利?堆排序稳在哪? |
| 15 扩展堆 | 合并两个堆、降低一个键,为什么值得四种新结构? |
| 16 字典树 | 字符串查找为什么能跟词库大小无关?trie/基数树/TST 怎么选? |
| 17 图 | 最短路径三个算法各管什么?拓扑排序怎么判环?生成树怎么贪? |
| 18 不可变数据结构 | 不改数据怎么「更新」?哪些结构救得回、哪些救不回? |
推荐顺序: 01 → 04 → 02/03 → 05 → 06–09 → 10 → 11 → 12–16 → 17 → 18。 赶时间的话:第 3、4、5 章 + 你正用的那类结构。
4. 这本书覆盖什么、不覆盖什么¶
覆盖(而且讲得比一般教材清楚)——读完你能回答:
- 同一 ADT 多套实现时,用哪个、弃哪个、为什么(性能表 + 边界明说);
- 排序、选择、洗牌、搜索四个经典问题的完整算法谱系与选型决策树;
- 树家族(搜索树/平衡树/B 树/堆/字典树)的完整谱系与「形状-性能」关系;
- 图的表示与五个经典问题(最短路/拓扑/环/连通/生成树);
- 摊还分析的真实用法(倍增数组、伸展树、惰性堆、双栈队列四处实战);
- 函数式视角:纯度纪律如何反过来筛选数据结构(末章三张清单);
- 每章习题 + 书末答案(把正文略过的坑逐个填上,如并查集加速、五元中位)。
不覆盖(别指望在这本里找):
| 缺什么 | 说明 |
|---|---|
| TypeScript 与静态类型 | 全书纯 JS;签名靠注释与表格,没有类型检查 |
| 并发与并行 | 无锁结构、并发容器、并行算法一字未提 |
| 工程大数据 | 外部排序推给系统工具;B+ 树、LSM 等存储引擎结构缺席 |
| 图的进阶课题 | 网络流、匹配、双连通分量、A* 均不在 |
| 哈希函数本身 | 只给 % 槽数 示例;好散列函数的构造与攻击面没讲 |
| 严格证明 | 平均/摊还界普遍「可证(略)」;要严谨得去算法分析教材 |
| 持久化的现代实现 | HAMT 等「近似 O(1) 持久化数组」未提(2025 年视角的小遗憾) |
5. 我们的判断¶
判断(我们的,不是书里的): 这本书今天的价值排序是—— **① 选型思维(ADT + 大 O + 决策树)> ② 可运行的现代 JS 参考实现
③ 函数式视角的贯穿 > ④ 习题答案的工程质量。** 当工具书查(②④)它合格;当教材读(①③)它出色。 它最适合的位置:不是第一本书,而是「写过 JS、想系统补课算法」的人的第二本。 如果错,会错在: 若读者的目标纯粹是面试速成,这本书的篇幅与深度 是过度供给;若读者的目标是形式化严谨(CLRS 路线),证明缺席是硬伤。 两个极端它都不伺候,这正是它的位置。
判断(我们的,不是书里的): 全书最该带走的不是任何结构, 而是两个反复出现的元技能:「摊还」与「路径复制」分别展示了 「把账记到别的地方」的两种形态——时间上记账(先欠后还) 与空间上记账(复制路径、共享其余)。 看懂这两个动作, 倍增数组、伸展树、惰性二项堆、双栈队列、持久化 BST 五个看似不相干的结构就塌缩成同一招。 如果错,会错在: 这是我们从全书编排里提炼的统一视角, 原书从未如此声明;作为记忆法它极强,作为历史归因它会失真 (这些结构各自有独立的工程动机)。
6. 许诺兑现表¶
| 许诺在哪 | 许诺了什么 | 兑现在哪 |
|---|---|---|
| 本页 §2 ① | 风格宪章的四块内容 | 02 §1、§3;01 §3 |
| 本页 §2 ② | ADT 操作表与三种实现 | 03 §2、§3.4–3.6 |
| 本页 §2 ③ | 大 O 阶梯与摊还 | 04 全章;摊还实战在 10、12、15、18 |
| 本页 §2 ④ | 五类设计策略 | 05 §1、§3 |
| 本页 §2 ⑤ | 比较下界与快排工程化 | 06 §3.2、§3.4 |
| 本页 §2 ⑥ | 收束操作集四结构 | 10 §1、§3.2–3.5 |
| 本页 §2 ⑦ | O(1) 查找三把钥匙 | 11 §3.4;16 §3.1 |
| 本页 §2 ⑧ | 形状修复与堆家族 | 12–15 各章 §1 |
| 本页 §2 ⑨ | 路径复制三张清单 | 18 §1、§3 |
05 §3.4 |
旅行商贪心解与生成树预告 | 17 §3.4 兑现 |
06 §3.5 |
基数排序「桶用列表模拟」预告 | 10 习题节(队列版基数排序)兑现 |
13 §3.2 |
B 树为磁盘而矮 | 14/15 不再重复;17 表示法呼应 |
14 §4 |
「数组堆牺牲了什么」的伏笔 | 15 全章兑现 |
拆解写于 2026-10-19,依据 2025 年首版(epub,ISBN 9781718502635)。
原书正文与习题答案全部转码入库;每条引用可用
node scripts/book-verify.mjs data-structures-algorithms-js 回核。